Word Problems Solvable in Logspace
From MaRDI portal
Publication:4131647
DOI10.1145/322017.322031zbMATH Open0359.68049OpenAlexW2009571139MaRDI QIDQ4131647FDOQ4131647
Authors: Richard J. Lipton, Yechezkel Zalcstein 
Publication date: 1977
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322017.322031
Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)
Cited In (56)
- On the power of algebraic branching programs of width two
- 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
- Compressed decision problems for graph products and applications to (outer) automorphism groups.
- The complexity of Grigorchuk groups with application to cryptography
- Complete problems for symmetric logspace involving free groups
- Some subclasses of context-free languages in \(NC^ 1\)
- On the parallel complexity of linear groups
- Logspace and compressed-word computations in nilpotent groups
- Parallel complexity for nilpotent groups
- Complexity, combinatorial group theory and the language of palutators
- Improved parallel algorithms for generalized Baumslag groups
- \(\mathcal C\)-graph automatic groups.
- Complexity classes of equivalence problems revisited
- Algorithmic problems in Engel groups and cryptographic applications
- The ring of \(k\)-regular sequences
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- Nondeterministic \(NC^1\) computation
- Evaluation of circuits over nilpotent and polycyclic groups
- Average-case complexity and decision problems in group theory.
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
- Inverse monoids: decidability and complexity of algebraic questions.
- Advice classes of parametrized tractability
- 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 word problem in graph products
- 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
- Logspace computations in graph products
- Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two
- Partially commutative inverse monoids.
- A note on representations of a certain monoid
- Algorithmically complex residually finite groups
- Algorithms for matrix groups and the Tits alternative
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamic algorithms for the Dyck languages
- Generic-case complexity, decision problems in group theory, and random walks.
- On groups that have normal forms computable in logspace.
- 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
- TC^0 circuits for algorithmic problems in nilpotent groups
- Log-space conjugacy problem in the Grigorchuk group
- Minsky Machines and Algorithmic Problems
- The Bounded and Precise Word Problems for Presentations of Groups
- The power word problem in graph products
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)
