Fast one-way cellular automata

✍ Scribed by Andreas Klein; Martin Kutrib

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 333 KB
• Volume: 295
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00406-1

✦ Synopsis

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 OCA-language families in that range. A generalization of a method in Terrier (Theoret. Comput. Sci. 156 (1-2) (1996) 281) is shown which provides a tool for proving that languages are not acceptable by OCAs with small time bounds. The hierarchies are established by such a language and a translation result. In addition, a notion of constructibility for CAs is introduced, along with some of its properties. We prove several closure properties of the families in the hierarchy.