A Hierarchy Theorem for Polynomial-Space Recognition
From MaRDI portal
Publication:4046031
DOI10.1137/0203014zbMath0294.02013OpenAlexW2085533822MaRDI QIDQ4046031
Publication date: 1974
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0203014
Related Items (7)
On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ A survey of space complexity ⋮ Hierarchies of Turing machines with restricted tape alphabet size ⋮ Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems ⋮ Techniques for separating space complexity classes ⋮ Relating refined space complexity classes ⋮ Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
This page was built for publication: A Hierarchy Theorem for Polynomial-Space Recognition
