Paper Info
Title
On the computational complexity of finite cellular automata
Abstract
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.
Year
DOI
Venue
1995
10.1006/jcss.1995.1009
J. Comput. Syst. Sci.
Keywords
Field
DocType
finite cellular automaton,computational complexity,cellular automata,cellular automaton
Discrete mathematics,Cellular automaton,Combinatorics,Continuous automaton,Nondeterministic finite automaton,Continuous spatial automaton,Mobile automaton,Reversible cellular automaton,Block cellular automaton,Stochastic cellular automaton,Mathematics
Journal
Volume
Issue
ISSN
50
1
Journal of Computer and System Sciences
Citations 
PageRank 
References 
36
2.03
4
Authors
1
Name
Order
Citations
PageRank
Klaus Sutner111919.42