An optimal lower bound for nonregular languages
From MaRDI portal
Publication:1330656
DOI10.1016/0020-0190(94)00056-5zbMath0810.68089OpenAlexW2076413258WikidataQ61677537 ScholiaQ61677537MaRDI QIDQ1330656
Carlo Mereghetti, Alberto Bertoni, Giovanni Pighizzini
Publication date: 21 July 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)00056-5
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (10)
On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Binary coded unary regular languages ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines ⋮ Preface ⋮ Hyper-minimizing minimized deterministic finite state automata ⋮ Magic numbers in the state hierarchy of finite automata ⋮ TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES ⋮ New Results on the Minimum Amount of Useful Space ⋮ Bridging across the \(\log(n)\) space frontier
Cites Work
This page was built for publication: An optimal lower bound for nonregular languages
