Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Self-verifying cellular automata

Kutrib, Martin ; Worsch, Thomas

Zum Volltext im pdf-Format: Dokument 1.pdf (1.024 KB)

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-135223

Freie Schlagwörter (Englisch): one-way cellular automata , self-verification , computatonal capacity , closure properties , decidability problems
MSC - Klassifikation: 68Q45
Universität Justus-Liebig-Universit√§t Gie√üen
Institut: Institut f√ľr Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 1803
Sprache: Englisch
Erstellungsjahr: 2018
Publikationsdatum: 24.04.2018
Kurzfassung auf Englisch: 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.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand