Fast one-way cellular automata
β
Andreas Klein; Martin Kutrib
π
Article
π
2003
π
Elsevier Science
π
English
β 333 KB
Space-bounded one-way cellular language acceptors (OCA) are investigated. The only inclusion known to be strict in their time hierarchy from real-time to exponential-time is between real-time and linear-time! We show the surprising result that there exists an inΓΏnite hierarchy of properly included O