Parallel algorithms for power circuits and the word problem of the Baumslag group

DOI10.1007/s00037-023-00244-xzbMath1525.20028OpenAlexW3131346071MaRDI QIDQ6083216

Caroline Mattes, Armin Weiß

Publication date: 31 October 2023

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-023-00244-x

zbMATH Keywords

word problemparallel complexityBaumslag grouppower circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational methods for problems pertaining to group theory (20-08)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• The complexity of membership problems for circuits over sets of integers
• Jump interpolation search trees and symmetric binary numbers
• A very hard log-space counting class
• Generic-case complexity, decision problems in group theory, and random walks.
• Evaluation of circuits over nilpotent and polycyclic groups
• Isoperimetric and isodiametric functions of groups
• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Minimum weight modified signed-digit representations and fast exponentiation
• Word Problems Solvable in Logspace
• Taming the hydra: The word problem and extreme integer compression
• POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY
• The conjugacy problem for Higman’s group
• On parameterized complexity of the word search problem in the Baumslag-Gersten group
• The co-word problem for the Higman-Thompson group is context-free
• Computational Complexity
• The Compressed Word Problem for Groups
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• A Finitely Generated Infinite Simple Group
• The word problem
• The word problem
• Improved parallel algorithms for generalized Baumslag groups
• Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group.

This page was built for publication: Parallel algorithms for power circuits and the word problem of the Baumslag group