TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES

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

zbMATH Keywords

theory of computationreal-timespace bounded computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

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