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.
Type de document :
Communication dans un congrès
Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.71-90, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185494
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 14:16:34
Dernière modification le : mardi 7 mars 2017 - 15:06:45
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:45:10

Fichier

dmAL0106.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185494, version 1

Collections

Citation

Martin Kutrib, Jonas Lefèvre, Andreas Malcher. The Size of One-Way Cellular Automata. Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.71-90, 2010, DMTCS Proceedings. 〈hal-01185494〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

87