Iterative arrays with self-verifying communication cell
- PDF / 541,519 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 2 Downloads / 244 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Iterative arrays with self-verifying communication cell Martin Kutrib1 Accepted: 3 October 2020 Ó The Author(s) 2020
Abstract We study the computational capacity of self-verifying iterative arrays (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 SVIAs 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. SVIAs can be sped-up by any constant multiplicative factor as long as the result does not fall below realtime. We show that even realtime 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. Keywords Iterative arrays Self-verification Computational capacity Speed-up Closure properties Decidability problems
1 Introduction One of the central questions in complexity and language theory asks for the power of nondeterminism in boundedresource computations. Traditionally, nondeterministic devices have been viewed as having as many nondeterministic guesses as time steps. The studies of this concept of unlimited nondeterminism led, for example, to the famous open LBA-problem or the unsolved question whether or not P equals NP. In order to gain a better understanding of the nature of nondeterminism, in Fischer and Kintala (1979) and Kintala (1977) it has been viewed as an additional limited resource at the disposal of time or space bounded computations. The concept of so-called self-verification at least dates back to the paper (Duris et al. 1997). It applies to automata
A preliminary version of this work was presented at the 25th International Workshop on Cellular Automata and Discrete Complex Systems, Guadalajara, Mexico, June 26–28, 2019, and it is published in Kutrib and Worsch (2019). & Martin Kutrib [email protected] 1
Institut fu¨r Informatik, Universita¨t Giessen, Arndtstr. 2, 35392 Giessen, Germany
for decision problems and makes use of stronger notions of acceptance and rejection of inputs. 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 unknown. 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. So, if a computation path gives the answer yes or no, in both cases the answer is definitely correct. This justifies the notion self-verifying and
Data Loading...
