Remarks on languages acceptable in log log n space

DOI10.1016/0020-0190(88)90026-9MaRDI QIDQ1107318zbMATH OpenOpenAlexFDO

Authors 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

determinismnondeterministic Turing machinespace complexity

Mathematics Subject Classification ID

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

Review text

A language is acceptable in the strong sense by a two-way nondeterministic Turing machine when all computation paths on every input stop and satisfy the space bound. The following main theorem is established. There exists a language which is acceptable in the strong sense by a two-way nondeterministic Turing machine in log log n space such that: if the language is not decidable by any two-way deterministic Turing machine in log log n space, then \(L\neq NL\).

Recommendations

• Some notes on strong and weak log log n space complexity
• If deterministic and nondeterministic space complexities are equal for n then they are also equal for n
• scientific article; zbMATH DE number 3984575
• Two-way automata versus logarithmic space
• scientific article; zbMATH DE number 8798

Cited in

(16)

• A new complete language for DSPACE(log n)
• A survey of space complexity
• A remark on middle space bounded alternating Turing machines
• Gap-languages and log-time complexity classes
• Some notes on strong and weak log log n space complexity
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• A space lower bound for acceptance by one-way _2-alternating machines
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• scientific article; zbMATH DE number 3976381 (Why is no real title available?)
• scientific article; zbMATH DE number 8798 (Why is no real title available?)
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• scientific article; zbMATH DE number 1101593 (Why is no real title available?)
• Lower Space Bounds for Accepting Shuffle Languages
• If deterministic and nondeterministic space complexities are equal for n then they are also equal for n
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107318)