There are no fully space constructible functions between log log n and log n

DOI10.1016/0020-0190(87)90111-6zbMath0653.68039OpenAlexW2015456620MaRDI QIDQ1108005

Andrzej Szepietowski

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90111-6

zbMATH Keywords

Turing machinespace complexityfully space constructible function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Related Items

A survey of two-dimensional automata theory ⋮ Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ A survey of space complexity

Cites Work

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