%0 Conference Proceedings
%T Iterative Arrays with Self-verifying Communication Cell
%+ Justus-Liebig-Universität Gießen = Justus Liebig University (JLU)
%+ Karlsruhe Institute of Technology (KIT)
%A Kutrib, Martin
%A Worsch, Thomas
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Guadalajara, Mexico
%Y Alonso Castillo-Ramirez
%Y Pedro P. B. de Oliveira
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-11525
%P 77-90
%8 2019-06-26
%D 2019
%R 10.1007/978-3-030-20981-0_6
%Z Computer Science [cs]Conference papers
%X We study the computational capacity of self-verifying iterative arrays ($$\text {SVIA}$$). 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. It turns out that, for any time-computable time complexity, the family of languages accepted by $$\text {SVIA}$$s is a characterization of the so-called complementation kernel of nondeterministic iterative array languages, that is, languages accepted by such devices whose complementation is also accepted by such devices. $$\text {SVIA}$$s can be sped-up by any constant multiplicative factor as long as the result does not fall below realtime. We show that even realtime $$\text {SVIA}$$ are as powerful as lineartime self-verifying cellular automata and vice versa. So they are strictly more powerful than the deterministic devices. Closure properties and various decidability problems are considered.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-02312617/document
%2 https://inria.hal.science/hal-02312617/file/484947_1_En_6_Chapter.pdf
%L hal-02312617
%U https://inria.hal.science/hal-02312617
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IFIP-LNCS-11525