Strong optimal lower bounds for Turing machines that accept nonregular languages
From MaRDI portal
Publication:3569021
DOI10.1007/3-540-60246-1_137zbMath1193.68119OpenAlexW1552693082MaRDI QIDQ3569021
Giovanni Pighizzini, Carlo Mereghetti, Alberto Bertoni
Publication date: 17 June 2010
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60246-1_137
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (10)
Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Space hierarchy theorem revised. ⋮ Pushdown and one-counter automata: constant and non-constant memory usage ⋮ A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines ⋮ Preface ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Factoring and Testing Primes in Small Space ⋮ New Results on the Minimum Amount of Useful Space ⋮ Bridging across the \(\log(n)\) space frontier ⋮ A variant of inductive counting
This page was built for publication: Strong optimal lower bounds for Turing machines that accept nonregular languages
