The power word problem in graph products

DOI10.1007/S00224-024-10173-ZMaRDI QIDQ6580077FDO

Authors Markus Lohrey, Florian Stober, Armin Weiß

Publication date 29 July 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

Grigorchuk groupright-angled Artin groupnilpotent groupword problemfinite index subgroupcompressed word problempower word problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Braid groups; Artin groups (20F36) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• The power word problem
• Knapsack in graph groups
• scientific article; zbMATH DE number 7559438
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Knapsack and the power word problem in solvable Baumslag–Solitar groups

Cites work

• scientific article; zbMATH DE number 6677405 (Why is no real title available?)
• scientific article; zbMATH DE number 4145340 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 42096 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 2156384 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 845841 (Why is no real title available?)
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• scientific article; zbMATH DE number 7559146 (Why is no real title available?)
• scientific article; zbMATH DE number 7561687 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Computational Complexity
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Efficient Computation in Groups Via Compression
• Evaluation of circuits over nilpotent and polycyclic groups
• Finite Monoids: From Word to Circuit Evaluation
• Improved parallel algorithms for generalized Baumslag groups
• Inhomogeneous sorting
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack in graph groups
• Knapsack problems for wreath products
• Knapsack problems in groups
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Linear time algorithm for the conjugacy problem in the first Grigorchuk group
• Log-space conjugacy problem in the Grigorchuk group
• Low-depth uniform threshold circuits and the bit-complexity of straight line programs
• Membership Problem for the Modular Group
• On Burnside's problem on periodic groups
• On a theorem of Marshall Hall.
• On some equations in free partially commutative monoids
• Power circuits, exponential algebra, and time complexity
• Some properties of commutation in free partially commutative monoids
• The Compressed Word Problem for Groups
• The complexity of Grigorchuk groups with application to cryptography
• The conjugacy problem in subgroups of right-angled Artin groups
• The power word problem in graph products
• The submonoid and rational subset membership problems for graph groups.
• The word problem
• The word problem for free partially commutative groups
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Uniqueness Theorems for Periodic Functions
• WORD EQUATIONS OVER GRAPH PRODUCTS
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• Word Problems Solvable in Logspace
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Über unendliche diskontinuierliche Gruppen.

This page was built for publication: The power word problem in graph products

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