Title :
Sublinear Space Real-Time Turing Machines Cannot Count
Author :
Bruda, Stefan D.
Author_Institution :
Dept. of Comput. Sci., Bishop´´s Univ., Sherbrooke, QC, Canada
Abstract :
We show that sub linear-space bounded real-time, deterministic or nondeterministic Turing machines are equivalent to finite automata. Non-regular real-time definable languages (and also quasi-real-time languages, their nondeterministic extension) can thus only be accepted with linear or super linear work space.
Keywords :
Turing machines; computational complexity; deterministic automata; finite automata; formal languages; finite automata; non-regular real-time definable languages; nondeterministic Turing machines; nondeterministic extension; quasi-real-time languages; sublinear space real-time turing machines; super linear work space; Complexity theory; Computer science; Magnetic heads; Radiation detectors; Real time systems; Turing machines; computational complexity; on-line; quasi real-time definable languages; real time; real-time definable languages; space complexity;
Conference_Titel :
Information Technology: New Generations (ITNG), 2011 Eighth International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-61284-427-5
Electronic_ISBN :
978-0-7695-4367-3
DOI :
10.1109/ITNG.2011.167
