Self-verifying cellular automata
Datum
Autor:innen
Betreuer/Gutachter
Weitere Beteiligte
Herausgeber
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Lizenz
Zitierlink
Zusammenfassung
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.