Infinite finitely generated automata semigroups have infinite orbits

2018/01/30 by Dominik Francoeur, Francoeur, Dominik
Computer Science · #semigroups and automata theory #Advanced Algebra and Logic #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1801.10009

Abstract

We prove that the semigroup generated by a finite state Mealy automaton A=(Q,A,τ) is infinite if and only if there exists some right-infinite word in the alphabet A with infinite orbit.

Related

• On the Orbits of Automaton Semigroups and Groups
• The Finiteness Problem for Automaton Semigroups of Extended Bounded Activity
• Deciding Word Problems of Semigroups using Finite State Automata
• To Infinity and Beyond
• Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups