Martin Kutrib

Andreas Malcher

Iterative Arrays with Finite Inter-Cell Communication

Iterative arrays whose internal inter-cell communication is quantitatively restricted are investigated. The quantity of communication is measured by counting the number of uses of the links between cells. In particular, iterative arrays are studied where the maximum number of communications per cell occurring in accepting computations is drastically bounded by a constant number. Additionally, the iterative arrays have to work in realtime. We study the computational capacity of such devices. One main result is that a strict and dense hierarchy with respect to the constant number of communications exists. Due to their very restricted communication, the question arises whether the usually studied decidability problems such as, for example, emptiness, finiteness, inclusion, or equivalence become decidable for such devices. However, by reduction of Hilbert's tenth problem it can be shown that all such decidability questions remain undecidable.

Introduction

Devices of homogeneous, interconnected, parallel acting automata have widely been investigated from a computational capacity point of view. Multidimensional devices with nearest neighbor connections whose cells are finite automata are commonly called cellular automata (CA). The cells work synchronously at discrete time steps. If the input mode is sequential to a distinguished communication cell, such devices are called iterative arrays.

In connection with formal language recognition one-dimensional iterative arrays (IA) have been introduced in [START_REF] Cole | Real-time computation by n-dimensional iterative arrays of finite-state machines[END_REF], where it was shown that the language family accepted by realtime IAs forms a Boolean algebra not closed under concatenation and reversal. In [START_REF] Chang | Parallel parsing on a one-way array of finite-state machines[END_REF] it is shown that for every context-free grammar a two-dimensional lineartime iterative array parser exists. A realtime IA for prime numbers has been constructed in [START_REF] Fischer | Generation of primes by a one-dimensional real-time iterative array[END_REF]. A characterization of various types of IAs in terms of restricted Turing machines and several results, especially speed-up theorems, are given in [START_REF] Ibarra | Some results concerning linear iterative (systolic) arrays[END_REF][START_REF] Ibarra | Two-dimensional iterative arrays: Characterizations and applications[END_REF]. Several more results concerning formal languages can be found, for example, in the survey [START_REF] Kutrib | Cellular automata and language theory[END_REF].

It is obvious that inter-cell communication is an essential resource for iterative arrays and can be measured qualitatively as well as quantitatively. In the first case, the number of different messages to be communicated by the cells is bounded by some fixed constant. IAs with this restricted inter-cell communication have been investigated in [START_REF] Umeo | A design of real-time non-regular sequence generation algorithms and their implementations on cellular automata with 1-bit inter-cell communications[END_REF][START_REF] Umeo | Real-time generation of primes by a 1-bit-communication cellular automaton[END_REF] with respect to the algorithmic design of sequence generation. In particular, it is shown that several infinite, non-regular sequences such as exponential or polynomial, Fibonacci, and prime sequences can be generated in realtime. In connection with language recognition and decidability questions multi-dimensional IAs and one-dimensional (one-way) CAs with restricted communication have intensively been studied in [START_REF] Kutrib | Computations and decidability of iterative arrays with restricted communication[END_REF][START_REF] Kutrib | Cellular automata with limited inter-cell bandwidth[END_REF][START_REF] Worsch | Linear time language recognition on cellular automata with restricted communication[END_REF].

For a quantitative measure of communication in iterative arrays the number of uses of the links between cells is counted. Additionally, it is distinguished between bounds on the sum of all communications of an accepting computation and bounds on the maximum number of communications per cell occurring in accepting computations. There are quite a few results in the literature with respect to these measures. Results for (one-way) cellular automata may be found in [START_REF] Kutrib | Cellular automata with sparse communication[END_REF][START_REF] Kutrib | One-way cellular automata, bounded languages, and minimal communication[END_REF]. In [START_REF] Kutrib | On one-way one-bit O(1)-message cellular automata[END_REF][START_REF] Kutrib | One-way cellular automata, bounded languages, and minimal communication[END_REF] also cellular automata are investigated that are restricted with respect to the qualitative and the quantitative measure. The main results are in both cases hierarchy results and the undecidability of almost all commonly studied decidability questions such as emptiness, finiteness, equivalence, inclusion, regularity, and context-freeness. It should be noted that already a finite amount of communication per cell is sufficient to obtain undecidability results for cellular automata. First results on iterative arrays with restricted communication are presented in [START_REF] Malcher | Hierarchies and undecidability results for iterative arrays with sparse communication[END_REF] and comprise again hierarchy results as well as undecidability results for the above questions. Concerning the measure on the maximum communication per cell the undecidability results hold as long as at least a logarithmic number of communications per cells is allowed. Moreover, it is stated as an open question whether the undecidable questions become decidable when the allowed communication is even more restricted, namely, to be bounded by a constant number.

In this paper, we can answer the latter question negatively. In addition, we establish a strict and dense hierarchy with respect to the constant number of communications. The paper is organized as follows. In the next section, we present some basic notions and definitions, introduce the classes of max communication bounded iterative arrays, and give an illustrative example. Then, in Section 3 we show that for every k ≥ 2, IAs with at most k + 1 communications per cell are more powerful than devices with at most k communications per cell. For k ∈ {0, 1, 2} it turns out that devices with at most k communications per cell can accept regular languages only. Section 4 is devoted to showing the undecidability of the usually studied decidability questions for IAs working in realtime with a constant number of communications per cell. This is done by a reduction of Hilbert's tenth problem and requires a couple of consecutive constructions of IAs with a constant number of communications per cell, whereby the goal is to evaluate a polynomial with integral coefficients given by an instance of Hilbert's tenth problem.

Definitions and Preliminaries

We denote the non-negative integers by N. Let Σ denote a finite set of letters. Then we write Σ * for the set of all finite words (strings) consisting of letters from Σ. The empty word is denoted by λ, and we set Σ + = Σ * \ {λ}. A subset of Σ * is called a language over Σ. For the reversal of a word w we write w R and for its length we write |w|. For the number of occurrences of a symbol x in w we use the notation |w| x . A language L over some alphabet {a 1 , a 2 , . . . ,

a k } is said to be letter bounded, if L ⊆ a * 1 a * 2 • • • a * k .
In general, we use ⊆ for inclusions and ⊂ for strict inclusions.

A one-dimensional iterative array is a linear, semi-infinite array of identical deterministic finite state machines, sometimes called cells. Except for the leftmost cell each one is connected to its both nearest neighbors (see Figure 1). For convenience we identify the cells by their coordinates, that is, by non-negative integers. The distinguished leftmost cell at the origin is connected to its right neighbor and, additionally, equipped with a one-way read-only input tape. At the outset of a computation the input is written on the input tape with an infinite number of end-of-input symbols to the right, and all cells are in the so-called quiescent state. The finite state machines work synchronously at discrete time steps. The state transition of all cells but the communication cell depends on the current state of the cell itself and on the information which is currently sent by its neighbors. The information sent by a cell depends on its current state and is determined by so-called communication functions. The state transition of the communication cell additionally depends on the input symbol to be read next. The head of the one-way input tape is moved to the right in each step. With an eye towards recognition problems the machines have no extra output tape but the states are partitioned into accepting and rejecting states.

Formally, an iterative array (IA) is a system S, F, A, B, , s 0 , b l , b r , δ, δ 0 , where S is the finite, nonempty set of cell states, F ⊆ S is the set of accepting states, A is the finite set of input symbols, B is the finite set of communication symbols, / ∈ A is the end-of-input symbol, s 0 ∈ S is the quiescent state, b l , b r : S → B ∪ {⊥} are communication functions which determine the information to be sent to the left and right neighbors, where ⊥ means nothing to send and b l (s 0 ) = b r (s 0 ) = ⊥, δ : (B ∪ {⊥}) × S × (B ∪ {⊥}) → S is the local transition function for all but the communication cell satisfying δ(⊥, s 0 , ⊥) = s 0 , and δ 0 : (A ∪ { }) × S × (B ∪ {⊥}) → S is the local transition function for the communication cell. Let M be an IA. A configuration of M at some time t ≥ 0 is a description of its global state which is a pair (w t , c t ), where w t ∈ A * is the remaining input sequence and c t : N → S is a mapping that maps the single cells to their current states. The configuration (w 0 , c 0 ) at time 0 is defined by the input word w 0 and the mapping c 0 that assigns the quiescent state to all cells, while subsequent configurations are chosen according to the global transition function ∆ that is induced by δ and δ 0 as follows: Let (w t , c t ), t ≥ 0, be a configuration. Then its successor configuration (w t+1 , c t+1 ) = ∆(w t , c t ) is as follows.

s 0 s 0 s 0 s 0 s 0 a 1 a 2 a 3 • • • a n ▽
c t+1 (i) = δ(b r (c t (i -1)), c t (i), b l (c t (i + 1)))
for all i ≥ 1, and c t+1 (0) = δ 0 (a, c t (0), b l (c t (1))), where a = and w t+1 = λ if w t = λ, as well as a = a 1 and

w t+1 = a 2 a 3 • • • a n if w t = a 1 a 2 • • • a n .
We remark that we obtain the classical definition of IA, if we set B = S and b l (s) = b r (s) = s for all s ∈ S.

An input w is accepted by an IA M if at some time i during the course of its computation the communication cell enters an accepting state. The language accepted by M is denoted by L(M ). Let t : N → N, t(n) ≥ n + 1 be a mapping. If all w ∈ L(M ) are accepted with at most t(|w|) time steps, then M and L(M ) are said to be of time complexity t.

The family of all languages which are accepted by some type of device X with time complexity t is denoted by L t (X). If t is the function n + 1, acceptance is said to be in realtime and we write L rt (X). Since for nontrivial computations an IA has to read at least one end-of-input symbol, realtime has to be defined as (n + 1)-time. The lineartime languages L lt (X) are defined according to L lt (X) = r∈Q, r≥1 L r•n (X).

In the following we study the impact of communication in iterative arrays. The communication is measured by the number of uses of the links between cells. It is understood that whenever a communication symbol not equal to ⊥ is sent, a communication takes place. Here we do not distinguish whether either or both neighboring cells use the link. More precisely, the number of communications between cell i and cell i + 1 up to time step t is defined by

com(i, t) = |{ j | 0 ≤ j < t and (b r (c j (i)) = ⊥ or b l (c j (i + 1)) = ⊥) }| .
For computations we now consider the maximal number of communications between two cells. Let c 0 , c 1 , . . . , c t(|w|) be the sequence of configurations computed on input w by some iterative array with time complexity t(n), that is, the computation on w. Then we define

mcom(w) = max{ com(i, t(|w|)) | 0 ≤ i ≤ t(|w|) -1 }.
Let f : N → N be a mapping. If all w ∈ L(M ) are accepted with computations where mcom(w) ≤ f (|w|), then M is said to be max communication bounded by f . We denote the class of IA that are max communication bounded by some function f by MC(f )-IA. In addition, we use the notation const for functions from O(1).

To illustrate the definitions we start with an example. In the next section it turns out that the non-regular language { a n b n | n ≥ 1 } is accepted by some realtime iterative array using at most three communications per inter-cell link.

The following example reveals that only five communications per inter-cell link are sufficient to accept the non-semilinear and, hence, non-context-free language

L = { a 3n+2 √ n b 2n | n ≥ 1 } in realtime.
Moreover, L is a subset of a * b * and, hence, a letter-bounded language.

Example 1. The language L belongs to L rt (MC(5)-IA).

The basic idea is to use the construction given in [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF] where a cellular automaton is described such that the nth cell enters a designated state s exactly at time step 2n + √ n . We basically implement this construction, but realize it with speed 1/2 in contrast to the construction in [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF]. Hence, the nth cell enters a designated state exactly at time step 4n + 2 √ n . When the communication cell reads the first b, it sends a signal with maximum speed to the right which arrives in the nth cell exactly at the moment when state s should be entered. In this case, another signal is sent with maximum speed to the left and the input is accepted if the latter signal reaches the communication cell when the end-of-input symbol is read. Thus, L is accepted by a realtime IA. Moreover, the construction given in [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF] needs three right-moving signals. Thus, four rightmoving signals and one left-moving signal are sufficient to accept L. This shows that the IA constructed is a realtime MC(5)-IA.

k + 1 Communications are Better than k

This section is devoted to studying the impact of the precise finite number k of communications between cells. It turns out that this number in fact matters unless it is very small. That is, we will obtain an infinite strict hierarchy for k ≥ 2, whereas the families of languages accepted with 0, 1, and 2 communications per inter-cell link coincide with the regular languages. We start at the bottom of the hierarchy.

Proposition 2. The language families L rt (MC(0)-IA), L rt (MC(1)-IA), and L rt (MC(2)-IA) coincide with the family of regular languages.

Proof. The proof is trivial for MC(0)-IAs. In this case the iterative array has the computational capacity of the communication cell, that is, of a deterministic finite automaton. Similarly, the proof is obvious for MC(1)-IAs. The sole communication on the inter-cell link between the communication cell and its neighbor sends some information to the right, but this information can never come back to the communication cell which, thus, is not affected by the communication at all. We conclude that the computational capacity also for MC(1)-IAs is that of deterministic finite automata.

Let us now consider MC(2)-IAs. Let the first communication on the inter-cell link between the communication cell and its neighbor take place at time step t ≥ 0. Before, all cells to the right of the communication cell are quiescent. So, the information transmitted by the communication causes the quiescent array to perform some computation and possibly to transmit some information back to the communication cell. More communications of the communication cell are useless. The computation performed by the array to the right of the communication cell only depends on the information transmitted during the first communication. However, these finitely many cases can be precomputed. Implementing the transition function of the communication cell so that it simulates the computations of the array in some state register allows to safely remove the first communication. In this way we obtain an equivalent MC(1)-IA that accepts regular languages only. Needless to say that a second communication from left right is useless and can be omitted as well.

The witnesses for the hierarchy are languages whose words are repetitions of unary blocks of the same size but with alternating symbols. For i ≥ 2 define

L hi = { (a n b n ) i 2 | n ≥ 1 } if i is even { (a n b n ) i 2 a n | n ≥ 1 } if i is odd . Lemma 3. For i ≥ 2,
the language L hi is accepted by some MC(i + 1)-IA.

Theorem 4. For i ≥ 2, the family L rt (MC(i)-IA) is strictly included in the family L rt (MC(i + 1)-IA)

Proof. For i ≥ 2, the witness language L hi is used to show the strict inclusion L rt (MC(i)-IA) ⊂ L rt (MC(i + 1)-IA). By Lemma 3, language L hi is accepted by some MC(i + 1)-IA in realtime. So, it remains to be shown that L hi is not accepted by any MC(i)-IA in realtime.

Let M = S, F, A, B, , s 0 , b l , b r , δ, δ 0 be an iterative array accepting L hi in realtime. We consider the communications on the inter-cell link between the communication cell and its neighbor. For clearer writing, we represent a configuration by a pair (w, sĉ), where w ∈ A * is the remaining input sequence as usual, s ∈ S is the state of the communication cell, and ĉ is a mapping that maps cells j ≥ 1 to their current states.

A key observation is that on unary inputs long enough the communication cell will run into state cycles unless a communication takes place. So, let w ∈ L hi be an accepted word whose block length n is long enough.

Assume that no communication takes place while processing the first |S| symbols a from the first block. Recall that by definition we have b l (s 0 ) = b r (s 0 ) = ⊥. Let w = a n v with the first letter in v being b. Then on processing the input prefix a |S| the communication cell necessarily enters some state at least twice. That is, there are 0 ≤ p 1 , 1 ≤ p 2 with p 1 + p 2 ≤ |S| such that ∆ p1 (a n v, s 0 ĉ0 ) = (a n-p1 v, s 1 ĉ0 ) and ∆ p2 (a n-p1 v, s 1 ĉ0 ) = (a n-p1-p2 v, s 1 ĉ0 ). That is, there is a state cycle of length p 2 leading from state s 1 to state s 1 . So, the input a n+p2 v is accepted as well. From the contradiction it follows that there is at least one communication during the first |S| time steps.

Next, we consider the sub-computations that process the last |S| symbols of a block and the first |S| 2 + |S| symbols of the following block. Without loss of generality, let this factor be a |S| b |S| 2 +|S| , and so w = ua |S| b |S| 2 +|S| v. Assume that no communication takes place (on the inter-cell link between the communication cell and its neighbor) while processing this factor. Let

∆ |u| (ua |S| b |S| 2 +|S| v, s 0 ĉ0 ) = (a |S| b |S| 2 +|S| v, sĉ).
Then there are 0 ≤ p 1 , 1 ≤ p 2 with p 1 + p 2 ≤ |S| such that

∆ p1 (a |S| b |S| 2 +|S| v, sĉ) = |S|-p1 b |S| 2 +|S| v, s 1 ĉ1 ) and ∆ p2 (a |S|-p1 b |S| 2 +|S| v, s 1 ĉ1 ) = (a |S|-p1-p2 b |S| 2 +|S| v, s 1 ĉ2 ).
That is, there is a state cycle of length p 2 leading from state s 1 to state s 1 . Continuing the computation without communication yields the existence of 0

≤ p 3 , 1 ≤ p 4 ≤ |S| with |S| ≤ p 1 + p 2 + p 3 and p 1 + p 2 + p 3 + p 4 ≤ 2|S| such that ∆ p3 (a |S|-p1-p2 b |S| 2 +|S| v, s 1 ĉ2 ) = (b |S| 2 +2|S|-p1-p2-p3 v, s 2 ĉ3 ), ∆ p4 (b |S| 2 +2|S|-p1-p2-p3 v, s 2 ĉ3 ) = (b |S| 2 +2|S|-p1-p2-p3-p4 v, s 2 ĉ4 ), and ∆ p2p4 (b |S| 2 +2|S|-p1-p2-p3-p4 v, s 2 ĉ4 ) = (b |S| 2 +2|S|-p1-p2-p3-p4-p2p4 v, s 2 ĉ5 ).
That is, there is a state cycle of length p 4 leading from state s 2 to state s 2 . Since there are no communications on the factor a |S| b |S| 2 +|S| , we can replace this factor by the factor a |S|+p2p4 b |S| 2 +|S|-p2p4 of the same length, and the configurations to the right of the communication cell develop exactly as before. We obtain the sub-computations

∆ p1 (a |S|+p2p4 b |S| 2 +|S|-p2p4 v, sĉ) = (a |S|+p2p4-p1 b |S| 2 +|S|-p2p4 v, s 1 ĉ1 ) and ∆ p2 (a |S|+p2p4-p1 b |S| 2 +|S|-p2p4 v, s 1 ĉ1 ) = (a |S|+p2p4-p1-p2 b |S| 2 +|S|-p2p4 v, s 1 ĉ2 ).
Since the communication cell runs through the state cycle of length p 2 leading from state s 1 to state s 1 and there is no communication, the sub-computation continues as

∆ p2p4 (a |S|+p2p4-p1-p2 b |S| 2 +|S|-p2p4 v, s 1 ĉ2 ) = (a |S|-p1-p2 b |S| 2 +|S|-p2p4 v, s 1 ĉ6 ), ∆ p3 (a |S|-p1-p2 b |S| 2 +|S|-p2p4 v, s 1 ĉ6 ) = (b |S| 2 +2|S|-p2p4-p1-p2-p3 v, s 2 ĉ7 ), ∆ p4 (b |S| 2 +2|S|-p2p4-p1-p2-p3 v, s 2 ĉ7 ) = (b |S| 2 +2|S|-p2p4-p1-p2-p3-p4 v, s 2 ĉ5 ).
For the last equation, note that the length of the replaced factor is the same as of the original factor. That, is the number of steps is the same on both factors. Moreover, since there is no communication of the communication cell, during these steps the right part of the configuration develops as before. So, the configuration of the right part is finally ĉ5 .

Since the configurations after processing the original factor and its replacement are identical, the input word with replaced factor not belonging to L hi is accepted as well. From the contradiction it follows that there is at least one communication while processing the factor a |S| b |S| 2 +|S| . Now we turn to the end of the computation. Assume that no communication takes place while processing the last 2|S| symbols from the last block, say these are symbols b. Let w = ub n with the last letter in u being an a. Then on processing the input suffix b 2|S| the communication cell necessarily enters some state at least twice. Let ∆ |u|+n-2|S| (ub n , s 0 ĉ0 ) = (b 2|S| , sĉ). Then there are 0 ≤ p 1 , 1 ≤ p 2 with p 1 + p 2 ≤ |S| such that ∆ p1 (b 2|S| , sĉ) = (b 2|S|-p1 , s 1 ĉ1 ) and ∆ p2 (b 2|S|-p1 , s 1 ĉ1 ) = (b 2|S|-p1-p2 , s 1 ĉ2 ). Since the input is accepted, the communication cell enters an accepting state in this state cycle of length p 2 (which cannot be left until the end of the computation) or before. This implies that input ub n-p2 is accepted as well. From the contradiction it follows that there is at least one communication during the last 2|S| time steps.

Altogether we have seen that the communication cell of M necessarily communicates with its neighbor, or vice versa, during the first |S| steps, during the last 2|S| steps, and on the factors a |S| b |S| 2 +|S| and b |S| a |S| 2 +|S| that include the block borders. Since there are i -1 such block borders, in total, there are at least i + 1 communications for n long enough.

Undecidability Results for Realtime MC(const)-IAs

In this section, we first show that the question of emptiness is undecidable for realtime MC(const)-IAs by reduction of Hilbert's tenth problem which is known to be undecidable (see, e.g., [START_REF] Jones | Proof of recursive unsolvability of Hilbert's tenth problem[END_REF][START_REF] Matijasevič | On recursive unsolvability of Hilbert's tenth problem[END_REF]). The problem is to decide whether a given polynomial p(x 1 , . . . , x n ) with integer coefficients has an integral root. That is, to decide whether there are integers α 1 , . . . , α n such that p(α 1 , . . . , α n ) = 0. A reduction of Hilbert's tenth problem to show the undecidability of emptiness for certain two-way counter machines has been used in [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF] for the first time. A recent paper that provides a simulation of counter machines by linear-time one-way cellular automata is [START_REF] Carton | Counter machines and distributed automata: A story about exchanging space and time[END_REF]. The basic idea of Ibarra in [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF] is to define a language that encodes all possible values for x 1 , x 2 , . . . , x n and evaluates the polynomial p for that values. Then, a two-counter machine is constructed accepting that language which is empty if and only if Hilbert's tenth problem has no solution in the integers. Such an approach we will in principal use here again. However, since we are concerned with IAs with constant communication and the input has to pass the communication cell to be processed by the IA, the definition of the language that evaluates the polynomial p is much more involved and will be presented in several steps.

As is remarked in [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF], it is sufficient to restrict the variables x 1 , . . . , x n to take non-negative integers only. If p(x 1 , . . . , x n ) contains a constant summand, then we may assume that it has a negative sign. Otherwise, we continue with p(x 1 , . . . , x n ) multiplied with -1, whose constant summand now has a negative sign and which has the same integral roots as p(x 1 , . . . , x n ). Such a polynomial has the following form:

p(x 1 , . . . , x n ) = t 1 (x 1 , . . . , x n ) + • • • + t r (x 1 , . . . , x n ),
where each t j (x 1 , . . . , x n ), 1 ≤ j ≤ r, is of the form

t j (x 1 , . . . , x n ) = s j x ij,1 1 • • • x ij,n
n with s j = 0 and i j,1 , . . . , i j,n ≥ 0.

Since changing the sequence in which the summands appear does not change the polynomial, we additionally may assume that the summands are ordered according to their sign starting with summands having a positive sign. Moreover, we may assume that a constant term occurs at the end of the sequence only. Thus, t r = s r , if p contains s r as constant. Finally, let i j = n k=1 i j,k . Now, we consider a polynomial p(x 1 , . . . , x n ) with integer coefficients that has the above form. Let t j with 1 ≤ j ≤ r be a positive term. Then, we define language L (t j ) over the alphabet {b 0 , b 1 , . . . , b ij } as

L (t j ) = { b sj 0 b α1 1 • • • b α1 ij,1 b α2 ij,1+1 • • • b α2 ij,1+ij,2 • • • b αn ij,1+•••+ij,n-1+1 • • • b αn ij | α 1 , α 2 , . . . , α n ≥ 0 }.
Similarly, we define languages L (t j ) over {b 0 , b 1 , . . . , b ij , c 1 , . . . , c ij -1 , $} where words of L (t j ) are interleaved with c-blocks and a $-block at the end, respectively, whose number of symbols is the product of the number of symbols of the two preceding blocks. So, the number of $-symbols is an evaluation of t j (α 1 , α 2 , . . . , α n ).

L (t j ) = { b sj 0 b α1 1 c sj α1 1 b α1 2 c sj α 2 1 2 b α1 3 c sj α 3 1 3 • • • b α1 ij,1 c sj α i j,1 1 ij,1 b α2 ij,1+1 c sj α i j,1 1 α2 ij,1+1 • • • b α2 ij,1+ij,2 c sj α i j,1 1 α i j,2 2 ij,1+ij,2 • • • b αn ij -1 c sj α i j,1 1 α i j,2 2 •••α i j,n -1 n ij -1 b αn ij $ sj α i j,1 1 α i j,2 2 •••α i j,n n | α 1 , α 2 , . . . , α n ≥ 0 } Finally, L(t j ) is defined over {b 0 , b 1 , . . . , b ij , c 1 , . . . , c ij -1 , d, $} as L(t j ) = { wd 7|w| | w ∈ L (t j ) }.
If t j with 1 ≤ j ≤ r is a negative and non-constant term, the definition of L(t j ) is identical except for the fact that each symbol $ is replaced by some symbol # and b

sj 0 is replaced by b |sj | 0 . If t r is a constant term, we define L(t r ) = {# |sr| d 7|sr| }. Example 5. Let t j (x 1 , x 2 , x 3 , x 4 ) = 3x 2 1 x 2 x 4 . Then, s j = 3, i j,1 = 2, i j,2 = 1, i j,3 = 0, i j,4 = 1, and i j = 4, L (t j ) = { b 3 0 b α1 1 b α1 2 b α2 3 b α4 4 | α 1 , α 2 , α 4 ≥ 0 } and L (t j ) = { b 3 0 b α1 1 c 3α1 1 b α1 2 c 3α 2 1 2 b α2 3 c 3α 2 1 α2 3 b α4 4 $ 3α 2 1 α2α4 | α 1 , α 2 , α 4 ≥ 0 }. For example, to evaluate t j (2, 3, x 3 , 2) = 3 • 2 2 • 3 • 2 = 72 we consider the word b 3 0 b 2 1 c 6 1 b 2 2 c 12 2 b 3 3 c 36 3 b 2 4 $ 72 d 7•138 ∈ L(t j ) and to evaluate t j (2, 1, x 3 , 2) = 3•2 2 •1•2 = 24 we consider the word b 3 0 b 2 1 c 6 1 b 2 2 c 12 2 b 3 c 12 3 b 2 4 $ 24 d 7•64 ∈ L(t j ).
Let us start our construction with three lemmas that will be essential in the sequel. Lemma 6. An MC(const)-IA can effectively be constructed that shifts an input of the form w ∈ a + b + c + into its cells within 2|w| time steps. Lemma 9. The language L(t j ) belongs to L rt (MC(const)-IA) for each term t j with 1 ≤ j ≤ r.

Proof. We describe the construction of a realtime MC(const)-IA accepting L(t j ), where t j is a positive term. The construction for negative non-constant terms is identical except for exchanging $ by #. If t j is a negative constant term, L(t j ) is a regular language and can be accepted by a realtime MC(const)-IA using its communication cell only.

A realtime MC(const)-IA for L(t j ) basically computes four tasks.

1. Check the correct format of the input and check whether there are exactly s j symbols b 0 . 2. Check whether the length of every c-block is the product of the lengths of its two preceding blocks. The first task can be done by the communication cell which rejects the input in case of a wrong format or a wrong number of b 0 's. For the second task we use the construction described in Lemma 8 multiple times. Having stored the complete input other than the d's in the array, the communication cell sends a signal with maximum speed to the right which starts in the b 0 -block as well as in every c-block an instance of the construction given in Lemma 8 which checks whether the length of every c-block and of the last $-block is the product of the lengths of its two preceding blocks. Whenever an error is encountered an error signal is sent to the left which rejects the input. Since there is only a finite number of c-blocks, we have to keep track of a finite number of instances of the construction of Lemma 8 which in addition are distributed over the array and at most two instances are overlapping. Since one instance can be realized by an MC(const)-IA, we obtain that the finite number of such instances can be realized by an MC(const)-IA as well. It has been shown in Lemma 8 that the total time for one instance is bounded by seven times the length of the input. Hence, we can conclude that, for some input wd * with w ∈ L (t j ), time 7|w| is sufficient to accomplish the second task. This time is provided by the number of d's whose correct number is checked in the third task as follows. The communication cell sends a signal C with speed 1/6 to the right which is reflected at the cell carrying the last $ and is sent back to the left with maximum speed. The third task is successful if and only if C arrives again at the communication cell when the end-of-input symbol is read for the first time.

Finally, we have to accomplish the fourth task. Here, we have to check for every 1 ≤ i ≤ n whether each of a finite number, say n i , of different b-symbols, say {b li , b li+1 , . . . , b li+ni-1 } is exactly α i . This can basically be realized by implementing n i -1 instances of the construction given in Lemma 7. The first instance checks that the number of symbols b li is equal to the number of symbols b li+1 , the second instance checks that the number of symbols b li+1 is equal to the number of symbols b li+2 , and so on. If all checks are positive for every 1 ≤ i ≤ n, the fourth task is accomplished and requires at most t = n i=1 5α i (n i -1) time steps due to Lemma 7. Let wd 7|w| with w ∈ L (t j ) be the input. Then, n i=1 α i (n i -1) is bounded by |w|. Hence, t ≤ 5|w| and the number of d's provided gives enough time to accomplish the fourth task in realtime. Since n and all n i for 1 ≤ i ≤ n are fixed numbers depending on t j , we need only a finite number of instances of the construction given in Lemma 7 each of which can be realized by an MC(const)-IA. Hence, we obtain that the fourth task can be realized by an MC(const)-IA.

Altogether, by implementing the different tasks in parallel in different tracks we obtain a realtime MC(const)-IA which accepts its input if and only if all four tasks have been accomplished successfully.

In Lemma 9 we have described how an evaluation of a term t j can be simulated. Our next step is to simulate an evaluation of the given polynomial p. To this end, we have to put the evaluations of the single terms together. This will be done by concatenating certain regular languages around each language L(t j ). Finally, the intersection of all these sets is considered which leads to an evaluation of all terms on the same input and thus to an evaluation of p.

Let us consider the following regular languages R k depending on the sign of the term t k . We set

R k = b * 0 b * 1 c * 1 . . . b * i k -1 c * i k -1 b * i k $ * d * if s k > 0, R k = # * d * if t k is the negative constant, and R k = b * 0 b * 1 c * 1 . . . b * i k -1 c * i k -1 b * i k # * d * otherwise. Then, we define L(t j ) = { a α1 1 • • • a αn n w 1 w 2 • • • w r | α 1 , . . . , α n ≥ 0, w i ∈ R i , 1 ≤ i ≤ r, i = j, w j = w j d 7|w j | , and w j = b sj 0 b α1 1 c sj α1 1 b α1 2 c sj α 2 1 2 b α1 3 c sj α 3 1 3 • • • b α1 ij,1 c sj α i j,1 1 ij,1 b α2 ij,1+1 c sj α i j,1 1 α2 ij,1+1 • • • b α2 ij,1+ij,2 c sj α i j,1 1 α i j,2 2 ij,1+ij,2 • • • b αn ij -1 c sj α i j,1 1 α i j,2 2 •••α i j,n -1 n ij -1 b αn ij $ sj α i j,1 1 α i j,2 2 •••α i j,n n
} and consider L(p) = r j=1 L(t j ). We can observe that each language L(t j ) consists of the language L(t j ), which evaluates t j (x 1 , x 2 , . . . , x n ), and the concatenation of the regular sets R 1 R 2 • • • R j-1 to the left and R j+1 • • • R r to the right. Additionally, each word of L(t j ) starts with the substring a α1 1 a α2 2 • • • a αn n which determines the variables x 1 , x 2 , . . . , x n to be evaluated. Since L(p) is the intersection over all terms of the polynomial p, L(p) simulates all those terms on the same input α 1 , α 2 , . . . , α n . Thus, L(p) denotes an evaluation of the given polynomial p whereby evaluations of positive and negative terms are encoded by $-symbols and #-symbols, respectively.

Lemma 10. The language L(p) belongs to L rt (MC(const)-IA). Proof. To accept L(p) three checks are performed in parallel. First, it is verified that the prefix w belongs to L(p) using the construction given in Lemma 10, which says in addition that the construction can be realized by an MC(const)-IA in realtime. Second, to check the correct number of e's the communication cell starts in the first time step a signal E 1 with speed 1/2 to the right and starts another signal E 2 when the first e is read with maximum speed to the right. When both signals meet, some signal E 3 is sent back to the left with speed 1/3 and has to arrive at the communication cell when the end-of-input symbol is read for the first time. Clearly, the second task can be done by a realtime MC(const)-IA. The third task is to check the equal number of $-and #-symbols. The basic idea here is to implement again the construction given in Lemma 7. Since the terms of the given polynomial p are ordered with respect to their sign, we know that blocks of $-symbols are followed by blocks of #-symbols. In between these blocks there are blocks of other alphabet symbols which have to be ignored. In a straightforward modification of the constructions given in Lemma 6 and Lemma 7 we first enqueue a finite number of $-blocks in one queue and then a finite number of #-blocks in a different queue. If both queues have an equal length, the third task is accomplished. According to Lemma 6 and Lemma 7 we know that the third task can be done by an MC(const)-IA and needs at most 5|w| time steps. Due to the e-symbols provided the overall length of the input is 5|w| which implies that the third task can be accomplished in realtime.

Altogether, the input is accepted when all three task have successfully been done and we obtain that L(p) is accepted by a realtime MC(const)-IA. Now, all prerequisites are done and we obtain the following undecidability results for realtime MC(const)-IAs.

Theorem 12. Emptiness is undecidable for realtime MC(const)-IAs.

Proof. By applying Lemma 11 we can construct a realtime MC(const)-IA M accepting language L(p) given a polynomial p(x 1 , . . . , x n ). Moreover, the language L(M ) = L(p) is empty if and only if the polynomial p(x 1 , . . . , x n ) has no solution in the non-negative integers Since Hilbert's tenth problem is undecidable, the emptiness problem for realtime MC(const)-IAs is undecidable as well.

Corollary 13. The questions of finiteness, infiniteness, equivalence, and inclusion are undecidable for realtime MC(const)-IAs.

Fig. 1 .

 1 Fig. 1. Initial configuration of an iterative array.

Lemma 7 .

 7 An MC(const)-IA can effectively be constructed that accepts every w ∈ { a n b m c n | n, m ≥ 1 } within 5|w| time steps. Lemma 8. An MC(const)-IA can effectively be constructed that accepts every w ∈ { a n b m c n•m | n, m ≥ 1 } within 7|w| time steps.

3 .

 3 Check whether the number of d's is equal to seven times the length of the preceding input. 4. Check the equal number of symbols b ij,1+•••+i j,k-1 +1 , . . . , b ij,1+•••+i j,k for every 1 ≤ k ≤ n.

Finally, we

  set L(p) = { we 4|w| | w ∈ L(p), |w| $ = |w| # } for some new alphabet symbol e. Lemma 11. The language L(p) belongs to L rt (MC(const)-IA).


Martin Kutrib

Thomas Worsch
email: worsch@kit.edu

Iterative Arrays with Self-Verifying Communication Cell

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.

Introduction

One of the central questions in complexity and language theory asks for the power of nondeterminism in bounded-resource computations. In order to gain a better understanding of nondeterminism 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 [START_REF] Duris | Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations[END_REF]. It applies to automata 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 is in contrast to the general case, where an answer different from yes does not allow to conclude whether or not the input belongs to the language. Here we study the computational capacity of self-verifying iterative arrays (SVIA).

Self-verifying finite automata have been introduced and studied in [START_REF] Duris | Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations[END_REF] and others mainly in connection with randomized Las Vegas computations. Descriptional complexity issues for self-verifying finite automata have been studied in [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF]. The computational and descriptional complexity of self-verifying pushdown automata has been studied in [START_REF] Fernau | Self-verifying pushdown automata[END_REF]. Self-verifying cellular automata have been introduced in [START_REF] Kutrib | Self-verifying cellular automata[END_REF]. Some of the results in the present paper look very similar, but they require different proofs.

The paper is organized as follows. In Section 2 we present the basic notation and the definitions of self-verifying iterative arrays as well as an introductory example. In general, the symmetric conditions for acceptance/rejection of selfverifying devices imply immediately the effective closures of the language families accepted under complementation. In Section 3 this observation is turned in a characterization. Moreover, the strong speed-up by a multiplicative constant is derived for any time-computable time complexity. In Section 4 we explore the computational capacity of realtime SVIAs. In particular, its is shown that even realtime SVIAs are as powerful as lineartime self-verifying cellular automata and vice versa. So they are strictly more powerful than deterministic iterative arrays. Closure properties of the family of languages accepted by realtime SVIAs are studied in Section 5. The family is closed under the Boolean operations, reversal, concatenation, and inverse homomorphisms, while it is not closed under arbitrary homomorphisms. Finally, decidability problems are considered in Section 6. In particular, by a reduction of the emptiness problem it is shown that the property of being self-verifying is non-semidecidable.

Preliminaries and Definitions

We denote the non-negative integers by N. Let Σ denote a finite set of letters. Then we write Σ * for the set of all finite words (strings) consisting of letters from Σ. The empty word is denoted by λ, and Σ + = Σ * \ {λ}. For the reversal of a word w we write w R and |w| denotes its length. A subset of Σ * is called a language over Σ. In general, we use ⊆ for inclusions and ⊂ for strict inclusions.

A one-dimensional iterative array is a linear, semi-infinite array of finite state machines (sometimes called cells) that are identical except for the leftmost one. All but the leftmost cells are connected to their both nearest neighbors, respectively (see Figure 1). For convenience we identify the cells by their coordinates, that is, by non-negative integers. The leftmost cell is distinguished. This socalled communication cell is connected to its right neighbor and, additionally, to the input supply which feeds the input sequentially. We assume that once the whole input is consumed an end-of-input symbol is supplied permanently. At the outset of a computation all cells are in the so-called quiescent state. The cells work synchronously at discrete time steps. Here we assume that the communication cell is a nondeterministic finite automaton while all the other cells are deterministic ones (cf. [START_REF] Buchholz | Iterative arrays with limited nondeterministic communication cell[END_REF]). Although this is a very restricted case, for easier writing we call such devices nondeterministic.

Formally, a nondeterministic iterative array (NIA, for short) is a system M = S, Σ, F + , s 0 , , δ nd , δ d , where S is the finite, nonempty set of cell states, Σ is the finite, nonempty set of input symbols, F + ⊆ S is the set of accepting states, s 0 ∈ S is the quiescent state, / ∈ Σ is the end-of-input symbol, δ nd : (Σ ∪ { }) × S × S → (2 S \ ∅) is the nondeterministic local transition function for the communication cell, δ d : S × S × S → S is the deterministic local transition function for non-communication cells satisfying δ d (s 0 , s 0 , s 0 ) = s 0 .

A configuration of M at time t ≥ 0 is a pair (w t , c t ), where w t ∈ Σ * is the remaining input sequence and c t : N → S is a mapping that maps the single cells to their current states. The initial configuration (w 0 , c 0 ) is defined by the given input w 0 ∈ Σ * and the mapping c 0 (i) = s 0 , i ≥ 0. Subsequent configurations are computed by the global transition function ∆ that is induced by δ d and δ nd as follows: Let (w t , c t ), t ≥ 0, be a configuration. Then the set of its possible successor configurations (w t+1 , c t+1 ) is defined as follows:

(w t+1 , c t+1 ) ∈ ∆((w t , c t )) ⇐⇒ c t+1 (0) ∈ δ nd (a, c t (0), c t (1)) c t+1 (i) = δ d (c t (i -1), c t (i), c t (i + 1))
for all i ≥ 1, where a = , w t+1 = λ if w t = λ, and a = a 1 ,

w t+1 = a 2 a 3 • • • a n if w t = a 1 a 2 • • • a n .
An input w is accepted by an NIA M if at some time step during the course of at least one computation for w the communication cell enters an accepting state. The language accepted by M is denoted by L(M ) = { w ∈ Σ * | w is accepted by M }. Let t : N → N, t(n) ≥ n + 1 be a mapping. If for each w ∈ L(M ) there is an accepting computation with at most t(|w|) time steps, then M and L(M ) are said to be of time complexity t.

In general, the family of all languages which are accepted by some type of device X with time complexity t is denoted by L t (X). If t is the function n + 1, acceptance is said to be in realtime. Since for nontrivial computations an iterative array has to read at least one end-of-input symbol, realtime has to be defined as (n + 1)-time. We write L rt (X) for realtime and L lt (X) for lineartime. Now we turn to self-verifying iterative arrays (SVIA). Basically, an SVIA is an NIA, but the definition of acceptance is different. There are now three disjoint sets of states representing answers yes, no, and neutral. Moreover, 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. In order to implement the three possible answers the state set is partitioned into three disjoint subsets S = F + ∪ F -∪ F 0 , where F + is the set of accepting states, F -is the set of rejecting states, and F 0 = S (F + ∪ F -) is referred to as the set of neutral states. If M = S, Σ, F + , F -, s 0 , , δ nd , δ d is an SVIA, for each input word w ∈ Σ * and for a corresponding computation c let S w,c denote the set of states entered by the communication cell during computation c. For the "self-verifying property" it is required that for each w ∈ Σ * and each corresponding c, S w,c ∩F + is empty if and only if S w,c ∩ F -is nonempty. If all w ∈ L(M ) are accepted and all w / ∈ L(M ) are rejected after at most t(|w|) time steps, then the self-verifying iterative array M is said to be of time complexity t.

a 1 a 2 • • • a n s 0 s 0 s 0 s 0 s 0
In the sequel we will often utilize the possibility of iterative arrays to simulate the data structures pushdown stores (stacks) [START_REF] Buchholz | Some relations between massively parallel arrays[END_REF][START_REF] Čulik | Iterative tree automata[END_REF], queues, and rings [START_REF] Kutrib | Cellular automata -a computational point of view[END_REF] without any loss of time. Here a ring is a queue that can write and erase at the same time. For pushdown stores the communication cell simulates the top of the store, for queues it simulates the front, and for rings the front and the end of the store.

We illustrate the definitions with an example.

Example 1. The nondeterministic context-free language { w ∈ {a, b} * | w = w R } is accepted by the SVIA M = S, {a, b}, F + , F -, s 0 , , δ nd , δ d . The basic idea is to simulate a stack whose top is the communication cell.

We set S = ({s 1 , s 2 , s 3 , s + , s -, s ? } × S pd ) ∪ {s 0 } ∪ Ŝpd with F + = {s + } × S pd and F -= {s -} × S pd . Here S pd are the register contents used by the communication cell to manage the top entries of the stack, while Ŝpd are the non-quiescent states of all but the communication cell, that realize the stack. So, the transition function δ d just realizes the interior of the stack and is omitted here.

The idea of the construction of δ nd is summarized in the following table and described below. Since we didn't make S pd explicit in detail and since the state of the right neighbor of the communicating cell is only needed for updating its part of the stack, the right neighbor state is left out in the table. The current state of the communication cell is indicated as (s i , y•••) meaning that at the top of the stack is a symbol y ∈ {a, b}. A transition to xy••• means that x has been pushed onto, and a transition to ••• means that y has been popped from the stack.

(1) δ nd ( , (s 0 , ⊥),

) (s + , ⊥) accept λ (2) δ nd (x, (s 0 , ⊥), ) (s 1 , x) push first symbol (3) δ nd (x, (s 1 , y•••), ) (s 1 , xy•••) in s 1 continue pushing input symbols (4) δ nd (x, (s 1 , y•••), ) (s 2 , y•••) switch to s 2 , dropping symbol x (5) δ nd (x, (s 1 , y•••), ) (s 2 , xy•••) switch to s 2 , without dropping x (6) δ nd (x, (s 2 , x•••), ) (s 2 , •••) continue in s 2 for matching symbols (7) δ nd ( , (s 2 , ⊥), ) (s + , ⊥) accept if everything matched (8) δ nd (x, (s 2 , x•••), ) (s 3 , •••) switch to s 3 if mismatch (ā = b, b = a) (9) δ nd (x, (s 3 , y•••), ) (s 3 , •••) drop remaining input symbols (10) δ nd ( , (s 3 , ⊥), ) (s -, ⊥)
reject since there was a mismatch Consider the point in time after the SVIA is in state s 2 for the first time. Let v denote the part of the input that has been pushed to the stack at that time and let u denote the part of the input that still has not been read. Then the input is vxu if (4) has been used to switch to s 2 and the input is vu if (5) was used.

If the communication cell switched from s 1 to s 2 "at the right time", that is |u| = |v|, then it will for the first time see input and the empty stack ⊥ simultaneously. Obviously, the decision to accept using [START_REF] Fernau | Self-verifying pushdown automata[END_REF] or to reject using [START_REF] Kutrib | Cellular automata and language theory[END_REF] is the correct one.

If the communication cell switched from s 1 to s 2 "at the wrong time", that is |u| = |v|, then it cannot decide whether the input is a palindrome. This can be recognized by the SVIA since either all input symbols have been consumed but the stack is not empty or the stack is empty but not all input symbols have been consumed. In this case a correct behavior is obtained by entering state s ? and rules that make the SVIA never leave it again.

Structural Properties and Speed-Up

Though we are mainly interested in fast computations, that is, realtime and lineartime computations, we allowed general time complexities in the definition of the devices (see [START_REF] Kutrib | Cellular automata and language theory[END_REF] for a discussion of this general treatment of time complexity functions). However, it seems to be reasonable to consider only time complexities t that allow the communication cell to recognize the time step t(n). Such functions are said to be time-computable. For example, the function t(n) = n + 1 is trivially a time-computable time complexity for IAs.

Other examples are time complexities y x • n , for any positive integers x < y, polynomials t(n) = n k , and exponential time complexities t(n) = k n , for any integer k ≥ 2. More details can be found in [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF].

In general, the symmetric conditions for acceptance/rejection of self-verifying devices imply immediately the effective closures of the language families accepted under complementation. In order to turn this observation in a characterization, we first give evidence that self-verifying iterative arrays are in fact a generalization of deterministic iterative arrays. The proof of a corresponding result for cellular automata [START_REF] Kutrib | Self-verifying cellular automata[END_REF] applies here almost literally.

Lemma 2. Any deterministic iterative array with a time-computable time complexity t can effectively be converted into an equivalent self-verifying iterative array with the same time complexity t.

The proper inclusion L rt (IA) ⊂ L rt (NIA) is well known [START_REF] Buchholz | Iterative arrays with limited nondeterministic communication cell[END_REF]. So, nondeterminism strengthens the computational capacity of iterative arrays. On the other hand, it is an open problem whether the family L rt (NIA) is closed under complementation. Therefore, the question whether the family L rt (SVIA) is properly included in L rt (NIA), or whether both families coincide, is of natural interest. Next we turn to relate it to the open complementation closure of L rt (NIA). Proposition 3. Let t be a time-computable time complexity. The family of languages L ∈ L t (NIA), such that the complement L belongs to L t (NIA) as well, coincides with the family L t (SVIA).

Proof. Given a t-time SVIA M , it is straightforward to construct an NIA that accepts the complement of L(M ) with the same time complexity t.

Conversely, let M 1 be an NIA accepting L and M 2 be an NIA accepting L with time complexity t. Now a t-time self-verifying iterative array M simulates M 1 and M 2 on different tracks, that is, it uses the same two channel technique of [START_REF] Dyer | One-way bounded cellular automata[END_REF][START_REF] Smith | Real-time language recognition by one-dimensional cellular automata[END_REF].

Then it remains to define the set of accepting states as Next, we turn to strong speed-up results for self-verifying iterative arrays from which follows that realtime is as powerful as lineartime.

F + = { (s, s ) | s ∈ F 1 } and the set of rejecting states as F -= { (s, s ) | s ∈ F 2 },
Theorem 4. Let k ≥ 1 be a constant and t be a time complexity. Then the families L k•t (SVIA) and L t (SVIA) coincide.

Proof. A given (k • t)-time SVIA M is simulated by a t-time SVIA M as follows. Basically, M performs two tasks in parallel on different tracks.

For the first task, assume that the input is fed to the communication cell of M in k-symbol blocks, that is, k input symbols in each step. Then each k cells of M are grouped together into one cell. In this well-known way the iterative array M can simulate k steps of M in one step. That is, this task of M has time complexity t and the self-verifying property, since M has time complexity k • t and the self-verifying property.

The second task of M is to make the assumption for the first task true. To this end, it simulates a ring store whose front (and end) is the communication cell. Now the communication cell starts to guess k input symbols in every step. These symbols are fed to the first task. Additionally, the communication step guesses when the end-of-input symbol appears. From that time step on no further input symbols are guessed. In order to verify that the guesses are correct, the k symbols are entered at the end of the ring store respectively. In each step, the symbol at the front of the ring is removed and compared with the actual input symbol. If both match, the guessed symbol is correct, otherwise it is not. In case of a mismatch or a wrongly guessed number of input symbols the second task remains in a neutral state. If it has guessed the input correctly, it enters a positive state.

Finally, M accepts if and only if the second task guesses the input correctly and the first task accepts. That is, if the actual input is accepted by M . The iterative array M rejects if and only if the second task guesses the input correctly and the first task rejects. That is, if the actual input is rejected by M . So, M has the self-verifying property.

Corollary 5. The families L rt (SVIA) and L lt (SVIA) coincide.

Computational Capacity

The first question in connection with the computational capacity of realtime SVIA is the impact of the (restricted) nondeterminism. Does it increase the capacity? More precisely, we are interested in the question whether the computing power of realtime SVIA is strictly stronger than that of realtime IA.

Example 1 shows that the mirror language is accepted by a realtime SVIA. However, by using a completely different algorithm the language is accepted by some deterministic realtime IA as well [START_REF] Cole | Real-time computation by n-dimensional iterative arrays of finite-state machines[END_REF]. So, it cannot be used as a witness for the strictness of the inclusion L rt (IA) ⊂ L rt (SVIA). Nevertheless, the strictness follows from a more general result below and is stated in Proposition 10. Corollary 6. The family of languages accepted by self-verifying pushdown automata is strictly included in the family L rt (SVIA).

In order to discuss further comparisons we now turn to results that show the strong computational capacity of realtime SVIA.

While iterative arrays fetch their input sequentially through the communication cell, so-called cellular automata obey a parallel input mode. In a preinitial step their cells fetch an input symbol. That is, there are as many cells as input symbols. So, a two-way cellular automaton (CA) is a linear array of identical finite automata which are numbered 1, 2, . . . , n. Except for border cells the state transition depends on the current state of a cell itself and those of its both nearest neighbors. Border cells receive a boundary symbol # on their free input lines. An input w is accepted by a cellular automaton if at some time step during some computation the leftmost cell enters an accepting state. For cellular automata, realtime is defined to be t(n) = n. Cellular automata whose first state transitions are nondeterministic, whose further transitions are deterministic, and that have the self-verifying property (SVCA) are studied in [START_REF] Kutrib | Self-verifying cellular automata[END_REF]. Lemma 7. The family L lt (SVIA) is included in L rt (SVCA). Lemma 7 gives an upper bound for languages accepted by lineartime SVIA. It shows that a sequential input mode and one nondeterministic cell can be traded for parallel input mode and all cells nondeterministic once only. In fact, the upper bound is sharp, that is, the converse is also true.

Lemma 8. The family L lt (SVCA) is included in L rt (SVIA).
Proof. The possibility to speed-up SVCAs by a constant factor is shown in [START_REF] Kutrib | Self-verifying cellular automata[END_REF]. That is, L lt (SVCA) = L rt (SVCA). So, given some realtime SVCA M with state set S and set of input symbols Σ, we construct an equivalent realtime SVIA M as follows. Basically, M works in three phases. First it guesses and generates a configuration that represents the fourfold packed initial configuration of M . Then this packed part is synchronized. Finally, the synchronized cells simulate M whereby four steps are simulated in one step. The phases are depicted in Figure 2. In parallel, the guesses are verified. Phase 1: Let n denote the length of the input. In the following we assume that n + 1 is a multiple of four. The generalization of the simulation to the other cases is a straightforward adaption.

So, during the first n+1 4 time steps the communication cell of M guesses four input symbols in every step. Additionally, the communication cell guesses a mapping (Σ ∪ {#}) × {a} × (Σ ∪ {#}) → S for each (guessed) input symbol a ∈ Σ. These mappings are used for the simulation of the nondeterministic first transitions of the cells of M . The blocks of four input symbols together with the corresponding mappings are shifted to the right such that each of the leftmost n+1 4 cells gets one block of symbols and mappings. When the communication cell guesses the end-of-input symbol the first phase ends.

In order to verify that the guesses are correct, the four symbols are entered at the end of a ring store respectively. In each step, the symbol at the front of the ring is removed and compared with the actual input symbol. If both match, the guessed symbol is correct, otherwise it is not. In case of a mismatch or a wrongly guessed number of input symbols the computation blocks in a neutral state.

Phase 2: At time step n+1 4 + 1 the communication cell initiates an FSSP synchronization of the leftmost n 4 cells. The blocks of four input symbols together with the corresponding mappings arrive at their destination cells 0 ≤ i ≤ n+1

4 -1 at time 2i+1. The initial signal for the FSSP arrives at cell i at time n+1 4 +1+i > 2i + 1. So, each cell starts Phase 2 after finishing Phase 1. Altogether, Phase 2 is finished when all cells are synchronized at time n+1

4 + 1 + 2 • n+1 4 -2 = 3 • n+1 4 -1.
Phase 3: Due to the compressed representation, M can simulate M with fourfold speed. In order to simulate the nondeterministic transitions which the cells of M perform during the first time step, the cells of M apply the nondeterministically guessed mappings to its local configurations. Thus, M simulates the nth step of M at time step 3

• n+1 4 -1 + n+1 4 = n.
Since the verification of the guessed input takes n + 1 time steps, we conclude that the total time complexity of M is t(n) = n + 1, that is realtime.

Finally, M accepts if and only if the input has been guessed correctly and M accepts, and it rejects if and only the input has been guessed correctly and M rejects. Since M has the self-verifying property, M is self-verifying as well. So, we have L(M ) = L(M ).

Lemma 7 and Lemma 8 reveal the equality of the next theorem.

Theorem 9. L lt (SVCA) = L rt (SVCA) = L rt (SVIA) = L lt (SVIA).
In particular, now we can deduce that even the restricted nondeterminism gained in considering a self-verifying communication cell strictly increases the computational capacity of realtime iterative arrays. That is, the inclusion L rt (IA) ⊂ L rt (SVIA) is strict.

Proposition 10. The family L rt (IA) is strictly included in L rt (SVIA).

Proof. The relations L rt (IA) ⊂ L lt (IA) = L lt (CA) are known (see, for example, [START_REF] Kutrib | Cellular automata and language theory[END_REF]). Since L lt (IA) ⊆ L lt (SVIA) the assertion follows.

Theorem 9 shows that a sequential input mode and one nondeterministic cell can be traded for parallel input mode and all cells nondeterministic once only, and vice versa. To this end, it does not matter whether the computations are in realtime or lineartime. But what about the world beyond lineartime? Are self-verifying arrays stronger than deterministic ones? Or weaker than nondeterministic ones? The open question of the strictness of one of the inclusions L lt (IA) ⊆ L rt (SVIA) ⊆ L (SVCA) ⊆ L (NCA) is strongly related to famous open problems in complexity theory (see [START_REF] Kutrib | Complexity of one-way cellular automata[END_REF]). Note that at the top of this hierarchy are devices that may have an exponential time complexity (due to the space bound).

Closure Properties

Here we turn to explore the closure properties of the family of realtime SVIA languages. They are summarized in Table 1. We start with the Boolean operations.

Proposition 11. The family of languages accepted by realtime SVIA is closed under complementation, union, and intersection.

The closure under reversal is of crucial importance. It is an open problem for L rt (CA) and, equivalently, for L lt (OCA) (OCAs are CAs where information can only be passed from right to left, that is, the new state of a cell does not depend on that of its left neighbor). Moreover, it is linked with the open closure property under concatenation for the same family and, hence, with the question whether lineartime CAs are more powerful than realtime CAs. It is known that the family L rt (IA) is not closed under reversal, while the family L lt (IA) is closed. marked by the simulation of M 1 and symbol y i+1 is marked by the simulation of M R 2 . Case 1:

x 1 • • • x n ∈ L 1 L 2 , say x 1 • • • x i ∈ L 1 .
Then there are computations by

M 1 accepting x 1 • • • x i and by M R 2 accepting y n y n-1 • • • y i+1 = x n x n-1 • • • x i+1 = (x i+1 • • • x n ) R . Having M accept an input iff x i is marked by M 1 and symbol y i+1 is marked by M R 2 makes M accept all words in L 1 L 2 . Case 2: x 1 • • • x n / ∈ L 1 L 2 . In this case for each i either x 1 • • • x i / ∈ L 1 or x n • • • x i+1 / ∈ L R 2
or both. That means that for each i there are computations by M 1 and M R 2 for the respective inputs such that at least one of both rejects. Hence, there will be a computation for M which correctly explicitly rejects an input, if for any two adjacent cells always at least one of them is marked rejecting.

In any other case, the leftmost cell remains in a neutral state.

For the computation on input of length n the SVIA M takes n + 1 steps to read (and guess) the input for the tasks, and further n + 1 steps to verify the guesses and test the markings. So, M works in lineartime which ca be sped-up to realtime.

Next, we turn to the operations homomorphism and inverse homomorphism. Proposition 14. The family of languages accepted by realtime SVIA is not closed under arbitrary homomorphisms.

Proof. It is shown in [START_REF] Kutrib | Self-verifying cellular automata[END_REF] that every recursively enumerable language would be contained in the family L rt (SVOCA) if the family were closed under arbitrary homomorphisms. Since L rt (SVOCA) ⊆ L rt (SVCA) = L rt (SVIA) the same is true for the family L rt (SVIA), a contradiction due to the time bound.

Proposition 15. The family of languages accepted by realtime SVIA is closed under inverse homomorphisms.

The closure properties of L rt (SVIA) with respect to iteration (Kleene star) and non-erasing homomorphisms are open problems. They are settled for nondeterministic devices since, basically, for iteration it is sufficient to guess the positions in the input at which words are concatenated, and for non-erasing homomorphism it is sufficient to guess the pre-image of the input. However, self-verifying devices have to reject explicitly if the input does not belong to the language. Intuitively, this means that they have to 'know' that all possible guesses either do not lead to accepting computations or are 'wrong.'

Decidability Questions

First we note that the membership problem is obviously decidable for SVIAs obeying a time-computable time complexity.

On the other hand, in [START_REF] Kutrib | Cellular automata and language theory[END_REF] it is observed that for any language family that effectively contains L rt (IA), the problems emptiness, universality, finiteness, infiniteness, regularity, and context-freeness are not semidecidable. Since we know L rt (IA) ⊂ L lt (IA) ⊆ L lt (SVIA) = L rt (SVIA) we derive the next corollary.

Family ∪ ∩ R • * h λ h h -1
Lrt(SVIA) ? ? Lrt(IA) L lt (IA) ? ? ?

Table 1. Closure properties of the language family Lrt(SVIA) in comparison with the families Lrt(IA) and L lt (IA), where h λ denotes λ-free homomorphisms.

Corollary 16. The problems emptiness, universality, finiteness, infiniteness, inclusion, equivalence, regularity, and context-freeness are not semidecidable for realtime IAs and thus for realtime SVIAs.

In [START_REF] Kutrib | Self-verifying cellular automata[END_REF] it is shown that the problem to decide whether a given realtime oneway cellular automaton is self-verifying or not is undecidable. Unfortunately, the result has no direct implications for the same question for iterative arrays. However, the undecidability for cellular automata is shown by a reduction of the emptiness problem. We turn to prove the undecidability for iterative arrays as well. Moreover, we use a reduction of the emptiness and universality problem, but the reduction itself is different. Since general iterative arrays do not have neutral or rejecting states (only accepting and non-accepting states), there is no partitioning of the state set. So, the decidability can be asked for a given fixed partitioning or for the existence of a partitioning. We first consider the latter question.

Theorem 17. Given a realtime (non)deterministic iterative array M with state set S and accepting states F + , it is not even semidecidable whether there exists F -⊆ (S \ F + ) such that M is an SVIA with respect to the sets F + and F -.

Proof. Let M 0 = S, Σ, F + , s 0 , , δ nd , δ d be an arbitrary realtime IA. We safely may assume that a cell which has left the quiescent state will never enter the quiescent state again. This behavior can be implemented by adding a new state that plays the role of the quiescent state. If necessary, the new state can be entered instead of s 0 .

We modify M 0 to M 1 = S , Σ , F + , s 0 , , δ nd , δ d by adding a new input symbol $ and two new states p + and p 0 . So, we set S = S ∪ {p + , p 0 }, Σ = Σ ∪ {$}, and F + = F + ∪ {p + }. The intention is that a $ in the input causes the IA to simulate a step on the end-of-input symbol (in restricted form) and to reinitialize the computation by letting the cells enter the quiescent state again (which is impossible in M 1 ). Therefore, the transition function δ nd is basically δ nd extended by transitions for the input symbol $ and the states p + and p 0 . When a $ appears in the input, the communication cell enters state p + if it could enter an accepting state on the end-of-input symbol . For all s 1 , s 2 ∈ S,

δ nd ($, s 1 , s 2 ) = {p + } if δ nd ( , s 1 , s 2 ) ∩ F + = ∅.
Otherwise it enters state p 0 : δ nd ($, s 1 , s 2 ) = {p 0 } if δ nd ( , s 1 , s 2 ) ∩ F + = ∅. In state p + or p 0 the computation continues as it would from the very beginning. For p ∈ {p + , p 0 }, all a ∈ Σ ∪ { }, and all s ∈ S , δ nd (a, p, s) = δ nd (a, s 0 , s 0 ). In order to implement the reinitialization of the other cells, recall that δ d drives no non-quiescent cell into the quiescent state. So, we can utilize the quiescent state as a signal sent by the communication cell. The signal causes the reinitialization of the cells passed through. So, the transition function δ d is basically δ d extended as follows. For p ∈ {p + , p 0 } and all s 1 , s 2 ∈ S,

δ d (p, s 1 , s 2 ) = s 0 , δ d (s 0 , s 1 , s 2 ) = s 0 , δ d (s 1 , s 0 , s 2 ) = δ(s 1 , s 0 , s 0 ).
Therefore L(M 1 ) consists of all concatenations of $ separated words u i such that at least one u i is in L(M 0 ). In particular L(M 1 ) ∩ Σ * = L(M 0 ).

We claim that there exists F -⊆ (S \ F + ) such that the iterative array M 2 = S , Σ , F + , F -, s 0 , , δ nd , δ d is self-verifying if and only if L(M 0 ) is empty or coincides with Σ * . Observe that L(M 2 ) = L(M 1 ) because both have the same set of accepting states.

If L(M 0 ) is empty then L(M 1 ) is empty. Therefore, the communication cell will never enter an accepting state from F + . So, we safely may set F -= (S \F + ) and obtain that M 2 is self-verifying. Similarly, if L(M 0 ) = Σ * then L(M 1 ) = Σ * , and we safely may set F -= ∅ to obtain a self-verifying IA. Now assume that L(M 0 ) and, thus, L(M 2 ) neither be empty nor contain all words over the input alphabet. Then there exists some u ∈ L(M 0 ) and some v / ∈ L(M 0 ). We consider the computation of M 2 on input u$v. Since M 0 accepts u, the IA M 2 enters an accepting state while processing the input prefix u$ (its computation is a simulation of M 0 on u ). Then the computation of M 2 is reinitialized and continues with a simulation of M 0 on input v. Since v / ∈ L(M 0 ), in this phase, M 2 cannot accept v either. However, since it already was in an accepting state and its overall answer is already yes, M 2 cannot enter a contradictory rejecting state in this phase either. This implies that the communication cell of M 2 on input v will only assume neutral states and, thus, neither accept nor reject v. That is, M 2 is not self-verifying and the claim follows.

From the construction of M 2 and the claim we conclude that the semidecidability of the problem in question implies the semidecidability of the emptiness or universality problem for realtime IAs contradicting Corollary 16.

What about the undecidability if we provide a partitioning of its state set? Can we test if this partitioning makes the IA self-verifying? The answer is no, since for a given realtime iterative array with accepting state set F + there are only finitely many partitions induced by setting F -⊆ (S \ F + ). All these could be tested in parallel. Now the problem in question can be semidecided if the test is successful for at least one partitioning.

Corollary 18. Given a realtime (non)deterministic iterative array M with state set S and partitioning S = F + ∪F -∪F 0 , it is not semidecidable whether M is an SVIA with respect to the partitioning.

By Lemma 2 any deterministic iterative with a time-computable time complexity can effectively be made self-verifying. But it is non-semidecidable whether it already is self-verifying. This non-semidecidability carries immediately over to nondeterministic iterative arrays. However, it is an open problem whether any nondeterministic iterative with a time-computable time complexity can effectively be made self-verifying. In fact, it is an open problem whether the family of languages accepted by realtime nondeterministic iterative arrays is closed under complementation or not.

Fig. 1 .

 1 Fig. 1. Initial configuration of an iterative array.

Fig. 2 .

 2 Fig. 2. Simulation phases.

  where F 1 is the set of accepting states of M 1 and F 2 is the set of accepting states of M 2 .Proposition 3 implies that L rt (SVIA) is properly included in L rt (NIA) if and only if L rt (NIA) is not closed under complementation; otherwise both families coincide.

Proposition 12. The family of languages accepted by realtime SVIA is closed under reversal.

Proof. Given some realtime SVIA M , Theorem 9 says that there is an equivalent lineartime SVCA M with transition functions δ nd and δ d . Now, the arguments of the local transition functions are interchanged. That is, δ d (s 3 , s 2 , s 1 ) is defined to be δ d (s 1 , s 2 , s 3 ), and δ nd (s 3 , s 2 , s 1 ) is defined to be δ nd (s 1 , s 2 , s 3 ). The resulting device M with transition functions δ nd and δ d . accepts the reversal L(M ) R at the rightmost cell. Then the result is sent as a signal to the leftmost cell. Altogether, M is still a lineartime SVCA and, thus,

Proposition 13. The family of languages accepted by realtime SVIA is closed under concatenation.

Proof. Let L 1 , L 2 ∈ L rt (SVIA). If the empty word belongs to L 1 then language L 2 belongs to the concatenation and vice versa. Since the family of languages accepted by realtime SVIA is closed under union, it remains to consider languages L 1 , L 2 ∈ L rt (SVIA) that do not contain the empty word. Let M 1 and M 2 be realtime SVIA that accept L 1 and L 2 .

Since the family L rt (SVIA) is closed under reversal, there is a realtime SVIA M R 2 that accepts the reversal L R 2 of L 2 . A realtime SVIA M that accepts the concatenation L 1 • L 2 works as follows. First we describe two tasks that are performed by M in parallel.

Basically, the first task is to read the input and to simulate M 1 . In addition, the input is stored into a ring whose front is the communication cell. Moreover, in any simulation step, M tests whether it would accept or reject the input prefix read so far by checking if it would accept or reject when the next input symbol were the end-of-input symbol . If the current input prefix is accepted or rejected, the input symbol stored into the ring is marked suitably.

The second task is to guess the reversal of the input symbol by symbol. The guessed reversal is stored into a pushdown store whose top is the communication cell. Additionally, the realtime SVIA M R 2 is simulated on the guessed input. Similarly as for the first task, if the current prefix of the guessed input would be accepted or rejected, the guessed input symbol stored into the pushdown store is marked suitably.

Let x 1 x 2 • • • x n be the actual input. It is stored in the ring when the endof-input symbol appears. At that time, let y 1 y 2 • y n be the content of the pushdown store (from top to bottom). Clearly, M has guessed the reversal of the input correctly if and only if

So, after having read the end-of-input symbol, the SVIA M verifies the guessed reversal of the input by successively removing symbols from the ring and pushdown store and testing whether they match. If M detects any mismatch it blocks in a neutral state. Now, assume that the reversal of the input has been guessed correctly.

Already while verifying the guesses by successively scanning the ring and the queue, the SVIA M tests whether for some 1 ≤ i ≤ n -1 input symbol x i is