Sublogarithmic Bounds on Space and Reversals

DOI10.1137/S0097539796301306zbMath0914.68068MaRDI QIDQ4210151

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Publication date: 21 September 1998

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

zbMATH Keywords

computational complexityformal languagesalternationcomputational lower bounds

Mathematics Subject Classification ID

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

Related Items (6)

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES

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