On Orbits and the Finiteness of Bounded Automaton Groups

DOI10.1142/S0218196721400087MaRDI QIDQ6331108arXivFDO

Authors Ievgen Bondarenko, Jan Philipp Wächter

Publication date 14 December 2019

Published in arXiv

Full work available at URL https://doi.org/10.1142/S0218196721400087

Mathematics Subject Classification ID

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

arXiv classification

cs.FLmath.GR

Abstract: We devise an algorithm which, given a bounded automaton A, decides whether the group generated by A is finite. The solution comes from a description of the infinite sequences having an infinite A-orbit using a deterministic finite-state acceptor. This acceptor can also be used to decide whether the bounded automaton acts level-transitively.

This page was built for publication: On Orbits and the Finiteness of Bounded Automaton Groups

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