Problems complete for deterministic logarithmic space
From MaRDI portal
Publication:3787477
Recommendations
Cited in
(52)- 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
- Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
- Complexity models for incremental computation
- Completeness results for graph isomorphism.
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Computation by interaction for space-bounded functional programming
- On the parallel complexity of linear groups
- Counting quantifiers, successor relations, and logarithmic space
- On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
- How to meet in anonymous network
- STACS 2004
- Parameterized complexity of finding regular induced subgraphs
- Equivalence classes and conditional hardness in massively parallel computations
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
- 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
- On the complexity of topological sorting
- scientific article; zbMATH DE number 4062587 (Why is no real title available?)
- Interleaved Group Products
- On the complexity of matrix rank and rigidity
- A note on logspace optimization
- The complexity of planarity testing
- The complexity of circuit value and network stability
- The word problem for finitary automaton groups
- 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
- Pure Pointer Programs with Iteration
- On the complexity of inverse semigroup conjugacy
- On the complexity of some problems on groups input as multiplication tables
- Space-efficient graph kernelizations
- Computing kernels in parallel: lower and upper bounds
- McNaughton families of languages.
- Complexity and enumeration in models of genome rearrangement
- Parallel vertex colouring of interval graphs
- Gradually intractable problems and nondeterministic log-space lower bounds
- A compendium of problems complete for symmetric logarithmic space
- Investigations concerning the structure of complete sets
- Low complexity algorithms in knot theory
- Monomials, multilinearity and identity testing in simple read-restricted circuits
- Complexity of testing reachability in matroids
- Oracle branching programs and Logspace versus \(P^*\)
- Distributed XML design
- Reversible space equals deterministic space
- Decision problems for reversible and permutation automata
- scientific article; zbMATH DE number 219246 (Why is no real title available?)
- 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)
