Problems complete for deterministic logarithmic space
DOI10.1016/0196-6774(87)90018-6zbMATH Open0644.68058OpenAlexW1990870868WikidataQ59567327 ScholiaQ59567327MaRDI QIDQ3787477FDOQ3787477
Authors: Pierre McKenzie, Stephen Cook 
Publication date: 1987
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(87)90018-6
Recommendations
breadth-first searchdepth-first searchlabellingdeterministic logarithmic spacelog spaceconnectivity of undirected graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (52)
- Decision problems for reversible and permutation automata
- Approximation in (Poly-) logarithmic space
- Planar and grid graph reachability problems
- The complexity of intersecting finite automata having few final states
- Dynamic complexity of expansion
- Complexity models for incremental computation
- Completeness results for graph isomorphism.
- Computation by interaction for space-bounded functional programming
- Counting quantifiers, successor relations, and logarithmic space
- On the parallel complexity of linear groups
- STACS 2004
- On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
- How to meet in anonymous network
- Equivalence classes and conditional hardness in massively parallel computations
- Parameterized complexity of finding regular induced subgraphs
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
- Title not available (Why is that?)
- A new complete language for DSPACE(log n)
- On measures of space over real and complex numbers
- Finding regular subgraphs in both arbitrary and planar graphs
- The arithmetic complexity of tensor contraction
- PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Title not available (Why is that?)
- On the complexity of topological sorting
- Interleaved Group Products
- On the complexity of matrix rank and rigidity
- Title not available (Why is that?)
- A note on logspace optimization
- The word problem for finitary automaton groups
- The complexity of planarity testing
- The complexity of circuit value and network stability
- Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
- Extensions to Barrington's M-program model
- Isomorphism testing of read-once functions and polynomials
- On the complexity of inverse semigroup conjugacy
- Pure Pointer Programs with Iteration
- On the complexity of some problems on groups input as multiplication tables
- Space-efficient graph kernelizations
- McNaughton families of languages.
- Complexity and enumeration in models of genome rearrangement
- Gradually intractable problems and nondeterministic log-space lower bounds
- A compendium of problems complete for symmetric logarithmic space
- Title not available (Why is that?)
- Low complexity algorithms in knot theory
- Monomials, multilinearity and identity testing in simple read-restricted circuits
- Reversible space equals deterministic space
- Distributed XML design
- Oracle branching programs and Logspace versus \(P^*\)
- Title not available (Why is that?)
- Investigations Concerning the Structure of Complete Sets
- The expressiveness of a family of finite set languages
This page was built for publication: Problems complete for deterministic logarithmic space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787477)
