On the complexity of the word problem for automaton semigroups and automaton groups

DOI10.1016/j.aam.2017.05.008zbMath1393.20014arXiv1611.09541OpenAlexW2557440256MaRDI QIDQ2363312

Jan Philipp Wächter, Daniele D'Angeli, Emanuele Rodaro

Publication date: 13 July 2017

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

word problemautomaton groupsautomaton semigroupsPSpace

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Inverse semigroups (20M18) Groups acting on trees (20E08)

Related Items

Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ An automaton group with undecidable order and Engel problems ⋮ The word problem for finitary automaton groups ⋮ An automaton group with \textsf{PSPACE}-complete word problem ⋮ Unnamed Item ⋮ Fragile words and Cayley type transducers ⋮ Orbit expandability of automaton semigroups and groups ⋮ Boundary dynamics for bireversible and for contracting automaton groups ⋮ Infinite automaton semigroups and groups have infinite orbits ⋮ On the structure theory of partial automaton semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Growth of Schreier graphs of automaton groups.
• Automaton semigroups: new constructions results and examples of non-automaton semigroups
• Automaton semigroup constructions.
• Groups of intermediate growth: an introduction.
• Automaton semigroups
• The method of forced enumeration for nondeterministic automata
• A geometric approach to (semi)-groups defined by automata via dual transducers.
• Relationships between nondeterministic and deterministic tape complexities
• Freeness of automaton groups vs boundary dynamics
• On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata
• Implementing Computations in Automaton (Semi)groups
• Groups and semigroups defined by colorings of synchronizing automata
• INVERSE SEMIGROUPS OF PARTIAL AUTOMATON PERMUTATIONS
• SELF-SIMILAR INVERSE SEMIGROUPS AND SMALE SPACES
• Nondeterministic Space is Closed under Complementation
• The word problem in Hanoi Towers groups
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE