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

DOI10.4230/LIPIcs.STACS.2013.502zbMath1354.68159arXiv1208.6324MaRDI QIDQ2957911

Ines Klimann

Publication date: 30 January 2017

Full work available at URL: https://arxiv.org/abs/1208.6324

zbMATH Keywords

automaton semigroupsdecidability of finitenessdecidability of freenessMealy automataNerode equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (9)

Automaton semigroups: the two-state case. ⋮ Ergodic decomposition of group actions on rooted trees ⋮ Orbit automata as a new tool to attack the order problem in automaton groups ⋮ Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$ ⋮ Automaton semigroups: new constructions results and examples of non-automaton semigroups ⋮ Algorithmic Decidability of Engel’s Property for Automaton Groups ⋮ Unnamed Item ⋮ On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata

This page was built for publication: The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable