Word Problems Solvable in Logspace
From MaRDI portal
Cited in
(60)- Minsky Machines and Algorithmic Problems
- The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
- On the power of algebraic branching programs of width two
- On the power of algebraic branching programs of width two
- Compressed decision problems for graph products and applications to (outer) automorphism groups.
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- The complexity of Grigorchuk groups with application to cryptography
- Complete problems for symmetric logspace involving free groups
- Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
- On the parallel complexity of linear groups
- Some subclasses of context-free languages in NC^ 1
- Logspace and compressed-word computations in nilpotent groups
- Complexity, combinatorial group theory and the language of palutators
- Parallel complexity for nilpotent groups
- C-graph automatic groups.
- Improved parallel algorithms for generalized Baumslag groups
- Complexity classes of equivalence problems revisited
- The Bounded and Precise Word Problems for Presentations of Groups
- The ring of k-regular sequences
- Nondeterministic NC^1 computation
- Algorithmic problems in Engel groups and cryptographic applications
- Evaluation of circuits over nilpotent and polycyclic groups
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
- Average-case complexity and decision problems in group theory.
- Advice classes of parametrized tractability
- Residually finite non-linear hyperbolic groups
- Inverse monoids: decidability and complexity of algebraic questions.
- THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
- The power word problem in graph products
- Between Broadway and the Hudson: A Bijection of Corridor Paths
- Complexity of word problems for HNN-extensions
- Complexity of word problems for HNN-extensions
- The word problem for finitary automaton groups
- Lower bounds on the complexity of real-time branching programs
- The power of a single qubit: two-way quantum finite automata and the word problem
- The power word problem in graph products
- Chebyshev polynomials involved in the Householder's method for square roots
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- Compression techniques in group theory
- Space functions of groups.
- On the complexity of intersection and conjugacy problems in free groups
- The Nielsen reduction and P-complete problems in free groups
- Skew circuits of small width
- Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two
- Partially commutative inverse monoids.
- Logspace computations in graph products
- A note on representations of a certain monoid
- Algorithmically complex residually finite groups
- Algorithms for matrix groups and the Tits alternative
- scientific article; zbMATH DE number 7561687 (Why is no real title available?)
- scientific article; zbMATH DE number 7561757 (Why is no real title available?)
- Dynamic algorithms for the Dyck languages
- On groups that have normal forms computable in logspace.
- Generic-case complexity, decision problems in group theory, and random walks.
- On oblivious branching programs of linear length
- Evaluating matrix circuits
- The complexity of the max word problem and the power of one-way interactive proof systems
- On the dimension of matrix embeddings of torsion-free nilpotent groups
- Log-space conjugacy problem in the Grigorchuk group
This page was built for publication: Word Problems Solvable in Logspace
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4131647)
