Computing the prefix of an automaton
Marie-Pierre Béal; Olivier Carton
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 34, Issue: 6, page 503-514
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topBéal, Marie-Pierre, and Carton, Olivier. "Computing the prefix of an automaton." RAIRO - Theoretical Informatics and Applications 34.6 (2010): 503-514. <http://eudml.org/doc/222063>.
@article{Béal2010,
abstract = {
We present an algorithm for computing the prefix of an automaton.
Automata considered are non-deterministic, labelled on words, and can
have ε-transitions. The prefix automaton of an automaton
$\mathcal\{A\}$ has the following characteristic properties. It has the
same graph as $\mathcal\{A\}$. Each accepting path has the same label as in
$\mathcal\{A\}$. For each state q, the longest common prefix of the
labels of all paths going from q to an initial or final state is empty.
The interest of the computation of the prefix of an automaton is that it
is the first step of the minimization of sequential transducers.
The algorithm that we describe has the same worst case time complexity as
another algorithm due to Mohri but our algorithm allows automata that
have empty labelled cycles. If we denote by P(q) the longest common
prefix of labels of paths going from q to an initial or final state, it
operates in time O((P+1) × |E|) where P is the maximal length of
all P(q).
},
author = {Béal, Marie-Pierre, Carton, Olivier},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {prefix of an automaton},
language = {eng},
month = {3},
number = {6},
pages = {503-514},
publisher = {EDP Sciences},
title = {Computing the prefix of an automaton},
url = {http://eudml.org/doc/222063},
volume = {34},
year = {2010},
}
TY - JOUR
AU - Béal, Marie-Pierre
AU - Carton, Olivier
TI - Computing the prefix of an automaton
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 6
SP - 503
EP - 514
AB -
We present an algorithm for computing the prefix of an automaton.
Automata considered are non-deterministic, labelled on words, and can
have ε-transitions. The prefix automaton of an automaton
$\mathcal{A}$ has the following characteristic properties. It has the
same graph as $\mathcal{A}$. Each accepting path has the same label as in
$\mathcal{A}$. For each state q, the longest common prefix of the
labels of all paths going from q to an initial or final state is empty.
The interest of the computation of the prefix of an automaton is that it
is the first step of the minimization of sequential transducers.
The algorithm that we describe has the same worst case time complexity as
another algorithm due to Mohri but our algorithm allows automata that
have empty labelled cycles. If we denote by P(q) the longest common
prefix of labels of paths going from q to an initial or final state, it
operates in time O((P+1) × |E|) where P is the maximal length of
all P(q).
LA - eng
KW - prefix of an automaton
UR - http://eudml.org/doc/222063
ER -
References
top- A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison Wesley (1974).
- M.-P. Béal, Codage Symbolique. Masson (1993).
- M.-P. Béal and O. Carton, Determinization of transducers over finite and infinite words. Tech. Rep. 99-12, I.G.M., Université de Marne-la-Vallée (1999).
- J. Berstel, Transductions and Context-Free Languages. B.G. Teubner (1979).
- D. Breslauer, The suffix tree of a tree and minimizing sequential transducers, in CPM'96. Springer-Verlag, Lecture Notes in Comput. Sci.1075 (1996) 116-129.
- D. Breslauer, The suffix tree of a tree and minimizing sequential transducers. Theoret. Comput. Sci.191 (1998) 131-144.
- C. Choffrut, Contribution à l'étude de quelques familles remarquables de fonctions rationnelles. Thèse d'État, Université Paris VII (1978).
- C. Choffrut, A generalization of Ginsburg and Rose's characterization of gsm mappings, in ICALP'79. Springer-Verlag, Lecture Notes in Comput. Sci.71 (1979) 88-103.
- T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. MIT Press (1990).
- M. Crochemore, C. Hancart and T. Lecroq, Algorithmique du Texte. Vuibert (to appear).
- C. Frougny, Numeration systems, in Algebraic Combinatorics on Words, edited by M. Lothaire. Cambridge (to appear).
- M. Mohri, Minimization of sequential transducers, in CPM'94, edited by M. Crochemore and D. Gusfield. Springer-Verlag, Lecture Notes in Comput. Sci.807 (1994) 151-163.
- M. Mohri, Minimization algorithms for sequential transducers. Theoret. Comput. Sci.234 (2000) 177-201.
- E. Roche and Y. Schabes, Finite-State Language Processing. MIT Press, Cambridge (1997) Chapter 7.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.