<figure><img src="image_1.png" /></figure>

HAL
open science

# Avoiding Overlaps in Pictures

Marcella Anselmo, Dora Giammarresi, Maria Madonia

► To cite this version:

Marcella Anselmo, Dora Giammarresi, Maria Madonia. Avoiding Overlaps in Pictures. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.16-32, 10.1007/978-3-319-60252-3_2. hal-01657001

HAL Id: hal-01657001

https://inria.hal.science/hal-01657001

Submitted on 6 Dec 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Avoiding Overlaps in Pictures*

Marcella Anselmo,<fnref n="1" /> Dora Giammarresi,<fnref n="2" /> Maria Madonia<fnref n="3" />

**Abstract.** In string combinatorics, the sets of strings that have no overlaps (i.e. the prefix of one string does not coincide with the suffix of another string) are extensively investigated since they play an important role in the context of string matching and coding. The notion of overlap can be extended naturally to two dimensions; two pictures *p* and *q* have an overlap if one can put one corner of *p* on some position in *q* in such a way that all symbols in the common positions coincide. A picture with no self-overlaps is called unbordered and it is a generalization in two dimensions of an unbordered (or bifix-free) string.

We study the problem of generating all unbordered pictures of fixed size and present a construction of non-expandable non-overlapping sets of pictures together with some examples.

**Keywords:** Two-dimensional language, overlap, unbordered pictures.

## 1 Introduction

Pictures are a generalization of strings to two dimensions and they are represented by two-dimensional (rectangular) arrays of symbols taken from a finite alphabet Σ. The size of a picture with *m* rows and *n* columns is indicated by (*m*, *n*). Single row or column pictures can be always identified with strings.

Extending results from the formal string language theory to two dimensions is a very challenging task. The intrinsic complexity of two-dimensional structures is evident even in the generalizations of the basic concepts and definitions. For example, the definition of “prefix” of a string can be naturally extended to a picture by considering its rectangular portion in the top-left corner; nevertheless, if one deletes a prefix from a picture, the remaining part is not a picture anymore. Despite such difficulties, several results from string language theory have been worthy extended to pictures. Many researchers have investigated how the notion of recognizability by finite state automata can be transferred to two dimensions to accept picture languages ([1, 5, 8, 20, 25, 26, 28, 30]). Moreover two dimensional codes were studied in different contexts ([1, 17, 21, 29]) and recently

<footnote n="1">¹ Dipartimento di Informatica, Università di Salerno, Via Giovanni Paolo II,
132-84084 Fisciano (SA) Italy. E-mail: manselmo@unisa.it</footnote>

<footnote n="2">² Dipartimento di Matematica. Università Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. E-mail: giammarr@mat.uniroma2.it</footnote>

<footnote n="3">³ Dipartimento di Matematica e Informatica, Università di Catania, Viale Andrea Doria 6/a, 95125 Catania, Italy. E-mail: madonia@dmi.unict.it</footnote>

<footnote>* Partially supported by INdAM-GNCS Project 2017, FARB Project ORSA138754 of University of Salerno and FIR Project 375E90 of University of Catania</footnote>
two-dimensional prefix codes were introduced as the two-dimensional counterpart of prefix string codes ([3, 8, 4, 10, 11]).

In the combinatorics of strings, the study of the structure and the special patterns of the strings plays an important role both from the theoretical and the applicative side. Given a string $s$, a *bifix* or a *border* of $s$ is a substring $x$ that is both prefix and suffix of $s$. A string $s$ is *bifix-free* or *unbordered* if it has no other bifixes besides the empty string and $s$ itself. Bifix-free strings are connected with the theory of codes [18] and are involved in the data structures for pattern matching algorithms [24, 27]. From a more applicative point of view, bifix-free strings are suitable as synchronization patterns in digital communications and similar communications protocols [30]. The combinatorial structure of bifix-free strings over a given alphabet was studied by P.T. Nielsen in [30]; he provided an algorithm to enumerate all bifix-free strings of the same length $n$ over a given alphabet. A set of strings $X$ in which no prefix of any string is the suffix of any other string in $X$ is called a *cross-bifix-free code*. Constructive methods for cross-bifix-free codes are widely investigated in [14, 19, 22].

In this paper we investigate the notion of *overlaps* in pictures. It can be very naturally extended from the string theory since it is not related to any preferred scanning direction. Informally, we say that two pictures $p$ and $q$ overlap when it is possible to place $p$ somewhere on $q$ in such a way that all the superimposed positions hold the same symbol. In other words, two pictures $p$ and $q$ overlap when we can find the same rectangular portion $x$ at one corner of $p$ and at the opposite corner of $q$. Observe that there are two different kinds of overlaps depending on the pair of opposite corners involved. If such common rectangular part $x$ is found at the top-left corner of $p$ (and bottom-right corner of $q$) we will say that $p$ and $q$ *tl-overlap*; if $x$ is found at the bottom-left corner of $p$ (and top-right corner of $q$) we will say that $p$ and $q$ *bl-overlap*. Moreover, special cases of overlaps will occur when such common part $x$ is a “string” (for example there is a prefix of the first row in $p$ that is a suffix of the last row in $q$). We refer to them as *frame-overlaps*.

The notion of overlap leads easily to the notion of *border*, when we consider overlaps between a picture $p$ and its copy $p'$. As for overlaps, we can have *tl-* and *bl*-borders. A picture $p$ is *unbordered* if it has no proper borders. Unbordered pictures are connected both to picture codes and to two-dimensional pattern matching. We are interested in computing all the unbordered pictures of a fixed size $(m, n)$ on a given alphabet.

It can be verified that the recursive construction of bifix-free strings given by Nielsen in [30] cannot be directly generalized to generate unbordered pictures. Nevertheless, a bidimensional version of Nielsen's construction produces a bigger set of pictures to which we referred to as *quasi-unbordered* pictures in [5]. The quasi-unbordered pictures can have only certain particular types of borders. The unbordered pictures can then be extracted from this set. In this paper we discuss more in detail the advantages of using quasi-unbordered pictures as an intermediate step in the construction of the unbordered ones. In particular we show that the probability that any quasi-unbordered picture is actually unbordered goes
to 1 when the size of the picture grows. Moreover we prove that unbordered
pictures can be obtained by intersecting two different sets of quasi-unbordered
pictures.

Next we consider particular sets of unbordered pictures where no picture
can be overlapped on another one of the same set. We refer to them to as *non-
overlapping sets*. They are therefore a generalization of cross-bifix-free codes of
strings and they correspond to a family of picture codes. In particular, non-
overlapping sets of pictures are two-dimensional comma-free codes (recently
studied in [12]) with a stronger property.

Using a naive algorithm, a non-overlapping set of pictures of a fixed size (*m*,*n*) can be “extracted” by getting pictures one by one from the set of all unbordered pictures, by checking at each step that the current picture does not overlap with all the previously chosen ones. This procedure can be useful for getting small sets. The major problem is to find *non-expandable non-overlapping (NENO) sets of pictures*, i.e. sets to which it is not possible to add other non-overlapping pictures of the same size.

Very recently, in [15, 16], some sets of non-overlapping matrices have been
presented by exploiting some techniques from the string case. The problem of
finding non-expandable non-overlapping sets was left open. Note that also in the
string case the corresponding problem of finding large non-expandable cross-
bifix-free sets is difficult ([14, 19, 22]). In [9] a first example of a family of NENO
sets of pictures is proposed. It is constructed by exploiting some conditions on
the frames of the pictures of NENO sets. (The frame of a picture is the quadruple
of strings corresponding to its first and last rows and columns). Once fixed the
“right” set of frames $\mathcal{F}$ that avoid frame overlaps, the NENO set is found as
subset of all the pictures with frame in $\mathcal{F}$.

The method can be applied to obtain further examples. It was not clear the
role of the frame for the selection of the pictures of the NENO set; in particu-
lar it was left open the problem whether fixing the frame set could univocally
determine the NENO set. In this paper we solve this problem by exhibiting two
different NENO sets with the same frame set.

## 2 Preliminaries

We recall some definitions about two-dimensional languages (see [26]). A *picture* over a finite alphabet Σ is a two-dimensional rectangular array of elements of Σ. Given a picture p, |p|<sub>row</sub> and |p|<sub>col</sub> denote the number of rows and columns, respectively, while size(p) = (|p|<sub>row</sub>, |p|<sub>col</sub>) denotes the picture size. We also consider all the empty pictures that correspond to all pictures of size (m, 0) or (0, n). The set of all pictures over Σ of fixed size (m, n) is denoted by Σ<sup>m,n</sup>. The set of all pictures over Σ is denoted by Σ<sup>**</sup> while Σ<sup>++</sup> refers to the set Σ<sup>**</sup> without the empty pictures. A *two-dimensional language* (or *picture language*) over Σ is a subset of Σ<sup>**</sup>.

In order to locate a position in a picture, it is necessary to put the picture
in a reference system. Let *p* be a picture of size (*m*, *n*). The set of coordinates
$dom(p) = \{1, 2, \dots, |p|_{row}\} \times \{1, 2, \dots, |p|_{col}\}$ is referred to as the *domain* of a picture $p$. We let $p(i, j)$ denote the symbol in $p$ at coordinates $(i, j)$. We assume the top-left corner of the picture to be at position $(1, 1)$, and fix the scanning direction for a picture from the top-left corner toward the bottom right one. Moreover, to easily detect border positions of pictures, we use initials of words “top”, “bottom”, “left” and “right”; then, for example the *tl-corner* of $p$ refers to position $(1, 1)$ while the *br-corner* refers to position $(m, n)$. Furthermore, we denote by $r_F(p), r_L(p) \in \Sigma^n$ the first and the last row of $p$, respectively and by $c_F(p), c_L(p) \in \Sigma^m$ the first and the last column of $p$, respectively. Then, the *frame* of $p$ is $frame(p) = (r_F(p), r_L(p), c_F(p), c_L(p))$.

For the sequel, it is convenient to extend the notation for the frame of a picture to languages. Let $X \subseteq \Sigma^{m,n}$. Let us denote by $R_F(X) \subseteq \Sigma^n$ the set $R_F(X) = \{r_F(p) \mid p \in X\}$ of the first rows of all pictures in $X$. In a similar way, $R_L(X), C_F(X)$, and $C_L(X)$ will denote the sets of the last rows, of the first columns, and of the last columns of all pictures in $X$, respectively. The *frame* of $X$ is the quadruple $frame(X) = (R_F(X), R_L(X), C_F(X), C_L(X))$.

A *subdomain* of $dom(p)$ is a set $d$ of the form $\{i, i+1, \dots, i'\} \times \{j, j+1, \dots, j'\}$, where $1 \le i \le i' \le m$, $1 \le j \le j' \le n$, also specified by the pair $[(i, j), (i', j')]$. The portion of $p$ corresponding to positions in subdomain $[(i, j), (i', j')]$ is denoted by $p[(i, j), (i', j)]$. Then, a non-empty picture $x$ is *subpicture* of $p$ if $x = p[(i, j), (i', j)]$, for some $1 \le i \le i' \le m$, $1 \le j \le j' \le n$; we say that $x$ *occurs* at position $(i, j)$ (its *tl-corner*).

Observe that the notion of subpicture generalizes very naturally to two dimensions the notion of substring. On the other hand, the notions of prefix and suffix of a string implicitly assume the left-to-right reading direction. In two dimensions, there are four corners and four scanning-directions from a corner toward the opposite one. Hence, we introduce the definition of four different “prefixes” of a picture, each one referring to one corner.

Given pictures $p \in \Sigma^{m,n}$, $x \in \Sigma^{h,k}$, with $1 \le h \le m$, $1 \le k \le n$, we say that $x$ is a *tl-prefix* of $p$ if $x$ is a subpicture of $p$ occurring at position $(1, 1)$; $x$ is a *tr-prefix* of $p$ if $x$ is a subpicture of $p$ occurring at position $(1, n-k+1)$; $x$ is a *bl-prefix* of $p$ if $x$ is a subpicture of $p$ occurring at position $(m-h+1, 1)$; $x$ is a *br-prefix* of $p$ if $x$ is a subpicture of $p$ occurring at position $(m-h+1, n-k+1)$.

Some operations can be defined on pictures. Let $p, q \in \Sigma^{**}$ be pictures of size $(m, n)$ and $(m', n')$, respectively. The *column* and the *row concatenation* of $p$ and $q$ are defined by horizontally and vertically juxtaposing $p$ and $q$ and are denoted by $p \ominus q$ and $p \oslash q$, respectively. They are partial operations, defined only if $m = m'$ and if $n = n'$, respectively. The reverse operation on strings can be generalized to pictures and gives rise to two different mirror operations (called *row-* and *col-mirror*) obtained by reflecting with respect to a vertical and a horizontal axis, respectively. Another operation that has no counterpart in one dimension is the *rotation*. The rotation of a picture $p$ of size $(m, n)$, is the clockwise rotation of $p$ by $90^\circ$, denoted by $p^{90^\circ}$. Note that $p^{90^\circ}$ has size $(n, m)$. All the operations defined on pictures can be extended in the usual way to sets of pictures.
We conclude by remarking that any string $s = y_1y_2\cdots y_n$ can be identified either with a single-row or with a single-column picture.

### 3 Overlaps in strings and in pictures

In the string theory, patterns and overlaps are widely investigated. Two strings $s$ and $s'$ overlap if there exists a string $x$ that is a suffix of $s$ and a prefix of $s'$, or vice versa; we will equivalently say that $s$ overlaps $s'$. In this framework, the cross-bifix-free sets have been introduced in [13] by taking back a notion introduced in early sixties. A set of strings $X$ is cross-bifix-free when no prefix of any string is the suffix of any other string in $X$ (i.e. no two strings in $X$ overlaps); it is non-expandable if no other element can be added to $X$ without falsifying the property of the set.

The case when a string overlaps with itself leads to the notions of border (or bifix) of a string and unbordered (or bifix-free) strings. A string $x$ that is both prefix and suffix of $s$ is called a border or a bifix of $s$. The empty string and $s$ itself are trivial borders of $s$. A string $s$ is unbordered or bifix-free if it has no borders other than the trivial ones. In [30] P. T. Nielsen proposed a procedure to generate all bifix-free strings of a given length that is based on a property of string borders; we will give some details of this procedure in Section 4.

This notion of overlap of strings can be extended very naturally to two dimensions by taking into account that now four different corners exist. Informally, we say that two pictures $p$ and $q$ overlap when we can find the same rectangular portion at a corner of $p$ and at the opposite corner of $q$. Observe that there are two different kinds of overlaps depending on the pair of opposite corners involved. The definitions here reported can be found in [9].

**Definition 1.** Let $p \in \Sigma^{m,n}$ and $q \in \Sigma^{m',n'}$.

The pictures $p$ and $q$ tl-overlap if there exists a picture $x \in \Sigma^{h,k}$, with $1 \le h \le \min\{m, m'\}$ and $1 \le k \le \min\{n, n'\}$, which is a tl-prefix of $p$ and a br-prefix of $q$, or vice versa.

The pictures $p$ and $q$ bl-overlap if there exists a picture $x \in \Sigma^{h,k}$, with $1 \le h \le \min\{m, m'\}$ and $1 \le k \le \min\{n, n'\}$, which is a bl-prefix of $p$ and a tr-prefix of $q$, or vice versa.

The pictures $p$ and $q$ overlap if they tl-overlap or they bl-overlap.

The picture $x$ is called an overlap of $p$ and $q$, and its size $(h, k)$ is the size of the overlap.

For the sequel, it is useful to identify some special cases of picture overlaps and we list them in the definition below. Note that the same overlap can be of different types. Let $p \in \Sigma^{m,n}$ and $q \in \Sigma^{m',n'}$, then

$p$ and $q$ properly overlap if they have an overlap $x$ with $x \ne p$ and $x \ne q$

$p$ and $q$ h-slide overlap if they have an overlap $x \in \Sigma^{h,k}$ with $h = m = m'$

$p$ and $q$ v-slide overlap if they have an overlap $x \in \Sigma^{h,k}$ with $k = n = n'$

$p$ and $q$ frame-overlap if they have an overlap $x \in \Sigma^{h,k}$ with $h = 1$ or $k = 1$.

Examples are given in Figure 1.
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** From left to right: a pair of pictures that tl-overlap, h-slide overlap, v-slide overlap, frame-overlap (and also bl-overlap).</figcaption></figure>

Consider now the case when a picture overlaps with itself; this case leads to the generalization of the notion of border from strings to pictures.

**Definition 2.** Given pictures $p \in \Sigma^{m,n}$ and $x \in \Sigma^{m',n'}$, with $1 \le m' \le m$ and $1 \le n' \le n$, the picture $x$ is a tl-border of $p$, if $x$ is a subpicture of $p$ occurring at position $(1,1)$ and at position $(m-m'+1, n-n'+1)$; picture $x$ is a bl-border of $p$, if $x$ is a subpicture of $p$ occurring at position $(m-m'+1, 1)$ and at position $(1, n-n'+1)$. Moreover $x$ is a border of $p$ if it is either a tl- or a bl-border.

As special cases, $p$ is a *trivial border* of itself, and $x$ is a *proper border* of $p$ if it is not trivial. A tl-border is called a diagonal border in [23]. Notice that a tl-border $x$ of a picture $p$ of size $(m,n)$ can be univocally detected either by giving the position where it occurs in $p$ (besides position $(1,1)$) or by giving its size. The same holds for bl-borders. Examples of pictures together with their borders are given below.

<figure><img src="image_4.png" /></figure>

Note that if a picture $p$ has a tl-border $x$, then the rotation $p^{90^\circ}$ has a bl-border (that coincides with $x^{90^\circ}$). In the figure above, the second picture is the rotation of the first one.

**Definition 3.** A picture $p \in \Sigma^{m,n}$ is bordered if there exists a picture $x$ that is a proper border of $p$. Picture $p$ is unbordered (or border-free) if it is not bordered.

In the next two sections we consider two main problems. Firstly we discuss the problem of generating the set of all unbordered pictures of fixed size and secondly we study sets of unbordered pictures that also do not overlap each others and that are non-expandable. Such sets, we call NENO sets, are the generalization to two dimensions of cross-bifix-free sets of strings.
# 4 Unbordered pictures

The aim of this section is to construct all the unbordered pictures of a fixed size $(m, n)$. Some of the results in this section can be also found in [5]. Let us denote by $U_\Sigma(m, n)$, or simply $U(m, n)$, when the alphabet can be omitted, the set of all unbordered pictures of size $(m, n)$ over the alphabet $\Sigma$.

Few simple results useful in determining the unbordered pictures can be immediately listed. They hold for any alphabet $\Sigma$ and integers $m, n \ge 1$.

The set $U_\Sigma(m, n)$ is closed with respect to the col- and row-mirror operations, and with respect to permutation of symbols in $\Sigma$. Moreover, $U_\Sigma(m, n)^{90^\circ} = U_\Sigma(n, m)$. The first row (column, resp.) of an unbordered picture $p$ of size $(m, n)$ must be different from its last one, otherwise $p$ would have a border of size $(1, n)$ ($(m, 1)$, respectively).

The opposite corners of an unbordered picture $p$ of size $(m, n)$ must contain different symbols otherwise $p$ would have a border of size $(1, 1)$. This last simple remark allows to give a bound on the cardinality of the set of all unbordered pictures, $|U(m, n)| \le 1/4|\Sigma^{m,n}|$.

The unbordered pictures of size $(1, n)$ or $(m, 1)$ coincide with the unbordered strings, which have been widely investigated in the literature. In particular, as we recalled in the previous section, P. T. Nielsen proposed a recursive procedure to generate all bifix-free strings of a given length (cf. [30]). Let us report briefly the main steps of this construction.

The construction is based on the result that a string $s$ of length $n$ is unbordered if and only if it has no “short” border, that is no border of length $i$ for $1 \le i \le \lfloor n/2 \rfloor$. Unbordered strings of length $n$ are constructed from unbordered strings of shorter length, by inserting extra symbols in the central positions. The starting set of unbordered strings of length 2 is simply the set of all strings $ab$ with $a, b \in \Sigma$ and $a \ne b$. Then, the unbordered strings of odd length $n$ are obtained by inserting any symbol in the middle of any unbordered string of length $n-1$. The unbordered strings of even length $n$ are obtained by inserting two symbols in the middle of any unbordered string of length $n-2$ and excluding those strings that have a border of length $n/2$.

Before studying the general case let us consider the case of the binary alphabet $\Sigma = \{0, 1\}$ and of pictures of “small” size. It is immediate to see that there are no unbordered pictures of size $(2, 2)$, since there is no way to have different opposite corners and different first and last row. For similar reasons there are no unbordered pictures of sizes $(2, 3)$, $(3, 2)$ and $(3, 3)$. The “smallest” unbordered pictures are of size $(4, 2)$ and they all are listed below:

<figure><img src="image_5.png" /></figure>

To generate the 40 unbordered pictures of size (4, 3) we can generalize Nielsen's construction, and construct them by inserting a suitable middle row in the un-
bordered pictures of size (4, 2) listed above. Unfortunately, this procedure does not work when the size of pictures grows, as shown by the following example.

*Example 4.* The following picture of size (5, 4) is unbordered but it cannot be obtained by insertion of a row or a column in a middle position of a smaller picture. All the pictures obtained by deleting either the third row or the second column or the third column (or both the second and the third column) are bordered pictures.

<figure><img src="image_6.png" /></figure>

The main reason why Nielsen's construction of unbordered strings can not be directly generalized to pictures (as in Example 4), is that the result that any string with a "long" border has necessarily a "short" border too, does not hold in two dimensions. For pictures we have the following weaker result claiming that if a picture has a "large" border then it necessarily has a "small" or a "middle" border. More precisely, ([5]), if a picture $p \in \Sigma^{m,n}$ has a border of size $(i, j)$ with $i \ge \lfloor m/2 \rfloor + 1$ and $j \ge \lfloor n/2 \rfloor + 1$ then $p$ has a border of size $(h, k)$ with $h \le \lfloor m/2 \rfloor$ or $k \le \lfloor n/2 \rfloor$.

A simple generalization of Nielsen's construction to pictures, presented in [5], produces the family of *quasi-unbordered* pictures, which is a family containing all unbordered pictures. In the sequel, we will recall such construction and then discuss the ways to obtain the set of unbordered pictures of given size from the family of quasi-unbordered pictures of that size. Notice that in the special case of one-row pictures, identifiable with strings, the quasi-unbordered pictures are exactly the unbordered strings and the construction presented below coincides with Nielsen's construction.

**Definition 5.** A picture $p \in \Sigma^{m,n}$ is quasi-unbordered if $p$ has no border at position $(i, j)$ with $1 \le i \le m$ and $\lceil n/2 \rceil + 1 \le j \le n$.

Informally, a picture is quasi-unbordered if it has no border occurring in its right side. The set of all quasi-unbordered pictures of size $(m, n)$ over an alphabet $\Sigma$ is denoted by $Q_{\Sigma}(m, n)$, or simply $Q(m, n)$, when the alphabet can be omitted. Observe that $U(m, n) \subseteq Q(m, n)$. Moreover, a quasi-unbordered picture either is an unbordered picture or it necessarily has a border of size $(i, j)$, with $i \le \lfloor m/2 \rfloor$ and $j > \lfloor n/2 \rfloor$ (and possibly a large one).

In the following, the set $Q(m, n)$ is constructed in a recursive way by the insertion of one column in the middle of pictures in $Q(m, n-1)$. We introduce first some formal notations. For any picture $p \in \Sigma^{m,n}$, the *left side* of $p$ is the subpicture $p_L = p[(1, 1), (m, \lfloor n/2 \rfloor)]$, containing the first $\lfloor n/2 \rfloor$ columns of $p$, and the *right side* of $p$ is the subpicture $p_R = p[(1, \lfloor n/2 \rfloor + 1), (m, n)]$ containing the remaining columns. Hence $p = p_L \circ p_R$.
The picture obtained by inserting in the “middle” of $p$ a column $c \in \Sigma^{m,1}$ is denoted $p^{\parallel c} = p_L \oplus c \oplus p_R$. We also define the inverse operation of removing the central column in a picture. More exactly, if $n$ is odd, then $p^{\parallel c}$ denotes the picture obtained by removing the $\lfloor n/2 \rfloor$-th column; if $n$ is even, then $p^{\parallel c}$ denotes the picture obtained by removing the $(n/2+1)$-th column.

We are now ready to sketch the algorithm that provides the set $Q(m, n)$ of quasi-unbordered pictures of a given size $(m, n)$ (see [5] for more details). It consists in the following two steps.

1. Construct $Q(m, 2)$.

2. Recursively construct $Q(m, n)$ from $Q(m, n-1)$ as follows.

If $n$ is odd then define $Q(m, n)$ as the set of all pictures $p^{\parallel c}$ for all $p \in Q(m, n-1)$, $c \in \Sigma^{m,1}$.

If $n$ is even then define $Q(m, n)$ as the set of all pictures $p^{\parallel c}$ for all $p \in Q(m, n-1)$, $c \in \Sigma^{m,1}$, such that $p^{\parallel c}$ has no border occurring at a position in $c$.

A detailed example of this construction can be found in [5].

After having recalled the construction for the quasi-unbordered pictures let us now come back to the unbordered pictures. We discuss here more in detail the advantages of using such construction as an intermediate step in the construction of the unbordered ones.

Recall that $U(m, n) \subseteq Q(m, n)$. In the special case of one-row pictures, identifiable with strings, $Q(1, n) = U(1, n)$, for any $n \ge 1$. In the general case, $Q(m, n)$ contains all unbordered pictures in $U(m, n)$, but it may also contain some bordered pictures which are characterized by the occurrence of a “middle” border in their left side.

In order to estimate the overhead of considering the set $Q(m, n)$ as intermediate step for obtaining $U(m, n)$, note that the difference in size of the two sets sensibly decreases when $n$ grows. This can be easily understood if we think that the probability that a picture has a border with more than $n/2$ columns sensibly decreases when $n$ grows. More precisely, the following result holds.

**Proposition 6.** Let $m, n, h$ be positive integers, $1 \le h \le \lfloor m/2 \rfloor$, and $\Sigma$ be an alphabet. The probability $P(m, n, h)$ that a random picture $p$ in $Q_{\Sigma}(m, n)$ has a border in its left part of size $(h, k)$ for some $\lfloor n/2 \rfloor \le k \le n$ is such that $\lim_{n \to \infty} P(m, n, h) = 0$.

*Proof.* Let $p \in Q_{\Sigma}(m, n)$ and $m, n, h, k$ be fixed as in the statement and let $P(m, n, h, k)$ be the probability that $p$ has a border $x$ in its left part of size $(h, k)$. Since the two occurrences of the border $x$ inside $p$ do not overlap, $P(m, n, h, k) = \frac{1}{|\Sigma|^{|h|n/2|}}$. Suppose that $n$ is even (the case of $n$ odd goes similarly). Then, $P(m, n, h) = P(m, n, h, n/2) + P(m, n, h, n/2+1) + \dots + P(m, n, h, n)$.

By simple calculations one obtains that $P(m, n, h) = \frac{1}{|\Sigma|^{|h|n/2|}} \cdot \frac{1-\frac{1}{|\Sigma|^{|h|(n/2+1)|}}}{1-\frac{1}{|\Sigma|^{|h|}}}$.

Hence, $\lim_{n \to \infty} P(m, n, h) = 0$. $\square$

<figure><img src="image_7.png" /></figure>
Let us now consider the problem of extracting $U(m, n)$ from $Q(m, n)$.

A first solution consists in considering any picture $p$ in $Q(m, n)$ and test whether it has a “middle” border in its left side. Notice that this procedure is more efficient (at least in terms of the necessary comparisons) than the one of taking any picture in $\Sigma^{m,n}$ and test whether it has a border of any size inside the whole picture. A simple bound on $|Q(m, n)|$ is $|Q(m, n)| \le 1/4|\Sigma^{m,n}|$, for any $m, n \ge 2$, since opposite corners in quasi-unbordered pictures must be different.

A second way to obtain $U(m, n)$, once $Q(m, n)$ is constructed, is provided by the following result, where $Q(m, n)^{rev}$ denotes the col-mirror of $Q(m, n)$.

**Proposition 7.** For any $m, n \ge 2$, $U(m, n) = Q(m, n) \cap Q(m, n)^{rev}$.

*Proof.* Recall that by definition $Q(m, n)$ is the set of all pictures with no border in their right sides. Then, $Q(m, n)^{rev}$ is the set of all pictures with no border in their left sides. The intersection of these two sets gives the set of all pictures with no border at all, that is $U(m, n)$. $\square$

The previous proposition motivates a further investigation to find a clever procedure to generate $Q(m, n)$ and $Q(m, n)^{rev}$ in such a way to easily perform the intersection operation.

# 5 Non-overlapping sets of pictures

In this section we consider the generalization to two dimensions of the notion of cross-bifix-free sets of strings, introduced in [13]. They are special sets of unbordered pictures such that all the pictures do not overlap each others. Moreover, in analogy to the case of cross-bifix-free sets of strings, we will consider sets of pictures of fixed size.

**Definition 8.** A set of pictures $X \subseteq \Sigma^{m,n}$ is non-overlapping if for any $p, q \in X$, $p$ and $q$ do not properly overlap.

A set $X \subseteq \Sigma^{m,n}$ is non-expandable non-overlapping, NENO for short, if $X$ is non-overlapping and for any $p \in \Sigma^{m,n} \setminus X$, there exists $q \in X$ such that $p$ and $q$ overlap.

We here consider the problem of constructing NENO sets, continuing the investigation in [9] where all the missing proofs can be found.

Notice that a way to obtain a NENO set $X$ of pictures of size $(m, n)$ is to consider the set $U(m, n)$ of all unbordered pictures, constructed following the results in Section 4; pick a picture $p \in U(m, n)$ and put in $X$; then add one by one the other pictures in $U(m, n)$ after checking that they do not cause conflicts. For example, a NENO set $X$ of pictures of size (4, 2), can be obtained from the set $U(4, 2)$ shown in Section 4. By an exhaustive procedure, one can show that, for any picture $p \in U(4, 2)$, the set $\{p\}$ is a NENO set. This kind of technique does not shed light on the structure of NENO sets. Indeed, our aim is to give a description of some families of NENO sets.
In general it seems not too complicate to construct sets of non-overlapping
pictures by selecting ad-hoc pictures; the hard part is to let them satisfy the
non-expandability property. In [9] the problem is tacked in a sort of reverse way.
First, it is generated a set of pictures X non-expandable with respect to the non-
overlapping property. This set X is defined by imposing particular conditions
only on the frames of the pictures. Then, the problem is reduced to finding a non-
overlapping set inside such X, by stating some conditions on the internal part
of the pictures. We briefly report here the main steps of this procedure (all the
proofs can be found in [9]) and subsequently, we discuss some questions related
to the choice of the conditions on the internal part of the pictures. Moreover we
introduce some significant new examples of NENO sets.

Recall that the frame of a picture language $X$ is the quadruple of the sets of its first and last rows and columns, $frame(X) = (R_F(X), R_L(X), C_F(X), C_L(X))$. Note that not any quadruple $(S_1, S_2, S_3, S_4)$ of string languages $S_1, S_2 \subseteq \Sigma^n$ and $S_3, S_4 \subseteq \Sigma^m$, can be the frame of a set of pictures since the corresponding strings need to match in the corner positions. If there exists a picture language $X \subseteq \Sigma^{m,n}$ such that $frame(X) = (S_1, S_2, S_3, S_4)$ we say that the quadruple is frame-compatible.

The following definition captures a sufficient condition for a set $X$ to be non-
expandable with respect to the overlapping. (Note that pictures inside $X$ could
possibly overlap each others).

**Definition 9.** Let $X \subseteq \Sigma^{m,n}$. $X$ is frame-complete if for any $p, q \in X$, $p$ and $q$ do not frame-overlap, and if for any picture $p \in \Sigma^{m,n} \setminus X$ there exists a picture $q \in X$ such that $p$ and $q$ frame-overlap.

Frame-complete sets of pictures can be constructed by exploiting the follow-
ing proposition.

**Proposition 10.** Let $S_1, S_2 \subseteq \Sigma^n, S_3, S_4 \subseteq \Sigma^m$ and $(S_1, S_2, S_3, S_4)$ be a quadruple of frame-compatible string languages. If for each pair $(M, N) = (S_1, S_2)$ or $(M, N) = (S_3, S_4)$ the following properties hold

1. $M \cap N = \emptyset$.

2. for any $u \in M, v \in N$, $u$ and $v$ do not overlap.

3. for any $w \notin M \cup N$, there exist $u \in M, v \in N$ such that $w$ and $u$ overlap, and $w$ and $v$ overlap

then the set $X$ of all the pictures $p$ with $frame(p) \in S_1 \times S_2 \times S_3 \times S_4$ is
frame-complete.

The next proposition states some sufficient conditions for a subset $Y$ of a
frame-complete set $X$ to be NENO. The idea is that, providing that $Y$ has the
same frame as $X$, we can choose $Y$ as a maximal non-overlapping set inside $X$.
Moreover, in order to choose the pictures in $Y$, we need only to check overlaps
of size $(h, k)$ with $h, k \ge 2$; that is we do not need to take care of frame-overlaps
in this next step.
**Proposition 11.** Let $X \subseteq \Sigma^{m,n}$ be a frame-complete set. If a subset $Y$ of $X$ is such that

a) $frame(Y) = frame(X)$

b) $Y$ is non-overlapping

c) for any $p \in X \setminus Y$ there exists $q \in Y$ such that $p$ and $q$ overlap

then $Y$ is a NENO set.

A first example of a NENO set is given in [9] by exploiting Proposition 11. A particular frame is chosen in a way that the set $X$ of all pictures with that frame is frame-complete and then the NENO set $Y$ is extracted from $X$. It was not clear the role of the frame in extracting $Y$. The problem whether, once fixed the frame, the set $Y$ was uniquely determined, was left open. Here, we show that there can be different NENO sets with the same frame. Let us start defining the frame.

*Example 12.* Let $\Sigma = \{0,1\}$ and let $\mathcal{F} = (S_1, S_2, S_3, S_4)$ be a quadruple of string languages defined as follows:

$$ - S_1 = \{1w0 \mid |w| = n-2, w \neq 0^{n-2}, w \text{ with no suffix in } 110^*\} \subseteq \Sigma^n $$

$$ - S_2 = \{110^{n-2}\} \subseteq \Sigma^n $$

$$ - S_3 = \{1w1 \mid w \in \{0,1\}^{m-2}\} \subseteq \Sigma^m $$

$$ - S_4 = \{0^m\} \subseteq \Sigma^m $$

After comparing the first and last symbols of the strings in $S_i$, we note that $\mathcal{F}$ is frame-compatible. Let us show that the pairs $(S_1, S_2)$ and $(S_3, S_4)$ verify all the conditions in Proposition 10.

Consider the pair $(S_1, S_2)$. The sets $S_1$ and $S_2$ are disjoint and no strings $u \in S_1$ and $v \in S_2$ overlap by definition. Let $s$ be any string $s \notin S_1 \cup S_2$. If $s = 0x$ then $s$ overlaps any string in $S_1$ and the string in $S_2$ with an overlap of length 1. If $s = 1y1$ then $s$ overlaps any string in $S_1$ and the string in $S_2$ with an overlap of length 1. If $s = 1z0$ then, since $s \notin S_1$, two cases are possible: either $z \in 0^*$ or $z$ has a suffix, say $r$, in $110^*$. In the first case, $s$ overlaps some string in $S_1$ with an overlap of length 2 and $s$ overlaps the string in $S_2$ with an overlap of length $|s| - 1$. In the second case $s$ overlaps some string in $S_1$ with an overlap of length $|r|$ and $s$ overlaps the string in $S_2$ with an overlap of length $|r| + 1$.

Consider now the pair $(S_3, S_4)$. The sets $S_3$ and $S_4$ are disjoint and no strings in $S_3$ can be overlapped with a string in $S_4$. Moreover, let $s$ be any string $s \notin S_3 \cup S_4$. Two cases are possible: $s = 0x$ or $s = 1y$. In the first case, $s$ overlaps the string in $S_4$ with an overlap of length 1. Moreover, since $s \notin S_4$, we can write $s = 0^k 1 r$ for some $k \ge 1$, and then $s$ overlaps some string in $S_3$ with an overlap of length $k + 1$. In the second case, $s$ overlaps any string in $S_3$ with an overlap of length 1. Moreover, since $s \notin S_3$, we have $s = 1z0$ and therefore $s$ overlaps the string in $S_4$ with an overlap of length 1.

Finally, by Proposition 10, we can affirm that the set of all the pictures in $\Sigma^{m,n}$ that have frame in $(S_1, S_2, S_3, S_4)$ is frame-complete.

We now define a set $P(m,n)$ of pictures of size $(m,n)$, which have the quadruple $(S_1, S_2, S_3, S_4)$ of Example 12 as their frame, while their internal part is
filled with all 0's, apart for the positions in the second column that can hold either 0 or 1. See the leftmost picture in Figure 2 for a generic picture in $P(m, n)$, where $x, y, w \in \{0, 1\}^*$, $w \neq 0^{n-2}$, and $w$ has no suffix in $110^*$.

**Definition 13.** Let $\Sigma = \{0, 1\}$ and $m, n \ge 4$. Let $S_1, S_2 \subseteq \Sigma^n$ and $S_3, S_4 \subseteq \Sigma^m$ be the languages $S_1 = \{1w0 \mid |w| = n - 2, w \neq 0^{n-2}, w \text{ with no suffix in } 110^*\}$, $S_2 = \{110^{n-2}\}$, $S_3 = \{1w1 \mid w \in \{0, 1\}^{m-2}\}$ and $S_4 = \{0^m\}$. Let $X(m, n) \subseteq \Sigma^{m,n}$ be the set of all the pictures $p$ with $frame(p) \in S_1 \times S_2 \times S_3 \times S_4$.

The set $P(m,n) \subseteq X(m,n)$ is the set of all the pictures $p \in X(m,n)$ such that $p(i,j) = 0$ for $2 \le i \le m-1$ and $3 \le j \le n-1$.

**Proposition 14.** The language $P(m,n)$ in Definition 13 is a NENO set, for any $m,n \ge 4$.

*Proof.* Let $X(m, n)$ and $P(m, n)$ be the languages defined in Definition 13. The set $X(m, n)$ is frame-complete as shown in Example 12. Let us show that $P(m, n)$ satisfies the conditions a), b), and c), of Proposition 11.

a) $frame(P(m,n)) = frame(X(m,n))$

It is obvious.

b) *P*(m, n) is non-overlapping.

Let $p, q \in P(m,n)$. The pictures $p$ and $q$ cannot frame-overlap, because the pairs $(R_F(X(m,n)), R_L(X(m,n)))$, $(C_F(X(m,n)), C_L(X(m,n)))$ satisfy condition 2. of Proposition 10 (as shown in Example 12).

The pictures $p$ and $q$ cannot h-slide overlap, because the last row of any picture in $P(m,n)$ is unbordered. The pictures $p$ and $q$ cannot v-slide overlap because, for any $p, q \in P(m,n)$, $p(1,3)p(1,4) \dots p(1,n) \neq q(i,3)q(i,4) \dots q(i,n)$, for $2 \le i \le m$.

Moreover, $p$ and $q$ cannot tl-overlap. Indeed, since they cannot h-slide or v-slide overlap, and $p(1,1) = q(1,1) = 1$, then $p$ and $q$ could eventually tl-overlap only with an overlap of size $(h,n-1)$ with $1 < h < m$. But this would imply that the first row of a picture in $P(m,n)$ is of the form $1w0$ with $w = 0^{n-2}$ and this is impossible.

Finally, $p$ and $q$ cannot bl-overlap. Indeed, since they cannot h-slide or v-slide overlap, and $p(m,1) = q(m,1) = 1$, we have that $p$ and $q$ could eventually bl-overlap only with an overlap of size $(h,n-1)$ with $1 < h < m$. But this would imply that position $(h,3)$ of a picture in $P(m,n)$ carries symbol 1 and this is impossible.

c) For any $p \in X(m,n) \setminus P(m,n)$ there exists $q \in P(m,n)$ such that $p$ and $q$ overlap.

If $p \in X(m,n) \setminus P(m,n)$ then $frame(p) \in S_1 \times S_2 \times S_3 \times S_4$, but there exists $(i,j)$, with $2 \le i \le m-1$ and $3 \le j \le n-1$, such that $p(i,j) = 1$. Let $(i_0, j_0)$ be the rightmost among the lowest positions such that $p(i_0, j_0) = 1$. Then, one can find in $P(m,n)$ a picture $q$ such that $p$ and $q$ tl-overlap, since there exists in $P(m,n)$ a picture $q$ with its tl-prefix of size $(m-i_0+1, n-j_0+1)$ equal to the br-prefix of $p$ of size $(m-i_0+1, n-j_0+1)$. $\square$
<figure><img src="image_8.png" /><figcaption>**Fig. 2.** From left to right: a generic picture in $P(m, n)$ and three pictures in $X(5, 5) \setminus T(5, 5)$ that violate condition 1), 2) and 3), respectively, in the positions in bold.</figcaption></figure>

We now define another set of pictures $T(m, n)$ with the same frame as $P(m, n)$. This time the positions in the internal part of the pictures can hold 0 or 1 everywhere, except for some special forbidden configurations. For example, there cannot be rows with a suffix in $110^+$, or some particular L-shapes. Here below is the formal definition, while some forbidden configurations are illustrated in Figure 2.

**Definition 15.** Let $X(m, n) \subseteq \Sigma^{m,n}$ be the set given in Definition 13. The set $T(m, n) \subseteq X(m, n)$ is the set of all the pictures $p \in X(m, n)$ such that

1. if there exists $(i, j)$, with $2 \le i \le m-1$ and $2 \le j \le n-2$, such that $p(i, 1) = p(i, 2) = \dots = p(i, j) = 0$ and $p(1, j) = p(2, j) = \dots = p(i-1, j) = 0$, then there exists $(i', j')$, with $1 \le i' < i$ and $1 \le j' < j-1$, such that $p(i', j')p(i', j'+1)\dots p(i', j) \in 110^+$.

2. there exists no index $i, 2 \le i \le m-1$, such that $p(i, 1) = 1, p(i, 2) = p(i, 3) = \dots = p(i, n-1) = 0$ and $p(1, n-1) = p(2, n-1) = \dots = p(i-1, n-1) = 0$.

3. there exists no $(i, j)$, with $1 \le i \le m-1$ and $1 \le j \le n-1$, such that $p(i, j)p(i, j+1)\dots p(i, n) \in 110^+$.

**Proposition 16.** The language $T(m, n)$ in Definition 15 is a NENO set, for any $m, n \ge 4$.

*Proof.* The set $X(m, n)$ is frame-complete (see Example 12). Let us show that $T(m, n)$ satisfies conditions a), b), and c), of Proposition 11. Condition a) is trivially true.

b) $T(m, n)$ is non-overlapping.

Let $p, q \in T(m, n)$. The pictures $p$ and $q$ cannot frame-overlap, because the pairs $(R_F(X(m, n)))$, $(R_L(X(m, n)))$, $(C_F(X(m, n)))$, $(C_L(X(m, n)))$ satisfy condition 2. of Proposition 10 (as shown in Example 12).

The pictures $p$ and $q$ cannot h-slide overlap, because the last row of any picture in $T(m, n)$ is unbordered. The pictures $p$ and $q$ cannot v-slide overlap because of condition 3) in the definition of $T(m, n)$.

Moreover, $p$ and $q$ cannot tl-overlap. Indeed, suppose that $p$ and $q$ tl-overlap with an overlap of size $(h, k)$ and w.l.o.g. suppose that the tl-corner of $p$ is inside $q$.
If $k = n - 1$ then $p$ violates condition 2) with $i = h$.

If $k < n - 1$, then we have $p(h, 1) = p(h, 2) = \dots = p(h, k) = 0$ and $p(1, k) = p(2, k) = \dots = p(h - 1, k) = 0$. By condition 1), there exists $(i', j')$, with $1 \le i' < h$ and $1 \le j' < k - 1$, such that $p(i', j')p(i', j' + 1) \dots p(i', k) \in 110^+$. Therefore, picture $q$ violates condition 3) in its $(m - h + i' + 1)$-th row.

Finally, $p$ and $q$ cannot bl-overlap. Indeed, suppose that $p$ and $q$ bl-overlap with an overlap of size $(h, k)$ and w.l.o.g. suppose that the bl-corner of $p$ is inside $q$. In this case $q$ violates condition 3) in position $(h, n - k + 1)$.

c) For any $p \in X(m, n) \setminus T(m, n)$ there exists $q \in T(m, n)$ such that $p$ and $q$ overlap.

If $p \in X(m, n) \setminus T(m, n)$ then $frame(p) \in S_1 \times S_2 \times S_3 \times S_4$, but $p$ does not satisfy at least one condition among 1), 2) and 3) in Definition 15.

Let $(i_0, j_0)$ be the highest position of $p$ that violates some condition.
If in position $(i_0, j_0)$ condition 1) is violated, then there exists $q \in T(m, n)$ with the br-prefix of $q$ of size $(i_0, j_0)$ equal to the tl-prefix of $p$ of the same size i.e. $p$ and $q$ tl-overlap. Note that the maximality of $(i_0, j_0)$ implies that $q$ does not violate neither condition 1) nor condition 2). Moreover, since there exists no $(i', j')$, with $1 \le i' < i_0$ and $1 \le j' < j_0 - 1$, such that $p(i', j')p(i', j' + 1) \dots p(i', j_0) \in 110^+$, then $q$ does not violate condition 3).

Similar reasonings show that there exists $q \in T(m, n)$ such that $p$ and $q$ tl-overlap, also when in position $(i_0, j_0)$ condition 2) or 3) is violated. □

We have defined two NENO sets of pictures $P(m, n)$ and $T(m, n)$ with the same frame. Note that the two languages are different, actually they are disjoint. It would be interesting to investigate the relationships among NENO sets with the same frame together with the role of the frame in their definitions.

## References

1. Aigrain, P., Beauquier, D.: Polyomino tilings, cellular automata and codicity. Theoretical Computer Science 147, 165–180 (1995)

2. Anselmo, M., Giammarresi, D., Madonia, M.: Deterministic and unambiguous families within recognizable two-dimensional languages. Fund. Inform 98(2-3), 143–166 (2010)

3. Anselmo, M., Giammarresi, D., Madonia, M.: Strong prefix codes of pictures. In: Muntean, T., Poulakis, D., Rolland, R. (eds.) Procs. CAI2013. pp. 47–59. LNCS 8080. Springer-Verlag, Berlin Heidelberg (2013)

4. Anselmo, M., Giammarresi, D., Madonia, M.: Two-dimensional codes of pictures. In: Béal, M.P., Carton, O. (eds.) Procs. DLT2013. pp. 46–57. LNCS 7907, Springer, Heidelberg (2013)

5. Anselmo, M., Giammarresi, D., Madonia, M.: Unbordered pictures: Properties and construction. In: Maletti, A. (ed.) Procs. CAI2015. pp. 45–57. LNCS 9270. Springer (2015)

6. Anselmo, M., Giammarresi, D., Madonia, M., Restivo, A.: Unambiguous recognizable two-dimensional languages. ITA 40(2), 227–294 (2006)

7. Anselmo, M., Giammarresi, D., Madonia, M.: A computational model for tiling recognizable two-dimensional languages. Theor. Comput. Sci. 410(37), 3520–3529 (2009)
8. Anselmo, M., Giammarresi, D., Madonia, M.: Prefix picture codes: a decidable class of two-dimensional codes. Int. J. Found. Comput. Sci. 25(8), 1017–1032 (2014)

9. Anselmo, M., Giammarresi, D., Madonia, M.: Non-expandable non-overlapping sets of pictures. Theor. Comput. Sci. 657, 127–136 (2017)

10. Anselmo, M., Giammarresi, D., Madonia, M.: Picture codes and deciphering delay. Inf. Comput. 253, 358–370 (2017)

11. Anselmo, M., Giammarresi, D., Madonia, M.: Structure and properties of strong prefix codes of pictures. Mathematical Structures in Computer Science 27(2), 123–142 (2017), http://journals.cambridge.org/article-S0960129515000043

12. Anselmo, M., Madonia, M.: Two-dimensional comma-free and cylindric codes. Theor. Comput. Sci. 658, 4–17 (2017)

13. Bajic, D.: On construction of cross-bifix-free kernel sets. 2nd MCM COST 2100 (2007, Lisbon, Portugal)

14. Bajic, D., Loncar-Turukalo, T.: A simple suboptimal construction of cross-bifix-free codes. Cryptography and Communications 6(1), 27–37 (2014)

15. Barcucci, E., Bernini, A., Bilotta, S., Pinzani, R.: Cross-bifix-free sets in two dimensions. Theor. Comput. Sci. 664, 29–38 (2017)

16. Barcucci, E., Bernini, A., Bilotta, S., Pinzani, R.: Non-overlapping matrices. Theor. Comput. Sci. 658, 36–45 (2017)

17. Beauquier, D., Nivat, M.: A codicity undecidable problem in the plane. Theoret. Comp. Sci 303, 417–430 (2003)

18. Berstel, J., Perrin, D., Reutenauer, C.: *Codes and Automata*. Cambridge University Press (2009)

19. Bilotta, S., Pergola, E., Pinzani, R.: A new approach to cross-bifix-free sets. IEEE Transactions on Information Theory 58(6), 4058–4063 (2012)

20. Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: SWAT (FOCS). pp. 155–160 (1967)

21. Bozapalidis, S., Grammatikopoulou, A.: Picture codes. ITA 40(4), 537–550 (2006)

22. Chee, Y.M., Kiah, H.M., Purkayastha, P., Wang, C.: Cross-bifix-free codes within a constant factor of optimality. IEEE Transactions on Information Theory 59(7), 4668–4674 (2013)

23. Crochemore, M., Iliopoulos, C.S., Korda, M.: Two-dimensional prefix string matching and covering on square matrices. Algorithmica 20(4), 353–373 (1998)

24. Crochemore, M., Rytter, W.: Jewels of stringology. World Scientific (2002), http://www-igm.univ-mlv.fr/mac/JOS/JOS.html

25. Giammarresi, D., Restivo, A.: Recognizable picture languages. Int. Journal Pattern Recognition and Artificial Intelligence 6(2-3), 241–256 (1992)

26. Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Handbook of Formal Languages, pp. 215–268. Springer Verlag, G.Rozenberg, Eds, Vol. III (1997)

27. Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press (1997)

28. Kari, J., Salo, V.: A survey on picture-walking automata. In: Kuich, W., Rahonis, G. (eds.) Algebraic Foundations in Computer Science. LNCS, vol. 7020, pp. 183–213. Springer (2011)

29. Kolarz, M., Moczurad, W.: Multiset, set and numerically decipherable codes over directed figures. In: Combinatorial Algorithms. pp. 224–235. LNCS 7643, Springer (2012)

30. Nielsen, P.T.: A note on bifix-free sequences. IEEE Transactions on Information Theory 19(5), 704–706 (1973)

31. Pradella, M., Cherubini, A., Crespi-Reghizzi, S.: A unifying approach to picture grammars. Inf. Comput. 209(9), 1246–1267 (2011)