# 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

top## How 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). Zbl0326.68005
- 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). Zbl1061.68088
- 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. Zbl0896.68058
- 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. Zbl0419.68086
- T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. MIT Press (1990). Zbl1158.68538
- 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). Zbl0787.68057
- 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. Zbl0944.68091
- E. Roche and Y. Schabes, Finite-State Language Processing. MIT Press, Cambridge (1997) Chapter 7.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.