Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/ITNG.2011.167 | ITNG |
Keywords | Field | DocType |
finite automaton,super linear work space,sublinear space real-time turing,sub linear-space,non-regular real-time definable language,nondeterministic turing machine,nondeterministic extension,quasi-real-time language,computer science,radiation detectors,formal languages,space complexity,turing machine,turing machines,real time systems,computational complexity,real time,finite automata,radiation detector | DTIME,Discrete mathematics,NSPACE,Computer science,Super-recursive algorithm,Theoretical computer science,PSPACE,Turing machine,Linear bounded automaton,Linear speedup theorem,Time hierarchy theorem,Distributed computing | Conference |
Citations | PageRank | References |
1 | 0.63 | 6 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan D. Bruda | 1 | 62 | 12.18 |