The power word problem in graph products

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

Authors: Markus Lohrey, Florian Stober, Armin Weiß 

Publication date: 29 July 2024

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

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

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)

Cites Work

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

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)