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.

CROCHEMORE, M., EPIFANIO, C., GROSSI, R., MIGNOSI, F. (2004). A Trie-Based Approach for Compacting Automata. In Combinatorial Pattern Matching (pp.145-158) [10.1007/978-3-540-27801-6_11].

A Trie-Based Approach for Compacting Automata

EPIFANIO, Chiara;MIGNOSI, Filippo
2004-01-01

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.
CPM Annual Symposium on Combinatorial Pattern Matching
Istanbul, Turkey
5-7 luglio
15
2004
14
A stampa
CROCHEMORE, M., EPIFANIO, C., GROSSI, R., MIGNOSI, F. (2004). A Trie-Based Approach for Compacting Automata. In Combinatorial Pattern Matching (pp.145-158) [10.1007/978-3-540-27801-6_11].
Proceedings (atti dei congressi)
CROCHEMORE, M; EPIFANIO, C; GROSSI, R; MIGNOSI, F
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/2837
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 9
social impact