A new complete language for DSPACE(log n)
From MaRDI portal
Publication:1123607
DOI10.1016/0166-218X(89)90043-7zbMath0677.68035MaRDI QIDQ1123607
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- A comparison of polynomial time reducibilities
- On non-determinacy in simple computing devices
- On two-way multihead automata
- A taxonomy of problems with fast parallel algorithms
- Problems complete for deterministic logarithmic space
- Parallel Prefix Computation
- On Relating Time and Space to Size and Depth
- k + 1 Heads Are Better than k
- Relations Among Complexity Measures
- Parallel computation and the NC hierarchy relativized
- On Multi-Head Finite Automata
This page was built for publication: A new complete language for DSPACE(log n)
