 |
 |
 |
Conference papers
The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
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.
Cited literature [22 references]
https://hal-univ-paris.archives-ouvertes.fr/hal-00875177
Contributor : Ines Klimann <>
Submitted on : Monday, October 21, 2013 - 1:03:29 PM
Last modification on : Wednesday, October 14, 2020 - 3:58:33 AM
Long-term archiving on: : Friday, April 7, 2017 - 2:11:03 PM
Contributor : Ines Klimann <>
Submitted on : Monday, October 21, 2013 - 1:03:29 PM
Last modification on : Wednesday, October 14, 2020 - 3:58:33 AM
Long-term archiving on: : Friday, April 7, 2017 - 2:11:03 PM
Files
stacs010.klimann.pdf
Files produced by the author(s)