TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
From MaRDI portal
Publication:5168415
DOI10.1142/S0129054113500329zbMath1291.68234arXiv1108.2613OpenAlexW2047061522MaRDI QIDQ5168415
Abuzer Yakaryılmaz, A. C. Cem Say
Publication date: 4 July 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.2613
Related Items (3)
Uncountable realtime probabilistic classes ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ New Results on the Minimum Amount of Useful Space
Cites Work
- Unbounded-error quantum computation with small space bounds
- On probabilistic pushdown automata
- Remarks on languages acceptable in log log n space
- An optimal lower bound for nonregular languages
- Corrigendum to ``An optimal lower bound for nonregular languages
- A remark on middle space bounded alternating Turing machines
- Quantum computation with write-only memory
- Real time computation
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
- A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES
- Sublogarithmic Bounds on Space and Reversals
- Probabilistic automata
This page was built for publication: TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES