Abstract
A reversible automaton is a finite (possibly incomplete) automaton in which each letter induces a partial one-to-one map from the set of states into itself. We give four non-trivial characterizations of the languages accepted by a reversible automaton equipped with a set of initial and final states and we show that one can effectively decide whether a given rational (or regular) language can be accepted by a reversible automaton. The first characterization gives a description of the subsets of the free group accepted by a reversible automaton that is somewhat reminiscent of Kleene's theorem. The second characterization is more combinatorial in nature. The decidability follows from the third — algebraic — characterization. The last and somewhat unexpected characterization is a topological description of our languages that solves an open problem about the finite-group topology of the free monoid.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Angluin, Inference of reversible languages, Journal of the Association for Computing Machinery 29 (1982) 741–765.
C.J. Ash, Finite semigroups with commuting idempotents, J. Austral. Math. Soc. Series A, to appear.
J.C. Birget, S.W. Margolis and J. Rhodes, Finite semigroups whose idempotents commute or form a subsemigroup, Proceedings of the Chico Conference on Semigroups (1986), to appear.
S. Eilenberg, Automata, Languages and Machines, Vol B, Academic Press, New-York (1976).
M. Hall Jr, A topology for free groups and related groups, Ann. Math. 52 (1950) 127–139.
T.E. Hall, Biprefix codes, inverse semigroups and syntactic monoids of injective automata, Theoretical Computer Science.
G. Lallement, Semigroups and Combinatorial Applications, Wiley, New-York (1979).
M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics 17, Addison Wesley, New-York (1983).
R. McNaughton, The loop complexity of pure-group events. Inf. Control 11 (1967) 167–176.
S.W. Margolis and J.E. Pin, Languages and inverse semigroups, 11th ICALP, Lecture Notes in Computer Science 199, Springer, Berlin (1985) 285–299.
S.W. Margolis and J.E. Pin, Finite inverse semigroups, varieties and languages, Journal of Algebra, to appear.
J.E. Pin, Finite group topology and p-adic topology for free monoids, 12th ICALP, Lecture Notes in Computer Science 194 (1985) 445–455.
J.E. Pin, Varieties of formal languages, Masson, Paris (1984), North Oxford Academic, London and Plenum, New-York (1986).
Ch. Reutenauer, Une topologie du monoide libre, Semigroup Forum 18, (1979), 33–49.
Ch. Reutenauer, Sur mon article "une topologie du monoide libre", Semigroup Forum 22, (1981), 93–95.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pin, J.E. (1987). On the languages accepted by finite reversible automata. In: Ottmann, T. (eds) Automata, Languages and Programming. ICALP 1987. Lecture Notes in Computer Science, vol 267. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18088-5_19
Download citation
DOI: https://doi.org/10.1007/3-540-18088-5_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18088-3
Online ISBN: 978-3-540-47747-1
eBook Packages: Springer Book Archive