Self-verifying cellular automata
Loading...
Date
Authors
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
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.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report; 1803