The word and order problems for self-similar and automata groups

2017/10/27 by Bartholdi, Laurent, Mitrofanov, Ivan
#FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1710.10109

Abstract

We prove that the word problem is undecidable in functionally recursive groups, and that the order problem is undecidable in automata groups, even under the assumption that they are contracting.

Related

• Some non-contracting automata groups
• Groups defined by automata
• An automaton group with undecidable order and Engel problems
• Deciding Word Problems of Semigroups using Finite State Automata
• Automatic groups associated with word orders other than shortlex