Skip to Main content Skip to Navigation
Conference papers

The Size of One-Way Cellular Automata

Abstract : We investigate the descriptional complexity of basic operations on real-time one-way cellular automata with an unbounded as well well as a fixed number of cells. The size of the automata is measured by their number of states. Most of the bounds shown are tight in the order of magnitude, that is, the sizes resulting from the effective constructions given are optimal with respect to worst case complexity. Conversely, these bounds also show the maximal savings of size that can be achieved when a given minimal real-time OCA is decomposed into smaller ones with respect to a given operation. From this point of view the natural problem of whether a decomposition can algorithmically be solved is studied. It turns out that all decomposition problems considered are algorithmically unsolvable. Therefore, a very restricted cellular model is studied in the second part of the paper, namely, real-time one-way cellular automata with a fixed number of cells. These devices are known to capture the regular languages and, thus, all the problems being undecidable for general one-way cellular automata become decidable. It is shown that these decision problems are $\textsf{NLOGSPACE}$-complete and thus share the attractive computational complexity of deterministic finite automata. Furthermore, the state complexity of basic operations for these devices is studied and upper and lower bounds are given.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185494
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 2:16:34 PM
Last modification on : Friday, November 29, 2019 - 2:22:03 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:45:10 AM

File

dmAL0106.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185494, version 1

Collections

Citation

Martin Kutrib, Jonas Lefèvre, Andreas Malcher. The Size of One-Way Cellular Automata. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. pp.71-90. ⟨hal-01185494⟩

Share

Metrics

Record views

388

Files downloads

790