Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems

DOI10.1145/3569708MaRDI QIDQ7023433zbMATH OpenFDO

Authors Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß

Publication date 21 February 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3569708

zbMATH Keywords

G-programsGrigorchuk's groupnon-solvable groupsself-similar groupsstraight-line programsThompson's groupsword problem

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A uniform approach to define complexity classes
• A universal tree balancing theorem
• Arithmetic circuits: a survey of recent results and open questions
• Asymptotic aspects of Schreier graphs and Hanoi Towers groups.
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• C*-algebras and self-similar groups
• Compressed decision problems in hyperbolic groups
• Computational Complexity
• Counting classes: Thresholds, parity, mods, and fewness
• Coxeter groups are virtually special
• Embedding theorems for residually finite groups
• Evaluation of circuits over nilpotent and polycyclic groups
• Finite monoids and the fine structure of NC ¹
• Finite Monoids: From Word to Circuit Evaluation
• Free subgroups in linear groups
• GROUP LAWS AND FREE SUBGROUPS IN TOPOLOGICAL GROUPS
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Groups, languages and automata
• scientific article; zbMATH DE number 3642708 (Why is no real title available?)
• scientific article; zbMATH DE number 4145340 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 1003252 (Why is no real title available?)
• scientific article; zbMATH DE number 1088282 (Why is no real title available?)
• scientific article; zbMATH DE number 2156384 (Why is no real title available?)
• scientific article; zbMATH DE number 1453080 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 7650891 (Why is no real title available?)
• Introductory notes on Richard Thompson's groups
• Isomorphism of regular trees and words
• Iterated monodromy groups of quadratic polynomials. I.
• Knapsack problems for wreath products
• Leaf languages and string compression
• Logspace and logtime leaf languages
• Nondeterministic NC^1 computation
• On balanced versus unbalanced computation trees
• On Burnside's problem on periodic groups
• On subgroups of R. Thompson's group F and other diagram groups
• On the Burnside problem for periodic groups
• Parallel identity testing for skew circuits with big powers and applications
• Querying and Embedding Compressed Texts
• Relations among MOD-classes
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• The co-word problem for the Higman-Thompson group is context-free
• The complexity of Grigorchuk groups with application to cryptography
• The Compressed Word Problem for Groups
• The compressed word problem in relatively hyperbolic groups
• The iterated mod problem
• The Ore conjecture.
• The power word problem
• The Smallest Grammar Problem
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• The word problem
• Word Problems and Membership Problems on Compressed Words
• Word Problems Solvable in Logspace
• Über unendliche diskontinuierliche Gruppen.

This page was built for publication: Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems

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