# Deterministic recognizability of picture languages with Wang automata.

1 Introduction

Picture languages are a generalization of string languages to two dimensions: a picture is a two-dimensional array of elements from a finite alphabet. The literature on picture languages is rather rich of models, see e.g. [17, 15, 22, 11, 7, 12]. Here we regard class REC, the class of tiling recognizable languages, introduced in 15] with the aim to generalize to 2D the class of regular string languages. REC is a robust class that has various characterizations: for instance it is the class of picture languages that can be generated by online tessellation acceptors [16], tiling systems [14], or Wang systems [13].

In this paper we characterize REC by introducing a new model of 2D automata based on tiles. We call such model Wang automaton, since its description is based on the notation of Wang systems, i.e a particular kind of tiles called labeled Wang tiles. Wang automata combine features of both online tessellation acceptors [16] and 4-ways automata [17]: as in online tessellation acceptors, computation assigns states to each input picture position; as in 4-way automata, the input head visits the input picture following a given scanning strategy, that is a method to visit its positions.

The choice of a suitable scanning strategy is a central issue in this context. In particular it has been considered recently in [3], [10]. Here we introduce polite scanning strategies, that sort all positions in a picture, and visit each of them exactly once, in such a way that the next position to visit is always adjacent to the previous one, and depends only on this information: which neighboring positions have already been visited, and which direction we are moving from. Examples of such scanning strategies are those following the boustrophedonic order (a natural scanning strategy used by many algorithms on pictures and 2D arrays, such as shearsort [6], [3], [7]), spirals, and others.

Differently from 4-way automata, Wang automata directed by polite scanning strategies visit each position exactly once, and the next position function does not depend on the input symbol, like traditional finite state automata on strings. Nonetheless, we prove here that this kind of automata are equivalent to tiling systems, thus strictly more powerful than 4-way automata [15].

For string regular languages, two central notions are those of determinism and unambiguity. In two dimensions, the concept of unambiguity is straightforward and yields to class UREC [14]. UREC defines unambiguously tiling-recognizable languages, whose pictures are the projection of a unique element in the corresponding local language. In an effort to go towards determinism, the authors of [1] introduced an intermediate notion of "line" unambiguity, embodied in classes Row-UREC and Col-UREC, and based on backtracking at most linear in one dimension of the picture.

The concept of determinism for picture languages is still far from being well understood. The most relevant difficulty is that in 2D any notion of determinism seems to require some pre-established "scanning strategy" for reading the picture. Tiling systems are implicitly nondeterministic: REC is not closed under complement, and the membership problem is NP-complete [18]. Clearly, this latter fact severely hinders the potential applicability of the notation. The identification of a reasonably "rich" deterministic subset of REC would spur its application, since it would allow parsing linear with respect to the number of pixels of the input picture.

In past and more recent years, several different deterministic subclasses of REC have been studied, e.g. the classes defined by deterministic 4-way automata [17] or deterministic online tessellation acceptors [16]. This latter model inspired the notion of determinism of [1], that relies on four diagonal-based scanning strategies, each starting from one of the four corners of the picture. To mark this aspect, in this paper we will call the corresponding deterministic class Diag-DREC (i).

We cite also an interesting and radically different notion of determinism, proposed in [8], which is not based on prefixed scanning strategies. Such notion is built upon a definition of language recognized by a tiling system which is different from the usual one, e.g. of [15], so it is hard to compare it with other approaches. For instance, while it is decidable to check if a tiling system is diagonal-deterministic, at present we do not know anything about decidability for [8].

A new kind of tile-based automaton, closely related to Wang automata, is presented in [9]: quadrapolic automata are similar to Wang automata, in that both use variant of labeled Wang tiles for working. The main difference is that quadrapolic automata do not read an input picture by following a scanning strategy --to our knowledge, no definition of determinism for such devices is proposed in the literature. Indeed, a relevant aspect of Wang automata is the possibility to introduce a natural and decidable notion of determinism, yielding a proper subclass of REC, called Scan-DREC, which is closed under complement, rotation and mirror operations.

Among the different subclasses of Scan-DREC determined by different scanning strategies, we study here the class Snake-DREC of languages recognized by deterministic Wang automata directed by boustrophedonic scanning strategies. Snake-DREC can be defined equivalently in terms of tiling systems or online tessellation acceptors [20], and properly extends Diag-DREC while keeping some important closure properties. For instance, it is still closed under complement, rotation and symmetries. However, like Diag-DREC, it is not closed under intersection. Quite surprisingly, we found that this notion of determinism coincides with line unambiguity of Row-UREC (or Col-UREC): we show that the languages of this class can actually be recognized deterministically by following a boustrophedonic scanning strategy.

The paper is organized as follows. In Section 2 we recall some basic definitions and properties on two-dimensional languages, Wang systems, unambiguity, and determinism. In Section 3 we introduce polite scanning strategies and compare them with other scanning strategies already studied in the literature. In Section 4 we present our model of Wang automaton and prove the main theorem characterizing REC as the class of picture languages recognized by Wang automata. In Section 5 we introduce the concept of determinism natural in this framework, i.e. class Scan-DREC; we present its main properties and also compare some of its subclasses; we consider in particular class Snake-DREC [subset] Scan-DREC and prove its characterization in terms of line-unambiguity. Last, in Section 6 we draw some conclusions.

2 Preliminaries

The following definitions are taken and adapted from [15].

Let [SIGMA] be a finite alphabet. A two-dimensional array of elements of [SIGMA] is a picture over [SIGMA]. For n, m [greater than or equal to] 1, [[summation].sup.n,m] denotes the set of pictures of size (n, m), i.e. having n rows and m columns. The support of a picture of size (n, m) is the set n x m = {1,2, ..., n} x {1,2, ..., m}. # [not member of] [summation] is used when needed as a boundary symbol; [??] refers to the bordered version of picture p. That is, for p [member of] [[summation].sup.n,m], it is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

A pixel is an element p(i, j) of p. We call (i, j) the position in p of the pixel. We will sometimes use position (i,j) with i or j equal to 0, or n + 1, or m + 1 for referring to borders. We say that (i - 1, j), (i + 1,j), (i,j - 1), and (i, j + 1) are adjacent to position (i,j).

The set of all pictures over [SIGMA] is [[summation].sup.++]. A picture language is a subset of [[summation].sup.++]. If C denotes some kind of picture-accepting device, then L(C) denotes the class of picture languages recognized by such devices.

We will sometimes consider the 90[degrees] clockwise rotation, the horizontal mirror, and the vertical mirror of a picture p. E.g. if p [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are its rotation, horizontal mirror and vertical mirror, respectively. Naturally, the same operations can be applied to languages, and classes of languages, too.

Sometimes we need to consider fragments, that can be thought of as connected portions of pictures: fragments are not necessarily rectangular and can include also borders. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a fragment of the picture [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2.1 Tiling recognizable picture languages

An important class of two-dimensional languages is REC, i.e., the class of tiling-recognizable languages, originally defined in terms of tiling systems [14]. Here we define this class by using the equivalent notation introduced in [13], which is based on a variant of Wang tiles.

Labeled Wang tiles. Let [SIGMA] be a finite alphabet and K be a set of colors, containing the special color # representing borders. A labeled Wang tile (or tile for short) is a unitary square with colored edges and a label in [SIGMA]. Formally, a tile is an element A = (a, t, l, r, b) [member of] [SIGMA] x [K.sup.4], where t, b, r, l represent the colors at top, bottom, right and left edges, respectively.

For better readability, we represent labeled Wang tiles as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

In the rest of the paper, we will suppose that the Wang tilings cover the plane, so all the tiles that are beyond the borders of the considered picture will be the special tile # = (#, #, #, #, #).

For any direction d [member of] Dirs = {[up arrow], [right arrow], [left arrow], [down arrow]}, [A.sub.d] is the color of the edge of A towards direction d. We also use -d for referring to the direction opposite to d. Also, A(A) refers to the label of tile A. For example, in the case of A given by (1), [A.sub.[down arrow] = b and [lambda](A) = a. The set of tiles (including #) with labels in [SIGMA] and colors in K is [[summation].sub.4K].

We also consider partial tiles, where some colors may be undefined: the set of partial tiles is denoted by [[summation].sub.K]. The domain of a tile A is the set [[DELTA].sub.A] of directions where A is defined. Given two partial tiles A, B bearing the same label, we say that B extends A if [B.sub.d] = [A.sub.d] for every d [member of] [DELTA].sub.A]. When we need to emphasize the fact that a tile is not partial, we will call it complete.

Wang pictures. Labeled Wang tiles in [[summation].sub.4K] can be used to build pictures over [SIGMA], by using colors to check compatibility: two tiles may be adjacent only if the color of the touching edges is the same.

A picture P [member of] [[summation].sub.4K.sup.++] is called a Wang picture if all borders are colored with # and

P[(i, j).sub.[down arrow] = P[(i + 1, j).sub.[up arrow] for every 1 [less than or equal to] < n,

P[(i, j).sub.[right arrow] = P[(i, j + 1).sub.[left arrow] for every 1 [less than or equal to] j < m,

where (n, m) is the size of P. Next (on the left), the reader may find the example of a Wang picture of size (2, 2). For better readability, we represent Wang pictures by writing each common color only once, as in the figure on the right:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The label of a Wang picture P over [[summation].sub.4K] is the picture p = [lambda](P) [member of] [[summation].sup.++] having for pixels the labels of pixels of P, i.e., p(i, j) = [lambda](P(i, j)). For instance, the label of the example above is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Sometimes we need to consider Wang fragments, i.e. picture fragments whose pixels are partial tiles with compatible borders. For instance, if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the following Wang fragment:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Given [THETA] [subset or equal to] [[summation].sub.4K], the set of Wang pictures (resp. Wang fragments) built with tiles in [THETA] is denoted by [L.sub.W]([THETA]) (resp. [F.sub.W]([THETA])). Any Wang fragment is called a Wang tiling of its label.

Wang systems. A Wang system is a triple [omega] = ([SIGMA], K, [THETA]), where [SIGMA] is a finite alphabet, K is a set of colors, [THETA] is a subset of [[summation].sub.4K]. The language generated by [omega] is the language L([omega]) [subset or equal to] [[summation].sup.++] of the labels of all Wang pictures in [L.sub.W]([THETA]). Notice that a picture p [member of] L([omega]) may have more than one Wang tiling in [omega]. REC is the class of picture languages generated by Wang systems.

Example 1 The language [L.sub.center] of square pictures over {0,1}, with odd size greater than 2 and having 1 only in the center, is generated by the Wang system ([SIGMA], K, [THETA]), where K = {#, x, \, / , * } and [THETA] is the set of Wang tiles contained in picture P depicted in Figure 1.

Notice that it is straightforward to extend the previous Wang system to define the language [L'.sub.center] of square pictures with odd size, and having 1 not only in the center, but possibly elsewhere. E.g., we may set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 1 OMITTED]

Example 2 Consider the language [L.sub.half] [subset] [[summation].sup.++] of pictures of size (n,m), n [greater than or equal to] m [greater than or equal to] 4, with the first now like w x [bar.w], where [bar.w] is the reverse of w. Then [L.sub.half] is recognized by the Wang system ([SIGMA] K, [THETA]) where K = [SIGMA] [union] {*, #} and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The symbols on borders are used to connect each letter in w to the corresponding letter in w, along nested paths following a U-likeform. In Figure 2 we show an example of picture p [member of] [L.sub.half], together with its Wang tiling P [member of] [L.sub.W]([THETA]) (the colors in P are used in the figure only to emphasize the U-likeform of the resulting paths).

2.2 Unambiguous and diagonal-deterministic languages

Here we present the notions of unambiguity and determinism proposed in [14] and [1]. We adapt the basic definitions, results, and examples, proposing them with the notation of Wang systems.

Unambiguity. UREC can be defined as the class of tiling-recognizable languages whose pictures admits exactly one Wang tiling [14]. Formally, we say that a Wang system ([SIGMA], K, [THETA]) is unambiguous if, for every picture p [member of] L([omega]) there exists exactly one P [member of] [L.sub.W]([THETA]) such that p = [Lambda](P). UREC is the class of all languages generated by unambiguous Wang systems. It is known that UREC [subset] REC and, since it is undecidable whether a tiling system is unambiguous [5], it is also undecidable whether a Wang system is unambiguous.

[FIGURE 2 OMITTED]

Diagonal determinism. The notion of determinism proposed in [1] is inspired by the deterministic version of online tessellation acceptors [16], which are directed according to a corner-to-corner direction (namely, from top-left to bottom-right, or tl2br).

Consider a scanning strategy that respects the tl2br direction: any position (i, j) is read only if all the positions that are above and to the left of (i, j) have already been read. Roughly speaking, tl2br determinism means that any accepted picture p [member of] [[summation].sup.++] admits exactly one Wang tiling P [member of] [L.sub.W]([THETA]), which can be build deterministically when scanning p with any such strategy. Formally, a Wang system [omega] = ([SIGMA], K, [THETA]) is called tl2br-deterministic if, for any x, y [member of] K [union] {#} and a [member of] [SIGMA], there exists at most one tile

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By rotation, one can define d-deterministic Wang systems (d-DWS) for any corner-to-corner direction d in {tl2br, tr2bl, bl2tr, br2tl}, where t, b, l, and r stand as usual for top, bottom, left, and right, respectively.

We use Diag-DREC to denote the family of languages recognized by some d-DWS (for every corner-to-corner direction d).

Example 3 The WS of Example 1 is not tl2br-deterministic as testified by tiles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Actually, [L.sub.center] admits a tl2br-deterministic WS and hence is in Diag-DREC [4].

Example 4 The WS of Example 2 is not tl2br-deterministic as testified by tiles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] x.

Line unambiguity. Consider the side-to-side direction t2b (from top to bottom). A Wang system (K, [SIGMA], [THETA]) is called t2b-unambiguous if, for any Wang fragment X = [X.sub.1] [X.sub.2] ... [X.sub.m] [member of] [THETA].sup.1,m] [union] [{#}.sup.1,m] and a = ([a.sub.1], [a.sub.2], ..., [a.sub.m]) [member of] [summation].sup.1,m], there exists at most one Wang fragment A = [A.sub.1] [A.sub.2] ... [A.sub.m] [member of] [THETA].sup.1,m] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Similar properties define d-unambiguous Wang systems (d-UWS) for any side-to-side direction d [member of] {t2b, b2t, l2r, r2l}.

Row-UREC (resp. Col-UREC) denotes the class of row-unambiguous (resp. column-unambiguous) languages, i.e., the languages generated by t2b-UWS or b2t-UWS (resp. l2r-UWS or r2l-UWS). The following relation holds, with all strict inclusions [1]:

Diag-DREC [subset] (Col-UREC [intersection] Row-UREC) [subset] (Col-UREC [union] Row-UREC) [subset] UREC. (3)

In the rest of the paper we will use the informal term line unambiguity for referring both to row and to column unambiguity.

Example 5 The WS of Example 1 is d-unambiguous for any side-to-side direction d.

Example 6 The WS of Example 2 is not d-unambiguous for any side-to-side direction d: starting from the bottom of the picture, one does not know how to color the last row; starting from the top, one does not know where the inner U turns; starting from the side, one does not know, when moving upwards from an U to the next inner one, how to color it.

3 Two-dimensional scanning strategies

The notions of determinism in [1], [2], [10], [20] are all based on some fixed pre-established scanning strategies. This approach is rooted in a natural analogy with string languages: for instance finite state automata read their input string using a fixed strategy, usually left-to-right. The ability of moving the input head depending on the actual content of the string makes the device more powerful (e.g. Turing Machines exhibit this behavior).

Our approach basically follows the same vein, so we are going to consider strategies that do not depend on the content of the input picture. This means that the order in which we are visiting two different pictures, that have the same dimensions, is the same.

Scanning strategies are defined in terms of partial functions; for a partial function f, if the value of f at t is not defined, then we write f(t) = [perpendicular to].

Definition 3.1 A scanning strategy is a family

[mu] = [{[[mu].sub.nxm] : [{1,2, ...} [right arrow] n x m}.sub.n,m]

where each [[mu].sub.nxm] is a partial function such that [[mu].sub.nxm](t) [not equal to] [perpendicular to] for some t implies [[mu].sub.nxm](s) [not equal to][perpendicular to] for every 1 [less than or equal to] s < t; [[mu].sub.nxm] is called the scanning function over support n x m. A scanning strategy is said to be continuous if, for every t, n, and m, [[mu].sub.nxm](t + 1) is adjacent to [[mu].sub.nxm](t), provided they are both defined; it is said to be one-pass if each scanning function [[mu].sub.nxm] restricted to {1,2, ..., nm} is a bijection and [[mu].sub.nxm] (t) = [perpendicular to] for every t > nm.

Intuitively, a scanning strategy provides a method to visit positions in any picture support: [[mu].sub.nxm](t) is the position visited in n x m at time t. One-pass strategies are those that visit each position in each support exactly once.

Some one-pass scanning strategies are illustrated in Figure 3. Actually they are not fully defined: only the function [[mu].sub.3 x 4] on domain 3 x 4 is depicted, whereas the other functions should be defined analogously; each position c in 3 x 4 contains the number t such that c = [[mu].sub.3x4](t).

The strategies from (a) to (e) are all continuous: (a) has a boustrophedonic behavior, (b) draws nested L-like path, (c) draws nested U-like paths, (d) has a spiral behavior, (e) combines the behavior of (a) in the first half of the picture and (d) in the second one. The strategy (f) is not continuous and visits one row after the other, from left to right and from top to bottom.

[FIGURE 3 OMITTED]

As it is, this definition is quite general, and its generality may be source of issues. For instance, it is not uniform with respect to picture size: if we consider strings (i.e. n = 1) we could define strategies going from left to right for odd values of m, and from right to left otherwise. We could also exploit the knowledge of the input picture size to "jump", e.g. reading first the left-most (or first) character, then the last, then the second, then the last but one, and so on. Clearly this kind of strategy can be used to recognize strings like [a.sup.n] [b.sup.n] with a finite state device. We believe that this excessive flexibility is given by a kind of knowledge of the input picture which has a "global" flavor: we can rely on the exact size of the input picture, before even reading it.

In our opinion these issues could be addressed by introducing a qualitative concept, that we will call of blindness of the strategy. We consider blind a strategy which proceeds locally, by scanning adjacent positions, and cannot "see" neither the picture content, nor its size: it can only "feel" a border and an already considered position, when it reaches it. Considering the strategies presented in Figure 3, (f) is not blind, since it uses the knowledge of picture's width, after reaching the end of a row, to "jump" back to the beginning of the next row. Analogously, (e) is not blind, since it exploits the knowledge of the width of picture, to change direction when reaching its half. We accept all the other presented strategies, as they only depend on local information: already considered positions, and borders.

In the following we try to capture this idea of blindness, by adding some constraints to the scanning strategies we consider. To this aim, we shall need some notations.

Given a position y, we use edges(y) to denote the set of 4 edges adjacent to y. For every position y, and d [member of] Dirs, the edge of y in direction d is denoted by [y.sub.d], and the position adjacent to y in direction d is denoted by y [??] d.

A next-position function is a partial function n : [2.sup.Dirs] x Dirs [right arrow] Dirs such that [eta](D, d) = [perpendicular to] if -d [not member of] D. Informally, [eta] is used to chose where to go next: for a given position, we have a set of already considered edges, given by the set D of directions, and d, the direction from the "last-considered" edge; then [eta](D, d) is the direction towards the position to visit next. Clearly, if [absolute value of D] = 1, then d is the unique element of D; if [absolute value of D] = 3, then d' is uniquely determined.

Now fix any next-position function [eta], any starting corner [c.sub.s] [member of] Corners = {tl, tr, br, bl} and any starting direction [d.sub.s] [member of] Dirs. Then, for every picture support n x m, consider the following scanning function [[mu].sub.nxm] over n x m.

* The starting position is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

moreover we define [E.sub.1] as the set of outer edges (i.e. those adjacent to borders) of the picture support n x m, and we set [d.sub.1] = [d.sub.s].

* The inductive definition (ii) of [[mu].sub.nxm](t + 1) for t [greater than or equal to] 1 is given by:

[D.sub.t] = {d [member of] Dirs : [([[mu].sub.nxm](t)).sub.d] [member of] [E.sub.t]} [E.sub.t+1 = [E.sub.t] [union] edges([[mu].sub.nxm](t))

[d.sub.t+1] = [eta]([D.sub.t], [d.sub.t]) [[mu].sub.nxm](t + 1) = [[mu].sub.nxm](t) [??] [d.sub.t+1]

Notice that [[mu].sub.nxm][(1).sub.-d1] must be in [E.sub.1] for n([D.sub.1], [d.sub.1]) to be defined.

We say that [mu] = [{[[mu].sub.nxm]}.sub.n,m] is the scanning strategy induced by the triple ([eta], [c.sub.s], [d.sub.s]).

Definition 3.2 A scanning strategy is blind if it is induced by a triple ([eta], [c.sub.s], [d.sub.s]), where n is a next-position function, [c.sub.s] a starting corner, and [d.sub.s] a starting direction.

Notice that, in general, a blind scanning strategy is not one-pass. However, it is continuous and satisfies the other requirements we need. First, all scanning functions are defined by the same triple ([eta], [c.sub.s], [d.sub.s]) for every picture support; second, the next position to visit always depends only on this information: which neighboring positions have already been visited, and which direction we are moving from. This yields the following definition.

Definition 3.3 A scanning strategy is called polite if it is blind and one-pass.

Example 7 The one-pass scanning strategies represented in Figure 3(a-d) are all blind, hence polite. In particular we denote the strategies (a), (c), (d) as S, U, C, respectively.

For instance, C is induced by the triple ([[eta].sub.C], tl, [right arrow]), where its next-position function is shown in the following table. For better readability, set of directions and incoming direction (i.e. D [member of] [2.sup.Dirs], d [member of] Dirs) are graphically depicted together in a partially outlined rectangle, where marked sides correspond to elements of D. E.g. D = {[up arrow], [left arrow]}, d = [right arrow] is shown as [??].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is interesting to note that any polite scanning strategy can be described in terms of Strategies (a-d) of Figure 3 as proved in [19].

Related works. In the literature on 2D languages, two recent works considered the problem of defining pre-established scanning strategies for pictures, namely [2] and [10].

In [2] an automata model called tiling automaton is introduced, with the aim to define a general computational model for recognizable languages. This approach is centered upon the concept of scanning strategy itself, which directly depends on the size of the picture to be scanned. This definition is very general, in a sense like the one we introduced here in Definition 3.1, thus allowing complex behaviors. In practice, and like in our approach, scanning strategies presented and actually used in [2] are simpler, and do not exceed REC. Among these strategies there are some that we do not consider here, e.g. row-by-row, left-to-right scan, that we discard because is not continuous and rely on the knowledge of picture width. On the other hand, all these strategies are not more expressive than the ones considered here, as we will see next.

The very recent work [10] is also based on the concept of scanning strategy. In it, the considered strategies are "continuous" (hence called "snakes", not to be confused with the homonym we used before), in the sense that the next considered position is adjacent to the current one. This approach is similar to ours, in that it requires continuity, but different, because some knowledge of the picture size is used to define complex strategies such as Peano-Hilbert curves.

4 Wang automata

We are now able to formally introduce Wang automata and to show that they are equivalent to tiling systems.

Definition 4.1 A [mu]-directed Wang automaton ([mu]-WA) is a tuple ([SIGMA], K, [delta], [mu], F) where:

* [SIGMA] is a finite input alphabet,

* K is a finite set of colors

* F [subset] [[summation].sub.4K],

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a partial function such that each tile in [delta](A, d) extends A,

* [mu] is a polite scanning strategy induced by some ([eta], [c.sub.s], [d.sub.s]) such that [delta](A, d) [not equal to] 0 implies [eta]([[DELTA].sub.A], d) [not equal to] [perpendicular to].

A Wang automaton can be seen as having a head that visits a picture, by moving from a position to an adjacent one, and coloring at each step the edges of the position it is visiting (in a sense, the elements of [[summation].sub.K] x Dirs are the states of the automaton). For each accepting computation, the automaton produces a Wang picture whose label is equal to the input picture. The movements of the head are lead by the scanning strategy [mu], whereas the coloring operations the automaton performs are determined by a finite control formalized by function [delta]. Since the scanning strategy [mu] is polite and hence blind, the automaton visits the picture positions independently of the input symbols, and only the choice of colors to assign to edges is nondeterministic.

More precisely, the behavior of [mu]-directed Wang automaton over an input picture p can be described as follows. At the beginning, the head of the automaton points at the position in the starting corner [c.sub.s] and the current direction is set to [d.sub.s]. When the current direction is d, the head is pointing towards position y, the pixel and the colors of borders of p at position y are summarized by A, then let d' = [eta]([[DELTA].sub.A], d) and A' [member of] [delta](A, d). Hence the automaton may execute this move: color the borders of y according to A', set the current direction to d', and move to position y [??] d'. If no move is possible, the automaton halts. The input picture p is accepted if there is a computation such that the borders of the final position are colored according to some Wang tile in F.

Example 8 Consider the language [L.sub.half] presented in Example 2. Starting from the Wang system sketched in the same example, one can define an equivalent C-WA as described in Table 1. Note that [delta](A, d) has at most one element, for any A, d, so in the table these are not represented as sets. For better readability, the table also presents the next-position function [eta]. The set of accepting tiles is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is interesting to note that the set of complete tiles coincides with tile-set [THETA] of Example 2.

As illustrated in the following theorem, for nondeterministic Wang automata the choice of the scanning strategy (as long as it is polite) is not relevant from the point of view of the recognizing power of the device. In the next section we will show that this is no longer true when determinism is concerned.

Theorem 4.1 For every polite scanning strategy [mu], we have L([mu]-WA) = REC.

Proof: We show that, for every polite [mu], [mu]-directed Wang automata are equivalent to Wang systems.

First let [tau] = ([SIGMA], K, [delta], [mu], F) be a [mu]-WA recognizing a language L. Then, given A' [member of] [delta](A, d), let d' = [eta]([[DELTA].sub.A], d) and, for every direction x, set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now consider the labeled Wang tile B [member of] [[summation].sub.4(KxDirs)] defined by setting [lambda](B) = [lambda](A') and [B.sub.d] = ([A'.sub.d], f (d)) for every direction d. Together with its label, any such tile B carries simultaneously two kinds of information: [B.sub.d]'s give the colors assigned to borders by the automaton, and f (d) gives the path followed by the head of the automaton, corresponding to the scanning strategy [mu]. Moreover, for every A" [member of] F, consider all tiles

[TABLE 1 OMITTED]

C [member of] [[summation].sub.4(KxDirs)], which are like A", but have exactly one edge colored with an inbound arrow (while all the other second components are [perpendicular to]).

Let [THETA] be the set of any such B and C. One can verify that each Wang picture over [THETA] corresponds to an accepting computation of the automaton. Hence, L is the language generated by the Wang system [omega] = (K x Dirs, [SIGMA], [THETA]).

Vice versa, let [omega] = (K, [SIGMA], [THETA]) be a Wang system recognizing a language L. Then, take any polite scanning strategy [mu], and define the [mu]-WA [tau] = ([SIGMA], K, [delta], [mu], F) where F is the set of all Wang tiles over K, and [delta] is defined by setting, for each direction d and partial tile A:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

One can prove that the language generated by [tau] is L and this concludes the proof.

5 Determinism in Wang automata

In the framework of Wang automata, it is quite natural to introduce the concept of determinism:

Definition 5.1 A [mu]-WA ([SIGMA], K, [delta], [mu], F) is deterministic if [delta](A, d) has at most one element for every tile A [member of] [SIGMA] x [K.sup.4] and direction d. Deterministic [mu]-WA are denoted by [mu]-DWA. The union of classes L([mu]-DWA) over all polite scanning strategies [mu] is denoted by Scan-DREC.

If [delta] is the transition function of a [mu]-DWA, we shall write [delta](A, d) = A' instead of [delta](A, d) = {A'}.

Example 9 The C-WA in Example 8 is deterministic.

Example 10 Language [L.sub.half] presented in Example 2 can be recognized also by a U-DWA (see Table 2). The set of accepting tiles is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The first column in Table 2 is used for the outermost U, therefore going down first, then right, then up. The second column covers internal U's, following the direction down, then right, then up. The third column is for the other internal U's, i.e. following the direction down, then left, then up. As in Example 8, the set of complete tiles coincides with tile-set [THETA] of Example 2.

[TABLE 2 OMITTED]

Proposition 5.1 For any polite [mu], L([mu]-DWA) is a boolean sub-class of REC.

Proof: Given two [mu]-DWAs [tau].sub.1] and [tau].sub.2] recognizing two languages [L.sub.1] and [L.sub.2] respectively, one can reason as in [[15], Theorem 7.4] to build a [mu]-DWA recognizing the intersection [L.sub.1] [intersection] [L.sub.2] (the set of colors will be [K.sub.1] x [K.sub.2], where [K.sub.i] is the set of colors used by [[tau].sub.i]).

The closure under complement is quite easy, too. Let [tau] = ([SIGMA], K, [delta], [mu], F) be a [mu]-DWA recognizing L. We show how to build a deterministic Wang automaton recognizing the complement of L. First of all, modify [delta] so that any computation of [tau] scans the whole input picture. For example, one can use a special color [??] to complete the computations that halt prematurely: for any partial tile A, let[??] be the complete tile that extends A with color [??]; then, whenever [delta]'(A, d) is empty but [eta]([[DELTA].sub.A], d) [not equal to] [perpendicular to], then set [delta](A, d) = {[??]}; also set [delta]'(A, d) = {[??]} if A already has color [??] on some edge. Finally, let A be in F' if and only of it is not in F. One can verify that ([SIGMA], K [union]{[??]}, [delta]', [mu], F') is a [mu]-DWA accepting the complement of L.

The closure under union is a consequence of the previous properties.

Corollary 5.1 Scan-DREC is a proper subclass of REC, closed under complement, rotation and mirror.

Proof: The closure under complement is a straightforward consequence of the previous proposition. REC being not closed under complement, by Theorem 4.1 we have Scan-DREC [subset] REC. The closure under rotation (resp. mirror) is quite obvious, since one could easily define the rotation (resp. mirror) of a scanning strategy (and consequently the rotation (resp. mirror) of a [mu]-WA) and this operation preserves determinism.

Proposition 5.2 There exists a language in L(C-DW4) and not in L(S-DWA).

Proof: Consider the language [L.sub.half] defined in Example 2 and let L be its intersection with its 180[degrees] rotation, i.e., the language of pictures of size (n, m), n [greater than or equal to] m [greater than or equal to] 4, with both the first and the last rows like w x [bar.w], where [bar.w] is the reverse of w. We prove that L e L(C-DWA) \ L(S-DWA).

First of all, notice that L(C-DWA) is closed under rotation. For instance, let C' be the scanning strategy obtained as the 90[degrees] counter-clockwise rotation of C. Then any C'-DWA can be simulated by a C-DWA as follows: propagate the symbols in the first column rightwards and check them in the second spiral round; the rest of the computation is as before. Hence, [L.sub.half] being in L(C-DWA) as shown in Example 8, we get that L [member of] L(C-DWA).

On the other hand, L [not member of] L(S-DWA) by counting reasons. Let us assume by contradiction that there exists a S-DWA t recognizing L, and consider the language [T.sub.n] [subset or equal to] L formed by all square pictures of side size 2n having a fixed symbol in 2 everywhere except in the last row. For every p [member of] [T.sub.n], let k(p) be the color assigned by [tau] to the left border of position (2n, n + 1). For n great enough, the number of words over [SIGMA] of length n is greater than the number of colors used by [tau], hence there exist an integer [bar.n] > 1, two words [w.sub.1] + [w.sub.2] of length n and two pictures [p.sub.1], [p.sub.2] [member of] [T.sub.n] such that the last row of [p.sub.i] ends with [w.sub.i] for i = 1,2 and k([p.sub.1]) = k([p.sub.2]). Consider the pictures [p.sub.1] and [p.sub.2] built from [p.sub.1] and [p.sub.2] by replacing their last rows with [[bar.w].sub.1] x [w.sub.1] and [[bar.w].sub.1] x [w.sub.2], respectively. Then, the computation of [tau] over both [p'.sub.1] and [p'.sub.2] ends at position (2[bar.n], 1) with the same tile, but clearly [p'.sub.1] is in L whereas [p'.sub.2] is not, a contradiction.

Proposition 5.3 There exists a language in L (S-DWA) and not in L(C-DWA).

Proof: Consider the language [L.sub.[there exists]r=fr] of square pictures where there is at least one row that is equal to the first one.

On the one hand, it is very easy to define a S-DWA for [L.sub.[there exists]r=fr], as a S-DWA can propagate (by coloring) the symbols found in the first row to the rows below, one by one, and then check if at least one copy of the first row is present in the input picture.

On the other hand, we provide some intuition for the fact that [L.sub.[there exists]r=fr] [not member of] L(C-DWA). Let us suppose that there is a C-DWA, i.e. [tau] = ([SIGMA], K, [delta], C, F), such that L([tau]) = [L.sub.[there exists]r=fr]. We now consider w.l.o.g a generic picture p [member of] [L.sub.[there exists]r=fr] having even side size, i.e. 2n. We call w the first row of p, [p.sub.u] its upper half, [p.sub.l] its lower half (i.e. both having size (n, 2n)). It is easy to check if another copy of the row w is present in [p.sub.u] (using a technique analogous to the one used before with S-DWA). But, to check if w is present in pl, following a spiral scanning strategy, one needs to represent its content in the coloring of the lower part. Every "turn" of the spiral is able to propagate a number of symbols of w that depends on a constant k which is proportional to [absolute value of K]/[absolute value of [SIGMA]. Hence, to propagate w to the coloring of the lower part of p, the scanning of the input picture has to perform 2n/k "rounds", thus visiting completely the lower 2n/k rows of [p.sub.l]. Let us call this last subpicture [p'.sub.l], that has size (2n/k, 2n).

The following facts hold: (1) it is impossible to visit [p'.sub.l] after the first 2n/k rounds of the scanning; (2) the coloring at positions corresponding to [p'.sub.l] in p cannot encode the fact that w is (or is not) a row of [p'.sub.l], because before the first 2n/k rounds, the content of w was not completely available in the lower part of the picture; (3) it is impossible to represent the whole content of [p'.sub.l], made of 4[n.sup.2]/k symbols, in the coloring of the tiles which are partial after the first 2n/k rounds of the input picture scanning, because the number of these tiles is proportional to n.

Therefore, let us suppose that w is present in [p.sub.u] only as the first row, while it is not present in the upper n - 2n/k rows of [p.sub.l]. Because of facts (1-3), it is impossible for [tau] to state if p is in [L.sub.[there exists]r=fr], or not.

Corollary 5.2 L(S-DWA) and L(C-DWA) are incomparable.

In particular we characterize the boustrophedonic scanning strategy S in terms of line unambiguity.

Definition 5.2 Snake-DREC is the closure under rotation of L(S-DWA).

Notice that Snake-DREC was originally described by means of tiling systems or online tessellation acceptors [20]. The term snake comes from the boustrophedonic order of visiting of the pixels: if we draw the trajectory of the scanning strategy, it looks like a snake covering line by line (or column by column) the whole picture.

Theorem 5.1 Snake-DREC coincides with class Row-UREC [union] Col-UREC.

Before proving this theorem, we summarize its main consequences as follows:

Corollary 5.3 Snake-DREC is closed under complement, rotation and mirrors, but not under intersection. Moreover

Diag-DREC [subset] Snake-DREC [subset] Scan-DREC [subset or equal to] UREC.

Proof: Proposition 5.1 implies the closure under complement; the closure under rotation is obvious by definition; the closure under mirrors follows by the closure under mirrors of both Row-UREC and Col-UREC; [L.sub.[there exists]r=fr] is in Snake-DREC as shown in proof of Proposition 5.3, but its intersection with all its rotations is not [1].

The first proper inclusion is a straightforward consequence of the previous theorem and relation (3). Clearly Snake-DREC [subset or equal to] Scan-DREC [subset or equal to] UREC by definition. Snake-DREC is properly included in Scan-DREC: let Lhalf be the language defined in Example 2, and let L be its intersection with all its 90[degrees] rotations. Then L is in L(C-DWA) since L(C-DWA) is closed under rotation and [L.sub.half] [member of] L(C- DWA) by Proposition 5.2; on the other hand L is not in Snake-DREC for counting reasons similar to those used in Proposition 5.2.

[FIGURE 4 OMITTED]

Proof of Theorem 5.1

We actually show that

L (S-DWA) = L(t2b-UWS),

the proof of theorem follows by applying rotations. In one direction, the result is easy: starting from any S-DWA and using the construction of Theorem 4.1 one obtains a Wang system which is t2b-unambiguous.

The converse is less intuitive; in order to prove it, from now on let [omega] = ([SIGMA], K, [THETA]) be a t2b-UWS. We build a S-DWA

[tau] = ([SIGMA], K', [delta], S, F)

that simulates [omega]. Before formally defining [tau], let us first point out some important remarks.

Given any Wang fragment [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], there exists at most one Wang fragment A = [A.sub.1] [A.sub.2] ... [A.sub.m] [member of] [THETA].sup.l,m] satisfying relation ([2]). However, we have no guarantees that A can be built from left to right deterministically. For instance, for m = 4 and for some fixed X, [omega] may allow the choices of Wang tiles represented in Figure 4 (left).

Clearly, [omega] being t2b-unambiguous, only one branch of the graph ends with ft: the one corresponding to A. In the other cases, a backtracking linear in the length of the row is always sufficient to (eventually) determine A.

Remark 1 Since we are building a Wang tiling of a fixed row a, at each position we can choose among tiles that all have the same label. E.g., [lambda]([A.sub.1]) = [lambda]([A'.sub.1]) = [lambda]([A.sub.1]") = [a.sub.1].

Remark 2 Since co is t2b-unambiguous, the branch corresponding to A cannot contain Wang tiles with in-degree greater that one (otherwise there would exist two different Wang tilings of row a satisfying relation (2), a contradiction). In other words, if two or more branches "collapse", the successive tiles may be ignored. Then we can assume that the graph of the Wang tilings of a is actually a tree, where each tile has exactly one predecessor. We call it the tree of the Wang tiling of a in [THETA]. For the previous example, the tree is depicted in Figure 4 (right).

Similar remarks hold if we try to build the Wang tiling of row a from right to left.

To simulate co deterministically on a picture p, we proceed as follows. Let P be the unique Wang tiling of p in [L.sub.W]([THETA]). To locally represent the tree of Wang tilings of the current row, we store at each position the set a of tiles in [THETA] that may appear at the corresponding position in P. Notice that any such set [alpha] contains tiles having the same label, by Remark 1; moreover, each tile in any such set [alpha] admits exactly one predecessors in the tree, by Remark 2. The set of tile-sets [alpha] containing tiles with the same label is denoted by [PHI]; [lambda]([alpha]) is the label of any tiles in [alpha]. We also use the following convention: a, b, ... are used to denote symbols in [SIGMA]; A, B, ... are used to denote (possibly partial) tiles in [[summation].sub.K]; and [alpha],[beta], ... are used to denote elements of [PHI].

When scanning rightwards the first row of p, we compute and keep trace of the tree of its Wang tilings; at the end of the row, we determine which branch is successful (i.e, the one that corresponds to the first row of P). When scanning the second row backwards, we use such information (together with the traces we left in the previous scan) to reconstruct backwards the successful branch and, at the same time, we compute and keep trace of the tree of the Wang tilings of the current row. This procedure continues till the last row has been scanned. So, the set of colors K' of t must contain both pieces of information. This leads to the following definition:

K' = {#} [union] [PHI] [union] ([THETA] x [PHI]).

Colors in [PHI] used for the tiles in the first row and, in other rows, only at top and bottom of tiles, whereas colors in [THETA] x [PHI] are used at left and right: the role of color (A,[beta]) [member of] [THETA] x [PHI] is the following: A is the correct Wang tile that one should have chosen in the position immediately above the current one, whereas [beta] keeps trace of all possible Wang tiles that may appear in the current position.

We are now able to define the (deterministic) transition function [delta] of [tau]. It has to be a partial function

[delta] : [[summation].sub.K] x Dirs [right arrow] [[summation].sub.4K']

that satisfies two conditions: i) each Wang tiles in [delta](W d) extends W; ii) [delta](W, d) [not equal to] [perpendicular to] implies [eta]([[DELTA].sub.W], d) [not equal to] [perpendicular to], where [eta] is the next-position function associated with S. Thus, it is sufficient to define [delta](W, d) in the cases represented in Table 3: the left part of the table is used for the first and last row of the input picture, whereas the right part covers the other rows to be visited rightwards or leftwards.

In Table 3, for each W [member of] [[summation].sub.K'] such that [delta](W, d) [not equal to] [perpendicular to], a picture fragment f (W) is introduced; moreover tile-sets [[alpha].sub.0], [[alpha].sub.1], a and tile C appearing in the table are defined, for each W, by setting:

[[alpha].sub.0] = {A [member of] [lambda].sup.-1](a) | f(W) [member of] [F.sub.w]([THETA])}, (4)

[[alpha].sub.1] = {A [member of] [lambda].sup.-1] (a) | [there exists]! B [member of] [beta] such that f(W) [member of] [F.sub.w]([THETA])}, (5)

[alpha] = {A [member of] [lambda].sup.-1](a) | [there exists]! B [member of] [beta], [there exists]! C [member of] y such that f(W) [member of] [F.sub.w]([THETA])}. (6)

The uniqueness of B and C is required by Remark 2. Notice that [[alpha].sub.0] is used only at the beginning of rows, [[alpha].sub.1] only in the first row, [alpha] in all the other positions of a picture.

Finally, F is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now prove that the S-DWA [tau] = ([SIGMA], K', [delta], S, F) is equivalent to the t2b-unambiguous Wang system [omega] = ([SIGMA], K, [THETA]).

First we show that L([omega]) [subset or equal to] L([tau]). Let p [member of] L(co) and let P [member of] [L.sub.W]([THETA]) be the Wang tiling of p according to [omega]. W.l.o.g assume that p has a even number of row (the other case is similar), and let [a.sub.i,j] and [A.sub.i,j] be the pixels of p and P respectively. Then one can easily verify that the automaton [tau] accepts p producing a Wang tiling P' for p as in Figure 5, where [A.sub.i,j] [member of] [a.sub.i,j] for every i = 1,2, ..., n - 1 and j = 2,3, ..., m - 1.

[TABLE 3 OMITTED]

Vice versa, let p [member of] L([tau]) with pixels [a.sub.i,j] (again we assume w.l.o.g. that p has a even number of row), and let P' be the Wang tiling of p produced by [tau]. Then P' is as in Figure 5, for every i = 1,2, ..., n - 1 and j = 2,3, ..., m - 1. Now, for every odd i let [A.sub.i,l] be the unique element of [[alpha].sub.a,1] such that [A.sub.i,1] [A.sub.i,2] [member of] [F.sub.w]([THETA]); similarly, for every even i let [A.sub.i,m] be the unique element of [[alpha].sub.i,m] such that [A.sub.i,m-1] [A.sub.i,m] [member of] [F.sub.w]([THETA]). Moreover, let [A.sub.n,1] and [A.sub.n,2] be the unique tiles such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and, for every j= 3, ... m, let [A.sub.n,j] be the unique element of [[alpha].sub.n,j] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then it is immediate to verify that the Wang picture P with pixels [A.sub.i,j] is a Wang tiling of p and belongs to [L.sub.w]([THETA]). Hence, p [member of] L([omega]) and L([tau]) [subset] L([omega]).

[FIGURE 5 OMITTED]

Therefore, L([tau]) = L([omega]) and this proves that any t2b-UWS can be simulated by a S-DWA, thus concluding the proof of Theorem 5.1.

6 Conclusions

Wang automata are a simple and natural model for defining REC. Their main strength is coupling the power of Wang systems with simple scanning strategies, that permits a straightforward introduction of the notion of determinism. We proved here that such notion defines a relevant deterministic subclass of REC, properly containing the traditional one based on diagonal determinism. These results make WAs a worthy and relevant addition to the literature on 2D operational devices.

Among the open problems we mention the following:

* Is Scan-DREC a proper subset of UREC?

* Relation among L(C-DWA), L(S-DWA) and deterministic subclasses determined by the other significant scanning strategies, such as the ones of Figure 3 (b, c).

* Relation between Scan-DREC and deterministic 4-way automata.

As far as future work is concerned, we plan to investigate extensions of the Wang automata model, based on more complex (so "less polite") scanning strategies. For instance, we could drop the blindness requirement, thus allowing a behavior that depends on the actual content of the input picture. Or we could admit automata that are able to pass zero or more than one time over the same position. Such extensions may make the model more complex and powerful and have to be carefully considered and studied, since they could exceed REC.

received 30th November 2009, revised 29th July 2010, accepted 5th October 2010.

References

[1] M. Anselmo, D. Giammarresi, and M. Madonia. From determinism to non-determinism in recognizable two-dimensional languages. In Proc. DLT2007, volume 4588 of Lecture Notes in Computer Science, pages 36-47. Springer, 2007.

[2] M. Anselmo, D. Giammarresi, and M. Madonia. Tiling automaton: A computational model for recognizable two-dimensional languages. In Proc. CIAA 2007, volume 4783 of Lecture Notes in Computer Science, pages 290-302. Springer, 2007.

[3] M. Anselmo, D. Giammarresi, and M. Madonia. A computational model for recognizable two-dimensional languages. Theoretical Computer Science, 410(37):3520-3529, 2009.

[4] M. Anselmo, D. Giammarresi, and M. Madonia. Deterministic and unambiguous families within recognizable two-dimensional languages. Fundamenta Informaticae, 98(2-3):143-166, 2010.

[5] M. Anselmo, D. Giammarresi, M. Madonia, and A. Restivo. Unambiguous recognizable two-dimensional languages. Theoretical Informatics and Applications, 40(2):277-293, 2006.

[6] P. Behrooz. Introduction to Parallel Processing: Algorithms and Architectures. Kluwer Academic Publishers, Norwell, MA, USA, 1999.

[7] A. Bertoni, M. Goldwurm, and V. Lonati. On the complexity of unary tiling-recognizable picture languages. Fundamenta Informaticae, 91(2):231-249, 2009.

[8] B. Borchert and K. Reinhardt. Deterministically and sudoku-deterministically recognizable picture languages. In Proc. LATA 2007, 2007.

[9] S. Bozapalidis and A. Grammatikopoulou. Recognizable picture series. Journal of Automata, Languages and Combinatorics, 10(2/3):159-183, 2005.

[10] R. Brijder and H. J. Hoogeboom. Perfectly quilted rectangular snake tilings. Theoretical Computer Science, 410(16):1486-1494, 2009.

[11] A. Cherubini, S. Crespi Reghizzi, and M. Pradella. Regional languages and tiling: A unifying approach to picture grammars. In Proc. MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pages 253-264. Springer, 2008.

[12] A. Cherubini and M. Pradella. Picture languages: From Wang tiles to 2D grammars. In S. Bozapalidis and G. Rahonis, editors, Proc. CAI2009, volume 5725 of Lecture Notes in Computer Science, pages 13-46. Springer, 2009.

[13] L. de Prophetis and S. Varricchio. Recognizability of rectangular pictures by Wang systems. Journal of Automata, Languages and Combinatorics, 2(4):269-288, 1997.

[14] D. Giammarresi and A. Restivo. Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence, 6(2-3):241-256, 1992. Special Issue on Parallel Image Processing.

[15] D. Giammarresi and A. Restivo. Two-dimensional languages. In A. Salomaa and G. Rozenberg, editors, Handbook of Formal Languages, volume 3, Beyond Words, pages 215-267. Springer-Verlag, Berlin, 1997.

[16] K. Inoue and A. Nakamura. Some properties of two-dimensional on-line tessellation acceptors. Information Sciences, 13:95-121, 1977.

[17] K. Inoue and I. Takanami. A survey of two-dimensional automata theory. Information Sciences, 55(1-3):99-121, 1991.

[18] K. Lindgren, C. Moore, and M. Nordahl. Complexity of two-dimensional patterns. Journal of Statistical Physics, 91(5-6):909-951, June 1998.

[19] V. Lonati and M. Pradella. Strategies to scan pictures with automata based on Wang tiles. Submitted. Available at http://lonati.dsi.unimi.it/lavori/strategies_rapporto.pdf.

[20] V. Lonati and M. Pradella. Snake-deterministic tiling systems. In Proc. MFCS 2009, volume 5734 of Lecture Notes in Computer Science, pages 549-560. Springer, 2009.

[21] V. Lonati and M. Pradella. Picture recognizability with automata based on Wang tiles. In Proc. SOFSEM 2010, volume 5901 of Lecture Notes in Computer Science, pages 576-587. Springer, 2010.

[22] O. Matz. On piecewise testable, starfree, and recognizable picture languages. In M. Nivat, editor, Proc. FoSSaCS 1998, volume 1378 of Lecture Notes in Computer Science, pages 203-210. Springer, 1998.

(i) The original name is DREC.

(ii) In the definition, also [d.sub.t], [D.sub.t], and [E.sub.t] depend on n and m; for better readability, this dependence is not explicit. We also agree that the value of any expression containing [perpendicular to] is still [perpendicular to].

Violetta Lonati (1) ([double dagger]) and Matteo Pradella (2) ([section])

(1) Dipartimento di Scienze dell'Informazione, Universita degli Studi diMilano, Italy. Email: lonati@dsi.unimi.it

(2) IEIIT, Consiglio Nazionale delle Ricerche, Milano, Italy. Email: matteo.pradella@polimi.it

([dagger]) This work includes the results presented in the two distinct papers 20 and 21.

([double dagger]) Supported by the MIUR PRIN project "Mathematical aspects and emerging applications of automata and formal languages".

([section]) Supported by the MIUR PRIN project "D-ASAP: Dependable Adaptable Software Architecture for Pervasive Computing".

Picture languages are a generalization of string languages to two dimensions: a picture is a two-dimensional array of elements from a finite alphabet. The literature on picture languages is rather rich of models, see e.g. [17, 15, 22, 11, 7, 12]. Here we regard class REC, the class of tiling recognizable languages, introduced in 15] with the aim to generalize to 2D the class of regular string languages. REC is a robust class that has various characterizations: for instance it is the class of picture languages that can be generated by online tessellation acceptors [16], tiling systems [14], or Wang systems [13].

In this paper we characterize REC by introducing a new model of 2D automata based on tiles. We call such model Wang automaton, since its description is based on the notation of Wang systems, i.e a particular kind of tiles called labeled Wang tiles. Wang automata combine features of both online tessellation acceptors [16] and 4-ways automata [17]: as in online tessellation acceptors, computation assigns states to each input picture position; as in 4-way automata, the input head visits the input picture following a given scanning strategy, that is a method to visit its positions.

The choice of a suitable scanning strategy is a central issue in this context. In particular it has been considered recently in [3], [10]. Here we introduce polite scanning strategies, that sort all positions in a picture, and visit each of them exactly once, in such a way that the next position to visit is always adjacent to the previous one, and depends only on this information: which neighboring positions have already been visited, and which direction we are moving from. Examples of such scanning strategies are those following the boustrophedonic order (a natural scanning strategy used by many algorithms on pictures and 2D arrays, such as shearsort [6], [3], [7]), spirals, and others.

Differently from 4-way automata, Wang automata directed by polite scanning strategies visit each position exactly once, and the next position function does not depend on the input symbol, like traditional finite state automata on strings. Nonetheless, we prove here that this kind of automata are equivalent to tiling systems, thus strictly more powerful than 4-way automata [15].

For string regular languages, two central notions are those of determinism and unambiguity. In two dimensions, the concept of unambiguity is straightforward and yields to class UREC [14]. UREC defines unambiguously tiling-recognizable languages, whose pictures are the projection of a unique element in the corresponding local language. In an effort to go towards determinism, the authors of [1] introduced an intermediate notion of "line" unambiguity, embodied in classes Row-UREC and Col-UREC, and based on backtracking at most linear in one dimension of the picture.

The concept of determinism for picture languages is still far from being well understood. The most relevant difficulty is that in 2D any notion of determinism seems to require some pre-established "scanning strategy" for reading the picture. Tiling systems are implicitly nondeterministic: REC is not closed under complement, and the membership problem is NP-complete [18]. Clearly, this latter fact severely hinders the potential applicability of the notation. The identification of a reasonably "rich" deterministic subset of REC would spur its application, since it would allow parsing linear with respect to the number of pixels of the input picture.

In past and more recent years, several different deterministic subclasses of REC have been studied, e.g. the classes defined by deterministic 4-way automata [17] or deterministic online tessellation acceptors [16]. This latter model inspired the notion of determinism of [1], that relies on four diagonal-based scanning strategies, each starting from one of the four corners of the picture. To mark this aspect, in this paper we will call the corresponding deterministic class Diag-DREC (i).

We cite also an interesting and radically different notion of determinism, proposed in [8], which is not based on prefixed scanning strategies. Such notion is built upon a definition of language recognized by a tiling system which is different from the usual one, e.g. of [15], so it is hard to compare it with other approaches. For instance, while it is decidable to check if a tiling system is diagonal-deterministic, at present we do not know anything about decidability for [8].

A new kind of tile-based automaton, closely related to Wang automata, is presented in [9]: quadrapolic automata are similar to Wang automata, in that both use variant of labeled Wang tiles for working. The main difference is that quadrapolic automata do not read an input picture by following a scanning strategy --to our knowledge, no definition of determinism for such devices is proposed in the literature. Indeed, a relevant aspect of Wang automata is the possibility to introduce a natural and decidable notion of determinism, yielding a proper subclass of REC, called Scan-DREC, which is closed under complement, rotation and mirror operations.

Among the different subclasses of Scan-DREC determined by different scanning strategies, we study here the class Snake-DREC of languages recognized by deterministic Wang automata directed by boustrophedonic scanning strategies. Snake-DREC can be defined equivalently in terms of tiling systems or online tessellation acceptors [20], and properly extends Diag-DREC while keeping some important closure properties. For instance, it is still closed under complement, rotation and symmetries. However, like Diag-DREC, it is not closed under intersection. Quite surprisingly, we found that this notion of determinism coincides with line unambiguity of Row-UREC (or Col-UREC): we show that the languages of this class can actually be recognized deterministically by following a boustrophedonic scanning strategy.

The paper is organized as follows. In Section 2 we recall some basic definitions and properties on two-dimensional languages, Wang systems, unambiguity, and determinism. In Section 3 we introduce polite scanning strategies and compare them with other scanning strategies already studied in the literature. In Section 4 we present our model of Wang automaton and prove the main theorem characterizing REC as the class of picture languages recognized by Wang automata. In Section 5 we introduce the concept of determinism natural in this framework, i.e. class Scan-DREC; we present its main properties and also compare some of its subclasses; we consider in particular class Snake-DREC [subset] Scan-DREC and prove its characterization in terms of line-unambiguity. Last, in Section 6 we draw some conclusions.

2 Preliminaries

The following definitions are taken and adapted from [15].

Let [SIGMA] be a finite alphabet. A two-dimensional array of elements of [SIGMA] is a picture over [SIGMA]. For n, m [greater than or equal to] 1, [[summation].sup.n,m] denotes the set of pictures of size (n, m), i.e. having n rows and m columns. The support of a picture of size (n, m) is the set n x m = {1,2, ..., n} x {1,2, ..., m}. # [not member of] [summation] is used when needed as a boundary symbol; [??] refers to the bordered version of picture p. That is, for p [member of] [[summation].sup.n,m], it is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

A pixel is an element p(i, j) of p. We call (i, j) the position in p of the pixel. We will sometimes use position (i,j) with i or j equal to 0, or n + 1, or m + 1 for referring to borders. We say that (i - 1, j), (i + 1,j), (i,j - 1), and (i, j + 1) are adjacent to position (i,j).

The set of all pictures over [SIGMA] is [[summation].sup.++]. A picture language is a subset of [[summation].sup.++]. If C denotes some kind of picture-accepting device, then L(C) denotes the class of picture languages recognized by such devices.

We will sometimes consider the 90[degrees] clockwise rotation, the horizontal mirror, and the vertical mirror of a picture p. E.g. if p [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are its rotation, horizontal mirror and vertical mirror, respectively. Naturally, the same operations can be applied to languages, and classes of languages, too.

Sometimes we need to consider fragments, that can be thought of as connected portions of pictures: fragments are not necessarily rectangular and can include also borders. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a fragment of the picture [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2.1 Tiling recognizable picture languages

An important class of two-dimensional languages is REC, i.e., the class of tiling-recognizable languages, originally defined in terms of tiling systems [14]. Here we define this class by using the equivalent notation introduced in [13], which is based on a variant of Wang tiles.

Labeled Wang tiles. Let [SIGMA] be a finite alphabet and K be a set of colors, containing the special color # representing borders. A labeled Wang tile (or tile for short) is a unitary square with colored edges and a label in [SIGMA]. Formally, a tile is an element A = (a, t, l, r, b) [member of] [SIGMA] x [K.sup.4], where t, b, r, l represent the colors at top, bottom, right and left edges, respectively.

For better readability, we represent labeled Wang tiles as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

In the rest of the paper, we will suppose that the Wang tilings cover the plane, so all the tiles that are beyond the borders of the considered picture will be the special tile # = (#, #, #, #, #).

For any direction d [member of] Dirs = {[up arrow], [right arrow], [left arrow], [down arrow]}, [A.sub.d] is the color of the edge of A towards direction d. We also use -d for referring to the direction opposite to d. Also, A(A) refers to the label of tile A. For example, in the case of A given by (1), [A.sub.[down arrow] = b and [lambda](A) = a. The set of tiles (including #) with labels in [SIGMA] and colors in K is [[summation].sub.4K].

We also consider partial tiles, where some colors may be undefined: the set of partial tiles is denoted by [[summation].sub.K]. The domain of a tile A is the set [[DELTA].sub.A] of directions where A is defined. Given two partial tiles A, B bearing the same label, we say that B extends A if [B.sub.d] = [A.sub.d] for every d [member of] [DELTA].sub.A]. When we need to emphasize the fact that a tile is not partial, we will call it complete.

Wang pictures. Labeled Wang tiles in [[summation].sub.4K] can be used to build pictures over [SIGMA], by using colors to check compatibility: two tiles may be adjacent only if the color of the touching edges is the same.

A picture P [member of] [[summation].sub.4K.sup.++] is called a Wang picture if all borders are colored with # and

P[(i, j).sub.[down arrow] = P[(i + 1, j).sub.[up arrow] for every 1 [less than or equal to] < n,

P[(i, j).sub.[right arrow] = P[(i, j + 1).sub.[left arrow] for every 1 [less than or equal to] j < m,

where (n, m) is the size of P. Next (on the left), the reader may find the example of a Wang picture of size (2, 2). For better readability, we represent Wang pictures by writing each common color only once, as in the figure on the right:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The label of a Wang picture P over [[summation].sub.4K] is the picture p = [lambda](P) [member of] [[summation].sup.++] having for pixels the labels of pixels of P, i.e., p(i, j) = [lambda](P(i, j)). For instance, the label of the example above is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Sometimes we need to consider Wang fragments, i.e. picture fragments whose pixels are partial tiles with compatible borders. For instance, if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the following Wang fragment:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Given [THETA] [subset or equal to] [[summation].sub.4K], the set of Wang pictures (resp. Wang fragments) built with tiles in [THETA] is denoted by [L.sub.W]([THETA]) (resp. [F.sub.W]([THETA])). Any Wang fragment is called a Wang tiling of its label.

Wang systems. A Wang system is a triple [omega] = ([SIGMA], K, [THETA]), where [SIGMA] is a finite alphabet, K is a set of colors, [THETA] is a subset of [[summation].sub.4K]. The language generated by [omega] is the language L([omega]) [subset or equal to] [[summation].sup.++] of the labels of all Wang pictures in [L.sub.W]([THETA]). Notice that a picture p [member of] L([omega]) may have more than one Wang tiling in [omega]. REC is the class of picture languages generated by Wang systems.

Example 1 The language [L.sub.center] of square pictures over {0,1}, with odd size greater than 2 and having 1 only in the center, is generated by the Wang system ([SIGMA], K, [THETA]), where K = {#, x, \, / , * } and [THETA] is the set of Wang tiles contained in picture P depicted in Figure 1.

Notice that it is straightforward to extend the previous Wang system to define the language [L'.sub.center] of square pictures with odd size, and having 1 not only in the center, but possibly elsewhere. E.g., we may set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 1 OMITTED]

Example 2 Consider the language [L.sub.half] [subset] [[summation].sup.++] of pictures of size (n,m), n [greater than or equal to] m [greater than or equal to] 4, with the first now like w x [bar.w], where [bar.w] is the reverse of w. Then [L.sub.half] is recognized by the Wang system ([SIGMA] K, [THETA]) where K = [SIGMA] [union] {*, #} and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The symbols on borders are used to connect each letter in w to the corresponding letter in w, along nested paths following a U-likeform. In Figure 2 we show an example of picture p [member of] [L.sub.half], together with its Wang tiling P [member of] [L.sub.W]([THETA]) (the colors in P are used in the figure only to emphasize the U-likeform of the resulting paths).

2.2 Unambiguous and diagonal-deterministic languages

Here we present the notions of unambiguity and determinism proposed in [14] and [1]. We adapt the basic definitions, results, and examples, proposing them with the notation of Wang systems.

Unambiguity. UREC can be defined as the class of tiling-recognizable languages whose pictures admits exactly one Wang tiling [14]. Formally, we say that a Wang system ([SIGMA], K, [THETA]) is unambiguous if, for every picture p [member of] L([omega]) there exists exactly one P [member of] [L.sub.W]([THETA]) such that p = [Lambda](P). UREC is the class of all languages generated by unambiguous Wang systems. It is known that UREC [subset] REC and, since it is undecidable whether a tiling system is unambiguous [5], it is also undecidable whether a Wang system is unambiguous.

[FIGURE 2 OMITTED]

Diagonal determinism. The notion of determinism proposed in [1] is inspired by the deterministic version of online tessellation acceptors [16], which are directed according to a corner-to-corner direction (namely, from top-left to bottom-right, or tl2br).

Consider a scanning strategy that respects the tl2br direction: any position (i, j) is read only if all the positions that are above and to the left of (i, j) have already been read. Roughly speaking, tl2br determinism means that any accepted picture p [member of] [[summation].sup.++] admits exactly one Wang tiling P [member of] [L.sub.W]([THETA]), which can be build deterministically when scanning p with any such strategy. Formally, a Wang system [omega] = ([SIGMA], K, [THETA]) is called tl2br-deterministic if, for any x, y [member of] K [union] {#} and a [member of] [SIGMA], there exists at most one tile

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By rotation, one can define d-deterministic Wang systems (d-DWS) for any corner-to-corner direction d in {tl2br, tr2bl, bl2tr, br2tl}, where t, b, l, and r stand as usual for top, bottom, left, and right, respectively.

We use Diag-DREC to denote the family of languages recognized by some d-DWS (for every corner-to-corner direction d).

Example 3 The WS of Example 1 is not tl2br-deterministic as testified by tiles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Actually, [L.sub.center] admits a tl2br-deterministic WS and hence is in Diag-DREC [4].

Example 4 The WS of Example 2 is not tl2br-deterministic as testified by tiles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] x.

Line unambiguity. Consider the side-to-side direction t2b (from top to bottom). A Wang system (K, [SIGMA], [THETA]) is called t2b-unambiguous if, for any Wang fragment X = [X.sub.1] [X.sub.2] ... [X.sub.m] [member of] [THETA].sup.1,m] [union] [{#}.sup.1,m] and a = ([a.sub.1], [a.sub.2], ..., [a.sub.m]) [member of] [summation].sup.1,m], there exists at most one Wang fragment A = [A.sub.1] [A.sub.2] ... [A.sub.m] [member of] [THETA].sup.1,m] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Similar properties define d-unambiguous Wang systems (d-UWS) for any side-to-side direction d [member of] {t2b, b2t, l2r, r2l}.

Row-UREC (resp. Col-UREC) denotes the class of row-unambiguous (resp. column-unambiguous) languages, i.e., the languages generated by t2b-UWS or b2t-UWS (resp. l2r-UWS or r2l-UWS). The following relation holds, with all strict inclusions [1]:

Diag-DREC [subset] (Col-UREC [intersection] Row-UREC) [subset] (Col-UREC [union] Row-UREC) [subset] UREC. (3)

In the rest of the paper we will use the informal term line unambiguity for referring both to row and to column unambiguity.

Example 5 The WS of Example 1 is d-unambiguous for any side-to-side direction d.

Example 6 The WS of Example 2 is not d-unambiguous for any side-to-side direction d: starting from the bottom of the picture, one does not know how to color the last row; starting from the top, one does not know where the inner U turns; starting from the side, one does not know, when moving upwards from an U to the next inner one, how to color it.

3 Two-dimensional scanning strategies

The notions of determinism in [1], [2], [10], [20] are all based on some fixed pre-established scanning strategies. This approach is rooted in a natural analogy with string languages: for instance finite state automata read their input string using a fixed strategy, usually left-to-right. The ability of moving the input head depending on the actual content of the string makes the device more powerful (e.g. Turing Machines exhibit this behavior).

Our approach basically follows the same vein, so we are going to consider strategies that do not depend on the content of the input picture. This means that the order in which we are visiting two different pictures, that have the same dimensions, is the same.

Scanning strategies are defined in terms of partial functions; for a partial function f, if the value of f at t is not defined, then we write f(t) = [perpendicular to].

Definition 3.1 A scanning strategy is a family

[mu] = [{[[mu].sub.nxm] : [{1,2, ...} [right arrow] n x m}.sub.n,m]

where each [[mu].sub.nxm] is a partial function such that [[mu].sub.nxm](t) [not equal to] [perpendicular to] for some t implies [[mu].sub.nxm](s) [not equal to][perpendicular to] for every 1 [less than or equal to] s < t; [[mu].sub.nxm] is called the scanning function over support n x m. A scanning strategy is said to be continuous if, for every t, n, and m, [[mu].sub.nxm](t + 1) is adjacent to [[mu].sub.nxm](t), provided they are both defined; it is said to be one-pass if each scanning function [[mu].sub.nxm] restricted to {1,2, ..., nm} is a bijection and [[mu].sub.nxm] (t) = [perpendicular to] for every t > nm.

Intuitively, a scanning strategy provides a method to visit positions in any picture support: [[mu].sub.nxm](t) is the position visited in n x m at time t. One-pass strategies are those that visit each position in each support exactly once.

Some one-pass scanning strategies are illustrated in Figure 3. Actually they are not fully defined: only the function [[mu].sub.3 x 4] on domain 3 x 4 is depicted, whereas the other functions should be defined analogously; each position c in 3 x 4 contains the number t such that c = [[mu].sub.3x4](t).

The strategies from (a) to (e) are all continuous: (a) has a boustrophedonic behavior, (b) draws nested L-like path, (c) draws nested U-like paths, (d) has a spiral behavior, (e) combines the behavior of (a) in the first half of the picture and (d) in the second one. The strategy (f) is not continuous and visits one row after the other, from left to right and from top to bottom.

[FIGURE 3 OMITTED]

As it is, this definition is quite general, and its generality may be source of issues. For instance, it is not uniform with respect to picture size: if we consider strings (i.e. n = 1) we could define strategies going from left to right for odd values of m, and from right to left otherwise. We could also exploit the knowledge of the input picture size to "jump", e.g. reading first the left-most (or first) character, then the last, then the second, then the last but one, and so on. Clearly this kind of strategy can be used to recognize strings like [a.sup.n] [b.sup.n] with a finite state device. We believe that this excessive flexibility is given by a kind of knowledge of the input picture which has a "global" flavor: we can rely on the exact size of the input picture, before even reading it.

In our opinion these issues could be addressed by introducing a qualitative concept, that we will call of blindness of the strategy. We consider blind a strategy which proceeds locally, by scanning adjacent positions, and cannot "see" neither the picture content, nor its size: it can only "feel" a border and an already considered position, when it reaches it. Considering the strategies presented in Figure 3, (f) is not blind, since it uses the knowledge of picture's width, after reaching the end of a row, to "jump" back to the beginning of the next row. Analogously, (e) is not blind, since it exploits the knowledge of the width of picture, to change direction when reaching its half. We accept all the other presented strategies, as they only depend on local information: already considered positions, and borders.

In the following we try to capture this idea of blindness, by adding some constraints to the scanning strategies we consider. To this aim, we shall need some notations.

Given a position y, we use edges(y) to denote the set of 4 edges adjacent to y. For every position y, and d [member of] Dirs, the edge of y in direction d is denoted by [y.sub.d], and the position adjacent to y in direction d is denoted by y [??] d.

A next-position function is a partial function n : [2.sup.Dirs] x Dirs [right arrow] Dirs such that [eta](D, d) = [perpendicular to] if -d [not member of] D. Informally, [eta] is used to chose where to go next: for a given position, we have a set of already considered edges, given by the set D of directions, and d, the direction from the "last-considered" edge; then [eta](D, d) is the direction towards the position to visit next. Clearly, if [absolute value of D] = 1, then d is the unique element of D; if [absolute value of D] = 3, then d' is uniquely determined.

Now fix any next-position function [eta], any starting corner [c.sub.s] [member of] Corners = {tl, tr, br, bl} and any starting direction [d.sub.s] [member of] Dirs. Then, for every picture support n x m, consider the following scanning function [[mu].sub.nxm] over n x m.

* The starting position is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

moreover we define [E.sub.1] as the set of outer edges (i.e. those adjacent to borders) of the picture support n x m, and we set [d.sub.1] = [d.sub.s].

* The inductive definition (ii) of [[mu].sub.nxm](t + 1) for t [greater than or equal to] 1 is given by:

[D.sub.t] = {d [member of] Dirs : [([[mu].sub.nxm](t)).sub.d] [member of] [E.sub.t]} [E.sub.t+1 = [E.sub.t] [union] edges([[mu].sub.nxm](t))

[d.sub.t+1] = [eta]([D.sub.t], [d.sub.t]) [[mu].sub.nxm](t + 1) = [[mu].sub.nxm](t) [??] [d.sub.t+1]

Notice that [[mu].sub.nxm][(1).sub.-d1] must be in [E.sub.1] for n([D.sub.1], [d.sub.1]) to be defined.

We say that [mu] = [{[[mu].sub.nxm]}.sub.n,m] is the scanning strategy induced by the triple ([eta], [c.sub.s], [d.sub.s]).

Definition 3.2 A scanning strategy is blind if it is induced by a triple ([eta], [c.sub.s], [d.sub.s]), where n is a next-position function, [c.sub.s] a starting corner, and [d.sub.s] a starting direction.

Notice that, in general, a blind scanning strategy is not one-pass. However, it is continuous and satisfies the other requirements we need. First, all scanning functions are defined by the same triple ([eta], [c.sub.s], [d.sub.s]) for every picture support; second, the next position to visit always depends only on this information: which neighboring positions have already been visited, and which direction we are moving from. This yields the following definition.

Definition 3.3 A scanning strategy is called polite if it is blind and one-pass.

Example 7 The one-pass scanning strategies represented in Figure 3(a-d) are all blind, hence polite. In particular we denote the strategies (a), (c), (d) as S, U, C, respectively.

For instance, C is induced by the triple ([[eta].sub.C], tl, [right arrow]), where its next-position function is shown in the following table. For better readability, set of directions and incoming direction (i.e. D [member of] [2.sup.Dirs], d [member of] Dirs) are graphically depicted together in a partially outlined rectangle, where marked sides correspond to elements of D. E.g. D = {[up arrow], [left arrow]}, d = [right arrow] is shown as [??].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is interesting to note that any polite scanning strategy can be described in terms of Strategies (a-d) of Figure 3 as proved in [19].

Related works. In the literature on 2D languages, two recent works considered the problem of defining pre-established scanning strategies for pictures, namely [2] and [10].

In [2] an automata model called tiling automaton is introduced, with the aim to define a general computational model for recognizable languages. This approach is centered upon the concept of scanning strategy itself, which directly depends on the size of the picture to be scanned. This definition is very general, in a sense like the one we introduced here in Definition 3.1, thus allowing complex behaviors. In practice, and like in our approach, scanning strategies presented and actually used in [2] are simpler, and do not exceed REC. Among these strategies there are some that we do not consider here, e.g. row-by-row, left-to-right scan, that we discard because is not continuous and rely on the knowledge of picture width. On the other hand, all these strategies are not more expressive than the ones considered here, as we will see next.

The very recent work [10] is also based on the concept of scanning strategy. In it, the considered strategies are "continuous" (hence called "snakes", not to be confused with the homonym we used before), in the sense that the next considered position is adjacent to the current one. This approach is similar to ours, in that it requires continuity, but different, because some knowledge of the picture size is used to define complex strategies such as Peano-Hilbert curves.

4 Wang automata

We are now able to formally introduce Wang automata and to show that they are equivalent to tiling systems.

Definition 4.1 A [mu]-directed Wang automaton ([mu]-WA) is a tuple ([SIGMA], K, [delta], [mu], F) where:

* [SIGMA] is a finite input alphabet,

* K is a finite set of colors

* F [subset] [[summation].sub.4K],

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a partial function such that each tile in [delta](A, d) extends A,

* [mu] is a polite scanning strategy induced by some ([eta], [c.sub.s], [d.sub.s]) such that [delta](A, d) [not equal to] 0 implies [eta]([[DELTA].sub.A], d) [not equal to] [perpendicular to].

A Wang automaton can be seen as having a head that visits a picture, by moving from a position to an adjacent one, and coloring at each step the edges of the position it is visiting (in a sense, the elements of [[summation].sub.K] x Dirs are the states of the automaton). For each accepting computation, the automaton produces a Wang picture whose label is equal to the input picture. The movements of the head are lead by the scanning strategy [mu], whereas the coloring operations the automaton performs are determined by a finite control formalized by function [delta]. Since the scanning strategy [mu] is polite and hence blind, the automaton visits the picture positions independently of the input symbols, and only the choice of colors to assign to edges is nondeterministic.

More precisely, the behavior of [mu]-directed Wang automaton over an input picture p can be described as follows. At the beginning, the head of the automaton points at the position in the starting corner [c.sub.s] and the current direction is set to [d.sub.s]. When the current direction is d, the head is pointing towards position y, the pixel and the colors of borders of p at position y are summarized by A, then let d' = [eta]([[DELTA].sub.A], d) and A' [member of] [delta](A, d). Hence the automaton may execute this move: color the borders of y according to A', set the current direction to d', and move to position y [??] d'. If no move is possible, the automaton halts. The input picture p is accepted if there is a computation such that the borders of the final position are colored according to some Wang tile in F.

Example 8 Consider the language [L.sub.half] presented in Example 2. Starting from the Wang system sketched in the same example, one can define an equivalent C-WA as described in Table 1. Note that [delta](A, d) has at most one element, for any A, d, so in the table these are not represented as sets. For better readability, the table also presents the next-position function [eta]. The set of accepting tiles is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is interesting to note that the set of complete tiles coincides with tile-set [THETA] of Example 2.

As illustrated in the following theorem, for nondeterministic Wang automata the choice of the scanning strategy (as long as it is polite) is not relevant from the point of view of the recognizing power of the device. In the next section we will show that this is no longer true when determinism is concerned.

Theorem 4.1 For every polite scanning strategy [mu], we have L([mu]-WA) = REC.

Proof: We show that, for every polite [mu], [mu]-directed Wang automata are equivalent to Wang systems.

First let [tau] = ([SIGMA], K, [delta], [mu], F) be a [mu]-WA recognizing a language L. Then, given A' [member of] [delta](A, d), let d' = [eta]([[DELTA].sub.A], d) and, for every direction x, set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now consider the labeled Wang tile B [member of] [[summation].sub.4(KxDirs)] defined by setting [lambda](B) = [lambda](A') and [B.sub.d] = ([A'.sub.d], f (d)) for every direction d. Together with its label, any such tile B carries simultaneously two kinds of information: [B.sub.d]'s give the colors assigned to borders by the automaton, and f (d) gives the path followed by the head of the automaton, corresponding to the scanning strategy [mu]. Moreover, for every A" [member of] F, consider all tiles

[TABLE 1 OMITTED]

C [member of] [[summation].sub.4(KxDirs)], which are like A", but have exactly one edge colored with an inbound arrow (while all the other second components are [perpendicular to]).

Let [THETA] be the set of any such B and C. One can verify that each Wang picture over [THETA] corresponds to an accepting computation of the automaton. Hence, L is the language generated by the Wang system [omega] = (K x Dirs, [SIGMA], [THETA]).

Vice versa, let [omega] = (K, [SIGMA], [THETA]) be a Wang system recognizing a language L. Then, take any polite scanning strategy [mu], and define the [mu]-WA [tau] = ([SIGMA], K, [delta], [mu], F) where F is the set of all Wang tiles over K, and [delta] is defined by setting, for each direction d and partial tile A:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

One can prove that the language generated by [tau] is L and this concludes the proof.

5 Determinism in Wang automata

In the framework of Wang automata, it is quite natural to introduce the concept of determinism:

Definition 5.1 A [mu]-WA ([SIGMA], K, [delta], [mu], F) is deterministic if [delta](A, d) has at most one element for every tile A [member of] [SIGMA] x [K.sup.4] and direction d. Deterministic [mu]-WA are denoted by [mu]-DWA. The union of classes L([mu]-DWA) over all polite scanning strategies [mu] is denoted by Scan-DREC.

If [delta] is the transition function of a [mu]-DWA, we shall write [delta](A, d) = A' instead of [delta](A, d) = {A'}.

Example 9 The C-WA in Example 8 is deterministic.

Example 10 Language [L.sub.half] presented in Example 2 can be recognized also by a U-DWA (see Table 2). The set of accepting tiles is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The first column in Table 2 is used for the outermost U, therefore going down first, then right, then up. The second column covers internal U's, following the direction down, then right, then up. The third column is for the other internal U's, i.e. following the direction down, then left, then up. As in Example 8, the set of complete tiles coincides with tile-set [THETA] of Example 2.

[TABLE 2 OMITTED]

Proposition 5.1 For any polite [mu], L([mu]-DWA) is a boolean sub-class of REC.

Proof: Given two [mu]-DWAs [tau].sub.1] and [tau].sub.2] recognizing two languages [L.sub.1] and [L.sub.2] respectively, one can reason as in [[15], Theorem 7.4] to build a [mu]-DWA recognizing the intersection [L.sub.1] [intersection] [L.sub.2] (the set of colors will be [K.sub.1] x [K.sub.2], where [K.sub.i] is the set of colors used by [[tau].sub.i]).

The closure under complement is quite easy, too. Let [tau] = ([SIGMA], K, [delta], [mu], F) be a [mu]-DWA recognizing L. We show how to build a deterministic Wang automaton recognizing the complement of L. First of all, modify [delta] so that any computation of [tau] scans the whole input picture. For example, one can use a special color [??] to complete the computations that halt prematurely: for any partial tile A, let[??] be the complete tile that extends A with color [??]; then, whenever [delta]'(A, d) is empty but [eta]([[DELTA].sub.A], d) [not equal to] [perpendicular to], then set [delta](A, d) = {[??]}; also set [delta]'(A, d) = {[??]} if A already has color [??] on some edge. Finally, let A be in F' if and only of it is not in F. One can verify that ([SIGMA], K [union]{[??]}, [delta]', [mu], F') is a [mu]-DWA accepting the complement of L.

The closure under union is a consequence of the previous properties.

Corollary 5.1 Scan-DREC is a proper subclass of REC, closed under complement, rotation and mirror.

Proof: The closure under complement is a straightforward consequence of the previous proposition. REC being not closed under complement, by Theorem 4.1 we have Scan-DREC [subset] REC. The closure under rotation (resp. mirror) is quite obvious, since one could easily define the rotation (resp. mirror) of a scanning strategy (and consequently the rotation (resp. mirror) of a [mu]-WA) and this operation preserves determinism.

Proposition 5.2 There exists a language in L(C-DW4) and not in L(S-DWA).

Proof: Consider the language [L.sub.half] defined in Example 2 and let L be its intersection with its 180[degrees] rotation, i.e., the language of pictures of size (n, m), n [greater than or equal to] m [greater than or equal to] 4, with both the first and the last rows like w x [bar.w], where [bar.w] is the reverse of w. We prove that L e L(C-DWA) \ L(S-DWA).

First of all, notice that L(C-DWA) is closed under rotation. For instance, let C' be the scanning strategy obtained as the 90[degrees] counter-clockwise rotation of C. Then any C'-DWA can be simulated by a C-DWA as follows: propagate the symbols in the first column rightwards and check them in the second spiral round; the rest of the computation is as before. Hence, [L.sub.half] being in L(C-DWA) as shown in Example 8, we get that L [member of] L(C-DWA).

On the other hand, L [not member of] L(S-DWA) by counting reasons. Let us assume by contradiction that there exists a S-DWA t recognizing L, and consider the language [T.sub.n] [subset or equal to] L formed by all square pictures of side size 2n having a fixed symbol in 2 everywhere except in the last row. For every p [member of] [T.sub.n], let k(p) be the color assigned by [tau] to the left border of position (2n, n + 1). For n great enough, the number of words over [SIGMA] of length n is greater than the number of colors used by [tau], hence there exist an integer [bar.n] > 1, two words [w.sub.1] + [w.sub.2] of length n and two pictures [p.sub.1], [p.sub.2] [member of] [T.sub.n] such that the last row of [p.sub.i] ends with [w.sub.i] for i = 1,2 and k([p.sub.1]) = k([p.sub.2]). Consider the pictures [p.sub.1] and [p.sub.2] built from [p.sub.1] and [p.sub.2] by replacing their last rows with [[bar.w].sub.1] x [w.sub.1] and [[bar.w].sub.1] x [w.sub.2], respectively. Then, the computation of [tau] over both [p'.sub.1] and [p'.sub.2] ends at position (2[bar.n], 1) with the same tile, but clearly [p'.sub.1] is in L whereas [p'.sub.2] is not, a contradiction.

Proposition 5.3 There exists a language in L (S-DWA) and not in L(C-DWA).

Proof: Consider the language [L.sub.[there exists]r=fr] of square pictures where there is at least one row that is equal to the first one.

On the one hand, it is very easy to define a S-DWA for [L.sub.[there exists]r=fr], as a S-DWA can propagate (by coloring) the symbols found in the first row to the rows below, one by one, and then check if at least one copy of the first row is present in the input picture.

On the other hand, we provide some intuition for the fact that [L.sub.[there exists]r=fr] [not member of] L(C-DWA). Let us suppose that there is a C-DWA, i.e. [tau] = ([SIGMA], K, [delta], C, F), such that L([tau]) = [L.sub.[there exists]r=fr]. We now consider w.l.o.g a generic picture p [member of] [L.sub.[there exists]r=fr] having even side size, i.e. 2n. We call w the first row of p, [p.sub.u] its upper half, [p.sub.l] its lower half (i.e. both having size (n, 2n)). It is easy to check if another copy of the row w is present in [p.sub.u] (using a technique analogous to the one used before with S-DWA). But, to check if w is present in pl, following a spiral scanning strategy, one needs to represent its content in the coloring of the lower part. Every "turn" of the spiral is able to propagate a number of symbols of w that depends on a constant k which is proportional to [absolute value of K]/[absolute value of [SIGMA]. Hence, to propagate w to the coloring of the lower part of p, the scanning of the input picture has to perform 2n/k "rounds", thus visiting completely the lower 2n/k rows of [p.sub.l]. Let us call this last subpicture [p'.sub.l], that has size (2n/k, 2n).

The following facts hold: (1) it is impossible to visit [p'.sub.l] after the first 2n/k rounds of the scanning; (2) the coloring at positions corresponding to [p'.sub.l] in p cannot encode the fact that w is (or is not) a row of [p'.sub.l], because before the first 2n/k rounds, the content of w was not completely available in the lower part of the picture; (3) it is impossible to represent the whole content of [p'.sub.l], made of 4[n.sup.2]/k symbols, in the coloring of the tiles which are partial after the first 2n/k rounds of the input picture scanning, because the number of these tiles is proportional to n.

Therefore, let us suppose that w is present in [p.sub.u] only as the first row, while it is not present in the upper n - 2n/k rows of [p.sub.l]. Because of facts (1-3), it is impossible for [tau] to state if p is in [L.sub.[there exists]r=fr], or not.

Corollary 5.2 L(S-DWA) and L(C-DWA) are incomparable.

In particular we characterize the boustrophedonic scanning strategy S in terms of line unambiguity.

Definition 5.2 Snake-DREC is the closure under rotation of L(S-DWA).

Notice that Snake-DREC was originally described by means of tiling systems or online tessellation acceptors [20]. The term snake comes from the boustrophedonic order of visiting of the pixels: if we draw the trajectory of the scanning strategy, it looks like a snake covering line by line (or column by column) the whole picture.

Theorem 5.1 Snake-DREC coincides with class Row-UREC [union] Col-UREC.

Before proving this theorem, we summarize its main consequences as follows:

Corollary 5.3 Snake-DREC is closed under complement, rotation and mirrors, but not under intersection. Moreover

Diag-DREC [subset] Snake-DREC [subset] Scan-DREC [subset or equal to] UREC.

Proof: Proposition 5.1 implies the closure under complement; the closure under rotation is obvious by definition; the closure under mirrors follows by the closure under mirrors of both Row-UREC and Col-UREC; [L.sub.[there exists]r=fr] is in Snake-DREC as shown in proof of Proposition 5.3, but its intersection with all its rotations is not [1].

The first proper inclusion is a straightforward consequence of the previous theorem and relation (3). Clearly Snake-DREC [subset or equal to] Scan-DREC [subset or equal to] UREC by definition. Snake-DREC is properly included in Scan-DREC: let Lhalf be the language defined in Example 2, and let L be its intersection with all its 90[degrees] rotations. Then L is in L(C-DWA) since L(C-DWA) is closed under rotation and [L.sub.half] [member of] L(C- DWA) by Proposition 5.2; on the other hand L is not in Snake-DREC for counting reasons similar to those used in Proposition 5.2.

[FIGURE 4 OMITTED]

Proof of Theorem 5.1

We actually show that

L (S-DWA) = L(t2b-UWS),

the proof of theorem follows by applying rotations. In one direction, the result is easy: starting from any S-DWA and using the construction of Theorem 4.1 one obtains a Wang system which is t2b-unambiguous.

The converse is less intuitive; in order to prove it, from now on let [omega] = ([SIGMA], K, [THETA]) be a t2b-UWS. We build a S-DWA

[tau] = ([SIGMA], K', [delta], S, F)

that simulates [omega]. Before formally defining [tau], let us first point out some important remarks.

Given any Wang fragment [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], there exists at most one Wang fragment A = [A.sub.1] [A.sub.2] ... [A.sub.m] [member of] [THETA].sup.l,m] satisfying relation ([2]). However, we have no guarantees that A can be built from left to right deterministically. For instance, for m = 4 and for some fixed X, [omega] may allow the choices of Wang tiles represented in Figure 4 (left).

Clearly, [omega] being t2b-unambiguous, only one branch of the graph ends with ft: the one corresponding to A. In the other cases, a backtracking linear in the length of the row is always sufficient to (eventually) determine A.

Remark 1 Since we are building a Wang tiling of a fixed row a, at each position we can choose among tiles that all have the same label. E.g., [lambda]([A.sub.1]) = [lambda]([A'.sub.1]) = [lambda]([A.sub.1]") = [a.sub.1].

Remark 2 Since co is t2b-unambiguous, the branch corresponding to A cannot contain Wang tiles with in-degree greater that one (otherwise there would exist two different Wang tilings of row a satisfying relation (2), a contradiction). In other words, if two or more branches "collapse", the successive tiles may be ignored. Then we can assume that the graph of the Wang tilings of a is actually a tree, where each tile has exactly one predecessor. We call it the tree of the Wang tiling of a in [THETA]. For the previous example, the tree is depicted in Figure 4 (right).

Similar remarks hold if we try to build the Wang tiling of row a from right to left.

To simulate co deterministically on a picture p, we proceed as follows. Let P be the unique Wang tiling of p in [L.sub.W]([THETA]). To locally represent the tree of Wang tilings of the current row, we store at each position the set a of tiles in [THETA] that may appear at the corresponding position in P. Notice that any such set [alpha] contains tiles having the same label, by Remark 1; moreover, each tile in any such set [alpha] admits exactly one predecessors in the tree, by Remark 2. The set of tile-sets [alpha] containing tiles with the same label is denoted by [PHI]; [lambda]([alpha]) is the label of any tiles in [alpha]. We also use the following convention: a, b, ... are used to denote symbols in [SIGMA]; A, B, ... are used to denote (possibly partial) tiles in [[summation].sub.K]; and [alpha],[beta], ... are used to denote elements of [PHI].

When scanning rightwards the first row of p, we compute and keep trace of the tree of its Wang tilings; at the end of the row, we determine which branch is successful (i.e, the one that corresponds to the first row of P). When scanning the second row backwards, we use such information (together with the traces we left in the previous scan) to reconstruct backwards the successful branch and, at the same time, we compute and keep trace of the tree of the Wang tilings of the current row. This procedure continues till the last row has been scanned. So, the set of colors K' of t must contain both pieces of information. This leads to the following definition:

K' = {#} [union] [PHI] [union] ([THETA] x [PHI]).

Colors in [PHI] used for the tiles in the first row and, in other rows, only at top and bottom of tiles, whereas colors in [THETA] x [PHI] are used at left and right: the role of color (A,[beta]) [member of] [THETA] x [PHI] is the following: A is the correct Wang tile that one should have chosen in the position immediately above the current one, whereas [beta] keeps trace of all possible Wang tiles that may appear in the current position.

We are now able to define the (deterministic) transition function [delta] of [tau]. It has to be a partial function

[delta] : [[summation].sub.K] x Dirs [right arrow] [[summation].sub.4K']

that satisfies two conditions: i) each Wang tiles in [delta](W d) extends W; ii) [delta](W, d) [not equal to] [perpendicular to] implies [eta]([[DELTA].sub.W], d) [not equal to] [perpendicular to], where [eta] is the next-position function associated with S. Thus, it is sufficient to define [delta](W, d) in the cases represented in Table 3: the left part of the table is used for the first and last row of the input picture, whereas the right part covers the other rows to be visited rightwards or leftwards.

In Table 3, for each W [member of] [[summation].sub.K'] such that [delta](W, d) [not equal to] [perpendicular to], a picture fragment f (W) is introduced; moreover tile-sets [[alpha].sub.0], [[alpha].sub.1], a and tile C appearing in the table are defined, for each W, by setting:

[[alpha].sub.0] = {A [member of] [lambda].sup.-1](a) | f(W) [member of] [F.sub.w]([THETA])}, (4)

[[alpha].sub.1] = {A [member of] [lambda].sup.-1] (a) | [there exists]! B [member of] [beta] such that f(W) [member of] [F.sub.w]([THETA])}, (5)

[alpha] = {A [member of] [lambda].sup.-1](a) | [there exists]! B [member of] [beta], [there exists]! C [member of] y such that f(W) [member of] [F.sub.w]([THETA])}. (6)

The uniqueness of B and C is required by Remark 2. Notice that [[alpha].sub.0] is used only at the beginning of rows, [[alpha].sub.1] only in the first row, [alpha] in all the other positions of a picture.

Finally, F is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now prove that the S-DWA [tau] = ([SIGMA], K', [delta], S, F) is equivalent to the t2b-unambiguous Wang system [omega] = ([SIGMA], K, [THETA]).

First we show that L([omega]) [subset or equal to] L([tau]). Let p [member of] L(co) and let P [member of] [L.sub.W]([THETA]) be the Wang tiling of p according to [omega]. W.l.o.g assume that p has a even number of row (the other case is similar), and let [a.sub.i,j] and [A.sub.i,j] be the pixels of p and P respectively. Then one can easily verify that the automaton [tau] accepts p producing a Wang tiling P' for p as in Figure 5, where [A.sub.i,j] [member of] [a.sub.i,j] for every i = 1,2, ..., n - 1 and j = 2,3, ..., m - 1.

[TABLE 3 OMITTED]

Vice versa, let p [member of] L([tau]) with pixels [a.sub.i,j] (again we assume w.l.o.g. that p has a even number of row), and let P' be the Wang tiling of p produced by [tau]. Then P' is as in Figure 5, for every i = 1,2, ..., n - 1 and j = 2,3, ..., m - 1. Now, for every odd i let [A.sub.i,l] be the unique element of [[alpha].sub.a,1] such that [A.sub.i,1] [A.sub.i,2] [member of] [F.sub.w]([THETA]); similarly, for every even i let [A.sub.i,m] be the unique element of [[alpha].sub.i,m] such that [A.sub.i,m-1] [A.sub.i,m] [member of] [F.sub.w]([THETA]). Moreover, let [A.sub.n,1] and [A.sub.n,2] be the unique tiles such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and, for every j= 3, ... m, let [A.sub.n,j] be the unique element of [[alpha].sub.n,j] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then it is immediate to verify that the Wang picture P with pixels [A.sub.i,j] is a Wang tiling of p and belongs to [L.sub.w]([THETA]). Hence, p [member of] L([omega]) and L([tau]) [subset] L([omega]).

[FIGURE 5 OMITTED]

Therefore, L([tau]) = L([omega]) and this proves that any t2b-UWS can be simulated by a S-DWA, thus concluding the proof of Theorem 5.1.

6 Conclusions

Wang automata are a simple and natural model for defining REC. Their main strength is coupling the power of Wang systems with simple scanning strategies, that permits a straightforward introduction of the notion of determinism. We proved here that such notion defines a relevant deterministic subclass of REC, properly containing the traditional one based on diagonal determinism. These results make WAs a worthy and relevant addition to the literature on 2D operational devices.

Among the open problems we mention the following:

* Is Scan-DREC a proper subset of UREC?

* Relation among L(C-DWA), L(S-DWA) and deterministic subclasses determined by the other significant scanning strategies, such as the ones of Figure 3 (b, c).

* Relation between Scan-DREC and deterministic 4-way automata.

As far as future work is concerned, we plan to investigate extensions of the Wang automata model, based on more complex (so "less polite") scanning strategies. For instance, we could drop the blindness requirement, thus allowing a behavior that depends on the actual content of the input picture. Or we could admit automata that are able to pass zero or more than one time over the same position. Such extensions may make the model more complex and powerful and have to be carefully considered and studied, since they could exceed REC.

received 30th November 2009, revised 29th July 2010, accepted 5th October 2010.

References

[1] M. Anselmo, D. Giammarresi, and M. Madonia. From determinism to non-determinism in recognizable two-dimensional languages. In Proc. DLT2007, volume 4588 of Lecture Notes in Computer Science, pages 36-47. Springer, 2007.

[2] M. Anselmo, D. Giammarresi, and M. Madonia. Tiling automaton: A computational model for recognizable two-dimensional languages. In Proc. CIAA 2007, volume 4783 of Lecture Notes in Computer Science, pages 290-302. Springer, 2007.

[3] M. Anselmo, D. Giammarresi, and M. Madonia. A computational model for recognizable two-dimensional languages. Theoretical Computer Science, 410(37):3520-3529, 2009.

[4] M. Anselmo, D. Giammarresi, and M. Madonia. Deterministic and unambiguous families within recognizable two-dimensional languages. Fundamenta Informaticae, 98(2-3):143-166, 2010.

[5] M. Anselmo, D. Giammarresi, M. Madonia, and A. Restivo. Unambiguous recognizable two-dimensional languages. Theoretical Informatics and Applications, 40(2):277-293, 2006.

[6] P. Behrooz. Introduction to Parallel Processing: Algorithms and Architectures. Kluwer Academic Publishers, Norwell, MA, USA, 1999.

[7] A. Bertoni, M. Goldwurm, and V. Lonati. On the complexity of unary tiling-recognizable picture languages. Fundamenta Informaticae, 91(2):231-249, 2009.

[8] B. Borchert and K. Reinhardt. Deterministically and sudoku-deterministically recognizable picture languages. In Proc. LATA 2007, 2007.

[9] S. Bozapalidis and A. Grammatikopoulou. Recognizable picture series. Journal of Automata, Languages and Combinatorics, 10(2/3):159-183, 2005.

[10] R. Brijder and H. J. Hoogeboom. Perfectly quilted rectangular snake tilings. Theoretical Computer Science, 410(16):1486-1494, 2009.

[11] A. Cherubini, S. Crespi Reghizzi, and M. Pradella. Regional languages and tiling: A unifying approach to picture grammars. In Proc. MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pages 253-264. Springer, 2008.

[12] A. Cherubini and M. Pradella. Picture languages: From Wang tiles to 2D grammars. In S. Bozapalidis and G. Rahonis, editors, Proc. CAI2009, volume 5725 of Lecture Notes in Computer Science, pages 13-46. Springer, 2009.

[13] L. de Prophetis and S. Varricchio. Recognizability of rectangular pictures by Wang systems. Journal of Automata, Languages and Combinatorics, 2(4):269-288, 1997.

[14] D. Giammarresi and A. Restivo. Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence, 6(2-3):241-256, 1992. Special Issue on Parallel Image Processing.

[15] D. Giammarresi and A. Restivo. Two-dimensional languages. In A. Salomaa and G. Rozenberg, editors, Handbook of Formal Languages, volume 3, Beyond Words, pages 215-267. Springer-Verlag, Berlin, 1997.

[16] K. Inoue and A. Nakamura. Some properties of two-dimensional on-line tessellation acceptors. Information Sciences, 13:95-121, 1977.

[17] K. Inoue and I. Takanami. A survey of two-dimensional automata theory. Information Sciences, 55(1-3):99-121, 1991.

[18] K. Lindgren, C. Moore, and M. Nordahl. Complexity of two-dimensional patterns. Journal of Statistical Physics, 91(5-6):909-951, June 1998.

[19] V. Lonati and M. Pradella. Strategies to scan pictures with automata based on Wang tiles. Submitted. Available at http://lonati.dsi.unimi.it/lavori/strategies_rapporto.pdf.

[20] V. Lonati and M. Pradella. Snake-deterministic tiling systems. In Proc. MFCS 2009, volume 5734 of Lecture Notes in Computer Science, pages 549-560. Springer, 2009.

[21] V. Lonati and M. Pradella. Picture recognizability with automata based on Wang tiles. In Proc. SOFSEM 2010, volume 5901 of Lecture Notes in Computer Science, pages 576-587. Springer, 2010.

[22] O. Matz. On piecewise testable, starfree, and recognizable picture languages. In M. Nivat, editor, Proc. FoSSaCS 1998, volume 1378 of Lecture Notes in Computer Science, pages 203-210. Springer, 1998.

(i) The original name is DREC.

(ii) In the definition, also [d.sub.t], [D.sub.t], and [E.sub.t] depend on n and m; for better readability, this dependence is not explicit. We also agree that the value of any expression containing [perpendicular to] is still [perpendicular to].

Violetta Lonati (1) ([double dagger]) and Matteo Pradella (2) ([section])

(1) Dipartimento di Scienze dell'Informazione, Universita degli Studi diMilano, Italy. Email: lonati@dsi.unimi.it

(2) IEIIT, Consiglio Nazionale delle Ricerche, Milano, Italy. Email: matteo.pradella@polimi.it

([dagger]) This work includes the results presented in the two distinct papers 20 and 21.

([double dagger]) Supported by the MIUR PRIN project "Mathematical aspects and emerging applications of automata and formal languages".

([section]) Supported by the MIUR PRIN project "D-ASAP: Dependable Adaptable Software Architecture for Pervasive Computing".

Printer friendly Cite/link Email Feedback | |

Author: | Lonati, Violetta; Pradella, Matteo |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Geographic Code: | 4EUIT |

Date: | Dec 1, 2010 |

Words: | 9695 |

Previous Article: | Contextual partial commutations. |

Next Article: | A characterization of infinite smooth Lyndon words. |

Topics: |