Remarks on languages acceptable in log log n space

DOI10.1016/0020-0190(88)90026-9zbMath0652.68055OpenAlexW2055191062MaRDI QIDQ1107318

Andrzej Szepietowski

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90026-9

zbMATH Keywords

determinismspace complexitynondeterministic Turing machine

Mathematics Subject Classification ID

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

Related Items (9)

A remark on middle space bounded alternating Turing machines ⋮ If deterministic and nondeterministic space complexities are equal for log log n then they are also equal for log n ⋮ If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ A survey of space complexity ⋮ TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES ⋮ Some notes on strong and weak log log n space complexity ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Remarks on languages acceptable in log log n space