Finiteness problem for automaton groups over a binary alphabet is almost decidable

DOI10.1016/J.TCS.2025.115478MaRDI QIDQ6930242zbMATH OpenFDO

Authors Andriy Russyev

Publication date 16 September 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115478

zbMATH Keywords

automaton groupfiniteness problemMealy automaton

Mathematics Subject Classification ID

Groups acting on trees (20E08) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic theory of languages and automata (68Q70)

Cites work

• Automata, dynamical systems, and groups
• Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
• Classification of groups generated by 3-state automata over a 2-letter alphabet
• scientific article; zbMATH DE number 5855532 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• On orbits and the finiteness of bounded automaton groups
• On the finiteness problem for automaton (semi)groups.
• The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
• The finiteness problem for automaton semigroups is undecidable.

This page was built for publication: Finiteness problem for automaton groups over a binary alphabet is almost decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930242)