A Trie-Based Approach for Compacting Automata

Chiara Epifanio, Filippo Mignosi, Maxime Crochemore, Roberto Grossi

Research output: Contribution to conferenceOther

11 Citations (Scopus)

Abstract

We describe a new technique for reducing the number of nodes and symbols in automata based on tries. The technique stems from some results on anti-dictionaries for data compression and does not need to retain the input string, differently from other methods based on compact automata. The net effect is that of obtaining a lighter automaton than the directed acyclic word graph (DAWG) of Blumer et al., as it uses less nodes, still with arcs labeled by single characters.
Original languageEnglish
Pages145-158
Number of pages14
Publication statusPublished - 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A Trie-Based Approach for Compacting Automata'. Together they form a unique fingerprint.

  • Cite this

    Epifanio, C., Mignosi, F., Crochemore, M., & Grossi, R. (2004). A Trie-Based Approach for Compacting Automata. 145-158.