3DI - Dipartimento di Informatica [Pisa] (University of Pisa Dipartimento di Informatica Largo B. Pontecorvo, 3 (formerly via F. Buonarroti, 2) I-56127 Pisa - Italy)
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.
https://hal-upec-upem.archives-ouvertes.fr/hal-00619974 Contributor : Maxime CrochemoreConnect in order to contact the contributor Submitted on : Tuesday, March 26, 2013 - 7:31:25 AM Last modification on : Saturday, January 15, 2022 - 3:56:15 AM Long-term archiving on: : Thursday, June 27, 2013 - 2:25:10 AM