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

Author Ines Klimann



PDF
Thumbnail PDF

File

LIPIcs.STACS.2013.502.pdf
  • Filesize: 0.61 MB
  • 12 pages

Document Identifiers

Author Details

Ines Klimann

Cite AsGet 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.
Keywords
  • Mealy automata
  • automaton semigroups
  • decidability of finiteness
  • decidability of freeness
  • Nerode equivalence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail