Abstract
The star height of a regular language is an invariant that has been shown to be effectively computable in 1988 by Hashiguchi. But the algorithm that corresponds to his proof leads to impossible computations even for very small instances. Here we solve the problem (of computing star height) for a special class of regular languages, called reversible languages, that have attracted much attention in various areas of formal language and automata theory in the past few years. These reversible languages also strictly extend the classes of languages considered by McNaughton, Cohen, and Hashiguchi for the same purpose, and with different methods.
Our method is based upon the definition (inspired by the reading of Conway’s book) of an automaton that is effectively associated to every language — which we call the universal automaton of the language — and that contains the image of any automaton that accepts the language. We show that the universal automaton of a reversible language contains a subautomaton where the star height can be computed.
Regular languages are closed under complement but complement is not considered as a regular operation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arnold A., Dicky A., and Nivat M., A Note about Minimal Non-deterministic Automata. Bull. of E.A.T.C.S.47 (1992), 166–169.
Büchi J. R., Finite Automata, their Algebras and Grammars: Toward a Theory of formal Expressions. D. Siefkes Ed.. Springer-Verlag, 1989.
Cohen R., Star height of certain families of regular events. J. Computer System Sci.4 (1970), 281–297.
Cohen R. and Brzozowski R., General properties of star height of regular events. J. Computer System Sci.4 (1970), 260–280.
Conway J. H., Regular algebra and finite machines. Chapman and Hall, 1971.
Dejean F. and Schützenberger M. P., On a question of Eggan. Inform. and Control9 (1966), 23–25.
Eggan L. C., T ransition graphs and the star-height of regular events. Michigan Mathematical J.10 (1963), 385–397.
Eilenberg S., Automata, Languages and Machines vol. A, A cademic Press, 1974.
Hashiguchi K., The star height of reset-free events and strictly locally testable events. Inform. and Control40 (1979), 267–284.
K. Hashiguchi, Algorithms for determining relative star height and star height. Inform. and Computation 78 (1988), 124–169.
Lombardy S., On the construction of reversible automata for reversible languages, submitted.
Lombardy S. and Sakarovitch J., On the star height of rational languages: a new version for two old results, Proc. 3rd Int. Col. on Words, Languages and Combinatorics, (M. Ito, Ed.) World Scientific, to appear. Available at the URL: http://www.enst.fr/~jsaka.
Héam P.-C., Some topological properties of rational sets. J. of Automata, Lang. and Comb., to appear.
McNaughton R., The loop complexity of pure-group events. Inform. and Control 11 (1967), 167–176.
Pin J.-E., On reversible automata. In Proc. 1st LATIN Conf., (I. Simon, Ed.), Lecture Notes in Comput. Sci.583 (1992), 401–416.
Sakarovitch J., Eléments de théorie des automates. Vuibert, to appear.
Salomaa A., Jewels of formal language theory. Computer Science Press, 1981.
Silva P., On free inverse monoid languages Theoret. Informatics and Appl.30 (1996), 349–378.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lombardy, S., Sakarovitch, J. (2002). Star Height of Reversible Languages and Universal Automata. In: Rajsbaum, S. (eds) LATIN 2002: Theoretical Informatics. LATIN 2002. Lecture Notes in Computer Science, vol 2286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45995-2_12
Download citation
DOI: https://doi.org/10.1007/3-540-45995-2_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43400-9
Online ISBN: 978-3-540-45995-8
eBook Packages: Springer Book Archive