Skip to Main content Skip to Navigation
Conference papers

A trie-based approach for compacting automata

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619974
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, March 26, 2013 - 7:31:25 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Thursday, June 27, 2013 - 2:25:10 AM

File

cpm04.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Maxime Crochemore, Chiara Epifanio, Roberto Grossi, Filippo Mignosi. A trie-based approach for compacting automata. Combinatorial Pattern Matching, 2004, Turkey. pp.145-158, ⟨10.1007/978-3-540-27801-6_11⟩. ⟨hal-00619974⟩

Share

Metrics

Record views

283

Files downloads

454