Acta Informatica (2015) 52:593–623 DOI 10.1007/s00236-015-0230-5 ORIGINAL ARTICLE

Deterministic ordered restarting automata for picture languages Friedrich Otto1 · František Mráz2

Received: 26 June 2014 / Accepted: 9 April 2015 / Published online: 28 April 2015 © Springer-Verlag Berlin Heidelberg 2015

Abstract The ordered restarting automaton (processing strings) is introduced, and it is shown that its nondeterministic variant is very expressive, as it accepts some languages that are not even context-free, while the deterministic ordered restarting automata just accept the regular languages. Then three different extensions of the deterministic ordered restarting automaton to two-dimensional inputs are defined that differ in the way in which they can move their read/write windows. We compare the classes of picture languages that these types of automata accept to each other and to some well studied classes of picture languages from the literature, and we present some closure and non-closure properties for them. Mathematics Subject Classification

68 Q 45

1 Introduction Already in the 1960s the notions of grammars and automata have been carried over from one-dimensional objects, that is, strings, to two-dimensional objects, that is, pictures [4, 28,29], and in the years since, many more analytical and generative methods have been

František Mráz was supported by the Grant Agency of the Czech Republic under the project 15-04960S. Some of the results of this paper have been announced at the 40-th International Conference on Current Trends in Theory and Practise of Computer Science (SOFSEM 2014) at Nový Smokovec, Slovakia, January 2014, and at the 8-th International Conference on Language and Automata Theory and Applications (LATA 2014) at Madrid, Spain, March 2014. Extended abstracts appeared in the proceedings of these conferences [17,18].

B

Friedrich Otto [email protected] František Mráz [email protected]

1

Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany

2

Faculty of Mathematics and Physics, Department of Computer Science, Charles University, 118 00 Praha 1, Czech Republic

123

594

F. Otto, F. Mráz

proposed for describing picture languages (see, e.g., [7]). One of the major concerns has been the quest for a class of picture languages that could rightfully be considered as the two-dimensional equivalent of the class REG of regular (string) languages. Eventually, a kind of agreement has been reached that the class REC of recognizable picture languages of Giammarresi and Restivo [6] is such a class. Unfortunately, this class contains some NP-complete languages [14], which means that in general the membership problem for a recognizable picture language can be quite complex. Motivated by this observation, the current authors started a research program in cooperation with Daniel Pr˚uša that aims at deriving a class of two-dimensional automata that satisfy all of the following conditions: – the automata should be conceptually simple, that is, it should be ‘easy’ to design automata of this type for interesting example languages; – they should at least accept all languages from the class DREC of deterministically recognizable picture languages [1,3], but, as still another generalization of the regular languages to two dimensions, this model should only accept the regular languages when restricted to the one-dimensional case (that is, strings); – the membership problem for the accepted languages should be decidable in polynomial time; – and the class of accepted picture languages should have nice closure properties. As a first such model, the Sgraffito automaton was introduced and studied [24,26,27]. The nondeterministic Sgraffito automaton is too powerful, as it accepts all recognizable picture languages, but the deterministic Sgraffito automaton meets most of these properties, and it is more expressive than the four-way alternating automaton [13] and the deterministic four-way one-marker automaton [4], and it accepts the sudoku-deterministically recognizable picture languages [5]. As the restarting automaton, which was introduced in [11] as a formal device to model the linguistic technique of analysis by reduction, is a fairly intuitive model, it is only natural to look for two-dimensional extensions of it. However, it is required in general that each rewrite step of a restarting automaton is strictly length-reducing, a requirement that is not easily carried over to the two-dimensional setting. H. Messerschmidt and M. Stommel have studied a corresponding model in [16], in which each rewrite step consists in an application of a replacement rule that is then followed by a consolidation step that transforms the result of the replacement into a proper picture. This model is technically quite involved and not very intuitive, but it may have practical applications (see [16]). Following a different approach, Mráz and Pr˚uša [23,25] extended the restarting automaton to the restarting tiling automaton, which is a stateless device with a two-by-two window. In each cycle it scans the current picture based on a given scanning strategy until, at some place, it performs a rewrite step, which replaces a single symbol by some symbol of less weight, and restarts. If no rewrite operation can be performed, then the automaton halts after scanning the current picture completely. It is said to accept if at that point the current picture satisfies certain local conditions, similar to a tiling automaton (see, e.g., [2]). Here we introduce and study three types of deterministic two-dimensional restarting automata that work more in the spirit of the restarting automaton as introduced in [11]. All these automata have a window of size 3-by-3, and they scan a given rectangular input picture starting at the top left corner. Based on the current state and the content of the window, such an automaton changes its state and moves its window, where the various types of automata differ in the movements allowed. It keeps on moving until it either halts, accepting or rejecting, or until it performs a rewrite step, in which it replaces the symbol in the middle

123

Deterministic ordered restarting automata for picture…

595

of its window by a symbol that is strictly smaller with respect to a given ordering on its tape alphabet. After performing such a rewrite, the automaton restarts immediately, that is, it jumps back to the top left corner, and its internal state is reset to the initial state. The different types of two-dimensional automata are all based on the same onedimensional model, the deterministic ordered restarting automaton. An ordered restarting automaton (an ORWW-automaton) has a window of size three that it uses to scan a given input string from left to right. It is equipped with a partial ordering > on its tape alphabet, and it is required that in each rewrite operation, the symbol in the middle position of the window is replaced by a symbol that is strictly smaller with respect to that ordering. In addition, the automaton restarts immediately after executing a rewrite operation, that is, it can be seen as a variant of the RWW-automaton (see, e.g., [19]). The nondeterministic variant of the ORWW-automaton is quite powerful, as it accepts some languages that are not even contextfree, while the deterministic ordered restarting automaton (the det-ORWW-automaton) can be simulated by a Hennie machine [8] implying that it can only accept the regular languages. The various types of two-dimensional ORWW-automata considered are obtained from the det-ORWW-automaton by extending the window to size 3-by-3, and by admitting vertical movements in addition to the horizontal movements. The most general model of this type is the deterministic two-dimensional four-way ORWW-automaton which can perform moveup and move-down steps as well as move-right and move-left steps. However, as shown in [21], each two-dimensional deterministic forgetting automaton [12] can be simulated by a deterministic two-dimensional four-way ORWW-automaton. As the former accept all deterministic context-free (string) languages [10], this means that the deterministic twodimensional four-way ORWW-automata are too expressive for our purposes. Accordingly, we only consider the following three models, which cannot make any move-left steps. The least restricted model of them is the deterministic two-dimensional three-way ORWW-automaton (the det-2D-3W-ORWW-automaton) which can perform move-up and move-down steps in addition to the move-right steps. This model is strictly more expressive than the deterministic variant of the restarting tiling automaton of [23,25], but as such an automaton may get stuck on a column of a given input picture, just moving up and down, we have to require its termination explicitly. In addition, it clearly favors vertical over horizontal movements, and accordingly, it is not surprising that the class of picture languages accepted is not closed under the operation of transposition. The second model is the deterministic two-dimensional two-way ORWW-automaton (the det-2D-2W-ORWW-automaton) which can only perform move-down steps in addition to the move-right steps. This model can be simulated by the deterministic Sgraffito automaton, but it is still more expressive than the class DREC mentioned above. However, an automaton of this type cannot scan a given input picture completely without performing any rewrite/restart steps, which means that the design of such an automaton may involve some special marking techniques in order to accept a complicated picture language like, e.g., the language L 1r1cr of square pictures over Σ = {, } for which the first row is identical to the reverse of the first column (see Example 2 in Sect. 5 below). Finally, we present the deterministic two-dimensional extended two-way ORWWautomaton (the det-2D-x2W-ORWW-automaton) for which the move operations are somewhat more general: when a move-right step is executed, while the central position of the window is placed in row i of the last column, then the window is moved such that its central position is in row i + 1 of the first column. Analogously, when a move-down step is executed, while the central position of the window is placed in column j of the bottommost row, then the window is moved such that its central position is in column j + 1 of the topmost row. In order to avoid infinite sequences of move operations, we require that in any cycle, the

123

596

F. Otto, F. Mráz

automaton can either use extended move-right or extended move-down steps, but not both. Already the stateless variant of the det-2D-x2W-ORWW-automaton can simulate the deterministic restarting tiling automaton, and the general model is strictly more expressive. On the other hand, the class of picture languages accepted by the det-2D-x2W-ORWW-automaton is closed under the operation of transposition, and it turns out that this class of picture languages is incomparable under inclusion to the class of picture languages that are accepted by the det-2D-3W-ORWW-automaton. This paper is structured as follows. In the next section we present the ordered restarting automaton (on strings) and investigate its expressive power. In Sect. 3 some basic notions and notation on pictures and picture languages are given and three types of two-dimensional automata are restated from the literature for reference. Then in Sects. 4, 5 and 6 the three types of deterministic two-dimensional ordered restarting automata are presented in turn. The paper closes with a short summary that includes a diagram which illustrates the various inclusion relations between the classes of picture languages considered. Also a number of open problems for future work are presented there.

2 Ordered restarting automata on strings The ordered restarting automaton, or ORWW-automaton for short, was introduced in [18]. It is a one-tape machine with a finite-state control and a read/write window of size 3. Formally, it is described by an 8-tuple M = (Q, Σ, Γ, , , q0 , δ, >). Here Q is a finite set of states, Σ is a finite input alphabet, and Γ is a finite tape alphabet containing Σ. The letters in Γ  Σ are called auxiliary symbols. Further, the symbols ,  ∈ / Γ serve as markers for the left and right border of the work space, respectively, q0 ∈ Q is the initial state, δ : Q × (((Γ ∪{}) · Γ · (Γ ∪{}))∪{}) → 2(Q×{MVR})∪Γ ∪{Accept} is the transition relation, where 2 S denotes the powerset of the set S, and > is a partial ordering on Γ . The transition relation describes three different types of transition steps: (1) A move-right step has the form (q  , MVR) ∈ δ(q, a1 a2 a3 ), where q, q  ∈ Q, a1 ∈ Γ ∪ {} and a2 , a3 ∈ Γ . If M is in state q and sees the string a1 a2 a3 in its read/write window, then this move-right step causes M to shift the read/write window one position to the right and to enter state q  . Observe that no move-right step is possible, if the content of the read/write window ends with the symbol . (2) A rewrite/restart step has the form b ∈ δ(q, a1 a2 a3 ), where q ∈ Q, a1 ∈ Γ ∪ {}, a2 , b ∈ Γ , and a3 ∈ Γ ∪ {} such that a2 > b holds. It causes M to replace the symbol a2 in the middle of its read/write window by the symbol b and to restart, that is, M moves its read/write window to the left end of the tape, so that it contains the left delimiter  and the first two letters of the current tape content, and to reenter the initial state q0 . (3) An accept step has the form Accept ∈ δ(q, a1 a2 a3 ), where q ∈ Q, a1 ∈ Γ ∪ {}, a2 ∈ Γ , and a3 ∈ Γ ∪ {}. It causes M to halt and accept. In addition, we allow an accept step of the form Accept ∈ δ(q0 , ). If δ(q, u) is undefined for some q ∈ Q and u ∈ ((Γ ∪ {}) · Γ · (Γ ∪ {})) ∪ {}, then

M necessarily halts, when it is in state q seeing u in its read/write window, and we say that M rejects in this situation.

123

Deterministic ordered restarting automata for picture…

597

A configuration of M is a string αqβ, where q ∈ Q and |β| ≥ 3, and either α = λ (the empty string) and β ∈ {}·Γ + ·{} or α ∈ {}·Γ ∗ and β ∈ Γ ·Γ + ·{}; here q ∈ Q represents the current state, αβ is the current content of the tape, and it is understood that the read/write window contains the first three symbols of β. In addition, we admit the configuration q0 . A restarting configuration has the form q0  w ; if w ∈ Σ ∗ , then q0  w  is an initial configuration. Further, we use Accept to denote the accepting configurations, which are those configurations that M reaches by executing an accept instruction. A configuration of the form αqβ such that δ(q, β1 ) is undefined, where β1 is the current content of the read/write window, is a rejecting configuration. A halting configuration is either an accepting or a rejecting configuration. In general, the automaton M is nondeterministic, that is, there can be two or more instructions with the same left-hand side (q, u), and thus, there can be more than one computation for an input string. If this is not the case, the automaton is deterministic. By det-ORWW we denote the deterministic ordered restarting automata. We observe that any computation of an ordered restarting automaton M consists of certain phases. A phase, called a cycle, starts in a restarting configuration, the head is moved along the tape by MVR operations until a rewrite/restart operation is performed and thus a new restarting configuration is reached. If no further rewrite/restart operation is performed, any computation necessarily finishes in a halting configuration—such a phase is called a tail. By ∗ cM we denote the execution of a complete cycle, and cM is the reflexive transitive closure c of M . An input w ∈ Σ ∗ is accepted by M, if there exists a computation of M which starts with the initial configuration q0  w , and which finally ends with the execution of an accept instruction. The language consisting of all strings that are accepted by M is denoted by L(M). Finally, we use the notation L(det-ORWW) (L(ORWW)) to denote the class of all languages that are accepted by det-ORWW-automata (ORWW-automata). As each cycle ends with a rewrite/restart operation, which replaces a symbol a by a symbol b that is strictly smaller than a with respect to the given ordering >, we see that each computation of M on an input of length n consists of at most n · (|Γ | − 1) many cycles and a tail. Thus, M can be simulated by a nondeterministic single-tape Turing machine in time O(n 2 ). The following example, taken from [18], illustrates the way in which an ORWWautomaton works. To simplify the presentation we use meta-instructions (see, e.g., [19]) to describe the behaviour of this ORWW-automaton. A meta-instruction of the form (E, u → v) means that when the current tape contains u preceded by a string from the regular language E, then M can rewrite u into v and restart. A meta-instruction of the form (E, Accept) means that if the tape content is a string from the regular language E, then M can accept it without a restart. Here we make use of the fact that we can assume without loss of generality that, within each accepting tail computation, M moves its read/write window all the way to the right delimiter  before it accepts. Example 1 Let M be the nondeterministic ORWW-automaton on Σ = {a, b, $} and Γ = {a, a1 , a2 , b, b1 , b2 , $} that is given by the following meta-instructions using the linear ordering $ > a > b > a1 > b1 > a2 > b2 , where c, d, e ∈ {a, b}:

123

598

F. Otto, F. Mráz

(1) (λ,  cd →  c1 d), (2) (λ,  c1 d →  c2 d), (3) ( ·{a2 , b2 }∗ , c2 de → c2 d1 e), (4) ( ·{a2 , b2 }∗ , c2 d1 e → c2 d2 e), (5) ( ·{a2 , b2 }∗ , c2 d$ → c2 d1 $), (6) ( ·{a2 , b2 }∗ , c2 d1 $ → c2 d2 $), (7) ( ·{a2 , b2 }∗ · d1 · {a, b}+ · $ · {a, b}∗ , cd  → cd1 ), (8) ( ·{a2 , b2 }∗ · d2 · {a, b}+ · $ · {a, b}∗ , cd1  → cd2 ), (9) ( ·{a2 , b2 }∗ · d1 · {a, b}+ · $ · {a, b}∗ , cde2 → cd1 e2 ), (10) ( ·{a2 , b2 }∗ · d2 · {a, b}+ · $ · {a, b}∗ , cd1 e2 → cd2 e2 ), (11) ( ·{a2 , b2 }∗ · d1 · {a, b}∗ , $de2 → $d1 e2 ), (12) ( ·{a2 , b2 }∗ · d2 · {a, b}∗ , $d1 e2 → $d2 e2 ), (13) ( ·{a2 , b2 }+ · $ · {a2 , b2 }+ · , Accept). Then M accepts the following language L on Σ: L = { w$u | w, u ∈ {a, b}∗ , |w|, |u| ≥ 2, u is a scattered subsequence of w R }, which is context-free, but not regular. Indeed it is obvious that each word accepted by M is of the form w#u for some w, u ∈ {a, b}∗ such that |w| ≥ 2 and |u| ≥ 2. Further, M rewrites the letters of w from left to right, first by attaching the index 1, then changing index 1 to index 2. Also M rewrites the letters of u from right to left, again by first attaching the index 1, and then changing index 1 to index 2. However, M can rewrite a letter d ∈ {a, b} of u only if at that moment in time, the currently rewritten prefix of w ends with the letter d1 [see (7), (9) and (11)]. Analogously, it can rewrite a letter d1 in the suffix of u only if at that moment in time, the currently rewritten prefix of w ends with the letter d2 [see (8), (10) and (12)]. When M accepts, then all letters of w and u have been rewritten twice (see (13)). Thus, it follows that u is a scattered subword of w R . Actually, the construction of Example 1 can easily be changed to obtain an ORWWautomaton for the language L copy = { w$u | w, u ∈ {a, b}∗ , |w|, |u| ≥ 2, u is a scattered subsequence of w }, which is not even context-free. However, while nondeterministic ORWW-automata are quite expressive, it turns out that their deterministic variants are fairly weak. Theorem 1 REG = L(det-ORWW)  L(ORWW). Proof Obviously every regular language is accepted by some deterministic ORWWautomaton. Conversely, let M = (Q, Σ, Γ, , , q0 , δ, >) be a det-ORWW-automaton, and let L = L(M) ⊆ Σ ∗ be the language it accepts. Now a one-tape Turing machine T can simulate M as follows. When simulating the first sweep to the right, T stores in each tape field the letter from the previous tape field, the current letter, and the state in which M reaches this position (more exactly, the state in which the read/write window of M reaches the position in which the letter under consideration is in the middle of the read/write window). When M rewrites the letter at position i by some smaller letter, then T does the same, after checking on the letter at position i + 1. In the next step, T moves one position to the left, and from the

123

Deterministic ordered restarting automata for picture…

599

state stored at that position, from the content of that tape field, and from the letter written at position i it can now determine the operation that M will perform in the next cycle at position i − 1. Observe that, since M is deterministic, it must perform MVR steps until this very position. If M executes another MVR step at position i − 1, then so does T , and it will then store the state in which M reaches position i together with the currently stored symbol at position i. If, however, M performs a rewrite/restart step at position i −1, then T simulates the corresponding rewrite and moves to position i − 2. It should be clear that in this way T correctly simulates the computation of M, that is, we see that L(T ) = L(M). At each position of the input, M performs at most γ := |Γ | − 1 many rewrite steps, and so, T does the same. In fact, T visits every tape field at most 4γ + 1 many times. Consider some tape position i such that 1 ≤ i ≤ n = |w|, where w is the input given. At some point T visits this position for the first time. For each rewrite step executed at position i, T first moves to the right to position i + 1 and then back to position i. After executing the rewrite step, T moves left, and hence, it may return to position i again. Thus, the rewrite steps at position i will lead to up to 2γ many visits to this position. Further, each time a rewrite step is executed at position i + 1, T moves to position i from the right, and each time a rewrite step is to be executed at position i − 1, T visits position i from the left and returns to position i − 1 immediately. This leads to up to 2γ many additional visits to position i. Together this means that T moves to the tape field at position i at most 4γ + 1 many times. Now Hennie has shown in [8] that a Turing machine that visits each of its tape fields at most a constant number of times can only accept a regular language. It follows that the language L(M) = L(T ) is regular. Finally, Example 1 shows that the class REG of regular languages is properly contained in L(ORWW).

It remains open at this point whether every context-free language is accepted by some ORWW-automaton. On the other hand, the two-way variant of the deterministic ORWWautomaton, which is obtained from the det-ORWW-automaton by admitting move-left steps in addition to the move-right steps (see, e.g., [19]), is easily seen to accept the aforementioned non-regular languages, too. Thus, for our intended generalization to the two-dimensional setting, we will take the deterministic ORWW-automaton as defined above as our basic model.

3 Picture languages We use the common notation and terms on pictures and picture languages (see, e.g., [7]). For a finite alphabet Σ, Σ ∗,∗ denotes the set of rectangular pictures over Σ, that is, if P ∈ Σ ∗,∗ , then P is a two-dimensional array of symbols from Σ. We denote the number of rows and columns of a picture P by rows(P) and cols(P), respectively. The pair (rows(P), cols(P)) is called the dimension of P, and the product rows(P) · cols(P) is the size of P. The empty picture Λ is defined as the only picture of dimension (0, 0), and for all m, n ≥ 1, Σ m,n denotes the set of pictures of dimension (m, n) over Σ. A picture language over Σ is a subset of Σ ∗,∗ . For 1 ≤ i ≤ rows(P) and 1 ≤ j ≤ cols(P), P(i, j) (or shortly Pi, j ) identifies the symbol located in row i and column j of P. Two (partial) binary operations are used to concatenate pictures. Let P and Q be pictures over Σ of dimensions (k, l) and (m, n), respectively. The column concatenation P dQ is defined if and only if k = m, while the row concatenation P dQ is defined if and only if l = n. These products are depicted below:

123

600

F. Otto, F. Mráz

⎡

⎡

P1,1 . . . P1,l Q 1,1 . . . ⎢ .. . . .. .. . . d P Q=⎣ . . . . . Pk,1 . . . Pk,l Q m,1 . . .

P1,1 ⎢ .. ⎤ ⎢ . Q 1,n ⎢ .. ⎥ and P dQ = ⎢ ⎢ Pk,1 ⎢ Q 1,1 . ⎦ ⎢ ⎢ . Q m,n ⎣ .. Q m,1

... .. . ... ... .. . ...

⎤ P1,l .. ⎥ . ⎥ ⎥ Pk,l ⎥ ⎥. Q 1,n ⎥ ⎥ .. ⎥ . ⎦ Q m,n

We also define Λ dP = P dΛ = Λ dP = P dΛ = P for any picture P. These operations are extended to languages by taking L 1 dL 2 = { P1 dP2 | P1 ∈ L 1 and P2 ∈ L 2 } and L 1 dL 2 = { P1 dP2 | P1 ∈ L 1 and P2 ∈ L 2 }. d d  d The column closure L ∗ of a picture language L is defined as L ∗ = i≥0 L i , where d d d d L 0 = {Λ}and L i = L dL (i−1) for all i ≥ 1. Similarly, the row closure L ∗ is defined d d d d d ∗ i 0 i (i−1) d as L = i≥0 L , where L = {Λ} and L = L L for all i ≥ 1. These two operations can be seen as the extensions of the Kleene star from string languages to picture languages. Also we consider the clockwise rotation P R and the transposition P T of a picture P ∈ Σ m,n : ⎡ ⎡ ⎤ ⎤ Pm,1 . . . P1,1 P1,1 . . . Pm,1 ⎢ ⎢ ⎥ ⎥ P R = ⎣ ... . . . ... ⎦ , and P T = ⎣ ... . . . ... ⎦ . Pm,n . . . P1,n P1,n . . . Pm,n Let π : Γ → Σ be a mapping, where Γ is an alphabet. Then π induces a mapping from Γ ∗,∗ to Σ ∗,∗ by sending P ∈ Γ m,n to P  ∈ Σ m,n such that P  (i, j) = π (P(i, j)) for each 1 ≤ i ≤ m and 1 ≤ j ≤ n. This mapping is called a projection from Γ ∗,∗ to Σ ∗,∗ , and P  is simply written as π(P). Note that each of these operations naturally extends to languages. Let S = {, , , ⊥, #} be a set of five special markers, called sentinels. In what follows, we will always assume implicitly that Σ ∩ S = ∅ for any alphabet Σ considered. In order to enable our automata to be defined below to detect the border of a picture P ∈ Σ m,n easily, over Σ ∪ S of size (m + 2, n + 2), which is illustrated in we define the boundary picture P Fig. 1. Here the symbols , ,  and ⊥ uniquely identify the corresponding borders (left, while the symbol # marks the corners of P. right, top, bottom) of P, For future reference we now present three types of two-dimensional automata that we will need below. Throughout the paper we will use the notation L(X) to denote the class of (string or picture) languages that are accepted by the automata of type X. The class DREC of deterministically recognizable picture languages was introduced in [1]. In [3] it is shown that DREC coincides with the closure of the language class L(DOTA) under rotation, where DOTA denotes the deterministic on-line tessellation automaton [9]. Here we follow the somewhat shorter presentation of [7]. A deterministic on-line tessellation

#

...

#

.. .

P

.. .

#

Fig. 1 The boundary picture P

123

⊥ ⊥

...

⊥ ⊥

#

Deterministic ordered restarting automata for picture…

601

automaton is defined by a tuple A = (Σ, Q, q0 , F, δ), where Σ is a finite input alphabet, Q is a finite set of states, q0 ∈ Q is the initial state, F ⊆ Q is a set of final states, and δ : Q × Q × Σ → Q is a transition function. A run of A on an input picture P ∈ Σ m,n associates a state from Q to each position (i, j) of P. The state q(i, j) associated to this position is obtained as q(i, j) = δ(q(i − 1, j), q(i, j − 1), Pi, j ), where the initial state q0 is taken for all positions (i, 0) and (0, j), i = 1, . . . , m and j = 1, . . . , n. Thus, A can be seen as executing m + n − 1 parallel steps, where in step k, states are associated to all those positions (i, j) that satisfy the condition i + j − 1 = k. It is said that A recognizes the picture P if the corresponding run associates a final state to the position (rows(P), cols(P)) of P. The two-dimensional Sgraffito automaton, 2SA for short, was introduced in [24]. A 2SA is given by a tuple A = (Q, Σ, Γ, δ, q0 , Q F , μ), where Q is a finite set of states, Σ is an input alphabet, Γ is a working alphabet such that Σ ⊆ Γ , q0 ∈ Q is the initial state, Q F ⊆ Q is the set of final states, δ : (Q  Q F ) × (Γ ∪ S ) → 2 Q×(Γ ∪S )×H is a transition function, where H = {R, L, D, U, Z} is the set of possible head movements (here Z stands for zero (no) movement), and μ : Γ → N is a weight function. It is required that the following properties are satisfied for each transition (q  , a  , d) ∈ δ(q, a): – if a ∈ S , then a  = a and d = ν(a), where ν() = R, ν() = L, ν() = D, and ν(⊥) = U, that is, whenever A encounters a sentinel from {, , , ⊥} within a then it moves immediately to the nearest field of the proper picture P; boundary picture P,  – if a ∈ / S , then a ∈ / S and μ(a  ) < μ(a) holds, that is, whenever A encounters a symbol a ∈ Γ , then it replaces this symbol by a symbol a  ∈ Γ of strictly less weight. If |δ(q, a)| ≤ 1 for all q ∈ Q and a ∈ Γ ∪ S , then A is a deterministic Sgraffito automaton, abbreviated as 2DSA. Given a picture P ∈ Σ ∗,∗ as input, the initial configuration of A consists in the working the initial state q0 , and the head scanning the top-left tape containing the boundary picture P, Now A walks across this boundary picture, and it cannot corner of P, that is, cell (2, 2) of P. Furthermore, when executing a transition step at a position leave the space covered by P. (i, j) of P, then it must replace the current symbol at that position by a symbol that has at most strictly less weight. It follows that A can visit each position of P, and therewith of P, |Γ | many times. The automaton A is said to accept P if there is a computation of A that starts from the initial configuration on input P and that finishes in a state from Q F . It is known L(2SA) properly includes the class REC of recognizable picture languages, and that the class L(2DSA), which is incomparable to REC with respect to inclusion, contains the class DREC and all picture languages that are accepted by four-way alternating automata, or by deterministic four-way one-marker automata, or that are sudoku-deterministically recognizable [22,24,26,27]. The third model is the two-dimensional deterministic restarting tiling automaton, which was introduced by Mráz and Pr˚uša in [23] (see [25] for an extended presentation). It combines the rewrite/restart capability of the restarting automaton with the acceptance condition of the tiling automaton. To describe this model, we introduce the notion of a ‘scanning strategy.’ Scanning strategies have also been considered in the context of tiling automata [2] and Wang systems [15]. A scanning strategy determines the way in which an automaton scans a given input picture. It is given through a pair s = (cs , f ), where cs ∈ {1, 2, 3, 4} is a starting position, and f : N4 → N2 is a computable partial function. Here cs = 1 denotes the top-left corner, 2 denotes the top-right corner, 3 stands for the bottom-right corner, and 4 stands for the bottom-left corner, and f (i, j, m, n) = (i  , j  ) states that in a picture of size (m, n), position (i  , j  ) is scanned immediately after position (i, j). It is required that, if (i 0 , j0 ) is the starting

123

602

F. Otto, F. Mráz

position in a picture P of size (m, n), and if (ir , jr ) = f (ir −1 , jr −1 , m, n) for all r ≥ 1, then the sequence (i 0 , j0 ), (i 1 , j1 ), . . . , (i (m+1)·(n+1)−1 , j(m+1)·(n+1)−1 ) is a permutation of ˆ Here the position of the set of all positions of tiles of size (2, 2) in the boundary picture P. An example is a tile is the position of its top-left corner cell within the boundary picture P. the scanning strategy νcol = (1, f col ), where

(i + 1, j), if i < m + 1, f col (i, j, m, n) = (1, j + 1), if i = m + 1 and j < n + 1, which scans a picture column by column from left to right starting at the top-left corner. A two-dimensional deterministic restarting tiling automaton, a 2DRTA for short, is given through a sixtuple M = (Σ, Γ, Θ F , δ, ν, μ), where Σ is a finite input alphabet, Γ is a finite working alphabet containing Σ, Θ F ⊆ (Γ ∪ S )2,2 is a set of accepting tiles, ν = (cν , f ν ) is a scanning strategy, μ : Γ → N is a weight function, and δ : (Γ ∪ S )2,2 → (Γ ∪ S )2,2 is a partial function such that, for all transitions δ(U ) = V , there is a single position (i, j) such that U (i, j)  = V (i, j), and moreover, if U (i, j) = a ∈ Γ is changed into V (i, j) = b ∈ Γ , then μ(a) > μ(b) holds. On input a picture P ∈ Σ m,n , the automaton M works in cycles, proceeding as follows: – at the beginning of each cycle, the scanning window of M of size (2, 2) is placed on that corresponds to the starting position cν of the the corner of the boundary picture P scanning strategy ν; step by step, moving its window according to the function f ν ; – now M scans P – when M reaches a position such that the tile being scanned is of the form U such that δ(U ) is defined, then M replaces this tile by the corresponding tile V = δ(U ) and restarts, that is, its scanning window is repositioned on the initial position corresponding to cν , completing the current cycle; completely without encountering a possible rewrite, then it – when M succeeds to scan P halts, finishing the current computation. M is said to accept if at this point the boundary picture obtained only contains tiles of size (2, 2) that belong to the set Θ F . By L(M) we denote the language accepted by M, which is the set of all pictures P ∈ Σ ∗,∗ for which M has an accepting computation. We denote by ν-2DRTA the class of two-dimensional deterministic restarting tiling automata that use the scanning strategy ν, and L(ν-2DRTA) denotes the corresponding class of picture languages. A picture language L is called strategy independent if, for each scanning strategy ν, there exists a ν-2DRTA Mν such that L(Mν ) = L holds. The class of all strategy independent languages is denoted by si-2DRTL. Obviously, si-2DRTL ⊆ L(ν-2DRTA) for each scanning strategy ν. Further, it is shown in [23,25] that L(2DSA) ⊆ si-2DRTL holds.

4 Deterministic two-dimensional three-way ORWW-automata Here we consider the deterministic two-dimensional three-way ordered restarting automaton, which is obtained as a generalization of the deterministic ORWW-automaton to two dimensions by using a read/write window of size (3, 3) and by using move-down and moveup steps in addition to the move-right steps. Formally this automaton is defined as follows, where H = {R, D, U} is the set of possible window movements. Definition 1 [18] A deterministic two-dimensional three-way ordered restarting automaton, a det-2D-3W-ORWW-automaton for short, is given through a 7-tuple M = (Q, Σ, Γ, S , q0 , δ, >), where

123

Deterministic ordered restarting automata for picture…

– – – – –

603

Q is a finite set of states containing the initial state q0 , Σ is a finite input alphabet, Γ is a finite tape alphabet containing Σ such that Γ ∩ S = ∅, > is a partial ordering on Γ , and δ : Q × (Γ ∪ S )3,3 → (Q × H) ∪ Γ ∪ {Accept} is the transition function that satisfies the following four restrictions for all q ∈ Q and all C ∈ (Γ ∪ S )3,3 : 1. 2. 3. 4.

if C1,2 = , then δ(q, C)  = (q  , U) for all q  ∈ Q, if C2,3 = , then δ(q, C)  = (q  , R) for all q  ∈ Q, if C3,2 = ⊥, then δ(q, C)  = (q  , D) for all q  ∈ Q, if δ(q, C) = b ∈ Γ , then C2,2 > b with respect to the ordering >.

To simplify the presentation we say that the window of M is at position (i, j) to mean that the field in the center of the window is at row i and column j of P. Given a picture P ∈ Σ m,n as input, M begins its computation in state q0 with its read/write window reading the subpicture at the upper left corner, that is, the window is at position (1, 1). Thus, M of size (3, 3) of P ⎛ ⎞ #   sees the subpicture ⎝  P1,1 P1,2 ⎠. Applying its transition function, M now moves through  P2,1 P2,2 until it reaches a state q and a position with current content C of the read/write window P such that – either δ( p, C) is undefined, or – δ( p, C) = Accept, or – δ( p, C) = b for some letter b ∈ Γ such that C2,2 > b. In the first case, M gets stuck, and so the current computation ends without acceptance, in the second case, M halts and accepts, and in the third case, M replaces the symbol C2,2 by the symbol b, moves its read/write window back to the upper left corner, and reenters its initial state q0 . This latter step is called a rewrite/restart step. A picture P ∈ Σ ∗,∗ is accepted by M, if the computation of M on input P ends with an accept instruction. By L(M) we denote the language consisting of all pictures over Σ that M accepts. Finally, by L(det-2D-3W-ORWW) we denote the class of all picture languages that are accepted by det-2D-3W-ORWW-automata. In principle it could happen that a computation of a det-2D-3W-ORWW-automaton M does not terminate on some input picture, as M may get stuck on a column, moving up and down. To avoid this, we require explicitly that M halts on all input pictures! This can be realized by either providing a simple pattern, e.g., up∗ − down∗ − up∗ − down∗ , such that on each column, the sequence of up and down movements must fit this pattern, or one could use an external counter that, for each column entered in the course of a computation, counts the number of uninterrupted up and down movements, making sure that the computation fails as soon as more than (m · |Q|) many such steps are encountered on a column of height m. Actually, in most cases termination follows from the fact that within a column, an automaton is just looking for an occurrence of a specific symbol, and if that is not found, then the computation fails anyway. Given a picture P ∈ Σ m,n as input, a det-2D-3W-ORWW-automaton M = (Q, Σ, Γ, S , q0 , δ, >) can execute at most m · n · (|Γ | − 1) many cycles. As each cycle, and also a tail computation, takes at most m · n · |Q| many steps, we see that for accepting P, M executes at most (m · n · (|Γ | − 1) + 1) · m · n · |Q| many steps. Thus, a two-dimensional Turing machine can simulate the computation of M on P in time O(m 2 · n 2 ). A multi-tape Turing machine that stores P column by column needs m steps to simulate a single move-right step of M.

123

604

F. Otto, F. Mráz

However, during each cycle M can execute at most n − 1 such steps. As P is of size m · n, we obtain the following upper bound for the time complexity of det-2D-3W-ORWW-automata. Theorem 2 [18] L(det-2D-3W-ORWW) ⊆ DTIME((size(P))2 ). Observe that this result even holds without the explicit requirement of termination for M, as the simulating Turing machine can use a counter to detect a loop of up and down movements within the computation of M being simulated. When restricted to one-row pictures P ∈ Σ 1,∗ , then the det-2D-3W-ORWW-automaton coincides with the deterministic ordered restarting automaton considered in Sect. 2. Hence, it follows that the det-2D-3W-ORWW-automaton just accepts the regular (string) languages, when it is restricted to one-row inputs. Actually, a somewhat stronger result can be derived. Let m ≥ 1 be a fixed integer, let Σ be a finite alphabet, let  be an additional symbol, and let Δ = Σ ∪ {}. With a (string) language L ⊆ Σ ∗ , we associate a language E m (L) of m-row pictures by taking E m (L) = { P ∈ Δm,∗ | ∃n ≥ 0 ∃w = w1 . . . wn ∈ L ∩ Σ n : P1,i = wi and P j,i =  for all 1 ≤ i ≤ n and 2 ≤ j ≤ m }. Thus, a picture P belongs to the m-row extension E m (L) of L if and only if its first row contains a string from the language L, and all other rows are filled with the symbol . Theorem 3 For all m ≥ 1 and all languages L ⊆ Σ ∗ , if the picture language E m (L) is accepted by some det-2D-3W-ORWW-automaton, then L is a regular (string) language. Proof As observed above, there is nothing to prove for the case m = 1. Hence, let m ≥ 2, let L ⊆ Σ ∗ , and let M = (Q, Δ, Γ, S , q0 , δ, >) be a det-2D-3W-ORWW-automaton with input alphabet Δ = Σ ∪ {} such that L(M) = E m (L) holds. From M we will construct (1) a det-ORWW-automaton M1 = (Q 1 , Σ, Ω, , , q0 , δ1 , > ) for the language L, which then implies by Theorem 1 that L is indeed a regular (string) language. First we determine the tape alphabet Ω and the partial ordering > by taking ⎧⎡ ⎫ ⎤ ⎨ A1 ⎬ – Ω = Σ ∪ ⎣ ... ⎦ | A1 , . . . , Am ∈ Γ and by defining ⎩ ⎭ ⎡ ⎤ Am ⎡ ⎤ ⎡ ⎤ a A1 B1 ⎥ ⎢ . . ⎦   ⎢ ⎥ ⎣ ⎦ ⎣ . . – a > ⎣ .. ⎦ for all a ∈ Σ, and > if there exists an index i ∈ {1, . . . , m} . . . 

Am

Bm

such that Ai > Bi and A j = B j for all j  = i. Thus, each column of height m over Γ is a letter in Ω, and each input letter a is larger than the column with the symbol a in the topmost position and the symbol  in all other positions. The set of states of M1 is defined as Q 1 = Q × {1, . . . , m}, and the initial state is (1) q0 = (q0 , 1). Here a state (q, i) of M1 will be interpreted as stating that M is currently in state q, and that the central position of its window is in row i. The det-ORWW-automaton M1 will proceed as follows. (1) First it rewrites the given input, say w = w1 . . . wn , w1 , . . . , wn ∈ Σ, letter by letter from right to left into the word ⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎢ ⎢ ⎣

123

w1 w2 wn  ⎥⎢  ⎥ ⎢⎥ ⎢ . ⎥ . . . ⎢ . ⎥. . ⎥ ⎣ .. ⎦ .. ⎦⎣ .. ⎦   

Deterministic ordered restarting automata for picture…

605 (1)

This is easily achieved just using the initial state q0 . (2) Then M1 simulates M on the corresponding input From ⎡ picture. ⎤⎡ ⎤ ⎡ its ⎤ state of the form A1

B1

C1

Am

Bm

Cm

(q, i) and the content of its window of the form ⎣ ... ⎦⎣ ... ⎦⎣ ... ⎦, it can determine the next step that M would execute. A move right step, a rewrite/restart step, or an accept step can be simulated immediately. Finally, if in the given situation M would first execute a sequence of move up and/or move down steps, then M1 can extract the corresponding information from the transition function of M, and it can combine this sequence with the subsequent move right, rewrite/restart, or accept step. Observe that an infinite sequence of up and down movements of M would lead to an undefined transition for M1 , as this would be detected by the analysis above. In this situation neither M nor M1 would be able to finish its current computation successfully. From the above description it should be clear that L(M1 ) = L holds.



What is the expressive power of the det-2D-3W-ORWW-automaton? On the one hand, it has been shown in [18] that det-2D-3W-ORWW-automata can simulate deterministic Sgraffito automata (see Sect. 3). On the other hand, it has been observed that deterministic Sgraffito automata can also be simulated by two-dimensional deterministic restarting tiling automata (Sect. 3). Here we improve upon the result from [18] cited above by showing that a det-2D3W-ORWW-automaton can even simulate a two-dimensional deterministic restarting tiling automaton if the latter scans its input pictures column by column from left to right, that is, if it uses the scanning strategy νcol presented in Sect. 3. Recall that the class of strategy independent languages si-2DRTL is contained in the class of languages L(νcol -2DRTA). Theorem 4 si-2DRTL  L(det-2D-3W-ORWW). Proof Let M = (Σ, Γ, Θ F , δ, νcol , μ) be a 2DRTA that uses the scanning strategy νcol = (1, f col ). We simulate the computations of M by a det-2D-3W-ORWW-automaton M = (Q, Σ, Γ, S , q0 , δ  , >) that uses the partial ordering > which is defined by a > b iff μ(a) > μ(b), and that proceeds as follows: – M scans the given picture column by column from left to right. This is possible as it can freely use up- and down-steps. – As soon as it detects an applicable rewrite operation of M, it performs the appropriate rewrite and restarts. – While scanning the picture, it checks whether all tiles of size (2, 2) encountered belong to Θ F . When it gets to the bottom right corner without having encountered an applicable rewrite operation, then it halts, and it accepts in case that all tiles of size (2, 2) encountered during the last sweep belong to the set Θ F . It follows that L(M ) = L(M). Thus, L(νcol -2DRTA) ⊆ L(det-2D-3W-ORWW),

which in turn yields the inclusion in Theorem 4. To prove that this inclusion is proper, we consider the following picture language L 1col over Σ = {a, b}: L 1col = { P ∈ Σ 2n,1 | n ≥ 1, P(1, 1) . . . P(n, 1) = (P(n + 1, 1) . . . P(2n, 1)) R },

123

606

F. Otto, F. Mráz

that is, L 1col consists of all pictures with a single column of even length such that the content of this column read from top to bottom is a palindrome. Based on the fact that a det-2D-3WORWW-automaton can freely move up and down a column, it can be shown that this language is accepted by some det-2D-3W-ORWW-automaton. From [23,25] it is known that the class si-2DRTL is closed under the operation of rotation. This operation turns the language L 1col into the string language L pal = { w ∈ Σ + | |w| = 0 mod 2, w = w R } of palindromes of even length, which is a non-regular language. As si-2DRTL only contains regular string languages [23,25], it follows that L 1col is not contained in si-2DRTL. This shows that the inclusion in Theorem 4 is proper.

Together with Theorem 3, the fact that L 1col is accepted by a det-2D-3W-ORWWautomaton also shows the following negative result. Corollary 1 [18] L(det-2D-3W-ORWW) is neither closed under rotation nor under transposition. Before we consider further non-closure and closure properties, we turn to a particular example language from the literature. Let Σ = {, }, and let L copy denote the language of duplicates that consists of all pictures P dP, where P is any quadratic picture over Σ. For example,    

   

   

   

   

   

   

   

is an element of L copy . It is shown in [22,24] that L copy is not accepted by any Sgraffito automaton, while its complement (L copy )c is accepted by a Sgraffito automaton. Concerning this language we have the following negative result. / L(det-2D-3W-ORWW). Proposition 1 L copy ∈ Proof Assume to the contrary that there exists a det-2D-3W-ORWW-automaton M = (Q, Σ, Γ, S , q0 , δ, >) on Σ = {, } such that L(M) = L copy . Without loss of generality we may assume that M accepts only at the lower right corner of the picture. Let n be a sufficiently large positive integer, the exact value of which will be determined later. We consider input pictures of the form P dP ∈ L copy for P ∈ Σ n,n , for which we fix the entries in the first column and in the last column to all be . We analyze the accepting computations of M on inputs P dP of the form above. The left half of the picture P dP will be denoted by P , and the right half will denoted by Pr . We say that M is on P (on Pr ) if the active position, that is, the middle position, of its read/write window is on a tape field that belongs to P (Pr ), that is, it is on column i for some 1 ≤ i ≤ n (n + 1 ≤ i ≤ 2n). As each cycle of M starts with the read/write window at the upper left corner of P , and as M cannot make any move-left steps, we see that each cycle of M consists of an initial part during which M is on P , which is then possibly followed by a part during which M is on Pr . In particular, when M performs a rewrite step on P , then it does not visit Pr at all during the corresponding cycle. Therefore, we are particularly interested in the behaviour of M at the border between P and Pr , that is, when the middle column of its read/write window is over the last column of P , that is, over column n of P dP. These positions are the only positions in which the contents of the tape fields containing Pr has any influence on the behaviour of M on P .

123

Deterministic ordered restarting automata for picture…

607

Now the computation of M on input P dPr can be divided into two types of phases: – a left-phase consists of a sequence of maximum length of cycles during which M executes rewrite steps on P ; – a right-phase consists of a sequence (of maximum length) of cycles during which M executes rewrite steps on Pr . Obviously, an accepting computation of M on an input of the form P dPr cannot consist of a single left-phase only. Thus, after a (possibly empty) left-phase, a right-phase follows. During each cycle of this right-phase, M moves from the upper left corner of P through P into Pr , where it performs a rewrite/restart step. As M is deterministic, this pattern of movements cannot change until at least one element in the first column of Pr has been rewritten, because only when encountering such a new symbol, M may make a step that is different from the one it made before at this very position. Of course, the same is true also for all later right-phases. Accordingly, we say that a right-phase ends as soon as an element in the first column of Pr is being rewritten. It follows either a left-phase or already the next right-phase. The first column of Pr has n entries only, each of which is initialized by the symbol  that can be rewritten at most |Γ | − 1 times. Thus, altogether at most n · (|Γ | − 1) rewrites can occur in this column, which implies that there are at most n · (|Γ | − 1) + 1 many right-phases and at most as many left-phases. We are interested in the configurations of M in which it enters the tape fields of Pr during a right-phase, that is, the configurations right after M moved its head from a field in column n to the right onto a field in column n + 1. We call these configurations enter configurations. An enter configuration is described by a pair (q, m), where q ∈ Q is the current state of M, and m ∈ {1, . . . , n} is the row of P on which the active field of the window is located. Thus, there are |Q| · n many different possible enter configurations. Each right-phase ends with an execution of a rewrite in the first column of Pr , that is, in column n + 1. Hence, we can associate with each right-phase a triple (m, n + 1, b) that indicates that this right-phase ended with a rewrite that placed the symbol b ∈ Γ into the tape field at position (m, n + 1). Obviously, there are n · |Γ | many different triples of this form. During the execution of a right-phase, the behaviour of M is influenced by the current content of the last column of P , that is, column n. This column has n entries, each of which is initialized by the symbol  that can be rewritten at most |Γ | − 1 times. These rewrites are performed during left-phases. Hence, in order to keep track of the content of this column, we write down the triple (m, n, b) whenever M executes a rewrite that places the symbol b ∈ Γ into the tape field at position (m, n). Again, there are n · |Γ | many different triples of this form. With the accepting computation of M on an input P dP of the form described above, we now associate a generalized crossing sequence GCS(M, P dP) that is defined as follows: 1. We begin with the empty sequence. 2. Whenever a rewrite operation is performed on a tape field in column n, then we append the corresponding triple of the form (m, n, b) to the sequence. 3. Whenever a right-phase starts, then we append the corresponding enter configuration of the form (q, m) to the sequence. 4. Whenever a right-phase ends with the execution of a rewrite operation on a tape field in column n + 1, then we append the corresponding triple of the form (m, n + 1, b) to the sequence.

123

608

F. Otto, F. Mráz

As there are at most n · (|Γ | − 1) + 1 many right-phases, at most n · (|Γ | − 1) many rewrites in column n, and at most n · (|Γ | − 1) many rewrites in column n + 1, we see that each sequence GCS(M, P dP) is of length at most 3 · n · (|Γ | − 1) + 1 ≤ 3 · n · |Γ |. Obviously, not each sequence of this length can occur as a generalized crossing sequence of an accepting computation of M, but by counting all the possible sequences we obtain an upper bound for the number of different generalized crossing sequences. The number of possible sequences of length up to 3 · n · |Γ | that consist of pairs (q, m) and triples (m, n, b) and (m, n + 1, b) is bounded from above by the following expression: 3·n·|Γ | i=1

(|Q| · n + 2 · |Γ | · n)i =

3·n·|Γ |

(n · (|Q| + 2 · |Γ |))i ∈ 2 O(n·log n) .

i=1

Thus, the number of different generalized crossing sequences grows at most as fast as the 2 function 2 O(n·log n) . However, there are 2n·(n−2) = 2n −2·n many pictures of the form P dP with all entries  in the first and in the last column. If n is sufficiently large, then there are more pictures of this form than there are possible generalized crossing sequences. Hence, there exist two pictures P, P  ∈ Σ n,n of this form such that P  = P  , but GCS(M, P dP) = GCS(M, P  dP  ). We claim that together with these pictures, M will also accept the picture P dP  ∈ / L copy . To prove this claim we compare the computation C(P, P) of M on input P dP and the computation C(P  , P  ) of M on input P  dP  to the computation C(P, P  ) of M on input P dP  . At the start of these computations, columns n and n + 1 of all these pictures coincide by our hypothesis. If C(P, P) starts with a left-phase, then the computation C(P, P  ) starts with an identical left-phase. If during this left-phase, some entries in column n are rewritten, then because of GCS(M, P dP) = GCS(M, P  dP  ), also the computation C(P  , P  ) begins with a left-phase during which the same rewrites in column n are executed in the same order. Thus, when these left-phases end, then the three pictures obtained will have identical n-th columns. If the computation C(P  , P  ) now starts a right-phase, then so do C(P, P) and C(P, P  ), and these right-phases have the same enter configuration. Thus, on the right half of the picture, the right-phase of C(P, P  ) is identical to the right-phase of C(P  , P  ). In particular, if it ends by performing a rewrite step that replaces a symbol a by a symbol b in row m of column n + 1, then also the right-phase of C(P, P) ends with this very rewrite. Hence, when these right-phases end, then the three pictures obtained will have identical column n +1. Continuing in this way, we see that the computation C(P, P  ) behaves on the left half of its input picture just like C(P, P), while it behaves like C(P  , P  ) on the right half of its input picture. In particular, since C(P  , P  ) accepts at the lower right corner of the picture, so does C(P, P  ). Thus, M does indeed accept the input picture P dP  ∈ / L copy . As this contradicts our assumption on M, it follows that the language L copy is not accepted by any det-2D-3W-ORWW-automaton.

Now we return to the (non-)closure properties of L(det-2D-3W-ORWW). The following results have been announced in [18]. Theorem 5 The language class L(det-2D-3W-ORWW) is closed under union, intersection and complement, but it is neither closed under projection nor under column concatenation. Proof Closure under complement: Let M be a det-2D-3W-ORWW-automaton on Σ that accepts a language L ⊆ Σ ∗,∗ . From M we obtain a det-2D-3W-ORWW-automaton Mc by turning every undefined transition of M into an accept transition, and by turning every accept transition of M into an undefined transition. On input P ∈ Σ ∗,∗ , M and Mc will

123

Deterministic ordered restarting automata for picture…

609

execute exactly the same sequence of cycles, but in the corresponding tail computation, Mc accepts if and only if M does not accept. Thus, L(Mc ) = Σ ∗,∗  L = L c , the complement of the language L = L(M). Observe that here we make essential use of the fact that every computation of a det-2D-3W-ORWW-automaton terminates after finitely many steps, as an infinite sequence of up and down movements of M would result in the same infinite sequence of up and down movements of Mc , that is, none of these two automata would accept the corresponding input. (1) Closure under intersection: Let M1 = (Q 1 , Σ, Γ1 , S , q0 , δ1 , >1 ) be a det-2D-3WORWW-automaton on Σ = {a1 , . . . , ak } that accepts a picture language L 1 = L(M1 ) ⊆ (2) Σ ∗,∗ , and let M2 = (Q 2 , Σ, Γ2 , S , q0 , δ2 , >2 ) be a det-2D-3W-ORWW-automaton that accepts a picture language L 2 = L(M2 ) ⊆ Σ ∗,∗ . We construct a det-2D-3W-ORWWautomaton M = (Q, Σ, Γ, S , q0 , δ, >) such that L(M) = L 1 ∩ L 2 . Essentially, M will work as follows: (1) M first simulates M1 , that is, it behaves exactly like M1 . If M1 should get stuck on the given input, that is, M1 does not accept, then neither does M. If, however, M1 accepts, then instead of accepting, M marks the position (i, j) at which M1 accepts, using a special symbol. (2) Now M should simulate M2 . However, unless the marked position (i, j) happens to satisfy the condition i, j ≤ 2, M does not know that it now should simulate M2 . Therefore, it still behaves just like M1 during the tail of its accepting computation. Hence, no rewrite will be performed, but the marked position (i, j) will be reached eventually. Now M adds a mark also to the position (i  , j  ) that it reached prior to the position (i, j). Thus, after finitely many cycles a path from the position (i, j), at which M1 accepted, to the initial position (1, 1) is completely marked. (3) When the symbol at position (1, 1) is marked, then M starts to simulate M2 . It keeps on doing that until M2 halts. Now M accepts iff M2 accepts. Obviously, with the above strategy M accepts the language L = L 1 ∩ L 2 . However, there are a few technical difficulties with this strategy that we must overcome. First of all, the initial content of the various tape fields must not be destroyed when M simulates the rewrite steps of M1 or when it places the aforementioned markers. Secondly, the partial ordering > must be defined. Observe that the orderings >1 and >2 may not coincide when restricted to the input alphabet Σ. To achieve our goals, we define the alphabet Γ as follows: Γ = Σ ∪ { [c, a] | c ∈ Γ1 , a ∈ Σ } ∪ { [∗, d] | d ∈ Γ2 }. Recall that Σ is a subset of Γ2 . Thus, [∗, a] ∈ Γ for all a ∈ Σ. The symbols of the form [c, a] (c ∈ Γ1 , a ∈ Σ) will be used in step (1), when M simulates M1 . For each rewrite step of M1 that replaces an input symbol a ∈ Σ by a symbol c ∈ Γ1 , M will have a rewrite step that replaces the symbol a by the combined symbol [c, a]. In addition, for each rewrite step of M1 that replaces a symbol c ∈ Γ1 by a symbol d ∈ Γ1 , M will have rewrite steps that replace the combined symbol [c, a] by the combined symbol [d, a] for all a ∈ Σ. In this way, M can keep the original content of each tape field while simulating the rewrite steps of M1 . When M1 accepts, then M replaces the content a or [c, a] of the corresponding tape field by the symbol [∗, a]. In step (2), M performs rewrite steps of this very form. Finally, in step (3), M simulates M2 by interpreting each symbol of the form [c, a] or [∗, a] as M2 would interpret the symbol a. A rewrite step of M2 that replaces an input symbol a ∈ Σ by a symbol d ∈ Γ2 will be simulated by rewrite steps that replace the symbol

123

610

F. Otto, F. Mráz

a or the combined symbol [∗, a] or a combined symbol [c, a] (c ∈ Γ1 ) by the symbol [∗, d]. In addition, for each rewrite step of M2 that replaces a symbol x ∈ Γ2  Σ by a symbol y ∈ Γ2 , M will have a rewrite step that replaces the combined symbol [∗, x] by the combined symbol [∗, y]. It follows that indeed L(M) = L 1 ∩ L 2 holds. It remains to specify the partial ordering > on Γ . It must satisfy the following requirements: 1. For each a ∈ Σ and each c ∈ Γ1 , a > [c, a] > [∗, a]. 2. For each a ∈ Σ, the subalphabet { [c, a] | c ∈ Σ1 } is ordered using >1 on the first components. 3. The subalphabet { [∗, d] | d ∈ Γ2 } is ordered using >2 on the second components. It can be checked easily that such an ordering exists, and that in each rewrite step of M, a symbol α ∈ Γ is replaced by a symbol β ∈ Γ satisfying the condition α > β. Thus, M is indeed a det-2D-3W-ORWW-automaton for the language L 1 ∩ L 2 . Closure under union: This follows from the closures under complement and intersection. Again this proof rests on our assumption that each computation of a det-2D-3W-ORWWautomaton terminates after finitely many steps. Non-closure under projection: In [24] (see also [22]) it is shown that there exists a language L on Σ  = {0, 1, 0 , 1 } and a projection π : Σ  → {, } such that L is accepted by a deterministic Sgraffito automaton and π(L) = L ccopy . As L(2DSA) ⊆ si-2DRTL [23,25], it follows that L ∈ si-2DRTL, and hence, Theorem 4 yields that L ∈ L(det-2D-3W-ORWW). On the other hand, Proposition 1 states that L copy is not accepted by any det-2D-3W-ORWWautomaton, which by closure under complement implies that L ccopy is not accepted by any det-2D-3W-ORWW-automaton, either. It follows that L(det-2D-3W-ORWW) is not closed under projections. Observe that also this proof is based on the termination requirement for det-2D-3W-ORWW-automata. Non-closure under column concatenation: From [7] (see, also [22,24]) it is known that the complement L ccopy of the language L copy can be decomposed as follows, where Σ = {, }: L ccopy L1 L2 and L2 L3 L4

= L 1 ∪ L 2 , where = { P ∈ Σ ∗,∗ | col(P)  = 2 · row(P) }, = { Q 1 dQ 2 | Q 1 , Q 2 ∈ Σ ∗,∗ , col(Q 1 ) = col(Q 2 ) = row(Q 1 ), Q 1  = Q 2 }, = L 3 ∩ (Σ ∗,∗ dL 4 dΣ ∗,∗ ), where = { P ∈ Σ ∗,∗ | col(P) = 2 · row(P) } and = { P ∈ Σ ∗,∗ | col(P) = row(P) + 1 and ∃i : P(i, 1)  = P(i, col(P)) }.

It is easily seen that the picture languages L 1 , L 3 , and L 4 are accepted by det-2D-3W-ORWWautomata. As L(det-2D-3W-ORWW) is closed under union, and as it does not contain the language L ccopy , this implies that L 2 is not accepted by any det-2D-3W-ORWW-automaton. Together with the closure under intersection this means that the language (Σ ∗,∗ dL 4 dΣ ∗,∗ ) is not accepted by any det-2D-3W-ORWW-automaton. As Σ ∗,∗ and L 4 are accepted by automata of this type, this yields the intended non-closure property. Observe that here again we used the termination requirement for det-2D-3W-ORWW-automata.

It remains open, however, whether or not L(det-2D-3W-ORWW) is closed under the operation of row concatenation. From the closure of L(det-2D-3W-ORWW) under complement and from Proposition 1 we see that L ccopy is not accepted by any det-2D-3W-ORWW-automaton, while it is accepted by a Sgraffito automaton [22,24]. Also it is known that L ccopy belongs to the class REC [7]. On the other hand, L 1col ∈ L(det-2D-3W-ORWW) does neither belong to the class REC

123

Deterministic ordered restarting automata for picture…

611

nor is it accepted by any Sgraffito automaton, as REC as well as L(2SA) are both closed under rotation, and the only string languages either of these classes contains are the regular languages [7,22,24]. Thus, we have the following incomparability results. Corollary 2 [18] The class of picture languages L(det-2D-3W-ORWW) is incomparable to the classes L(2SA) and REC with respect to inclusion. We conclude this section with another example language that illustrates the limitations of the det-2D-3W-ORWW-automaton and that will be of use later. Let L pal be the (string) language of palindromes of even length over {a, b}, and let L pal,2 be the picture language L pal,2 = E 2 (L pal ) (see above) over Σ = {a, b, }, that is, L pal,2 = { P ∈ Σ 2,2n | n ≥ 1, P(1, 1) . . . P(1, n) = (P(1, n + 1) . . . P(1, 2n)) R , P(1, i) ∈ {a, b} and P(2, i) =  for all 1 ≤ i ≤ 2n }. Thus, L pal,2 consists of all two-row pictures such that the first row contains a palindrome of even length over {a, b}, and the second row contains -symbols. As the (string) language L pal is not regular, Theorem 3 yields the following negative result, which was announced in [17]. / L(det-2D-3W-ORWW). Proposition 2 L pal,2 ∈

5 Deterministic two-dimensional two-way ORWW-automata The det-2D-3W-ORWW-automaton clearly favors the vertical dimension of a picture over its horizontal dimension, which led to the fact that the class of picture languages L(det-2D-3W-ORWW) is not closed under transposition. Even more, while these automata only accept languages of one-row pictures that correspond to regular (string) languages, they accept much more general languages of one-column pictures (recall the language L 1col from the proof of Theorem 4). In addition, we had to require uniform termination explicitly for these automata. In order to get rid of the termination problem, and in order to mend the asymmetry between the horizontal and the vertical dimensions, we now turn to a model of the two-dimensional ORWW-automaton for which the possible window movements are even further restricted. Definition 2 [21] A deterministic two-dimensional two-way ordered restarting automaton, a det-2D-2W-ORWW-automaton for short, is given through a 7-tuple M = (Q, Σ, Γ, S , q0 , δ, >), where all components are defined as for a det-2D-3W-ORWWautomaton with the restriction that H = {R, D} is taken in the definition of the transition function δ, that is, no move-left or move-up steps are possible. We illustrate this type of automaton by an example that will be refered to later. Example 2 Let Σ = {, }, and let L 1r1cr = { P ∈ Σ ∗,∗ | rows(P) = cols(P) ≥ 1, and P1,i = Pn+1−i,1 for all i = 1, . . . , rows(P) }, that is, L 1r1cr consists of all square pictures over Σ for which the first row is identical to the reverse of the first column. An example picture is given in Fig. 2a. We now present a det-2D-2W-ORWW-automaton M1r1cr = (Q, Σ, Γ, S , q0 , δ, >) for this language. We take Γ = Σ ∪ { a  , a  | a ∈ Σ }, we define a partial ordering > by taking

123

612

F. Otto, F. Mráz

(a)

(b)

(c)

Fig. 2 An example picture P from L 1r1cr (a), and the pictures obtained from P by step 1 (b) and step 2 (c)

a > a  > a  for all a ∈ Σ, and we define the transition function δ in such a way that M1r1cr proceeds as follows given a picture P ∈ Σ n,n as input:  . Then, for j = n − 1 down to 2, 1. First the symbol P1,n is rewritten into the symbol P1,n the symbols Pi, j , i = n + 1 − j, n − j, . . . , 2, are rewritten into P1, j . Once all rewrites have been made for a value of j, then the symbol P1, j is also rewritten into the symbol P1, j . The resulting picture has the form given in Fig. 2b. 2. For all i = 1 up to n − 1, the rightmost symbol in row i that is of the form a  for some a ∈ Σ is in column n + 1 − i. It is replaced by the symbol a  , and then proceeding from right to left, the symbols Pi, j with 2 ≤ j ≤ n −i are all replaced by the symbol a  . Now it can be checked whether Pi,1 is identical to the symbol a. If so, then Pi,1 is replaced by a  as well, otherwise, the computation halts without acceptance. This process is executed row by row from 1 up to n − 1. In case of success, the resulting picture has the form given in Fig. 2c. 3. Finally, when all entries P1,1 to Pn−1,1 have been replaced by their double-primed versions, then it is checked in a tail computation whether Pn,1 = P1,1 holds. In the affirmative, M1r1cr halts and accepts.

As the window of M1r1cr is of size (3, 3), it is easily seen that δ can be defined in the required way. It follows that indeed L(M1r1cr ) = L 1r1cr holds. By transposing the contents of the window within the transition function and by interchanging move-right steps and move-down steps, it is immediate that the language class L(det-2D-2W-ORWW) is closed under transposition. In fact, the following closure and non-closure results that have been announced in [21] can be established. Theorem 6 The language class L(det-2D-2W-ORWW) is closed under transposition, union, intersection, and complement, but it is neither closed under projection nor under column or row concatenation. Proof As mentioned above the class L(det-2D-2W-ORWW) is obviously closed under transposition, and as each det-2D-2W-ORWW-automaton halts on all inputs, it is easily seen that this class is also closed under complement. Closure under intersection (and therewith also under union) is proved in exactly the same way as for det-2D-3W-ORWW-automata (see Theorem 5). Non-closure under projection: As mentioned in the proof of Theorem 5, a language L on Σ  = {0, 1, 0 , 1 } and a projection π : Σ  → {, } are presented in [22,24] such that π(L) = L ccopy . Actually, let Σ = {0, 1} and let ϕ : Σ ∗ → Σ  ∗ be the morphism that is defined by 0  → 0 and 1  → 1 . Now L is the union of two languages L 1 and L 2 , where L 1 consists of all pictures over Σ  of the form Q 1 dQ 2 , where Q 1 is a square picture over Σ  that contains exactly one symbol from {0 , 1 } at some position (i, j), and Q 2 is a square picture of the same dimension as Q 1 over Σ only such

123

Deterministic ordered restarting automata for picture…

613

that ϕ(Q 2 (i, j))  = Q 1 (i, j), and L 2 is the language of all pictures over Σ  for which the number of columns is not twice the number of rows. Obviously, L 2 is accepted by some det-2D-2W-ORWW-automaton, and it can be shown that this also holds for the language L 1 . Now from the closure under union it follows that the language L = L 1 ∪ L 2 is accepted by some det-2D-2W-ORWW-automaton. As L ccopy ∈ / L(det-2D-3W-ORWW), and as obviously L(det-2D-2W-ORWW) ⊆ L(det-2D-3W-ORWW), it follows that L(det-2D-2W-ORWW) is not closed under projections. Non-closure under column concatenation: This follows as the corresponding result in the proof of Theorem 5. It suffices to notice that the languages L 1 , L 3 , and L 4 mentioned there are accepted by det-2D-2W-ORWW-automata. Non-closure under row concatenation: This follows from the closure under transposition and the non-closure under column concatenation.

When restricted to one-row pictures, then the det-2D-2W-ORWW-automaton coincides with the det-2D-3W-ORWW-automaton, and so it only accepts regular string languages. Concerning its expressive power, we have the following result, where 2DSA denotes the deterministic Sgraffito automaton (see Sect. 3). Theorem 7 L(det-2D-2W-ORWW) ⊆ L(2DSA). Proof Let M be a det-2D-2W-ORWW-automaton with input alphabet Σ. On input P ∈ starting at the upper left corner, until it executes a Σ ∗,∗ , M scans the boundary picture P, rewrite step at some position (i, j). Now a 2DSA A can simulate the computation of M step by step until it reaches position (i, j). As A must perform a rewrite in each step, we can assume that A encodes the corresponding state of M at each position visited together with the information on the last two steps that M performed when it moved to the current position. After performing its rewrite step, M restarts, but as it is deterministic, it will follow the same path again, entering the same states at the same positions, until it reaches a position (k, l) such that the new symbol at (i, j) is contained in its window of size (3, 3). This is either position (i − 1, j) or (i, j − 1) or (i − 1, j − 1). Recall that these positions refer to the field in the middle of the window. Now the window contains the newly written symbol at position (i, j), and accordingly, M may now behave differently from the cycle before. From the information stored at position (i, j), A can extract the two last move operations that brought M to this very position, and so it can determine the position (k, l) ∈ {(i −1, j), (i, j −1), (i −1, j −1)}. Thus, A simply moves to the position (k, l), extracts the corresponding state of M from the symbol written at that position, and continues to simulate M from that point on. It follows that A can enter a particular tape field at most a constant number of times (once at the first time this position is reached by M, once each time a field immediately to the right or down is rewritten, and once again each time the contents of the field itself has been rewritten).

It is still open whether the inclusion in Theorem 7 is proper. The problem lies in the fact that, in order to simulate the computation of a 2DSA, a det-2D-2W-ORWW-automaton would have to be able to rediscover the actual head position of the 2DSA after each restart step. In fact, it is not known whether the language L perm of ‘permutations,’ which is the subset of L copy that consists of all those pictures Q dQ for which each row and each column of Q contains the symbol  exactly once, is accepted by any det-2D-2W-ORWW-automaton. It is known, however, that L perm is accepted by a 2DSA [22,24]. On the other hand, we have the following result which shows that det-2D-2W-ORWWautomata are nevertheless quite expressive.

123

614

F. Otto, F. Mráz

Theorem 8 DREC  L(det-2D-2W-ORWW). Proof The class DREC coincides with the closure of L(DOTA) under rotation, where DOTA denotes the deterministic on-line tessellation automaton (see Sect. 3). Accordingly, we first consider a DOTA A = (Σ, Q, q0 , F, δ) and show that a det-2D-2W-ORWW-automaton M can simulate A as follows: 1. Let P ∈ Σ m,n be given as input, that is, M starts in its initial state at the top left corner Observe that the states assigned by A to the positions (1, j), of the boundary picture P. j = 1, . . . , n, do only depend on the content of the first row. Hence, M can now assign and store these states in the fields in row 1, proceeding from right to left, that is, M moves from left to right across row 1 until it encounters the last field (1, j) that does not yet store a state of A, simulating the transition function of A in its finite-state control. On reaching the field (1, j), it can then store the corresponding state of A there. This continues until all fields in row 1 contain the corresponding states of the run of A on input P. 2. If the states of A have been determined and stored in all fields in row i for some i ≥ 1, then the states assigned by A to the positions in row i + 1 can be determined. Hence, M moves to row i + 1, where it can now assign and store these states in the corresponding fields, again proceeding from right to left. This process continues for all rows 2 to m −1. 3. Once the states of the run of A on input P have been stored in all fields in row m − 1, M moves to the last row, and using its finite-state control it simulates the transition function of A while moving across this row from left to right. When it reaches the last entry, that is, position (m, n), then it knows the state q that A would assign to this position. Now M halts, and it accepts if and only if q is a final state of A. It is easily seen that L(M) = L(A) holds, implying that L(DOTA) ⊆ L(det-2D-2W-ORWW). If L ∈ DREC, then there exists a language L  ∈ L(DOTA) such that L is obtained from  L by a sequence of up to three rotations. This can be interpreted as follows: L is recognized by a DOTA that, however, may determine the states of its runs by starting in one of the other corners of its input pictures. However, the above simulation of a DOTA A by a det-2D-2WORWW-automaton M can easily be adapted to any such starting position. It follows that indeed DREC ⊆ L(det-2D-2W-ORWW) holds. Finally, in order to prove that this is a proper inclusion, we recall from [1,3] that the language L frames over {, } that consists of all square pictures P for which (i) the first row equals the first column, (ii) the second row equals the reverse of the second-last column, (iii) the second-last row equals the reverse of the second column, and (iv) the last row equals the last column, is not in DREC. From the above description we see that L frames is the intersection of the four languages L i , L ii , L iii , and L iv that are given though the conditions (i) to (iv). Each of these conditions is similar to the one that is used to define the language L 1r1cr considered in Example 2, and accordingly, each of these four languages can be shown to be accepted by some det-2D-2W-ORWW-automaton. As L(det-2D-2W-ORWW) is closed under intersection, it thus follows that the language L frames is accepted by a det-2D-2WORWW-automaton.



6 Deterministic two-dimensional extended two-way ORWW-automata The det-2D-2W-ORWW-automaton does not have the termination problem of the det-2D3W-ORWW-automaton, but as L(2DSA) ⊆ si-2DRTL [23,25], we see from Theorems 4

123

Deterministic ordered restarting automata for picture…

615

and 7 that the former is strictly less expressive than the latter. Also the fact that a det-2D-2WORWW-automaton cannot scan a given picture completely in a single cycle leads to rather complicated algorithms, as witnessed by Example 2. Therefore, we now turn to an extension of this model in which the move-right and move-down steps are slightly more general. Definition 3 [17] A deterministic two-dimensional extended two-way ordered restarting automaton, a det-2D-x2W-ORWW-automaton for short, is given through a 7-tuple M = (Q, Σ, Γ, S , q0 , δ, >), where all components are defined as for a det-2D-2W-ORWWautomaton, but the move-right and move-down steps are extended as follows: 1. When the window contains the right border marker , but not the bottom marker, then an extended move-right step shifts the window to the beginning of the next row, that is, if the central position of the window is on the last field of row i for some i < rows(P), then it is moved to the first field of row i + 1. 2. When the window contains the bottom marker ⊥, but not the right border marker, then an extended move-down step shifts the window to the top of the next column, that is, if the central position of the window is on the bottom-most field of column j for some j < cols(P), then it is moved to the top-most field of column j + 1. 3. In any cycle, as soon as M executes an extended move-right (move-down) step, then for the rest of this cycle, it cannot execute any extended move-down (move-right) steps. Finally, M is called a stateless det-2D-x2W-ORWW-automaton (or a stl-det-2D-x2WORWW-automaton) if it has just a single state. The components Q and q0 refering to states will be suppressed within the description of such an automaton. When restricted to one-row pictures P ∈ Σ 1,∗ , then the det-2D-x2W-ORWW-automaton coincides with the det-2D-3W-ORWW-automaton. Thus, we obtain the following result, where the part on the stateless variant follows from the fact that each det-ORWW-automaton can be simulated by a stateless det-ORWW-automaton that uses a larger tape alphabet [20]. Corollary 3 [17] When restricted to one-row inputs, then the (stl-)det-2D-x2W-ORWWautomaton just accepts the regular (string) languages. Given a picture P ∈ Σ m,n as input, a det-2D-x2W-ORWW-automaton M can execute at most m · n · (|Γ | − 1) many cycles. In each cycle, and also in a tail computation, M can either execute up to n move-right steps, n · (m − 1) move-down steps, and (n − 1) extended move-down steps, or m move-down steps, m · (n − 1) move-right steps, and (m − 1) extended move-right steps. Thus, M executes at most O(m 2 · n 2 · (|Γ | − 1)) many steps. Hence, a two-dimensional Turing machine can simulate M in time O(m 2 · n 2 ). A multi-tape Turing machine T that stores P column by column needs m steps to simulate a single move-right step of M, and it needs m · n steps to simulate an extended move-right step. Thus, T may need up to O(m 3 · n 2 ) many steps to simulate M on an input picture of dimension (m, n). Hence, we obtain the following upper bound. Theorem 9 [17] L(det-2D-x2W-ORWW) ⊆ DTIME((size(P))3 ). In the proof of Theorem 4 we have seen how to simulate a two-dimensional deterministic restarting tiling automaton (2DRTA) that uses the scanning strategy νcol by a det-2D-3WORWW-automaton. As a 2DRTA is stateless, we can adapt this simulation to stateless det2D-x2W-ORWW-automata, deriving the following inclusion, which has been announced in [21].

123

616

F. Otto, F. Mráz

Theorem 10 si-2DRTL ⊆ L(stl-det-2D-x2W-ORWW). Proof Let M = (Σ, Γ, Θ F , δ, νcol , μ) be a 2DRTA that uses the scanning strategy νcol = (1, f col ), that is, given a picture P ∈ Σ m,n as input, M starts at the top left corner, scanning P column by column from the top to the bottom and from left to right. A stl-det-2D-x2WORWW-automaton M can simulate M as follows: – M scans the given picture column by column from left to right. This is possible as it can use extended move-down steps. – As soon as it detects an applicable rewrite operation of M, it performs the appropriate rewrite and restarts. – When it reaches the bottom right corner, then it marks this position using special copies of the original symbols from Γ , and it restarts. – In the subsequent cycles the marking is carried through the complete picture until eventually the symbol in the top left corner is also marked. – When scanning a picture that consists of marked symbols only, then M halts without accepting as soon as it detects a tile of size (2, 2) that is the marked copy of a tile that does not belong to the set Θ F . – When M reaches the bottom right corner after scanning a picture that consists of marked symbols only, then it halts and accepts, as in this case all tiles of size (2, 2) are marked copies of tiles that belong to the set Θ F , and hence, M would accept. It now follows that L(M ) = L(M). Thus, L(νcol -2DRTA) ⊆ L(stl-det-2D-x2W-ORWW),

which implies the inclusion above, as si-2DRTL ⊆ L(νcol -2DRTA).



It is still open whether or not the inclusion in Theorem 10 is a proper inclusion. A det-2Dx2W-ORWW-automaton necessarily halts for all inputs. Further, it is completely symmetric with respect to horizontal and vertical movements. From these observations the following closure properties are immediate. Proposition 3 [17] L(det-2D-x2W-ORWW) and L(stl-det-2D-x2W-ORWW) are closed under transposition and complement. Thus, the language L 1col is not accepted by any det-2D-x2W-ORWW-automaton, as T its transpose L 1col is a non-regular string language. On the other hand, the following result holds. Proposition 4 [17] L pal,2 ∈ L(det-2D-x2W-ORWW). Proof A two-way deterministic ORWW-automaton can accept the language of even-length palindromes by marking the letters with indices 1 and 2, alternating between marking the first unmarked letter from the left and the first unmarked letter from the right. Here, to distinguish between these two cases, the second row is used. Accordingly, let Mpal,2 = (Q, Σ, Γ, S , q0 , δ, >) be defined by Γ = Σ ∪ {a1 , a2 , b1 , b2 , ↑1 , ↑2 }, where a > b > a1 > b1 > a2 > b2 >  > ↑1 > ↑2 , and by defining δ in such a way that Mpal,2 proceeds as follows: – In each cycle Mpal,2 scans the first row from left to right. Depending on the form of the string contained in this row, one of the following steps is executed:

123

Deterministic ordered restarting automata for picture…

617

1. If the first row contains a string from the set {a2 , b2 }∗ ·{a, b}+ ·{a2 , b2 }∗ , then Mpal,2 must compare the first letter of the {a, b}-syllable to the last letter of this syllable. Accordingly, it executes an extended move-right step, and then it replaces the symbol  in row 2 that is below the first letter of this syllable, say d, by the symbol ↑1 and restarts. In the next cycle, when Mpal,2 encounters a symbol d ∈ {a, b} in row 1 below which the symbol ↑1 is written, then it rewrites d into d1 and restarts. 2. If the first row contains a string from the set {a2 , b2 }∗ · {a1 , b1 } · {a, b}+ · {a2 , b2 }∗ , then Mpal,2 must compare the letter d1 ∈ {a1 , b1 } to the last letter of the {a, b}syllable. If that syllable ends with the letter d, then Mpal,2 replaces that occurrence of d by d1 and restarts, otherwise, it halts without accepting. 3. If the first row contains a string from the set {a2 , b2 }∗ · {a1 , b1 } · {a, b}∗ · {a1 , b1 } · {a2 , b2 }∗ , then the letters with index 1 must be replaced by the corresponding letters with index 2. Accordingly, Mpal,2 executes an extended move-right step, and then it replaces the symbol ↑1 that is below the first letter from {a1 , b1 }, say d1 , by the symbol ↑2 and restarts. In the next cycle, when Mpal,2 encounters a symbol d1 ∈ {a1 , b1 } in row 1 below which the symbol ↑2 is written, then it rewrites d1 into d2 and restarts. 4. If the first row contains a string from the set {a2 , b2 }+ · {a, b}∗ · {a1 , b1 } · {a2 , b2 }∗ , then Mpal,2 replaces the symbol from {a1 , b1 }, say d1 , by d2 and restarts. – If the first row contains a string from {a2 , b2 }∗ , then Mpal,2 halts and accepts. It follows easily from the description above that L(Mpal,2 ) = L pal,2 .



From Proposition 2 we know that the language L pal,2 is not accepted by any det-2D-3WORWW-automaton. Hence, from the results on L 1col and L pal,2 we obtain the following. Corollary 4 [17] The classes of picture languages L(det-2D-x2W-ORWW) and L(det-2D-3W-ORWW) are incomparable under inclusion. Actually, L pal,2 also separates the det-2D-x2W-ORWW-automaton from its stateless variant. Proposition 5 [17] L pal,2 ∈ / L(stl-det-2D-x2W-ORWW). Proof Assume that M = (Σ, Γ, S , δ, >) is a stl-det-2D-x2W-ORWW-automaton over Σ = {a, b, } such that L(M) = L pal,2 . We analyze the accepting computations of M on pictures of the form Pw dPwR ∈ L pal,2 , where     a1 a2 . . . an a a an . . . a2 a1 R Pw = , Pw = , and w = a1 . . . an ∈ {a, b}n .   ...     ...   Given Pw dPwR as input, M will perform an accepting computation, which consists of a finite sequence of cycles that is followed by an accepting tail computation. We now split this computation into a finite number of phases, where we distinguish between four types of phases: 1. A left-only phase (O) consists of a sequence of cycles in which the window of M stays on the left half of the picture. 2. An upper-right phase (U ) consists of a sequence of cycles in which all rewrite steps are performed on the right half of the picture, and in addition, in the first of these cycles, M enters the right half of the picture through move-right steps in row 1.

123

618

F. Otto, F. Mráz

3. A lower-left phase (L) is a sequence of cycles in which all rewrite steps are performed in the left half of the picture, and in addition, the first of these cycles contains an extended move-right step. 4. A lower-right phase (R) is a sequence of cycles in which all rewrite steps are performed in the right half of the picture, and in addition, in the first of these cycles, M enters the right half of the picture through a move-right step in row 2 or after executing an extended move-down step. Obviously, the sequence of cycles of the computation of M on input Pw dPwR can uniquely be split into a sequence of phases if we require that each phase is of maximum length. Thus, this computation can be described in a unique way by a string α over the alphabet Ω = {O, U, L , R}. Concerning the possible changes from one phase to the next there are some restrictions based on the fact that M is stateless. – While M is in a lower-right phase (R), it just moves through the left half of the current picture after each rewrite/restart step. Thus, M cannot get into another phase until it performs a rewrite step that replaces a symbol in the first column of the right half of the picture. Only then may follow a left-only phase (O) or a lower-left phase (L). However, in a fixed column, less than 2 · |Γ | many rewrite steps can be performed, and so |α| R ≤ 1 + 2 · |Γ | follows. – When M is in a lower-left phase (L), then it can next get into a lower-right phase (R) or into an upper-right phase (U ). However, when M got into the lower-left phase, then it moved all the way right across the first row. Thus, it cannot get into an upper-right phase (U ) before a rewrite step is performed that replaces a symbol in the last column of the left half of the picture. As there are less than 2 · |Γ | many rewrite steps that can be performed on this column, we see that |α| L ≤ 1 + |α| R + 2 · |Γ | ≤ 2 + 4 · |Γ | follows. – When M is in an upper-right phase (U ), then it can next get into a lower-left phase (L) or a left-only phase (O). However, when M got into the upper-right phase, then it moved across the left half of the first row, and so it can get into a left-only phase only after a symbol in the first column of the right half of the picture has been rewritten. It follows that |α|U ≤ 1 + |α| L + 2 · |Γ | ≤ 3 + 6 · |Γ |. – A left-only phase (O) can be followed by any other phase. Thus, we obtain that |α| O ≤ 1 + |α| R + |α| L + |α|U ≤ 7 + 12 · |Γ |. It follows that |α| ≤ |α| O + |α| R + |α| L + |α|U ≤ 13 + 24 · |Γ |, that is, each computation of M consists of at most 13 + 24 · |Γ | many phases. Now we associate a generalized crossing sequence GCS(M, Pw dPwR ) to the computation of M on the input picture Pw dPwR as follows. Let α(w) ∈ {O, U, L , R}+ be the description of the sequence of phases of the accepting computation of M on input Pw dPwR . After each letter X of α(w), we insert a 2-by-2 picture      c d such that ce is the contents of the rightmost column of the left half and df is e f the contents of the leftmost column of the right half of the picture at the end of the phase represented by the letter X . Thus, GCS(M, Pw dPwR ) is a string of length at most 26+48·|Γ | over the finite alphabet Ω ∪Γ 2,2 of size 4+|Γ |4 , that is, there are only finitely many different such crossing sequences. If n is sufficiently large, then there are two strings w, x ∈ {a, b}n , w = a1 . . . an and x = b1 . . . bn , such that w  = x, but GCS(M, Pw dPwR ) = GCS(M, Px dPxR ). As M accepts both Pw dPwR and Px dPxR , it follows that M will also accept on input Pw dPxR ,

123

Deterministic ordered restarting automata for picture…

619

which contradicts our assumption on M, as Pw dPxR ∈ / L pal,2 . This completes the proof of Proposition 5.

Together with Proposition 4 this yields the following separation result. Theorem 11 [17] L(stl-det-2D-x2W-ORWW)  L(det-2D-x2W-ORWW). By using the technique from the proof of Proposition 4, also the following can be shown. Proposition 6 L copy ∈ L(det-2D-x2W-ORWW). Proof A det-2D-x2W-ORWW-automaton Mcopy for the picture language L copy works in four phases. Let P ∈ Σ m,n be a given input picture, where Σ = {, }. Then Mcopy proceeds as follows: 1. First Mcopy checks that n = 2m holds by traversing P as follows. Starting from position (1, 1), it makes a move-right step to position (1, 2). Then it executes the sequence of two move-right steps and one move-down step repeatedly until it reaches a field at the border of P. If this is not the lower right corner, then n  = 2m, and accordingly, Mcopy halts without accepting. Otherwise, n = 2m. So Mcopy marks the current field, that is, it replaces the symbol Pm,n by a marked copy, and restarts. In the next cycles, Mcopy will follow the same path through P, but as soon as it detects a marked symbol, it will also mark the previous symbol on its path and restart. Hence, after 3m − 1 cycles, the symbol P1,1 has been marked, which means that from now on, Mcopy realizes immediately after each restart that n = 2m has been verified successfully. 2. Now M proceeds to mark all the symbols in column m + 1 using another kind of mark. This is achieved by first executing repeatedly the subsequence of one move-down and one move-right step until the border at the bottom is reached, which happens at position (m, m), and then an extended move-down step takes Mcopy to the topmost field of column m + 1. Now the symbols in this column can be marked from top to bottom, which takes m cycles, and then, in the next cycle, Mcopy realizes that this marking is complete when its read/write window reaches position (m, m). As in phase 1, this information can now be carried to the starting position by using still another type of mark. 3. Using the second row and the auxiliary symbols ↑1 , ↑2 , ↑1 , ↑2 , Mcopy applies the technique from the proof of Proposition 4 to check whether row 1 of P contains a square ww over Σ. In the negative, it halts without acceptance. 4. Mcopy scans the current picture row by row, from the top to the bottom, until it detects the first row, say row i, the input symbols of which have not been replaced by 2 and 2 . It detects this row as soon as it enters row i − 1 through an extended move-right step at the end of row i − 2. Now it scans row i − 1 from left to right, and while doing so it also scans row i using the bottom row of its window. Hence, it can determine whether the next replacement in row i must be performed on the left half or on the right half of this row. At the end of row i − 1, Mcopy performs an extended move-right step, and then it executes the appropriate rewrite step in row i. 5. When all rows have been checked successfully in phase 4, then Mcopy halts and accepts on reaching the bottom right corner of the current picture. It follows that L(Mcopy ) = L copy .



As L copy is not accepted by any Sgraffito automaton [22,24], we see that

L(det-2D-x2W-ORWW) is not contained in the class L(2SA) of picture languages that

123

620

F. Otto, F. Mráz

are accepted by Sgraffito automata. However, it remains the question of whether or not L(2SA) ⊂ L(det-2D-x2W-ORWW) holds. We complete this section with two more closure properties. Theorem 12 [17] The classes of picture languages L(stl-det-2D-x2W-ORWW) and L(det-2D-x2W-ORWW) are closed under union and intersection. (i)

Proof Let Mi = (Q i , Σ, Γi , S , q0 , δi , >i ), i = 1, 2, be det-2D-x2W-ORWW-automata on Σ that accept picture languages L 1 = L(M1 ) ⊆ Σ ∗,∗ and L 2 = L(M2 ) ⊆ Σ ∗,∗ . We construct a det-2D-x2W-ORWW-automaton M = (Q, Σ, Γ, S , q0 , δ, >) such that L(M) = L 1 ∩ L 2 . Essentially, M will work as follows: 1. M first simulates M1 , that is, it behaves exactly like M1 . If M1 should get stuck on the given input, that is, M1 does not accept, then neither does M. If, however, M1 accepts, then instead of accepting, M marks the position (i, j) at which M1 accepts, using a special symbol. 2. Now M should simulate M2 . However, unless the marked position (i, j) happens to be inside the initial position of the window, M does not know that it now should simulate M2 . Therefore, it still behaves just like M1 during the tail of its accepting computation. Hence, no rewrite will be performed, but the marked position (i, j) will be reached eventually. Now M adds a mark also to the position (i  , j  ) that it reached prior to the position (i, j). However, here a problem arises if position (i, j) was reached by an extended move-right (move-down) step, as then the previous position (i  , j  ) is not inside the window when the position (i, j) is reached. In that case, M marks the first unmarked position to the right of (below) position (i, j). Continuing in this manner, the final part of row i (the lower part of column j) will eventually be completely marked. Hence, when M reaches position (i  , j  ), then it already sees that the symbol in the next row (column) is marked, and instead of performing an extended move-right (movedown) step, the symbol at position (i  , j  ) is marked. Thus, after finitely many cycles a path from the position (i, j), at which M1 accepted, to the initial position (1, 1) is completely marked. 3. When the symbol at position (1, 1) is marked, then M starts to simulate M2 . It keeps on doing that until M2 halts. Now M accepts iff M2 accepts. Obviously, with the above strategy M accepts the language L = L 1 ∩ L 2 . There are some technical difficulties with this strategy. However, they can be overcome in the same way as described in the proof of Theorem 5 using the tape alphabet Γ = Σ ∪ { [c, a] | c ∈ Γ1 , a ∈ Σ } ∪ { [∗, d] | d ∈ Γ2 } and the corresponding ordering. If M1 and M2 are stateless det-2D-x2W-ORWW-automata, then a stateless automaton M can simulate M1 during the first phase in the same way as the automaton M above. In order to simulate M2 after checking that M1 would accept the current input picture we must ensure that no instruction simulating M1 can be executed. For that we rewrite the whole picture into new symbols corresponding to the symbols of the original input picture and only after that M can continue with simulating M2 . After checking that the picture is accepted by the first stl-det-2D-x2W-ORWWautomaton M1 , the automaton M marks a path from the tape field where M1 executed its accepting step to the initial position (1, 1). Note that this marking can be done in the same way as with the automaton M using a single state and symbols of the form [∗, a], where a is the original input symbol on the corresponding field. However, even when the markings arrive at the top left corner, the stateless automaton M cannot yet start to simulate M2 , as it could encounter a position at which an instruction for simulating M1 is applicable. At this

123

Deterministic ordered restarting automata for picture…

621

point we modify the above construction. The automaton M will first mark a path from the position (1, 1) to the bottom left corner and then to the right until the bottom right corner is marked. For this process we can use symbols of the form [1, a], where 1 ∈ / Γ1 is a new symbol and a is from Σ, in such a way that symbols a ∈ Σ or [c, a] ∈ (Γ1 ∪ {∗}) × Σ are rewritten into [1, a]. Then, proceeding row by row from the bottom to the top and from right to left, symbols of the form a ∈ Σ or [c, a] with c ∈ Γ1 ∪ {∗, 1} and a ∈ Σ are replaced by [2, a]. Finally, when the initial position (1, 1) has been marked by a symbol of the form [2, a], then the automaton M starts to simulate M2 using instructions that are obtained from the instructions of M2 by replacing all symbols c ∈ Γ2 by the corresponding symbols of the form [2, c]. Finally, the ordering of the alphabet of M used above can easily be extended to a suitable ordering on the alphabet containing the additional symbols of the form [1, c] and [2, c]. Thus, we obtain a stl-det-2D-x2W-ORWW-automaton M that accepts the language L = L 1 ∩ L 2 . The closure under intersection above and the closure under complement (Proposition 3) imply that the classes of picture languages considered are also closed under union.

It remains open whether the classes of picture languages L(stl-det-2D-x2W-ORWW) or L(det-2D-x2W-ORWW) are closed under row and column concatenation, row and column closure, or projection.

7 Concluding remarks We have introduced the ordered restarting automaton for strings, and we have seen that the deterministic variant accepts only the regular languages, while the nondeterministic variant is much more expressive. Then we have generalized the deterministic ORWW-automaton from one-dimensional objects (strings) to two-dimensional objects (pictures). Actually, we have studied three types of deterministic two-dimensional ORWW-automata, the det-2D3W-ORWW-automaton, the det-2D-2W-ORWW-automaton, and the det-2D-x2W-ORWWautomaton. When restricted to one-row pictures, all these types of automata just accept the regular (string) languages, but for two-dimensional inputs, they differ vastly in their expressive power. The three-way variant, that is, the det-2D-3W-ORWW-automaton, favors vertical over horizontal movements, as it can move up and down, but only to the right, and not to the left. Accordingly, it accepts one-column pictures for which the corresponding string languages are not even context-free, which implies in particular that the corresponding class of picture languages is neither closed under transposition nor under rotation. In addition, we had to enforce termination explicitly for these automata, and this termination property was crucial for proving that the class of picture languages is closed under complement, which in turn was used for establishing closure under union. Also our proof that the language L ccopy is not accepted by a det-2D-3W-ORWW-automaton is based on the closure under complement. The two-way variant, that is, the det-2D-2W-ORWW-automaton, is symmetric with respect to horizontal and vertical movements, as it can only perform move-right and movedown steps. It is still rather expressive, but its main drawback is its inability to scan a given picture completely within a single cycle. Accordingly, we extended this model by making the move-right and move-down steps somewhat more powerful by admitting cyclic steps. The resulting model, that is, the det-2D-x2W-ORWW-automaton, is symmetric with respect to horizontal and vertical movements, it is quite expressive, but it is still a fairly intuitive model. Unfortunately, many of its closure properties are still unknown. In the diagram in Fig. 3 we present a taxonomy of the classes of picture languages accepted by these types of

123

622

F. Otto, F. Mráz

P L(det-2D-x2W-ORWW)

L(det-2D-3W-ORWW)

L(stl-det-2D-x2W-ORWW) ?

L(2SA)

si-2DRTL ?

L(2DSA) ?

REC

L(det-2D-2W-ORWW) DREC

Fig. 3 Hierarchy of classes of picture languages accepted by various types of two-dimensional automata. Question marks indicate inclusions that are not known to be proper

deterministic two-dimensional ORWW-automata and some other well-known classes of picture languages, where P denotes the class of (picture) languages for which the membership problem is solvable deterministically in polynomial time. In addition to the questions of whether all inclusions presented in the diagram in Fig. 3 are proper, many closure properties for the classes of picture languages that are accepted by the various types of deterministic two-dimensional ORWW-automata remain open. Finally, it is still not known whether or not each det-2D-3W-ORWW-automaton can be transformed into an automaton of the same type that terminates for all inputs without enforcing this explicitly by external means.

References 1. Anselmo, A., Giammarresi, D., Madonia, M.: From determinism to non-determinism in recognizable twodimensional languages. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007, Proceedings, Lecture Notes on Computer Science, vol. 4588, pp. 36–47. Springer, Heidelberg (2007) 2. Anselmo, A., Giammarresi, D., Madonia, M.: A computational model for tiling recognizable twodimensional languages. Theor. Comput. Sci. 410, 3520–3529 (2009) 3. Anselmo, A., Giammarresi, D., Madonia, M.: Deterministic and unambiguous families within recognizable two-dimensional languages. Fundam. Inform. 98, 143–166 (2010) 4. Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: SWAT 1967, Proceedings, pp. 155–160. IEEE Computer Society, Washington, DC, USA (1967) 5. Borchert, B., Reinhardt, K.: Deterministically and sudoku-deterministically recognizable picture languages. In: Loos, R., Fazekas, S., Martín-Vide, C. (eds.) LATA 2007, Preproceedings, Report 35/07, pp. 175–186. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona (2007) 6. Giammarresi, D., Restivo, A.: Recognizable picture languages. Int. J. Pattern Recognit. Artif. Intell. 6(2–3), 241–256 (1992) 7. Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 215–267. Springer, New York (1997) 8. Hennie, F.: One-tape, off-line Turing machine computations. Inf. Control 8(6), 553–578 (1965) 9. Inoue, K., Nakamura, A.: Some properties of two-dimensional on-line tessellation acceptors. Inf. Sci. 13, 95–121 (1977) 10. Janˇcar, P., Mráz, F., Plátek, M.: Characterization of context-free languages by erasing automata. In: Havel, I., Koubek, V. (eds.) MFCS 1992, Proceedings, Lecture Notes on Computer Science, vol. 629, pp. 307–314. Springer, Heidelberg (1992)

123

Deterministic ordered restarting automata for picture…

623

11. Janˇcar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT’95, Proceedings, Lecture Notes on Computer Science, vol. 965, pp. 283–292. Springer, Heidelberg (1995) 12. Jiˇriˇcka, P., Král, J.: Deterministic forgetting planar automata are more powerful than non-deterministic finite-state planar automata. In: Rozenberg, G., Thomas, W. (eds.) DLT 1999, Proceedings, pp. 71–80. World Scientific, Singapore (2000) 13. Kari, J., Moore, C.: New results on alternating and non-deterministic two-dimensional finite-state automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001, Proceedings, Lecture Notes on Computer Science, vol. 2010, pp. 396–406. Springer, Heidelberg (2001) 14. Lindgren, K., Moore, C., Nordahl, M.: Complexity of two-dimensional patterns. J. Stat. Phys. 91(5–6), 909–951 (1998) 15. Lonati, V., Pradella, M.: Picture recognizability with automata based on Wang tiles. In: Leeuwen, J.V., Muscholl, A., Peleg, D., Pokorný, J., Rumpe, B. (eds.) SOFSEM 2010, Proceedings, Lecture Notes on Computer Science, vol. 5901, pp. 576–587. Springer, Heidelberg (2010) 16. Messerschmidt, H., Stommel, M.: Church–Rosser picture languages and their applications in picture recognition. J. Autom. Lang. Comb. 16, 165–194 (2011) 17. Mráz, F., Otto, F.: Extended two-way ordered restarting automata for picture languages. In: Dediu, A.H., Martín-Vide, C., Sierra-Rodríguez, J., Truthe, B. (eds.) LATA 2014, Proceedings, Lecture Notes on Computer Science, vol. 8370, pp. 541–552. Springer, Heidelberg (2014) 18. Mráz, F., Otto, F.: Ordered restarting automata for picture languages. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Min Tjoa, A. (eds.) SOFSEM 2014, Proceedings, Lecture Notes on Computer Science, vol. 8327, pp. 431–442. Springer, Heidelberg (2014) 19. Otto, F.: Restarting automata. In: Ésik, Z., Martín-Vide, C., Mitrana, V. (eds.) Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence, vol. 25, pp. 269–303. Springer, Heidelberg (2006) 20. Otto, F.: On the descriptional complexity of deterministic ordered restarting automata. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014, Proceedings, Lecture Notes on Computer Science, vol. 8614, pp. 318–329. Springer, Heidelberg (2014) 21. Otto, F.: Restarting automata for picture languages: a survey on recent developments. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014, Proceedings, Lecture Notes on Computer Science, vol. 8587, pp. 16–41. Springer, Heidelberg (2014) 22. Pr˚uša, D., Mráz, F., Otto, F.: Two-dimensional Sgraffito automata. RAIRO Theor. Inform. Appl. 48, 505–539 (2014) 23. Pr˚uša, D., Mráz, F.: Restarting tiling automata. In: Moreira, N., Reis, R. (eds.) CIAA 2012, Proceedings, Lecture Notes on Computer Science, vol. 7381, pp. 289–300. Springer, Heidelberg (2012) 24. Pr˚uša, D., Mráz, F.: Two-dimensional sgraffito automata. In: Yen, H., Ibarra, O. (eds.) DLT 2012, Proceedings, Lecture Notes on Computer Science, vol. 7410, pp. 251–262. Springer, Heidelberg (2012) 25. Pr˚uša, D., Mráz, F.: Restarting tiling automata. Int. J. Found. Comput. Sci. 24(6), 863–878 (2013) 26. Pr˚uša, D., Mráz, F., Otto, F.: Comparing two-dimensional one-marker automata to sgraffito automata. In: Konstantinidis, S. (ed.) CIAA 2013, Proceedings, Lecture Notes on Computer Science, vol. 7982, pp. 268–279. Springer, Heidelberg (2013) 27. Pr˚uša, D., Mráz, F., Otto, F.: New results on deterministic sgraffito automata. In: Béal, M., Carton, O. (eds.) DLT 2013, Proceedings, Lecture Notes on Computer Science, vol. 7907, pp. 409–419. Springer, Heidelberg (2013) 28. Rosenfeld, A.: Isotonic grammars, parallel grammars, and picture grammars. In: Meltzer, B., Michie, D. (eds.) Machine Intelligence, vol. 6, pp. 281–294. Edinburgh University Press, Edinburgh (1971) 29. Siromoney, G., Siromoney, R., Krithivasan, K.: Abstract families of matrices and picture languages. Comput. Graph. Image Process. 1(3), 284–307 (1972)

123