The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable

Ines Klimann 1
1 Automates et Applications
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-univ-diderot.archives-ouvertes.fr/hal-00875177
Contributor : Ines Klimann <>
Submitted on : Monday, October 21, 2013 - 1:03:29 PM
Last modification on : Friday, January 4, 2019 - 5:33:36 PM
Long-term archiving on : Friday, April 7, 2017 - 2:11:03 PM

Files

stacs010.klimann.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ines Klimann. The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Feb 2013, Kiel, Germany. pp.502--513, ⟨10.4230/LIPIcs.STACS.2013.502⟩. ⟨hal-00875177⟩

Share

Metrics

Record views

212

Files downloads

193