Word Problems Solvable in Logspace

DOI10.1145/322017.322031zbMath0359.68049OpenAlexW2009571139MaRDI QIDQ4131647

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

Mathematics Subject Classification ID

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)

Related Items (55)

Dynamic algorithms for the Dyck languages ⋮ On the parallel complexity of linear groups ⋮ Complexity, combinatorial group theory and the language of palutators ⋮ Inverse monoids: decidability and complexity of algebraic questions. ⋮ Between Broadway and the Hudson: A Bijection of Corridor Paths ⋮ Some subclasses of context-free languages in \(NC^ 1\) ⋮ Evaluating Matrix Circuits ⋮ The power word problem in graph products ⋮ Parallel complexity for nilpotent groups ⋮ Skew circuits of small width ⋮ On groups that have normal forms computable in logspace. ⋮ Minsky Machines and Algorithmic Problems ⋮ Algorithmically complex residually finite groups ⋮ Logspace and compressed-word computations in nilpotent groups ⋮ Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable. ⋮ Generic-case complexity, decision problems in group theory, and random walks. ⋮ Improved parallel algorithms for generalized Baumslag groups ⋮ The word problem for finitary automaton groups ⋮ The Bounded and Precise Word Problems for Presentations of Groups ⋮ A note on representations of a certain monoid ⋮ 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 ⋮ Lower bounds on the complexity of real-time branching programs ⋮ COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS ⋮ Advice classes of parametrized tractability ⋮ On the Power of Algebraic Branching Programs of Width Two ⋮ The ring of \(k\)-regular sequences ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ On the dimension of matrix embeddings of torsion-free nilpotent groups ⋮ Partially commutative inverse monoids. ⋮ Log-space conjugacy problem in the Grigorchuk group ⋮ THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY ⋮ Average-case complexity and decision problems in group theory. ⋮ TC^0 circuits for algorithmic problems in nilpotent groups ⋮ Complexity classes of equivalence problems revisited ⋮ Algorithmic problems in Engel groups and cryptographic applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of word problems for HNN-extensions ⋮ Complexity of word problems for HNN-extensions ⋮ CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS ⋮ The Nielsen reduction and P-complete problems in free groups ⋮ On the complexity of intersection and conjugacy problems in free groups ⋮ Nondeterministic \(NC^1\) computation ⋮ Logspace computations in graph products ⋮ Algorithms for matrix groups and the Tits alternative ⋮ Space functions of groups ⋮ The complexity of the max word problem and the power of one-way interactive proof systems ⋮ On oblivious branching programs of linear length ⋮ On the power of algebraic branching programs of width two ⋮ Compression techniques in group theory

This page was built for publication: Word Problems Solvable in Logspace