A remark on middle space bounded alternating Turing machines

DOI10.1016/0020-0190(95)00151-2zbMath0875.68395OpenAlexW1984165512WikidataQ61677536 ScholiaQ61677536MaRDI QIDQ1350303

Giovanni Pighizzini, Carlo Mereghetti

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00151-2

zbMATH Keywords

Computational complexityFormal languagesAlternationComputational lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Descriptional complexity of two-way pushdown automata with restricted head reversals, TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE, A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines, TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES

Cites Work

• Unnamed Item
• Unnamed Item
• Remarks on languages acceptable in log log n space
• Space bounds for processing contentless inputs
• Turing machines with sublogarithmic space
• Relationships between nondeterministic and deterministic tape complexities
• Alternation
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Some Results on Tape-Bounded Turing Machines