A Trie-Based Approach for Compacting Automata

Chiara Epifanio, Filippo Mignosi, Maxime Crochemore, Roberto Grossi

Risultato della ricerca: Other

11 Citazioni (Scopus)

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.
Lingua originaleEnglish
Pagine145-158
Numero di pagine14
Stato di pubblicazionePublished - 2004

Fingerprint

Data compression
Glossaries
Automata
Data Compression
Vertex of a graph
Arc of a curve
Strings
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Epifanio, C., Mignosi, F., Crochemore, M., & Grossi, R. (2004). A Trie-Based Approach for Compacting Automata. 145-158.

A Trie-Based Approach for Compacting Automata. / Epifanio, Chiara; Mignosi, Filippo; Crochemore, Maxime; Grossi, Roberto.

2004. 145-158.

Risultato della ricerca: Other

Epifanio, C, Mignosi, F, Crochemore, M & Grossi, R 2004, 'A Trie-Based Approach for Compacting Automata', pagg. 145-158.
Epifanio C, Mignosi F, Crochemore M, Grossi R. A Trie-Based Approach for Compacting Automata. 2004.
Epifanio, Chiara ; Mignosi, Filippo ; Crochemore, Maxime ; Grossi, Roberto. / A Trie-Based Approach for Compacting Automata. 14 pag.
@conference{3e01fcc3261144f6bfd975944e7f96cb,
title = "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.",
author = "Chiara Epifanio and Filippo Mignosi and Maxime Crochemore and Roberto Grossi",
year = "2004",
language = "English",
pages = "145--158",

}

TY - CONF

T1 - A Trie-Based Approach for Compacting Automata

AU - Epifanio, Chiara

AU - Mignosi, Filippo

AU - Crochemore, Maxime

AU - Grossi, Roberto

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10447/2837

M3 - Other

SP - 145

EP - 158

ER -

Accesso al documento