The word problem for finitary automaton groups
From MaRDI portal
Publication:6175091
Abstract: A finitary automaton group is a group generated by an invertible, deterministic finite-state letter-to-letter transducer whose only cycles are self-loops at an identity state. We show that, for this presentation of finite groups, the uniform word problem is coNP-complete. Here, the input consists of a finitary automaton together with a finite state sequence and the question is whether the sequence acts trivially on all input words. Additionally, we also show that the respective compressed word problem, where the state sequence is given as a straight-line program, is PSPACE-complete. In both cases, we give a direct reduction from the satisfiablity problem for (quantified) boolean formulae.
Recommendations
- On the complexity of the word problem for automaton semigroups and automaton groups
- On groups whose word problem is solved by a counter automaton.
- scientific article; zbMATH DE number 7650891
- scientific article; zbMATH DE number 3379206
- The word and order problems for self-similar and automata groups
- On the word problem for finitely-generated semigroups
- Groups whose word problems are accepted by abelian G-automata
- An automata theoretic approach to the generalized word problem in graphs of groups.
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
Cites work
- An automaton group with \textsf{PSPACE}-complete word problem
- An automaton group with undecidable order and Engel problems
- Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
- Bounded automata groups are co-ET0L
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Complexity and randomness in group theory. GAGTA book 1
- Groups and automata: a perfect match
- Groups defined by automata
- Groups of intermediate growth: an introduction.
- Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 2195483 (Why is no real title available?)
- On orbits and the finiteness of bounded automaton groups
- On some algorithmic properties of finite state automorphisms of rooted trees.
- On the complexity of the word problem for automaton semigroups and automaton groups
- On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
- Problems complete for deterministic logarithmic space
- The Compressed Word Problem for Groups
- The conjugacy problem in automaton groups is not solvable.
- The finiteness problem for automaton semigroups is undecidable.
- The word and order problems for self-similar and automata groups
- Word Problems Solvable in Logspace
Cited in
(7)- The use of Knuth-Bendix methods to solve the word problem in automatic groups
- Word problems of groups: formal languages, characterizations and decidability
- Permutive one-way cellular automata and the finiteness problem for automaton groups
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- The freeness problem for automaton semigroups
- Real computational universality: the word problem for a class of groups with infinite presentation
- The finiteness problem for automaton semigroups of extended bounded activity
This page was built for publication: The word problem for finitary automaton groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6175091)
