Affordable Access

Publisher Website

Fast one-way cellular automata

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
295
Identifiers
DOI: 10.1016/s0304-3975(02)00406-1
Keywords
  • Models Of Computation
  • Computational Complexity
  • Cellular Automata
  • Time Hierarchies
  • Closure Properties

Abstract

Abstract 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 infinite 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.

There are no comments yet on this publication. Be the first to share your thoughts.