Sublogarithmic Bounds on Space and Reversals

DOI10.1137/S0097539796301306MaRDI QIDQ4210151zbMATH OpenFDO

Authors Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539796301306

zbMATH Keywords

alternationcomputational complexitycomputational lower boundsformal languages

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 2172794
• Inequalities for space-bounded Kolmogorov complexity
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• Reversibility in space-bounded computation
• A tradeoff theorem for space and reversal
• scientific article; zbMATH DE number 177808
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Tight space bounds for -exclusion
• Tight space bounds for \(\ell\)-exclusion
• Lower space bounds for randomized computation

Cited in

(15)

• Space hierarchy theorem revised.
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Tight space bounds for \(\ell\)-exclusion
• A space lower bound for acceptance by one-way _2-alternating machines
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Reversal Complexity
• scientific article; zbMATH DE number 79114 (Why is no real title available?)
• On tight separation for Blum measures applied to Turing machine buffer complexity
• scientific article; zbMATH DE number 2172794 (Why is no real title available?)
• scientific article; zbMATH DE number 1848283 (Why is no real title available?)
• The Sublogarithmic Alternating Space World
• Alternating space is closed under complement and other simulations for sublogarithmic space
• Minimal Size of Counters for (Real-Time) Multicounter Automata
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• Latvian quantum finite state automata for unary languages

This page was built for publication: Sublogarithmic Bounds on Space and Reversals

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