A Trie-Based Approach for Compacting Automata

Chiara Epifanio, Filippo Mignosi, Maxime Crochemore, Roberto Grossi

Research output: Contribution to conferenceOther

11 Citations (Scopus)


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
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.