Parallel algorithms for power circuits and the word problem of the Baumslag group
From MaRDI portal
Publication:6083216
DOI10.1007/s00037-023-00244-xzbMath1525.20028OpenAlexW3131346071MaRDI QIDQ6083216
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
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