𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Computational Complexity of Finite Cellular Automata

✍ Scribed by K. Sutner

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
932 KB
Volume
50
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be NLOG-complete for one-dimensional cellular automata. The problem is NP-complete for all dimensions higher than one. Similarly, the question whether a target configuration occurs in the orbit of a source configuration may be P-complete, NP-complete or PSPACE-complete, depending on the type of cellular automaton. C. 1995 Academic Press, inc.

πŸ“œ SIMILAR VOLUMES

Comparison of cellular automata and fini
Comparison of cellular automata and finite volume techniques for simulation of incompressible flows in complex geometries
✍ J. Bernsdorf; F. Durst; M. SchΓ€fer πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 572 KB

A cellular automata method for the prediction of incompressible fluid flows is presented and its practical relevance is investigated by comparing it with a standard finite volume solver. The cellular automata approach is based on an advanced lattice Boltzmann technique for a discrete microscopic des