Space- and Time-Bounded Nondeterminism for Cellular Automata

Issue title: Cellular Automata

Article type: Research Article

Authors: Kutrib, Martin | Löwe, Jan-Thomas

Affiliations: Institute of Informatics, University of Giessen, Arndtstr. 2, D-35392 Giessen, Germany

Abstract: Nondeterministic cellular language acceptors are investigated. The nondeterminism is regarded as limited resource. For parallel devices it is natural to bound the nondeterminism in time and/or space. Depending on the length of the input, the number of allowed nondeterministic state transitions as well as the number of nondeterministic cells at all, is limited. For space-bounded nondeterminism it is shown that k+1 cells are not better than k, in case of one-way information flow. In the two-way case, one cell gains the power of unlimited nondeterminism. For the important real-time one-way arrays the range between deterministic and one guess per cell computations is studied. It is proved that there exists an infinite hierarchy of properly included families. By considering the relations with context-free languages, several relations between the devices in question are implied. Finally, a diagram is presented that summarizes relations between many cellular classes.

Keywords: cellular automata, formal languages, fimited Nondeterminism, parallel computing

Journal: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 273-293, 2003