6533b7d9fe1ef96bd126d66d
RESEARCH PRODUCT
A trie-based approach for compacting automata
Roberto GrossiFilippo MignosiChiara EpifanioMaxime Crochemoresubject
automataComputer scienceSuffix tree[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]suffix tree0102 computer and information sciences02 engineering and technologyω-automaton01 natural sciencesindex text compressionlaw.inventionlawfactor and suffixTrie0202 electrical engineering electronic engineering information engineeringAutomata and formal languagesPattern matchingDirected acyclic word graphString (computer science)Directed graphDirected acyclic graphMobile automatonAutomaton010201 computation theory & mathematics020201 artificial intelligence & image processingAlgorithmComputer Science::Formal Languages and Automata Theorydescription
International audience; 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2004-01-01 |