Self-verifying cellular automata

Abstract

We study the computational capacity of self-verifying cellular automata with an emphasis on one-way information flow (SVOCA). A self-verifying device is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers "yes", "no", or "do not know". For every input word, at least one computation path must give either the answer "yes" or "no", and the answers given must not be contradictory. We show that realtime SVOCA are strictly more powerful than realtime deterministic one-way cellular automata, since they can accept non-semilinear unary languages. It turns out that SVOCA can strongly be sped-up from lineartime to realtime. They are even capable to simulate any lineartime computation of deterministic two-way cellular automata. Closure properties and decidability problems are considered as well.