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