LIPIcs.STACS.2013.502.pdf
- Filesize: 0.61 MB
- 12 pages
Document
The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
Author
-
Part of:
Volume:
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2013-02-26
Cite As Get BibTex
Ines Klimann. The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 502-513, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.502
Abstract
We prove that a semigroup generated by a reversible two-state Mealy automaton is either finite or free of rank 2. This fact leads to the decidability of finiteness for groups generated by two-state or two-letter invertible-reversible Mealy automata and to the decidability of freeness for semigroups generated by two-state invertible-reversible Mealy automata.
Subject Classification
Keywords
- Mealy automata
- automaton semigroups
- decidability of finiteness
- decidability of freeness
- Nerode equivalence
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads