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.

Statistics

Seen <100 times
0 Comments

More articles like this

One-way bounded cellular automata

on Information and Control Jan 01, 1980

On One-way One-bitO(One)-message Cellular Automata

on Electronic Notes in Theoretica... Jan 01, 2009

One-way cellular automata on Cayley graphs

on Theoretical Computer Science Jan 01, 1994
More articles like this..