The universal automaton

Sylvain Lombardy (1) , Jacques Sakarovitch (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LTCI - Laboratoire Traitement et Communication de l'Information

This paper is a survey on the universal automaton, which is an automaton canonically associated with every language. In the last forty years, many objects have been defined or studied, that are indeed closely related to the universal automaton. We first show that every automaton that accepts a given language has a morphic image which is a subautomaton of the universal automaton of this language. This property justifies the name "universal" that we have coined for this automaton. The universal automaton of a regular language is finite and can be effectively computed in the syntactic monoid or, more efficiently, from the minimal automaton of the language. We describe the construction that leads to tight bounds on the size of the universal automaton. Another outcome of the effective construction of the universal automaton is the computation of a minimal NFA accepting a given language, or approximations of such a minimal NFA. From another point of view, the universal automaton of a language is based on the factorisations of this language, and is thus involved in the problems of factorisations and approximations of languages. Last, but not least, we show how the universal automaton gives an elegant solution to the star height problem for some classes of languages (pure-group or reversible languages).

Domaines: Algorithme et structure de données [cs.DS]

Sylvain Lombardy, Jacques Sakarovitch. The universal automaton. Flum Jörg, Grädel Erich, Wilke Thomas. Logic and Automata, History and Perspectives, 2, Amsterdam University Press, pp.457-504, 2008, Texts in Logic and Games. ⟨hal-00620807⟩