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

Abstract

top
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 𝒜 has the following characteristic properties. It has the same graph as 𝒜 . Each accepting path has the same label as in 𝒜 . 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).

How to cite

top

Bé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
  1. A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison Wesley (1974).  Zbl0326.68005
  2. M.-P. Béal, Codage Symbolique. Masson (1993).  
  3. 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
  4. J. Berstel, Transductions and Context-Free Languages. B.G. Teubner (1979).  
  5. 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.  
  6. D. Breslauer, The suffix tree of a tree and minimizing sequential transducers. Theoret. Comput. Sci.191 (1998) 131-144.  Zbl0896.68058
  7. C. Choffrut, Contribution à l'étude de quelques familles remarquables de fonctions rationnelles. Thèse d'État, Université Paris VII (1978).  
  8. 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
  9. T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. MIT Press (1990).  Zbl1158.68538
  10. M. Crochemore, C. Hancart and T. Lecroq, Algorithmique du Texte. Vuibert (to appear).  
  11. C. Frougny, Numeration systems, in Algebraic Combinatorics on Words, edited by M. Lothaire. Cambridge (to appear).  Zbl0787.68057
  12. 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.  
  13. M. Mohri, Minimization algorithms for sequential transducers. Theoret. Comput. Sci.234 (2000) 177-201.  Zbl0944.68091
  14. E. Roche and Y. Schabes, Finite-State Language Processing. MIT Press, Cambridge (1997) Chapter 7.  

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.