Cellular non-deterministic automata and partial differential equations

• Cellular non-deterministic automata (CNDA) extend the concept of cellular automata.
• CNDA are defined in the spirit of non-deterministic automata theory.
• The dynamical behavior of a CNDA can be analyzed with deterministic superautomata.
• A CNDA can be embedded in a deterministic cellular automaton.
• CNDA can be used to approximate dynamics of certain partial differential equations.

We define cellular non-deterministic automata (CNDA) in the spirit of non-deterministic automata theory. They are different from the well-known stochastic automata. We propose the concept of deterministic superautomata to analyze the dynamical behavior of a CNDA and show especially that a CNDA can be embedded in a deterministic cellular automaton. As an application we discuss a connection between certain partial differential equations and CNDA.