 |
HAL UPEC - UPEM Portal |  |
 |
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.
Cited literature [13 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00619974
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Tuesday, March 26, 2013 - 7:31:25 AM
Last modification on : Tuesday, October 19, 2021 - 11:25:53 AM
Long-term archiving on: : Thursday, June 27, 2013 - 2:25:10 AM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Tuesday, March 26, 2013 - 7:31:25 AM
Last modification on : Tuesday, October 19, 2021 - 11:25:53 AM
Long-term archiving on: : Thursday, June 27, 2013 - 2:25:10 AM
File
cpm04.pdf
Files produced by the author(s)