MnLargeSymbols’164 MnLargeSymbols’171

11institutetext: Politecnico di Milano - DEIB 22institutetext: Dipartimento di
Matematica e Informatica, Università di Palermo 22email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Two-dimensional Dyck words

Stefano Crespi Reghizzi 11 Antonio Restivo 22 Pierluigi San Pietro 11

###### Abstract

We propose different ways of lifting the notion of Dyck language from words to
2-dimensional (2D) arrays of symbols, i.e., pictures, by means of new
definitions of increasing comprehensiveness. Two of the proposals are based on
alternative definitions of a Dyck language, which are equivalent over words
but not on pictures.

First, the property that any two pairs of matching parentheses are either
well-nested or disjoint, is rephrased for rectangular boxes and leads to the
well-nested Dyck, $DW_{k}$. The latter is a generalization of the known
Chinese box language. We prove that, unlike the Chinese boxes, the language
$DW_{k}$ is not recognizable by a tiling system.

Second, the Dyck cancellation rule is rephrased as a neutralization rule,
mapping a quadruple of symbols representing the corners of a subpicture onto
neutral symbols.The neutralizable Dyck language $DN_{k}$ is obtained by
iterating neutralizations, starting from 2-by-2 subpictures, until the picture
is wholly neutralized.

Third, we define the Dyck crossword $DC_{k}$ as the row-column combination of
Dyck word languages, which prescribes that each column and row is a Dyck word.
The relation between matching parentheses is represented in $DC_{k}$ by an
edge of a graph situated on the picture grid. Such edges form a circuit, of
path length multiple of four, of alternating row and column matches. Length-
four circuits have rectangular shape, while longer ones exhibit a large
variety of forms. A proper subset of $DC_{k}$, called quaternate, is also
introduced by excluding all circuits of length greater than 4. We prove that
$DN_{k}$ properly includes $DW_{k}$, and that it coincides with the quaternate
$DC_{k}$ such that the neutralizability relation between subpictures induces a
partial order. The 2D languages well-nested, neutralizable, quaternate and
Dyck crossword are ordered by strict inclusions. This work can be also seen as
a first step towards the definition of context-free picture languages.

##  1 Introduction

The Dyck language is a fundamental concept in formal language theory. Its
alphabet $\\{a_{1},\ldots,a_{k},\,a^{\prime}_{1},\ldots,a^{\prime}_{k}\\}$,
for any $k\geq 1$, is partitioned into the pairs
$[a_{1},a^{\prime}_{1}],\ldots,[a_{k},a^{\prime}_{k}]$. The language is the
set of all words that can be reduced to the empty word by cancellations of the
form $a_{i}a^{\prime}_{i}\to\varepsilon$. The centrality of the Dyck language
is expressed by the Chomsky-Schützenberger theorem [3] stating that any
context-free language is the homomorphic image of the intersection of a Dyck
language and a local one; intuitively, a regular language is local if it is
defined by the set of factors, of prefixes and of suffixes of length two.

Motivated by our interest for the theory of two-dimensional (2D) or picture
languages, we investigate the possibility to transport the Dyck concept from
one dimension to 2D. When moving from 1D to 2D, most formal language concepts
and relationships drastically change. In particular, in 2D the Chomsky’s
language hierarchy is blurred because the notions of regularity and context-
freeness cannot be formulated for pictures without giving up some
characteristic properties that hold for words. In fact, it is known [8] that
the three equivalent definitions of regular languages by means of finite-state
recognizer, by regular expressions, and by the homomorphism of local
languages, produce in 2D three distinct language families. The third one gives
the family of _tiling system recognizable languages_ (REC) [8], that many
think to be the best fit for regularity in 2D.

The situation is less satisfactory for context-free (CF) languages where a
transposition in 2D remains problematic. None of the existing proposals of
“context-free” picture grammars ([16, 10, 11, 14, 5, 6], a survey is [4])
match the expressiveness and richness of formal properties of 1D CF grammars.
In this paper we make the first step towards a new definition of CF languages
by means of the following 2D reformulation of the Chomsky-Schützenberger
theorem, that, to avoid destroying the rectangular structure of a picture, we
take with a non-erasing homomorphism, as in [2, 12]. A context-free picture
language is the homomorphic, letter-to-letter image of the intersection of a
2D Dyck language and a 2D local language. While the notion of 2D local
language is well-known, we are not aware of any existing definitions of 2D
Dyck language; we know of just one particular example, the _Chinese box
language_ in [5], that intuitively consists of embedded or concatenated boxes,
and was proposed to illustrate the expressiveness of the grammars there
introduced; that language is not a satisfactory proposal, since it is in the
family REC, hence “regular”. Although a best definition of Dyck picture
languages might not exist, it is worth formalizing and comparing several
possible choices; this is our contribution, while the study of the resulting
2D CF languages is still under way and not reported here.

Our contribution includes four definitions of 2D “Dyck” languages based on
various approaches, a study of their properties and the proofs of their
inclusions.

It is time to describe the intuitions behind each proposal and, particularly,
the properties of Dyck words that are preserved in each case.

Instead of open and closed parentheses, the elements of a Dyck alphabet in 2D
are the four “corners” $\ulcorner,\,\urcorner,\,\llcorner,\,\lrcorner$; there
may be $k\geq 1$ distinct quadruples. Each corner quadruple encodes two 1D
Dyck alphabets, one for rows the other for columns. The row alphabet has the
pairs [$\ulcorner,\,\urcorner$] and [$\llcorner,\,\lrcorner$] while the column
alphabet has the pairs [$\ulcorner,\,\llcorner$] and
[$\urcorner,\,\lrcorner$]. When in a picture a corner quadruple is correctly
laid on the four vertexes of a rectangular subpicture we say that it
represents a rectangle.

We start from the simpler cases, the _well-nested Dyck language_ $DW_{k}$ and
the _neutralizable Dyck language_ $DN_{k}$. In both cases, a picture is
partitioned into rectangles, in the sense that each pixel is placed on a
vertex of a rectangle. The difference between $DW_{k}$ and $DN_{k}$ resides in
the relative positions that are permitted for the rectangles that cover a
picture.

In a $DW_{k}$ picture the rectangles are well nested and do not overlap each
other; thus it is fair to say that the well-nesting property of parenthesized
words is here preserved. This is the same constraint of the Chinese boxes [5],
which however use a different alphabet that is not a Dyck alphabet.

The definition of $DN_{k}$ is based on the observation that the Dyck
cancellation rule can be replaced by a neutralization rule that maps a pair of
matching parentheses onto a neutral symbol $N$, $a_{i}a^{\prime}_{i}\to NN$,
so that a word is well parenthesized if it can be transformed to a word in
$N^{+}$ of the same length. In 2D the reformulation of the neutralization rule
is: if a rectangle (having the four corner symbols as vertexes) includes only
neutral symbols, then the whole subpicture is neutralized. A picture is in
$DN_{k}$ if all corner symbols are replaced with $N$ by a sequence of
neutralization steps. We prove the language inclusion $DW_{k}\subset DN_{k}$.

The third approach is based on the crosswords of Dyck languages, a.k.a. row-
column compositions. A picture is in $DC_{k}$ if all rows and all columns are
Dyck words. Crosswords have been studied for regular languages (e.g., in [9,
7]) but not, to our knowledge, for context-free ones. A little reflection
suffices to realize that in $DN_{k}$, hence also in $DW_{k}$, the rows and
columns are Dyck words, therefore the inclusion $DN_{k}\subseteq DC_{k}$ is
obvious.

The interesting question is whether the inclusion is strict. Surprisingly,
$DC_{k}$ comprises pictures that do not belong to $DN_{k}$. A subclass of
$DC_{k}$, called _quaternate_ , or $DQ_{k}$, is the set of pictures covered by
rectangles. We prove that $DQ_{k}$ includes also not neutralizable pictures,
which present a circularity in the precedence relation that governs the
neutralization order.

But the family of Dyck crosswords includes a large spectrum of pictures where
patterns other than rectangles are present. Each pattern is a closed path,
called a _circuit_ , made by alternating horizontal and vertical edges,
representing a Dyck match on a row or on a column. A circuit label is a string
in the language $(\ulcorner\;\urcorner\,\lrcorner\;\llcorner)^{+}$, thus
having length $4k$. The circuit path may intersect itself one or more times on
the picture grid–the case of zero intersection is the rectangle. We prove that
for any value of $k\geq 0$ there exist pictures in $DC_{k}$ featuring a
circuit of length $4+8k$. We have examined some interesting types of Dyck
crosswords that involve complex circuits, but much remains to be understood of
the general patterns that are possible.

Section 2 lists basic concepts of picture languages and Dyck languages.
Section 3 recalls the Chinese boxes language, defines the $DW_{k}$ and
$DN_{k}$ languages, and studies their relations. Section 4 introduces the
$DC_{k}$ languages, exemplifies the variety of circuits they may contain, and
defines the quaternate subclass $DQ_{k}$. Section 5 proves the strict
inclusions of the four above languages. Section 6 mentions open problems.

##  2 Preliminaries

All the alphabets to be considered are finite. The following concepts and
notations for picture languages follow mostly [8]. A picture is a rectangular
array of letters over an alphabet. Given a picture $p$, $|p|_{row}$ and
$|p|_{col}$ denote the number of rows and columns, respectively;
$|p|=\left(|p|_{row},|p|_{col}\right)$ denotes the _picture size_. The set of
all non-empty pictures over $\Sigma$ is denoted by $\Sigma^{++}$.

A domain $d$ of a picture $p$ is a quadruple
$(i,j,{i^{\prime}},{j^{\prime}})$, with $1\leq i\leq i^{\prime}\leq|p|_{row}$,
and $1\leq j\leq j^{\prime}\leq|p|_{col}$. The _subpicture of $p$ _ with
domain $d=(i,j,{i^{\prime}},{j^{\prime}})$, denoted by $spic(p,d)$ is the
(rectangular) portion of $p$ defined by the top-left coordinates $(i,j)$ and
by the bottom right coordinates $({i^{\prime}},{j^{\prime}})$.

_Concatenations._ Let $p,q\in\Sigma^{++}$. The horizontal concatenation of $p$
and $q$ is denoted as $p\obar q$ and it is defined when $|p|_{row}=|q|_{row}$.
Similarly, the vertical concatenation $p\ominus q$ is defined when
$|p|_{col}=|q|_{col}$. We also use the power operations $p^{\ominus k}$ and
$p^{\obar k}$, $k\geq 1$, their closures $p^{\ominus+},$ $p^{\obar+}$ and we
extend the concatenations to languages in the obvious way.

The notation $N^{m,n}$, where $N$ is a symbol and $m,n>0$, stands for a
homogeneous picture of size $m,n$. For later convenience, we extend this
notation to the case where either $m$ or $n$ are 0, to introduce identity
elements for vertical and horizontal concatenations: given a picture $p$ of
size $(m,n)$, by definition $p\obar N^{m,0}=N^{m,0}\obar p=p$ and $p\ominus
N^{0,n}=N^{0,n}\ominus p=p$.

The _Simplot closure_ [15] operation $L^{**}$ is defined on a picture language
$L$ as the set of pictures $p$ tessellated by pictures in $L$, more precisely
defined by the following condition:

$\displaystyle\exists\text{ a partition of
}\\{1,\ldots,row(p)\\}\times\\{1,\ldots,col(p)\\}\text{ into }n\geq 1\text{
domains }d_{1},\ldots,d_{n}\text{ of }p$ $\displaystyle\text{ such that for
all }1\leq i\leq n\text{ the subpicture }spic(p,d_{i})\text{ is in }L.$ (1)

Notice that the concatenations $L^{\ominus k}$, $L^{\obar k}$ and their
closures $L^{\ominus+}$, $L^{\obar+}$ are included in the Simplot closure of
$L$, which therefore is the most general way of assembling a picture starting
from pictures in a given language.

To help understanding, we reproduce a picture in $L^{**}$, where $L$ is
tessellated into the 1-by-1, 1-by-2, 2-by-1, and 2-by-2 pictures shown, and
cannot be obtained by horizontal and vertical partitions:

p11&p12 p13 p14
p21 p22 p23 p24
p31 p32 p33 p34

[arcangle=90,linestyle=solid,linewidth=1.0pt]p11p12
[arcangle=90,linestyle=solid,linewidth=1.0pt]p12p11
[arcangle=90,linestyle=solid,linewidth=1.0pt]p14p24
[arcangle=90,linestyle=solid,linewidth=1.0pt]p24p14
[arcangle=90,linestyle=solid,linewidth=1.0pt]p21p31
[arcangle=90,linestyle=solid,linewidth=1.0pt]p31p21

[arcangle=90,linestyle=solid,linewidth=1.0pt]p22p23
[arcangle=90,linestyle=solid,linewidth=1.0pt]p23p33
[arcangle=90,linestyle=solid,linewidth=1.0pt]p33p32
[arcangle=90,linestyle=solid,linewidth=1.0pt]p32p22

We assume some familiarity with the basic properties of the family of REC
languages [8], in particular with their definition by the projection of a
local 2D language or equivalently, by the projection of the intersection of
two domino languages for rows and for columns.

#### Dyck alphabet and language

The definition and properties of Dyck languages are basic concepts in formal
language theory, yet we prefer to list them since each one of our developments
for 2D languages differs with respect to the property it strives to
generalize.

For a Dyck language $D\subseteq\Gamma_{k}^{*}$, the alphabet has size
$|\Gamma_{k}|=2k$ and is partitioned into two sets of cardinality $k\geq 1$,
denoted $\\{a_{i}\mid 1\leq i\leq k\\}\cup\\{a^{\prime}_{i}\mid 1\leq i\leq
k\\}$.

The Dyck language $D_{k}$ has several equivalent, definitions. We recall the
word congruence or cancellation rule defined by
$a_{i}a^{\prime}_{i}=\varepsilon$: a word is in $D_{k}$ if it is congruent to
$\varepsilon$, i.e., it can be erased to $\varepsilon$ by repeated application
of the cancellation rule. We say that in a word $x\in D_{k}$ two occurrences
of terminals $a_{i},\,a^{\prime}_{i}$ _match_ if they are erased together by
an application of the cancellation rule on $x$.

A characteristic of Dyck languages is that, in every word of $D_{k}$, any two
factors $a_{i}ya^{\prime}_{i}$ and $a_{j}wa^{\prime}_{j}$, with
$y,w\in\Gamma^{*}$ where $a_{i},a^{\prime}_{i}$ and $a_{j},a^{\prime}_{j}$ are
matching pairs, are either disjoint or _well-nested_.

A (non-$\varepsilon$) Dyck word is prime if it is not the concatenation of two
Dyck words. The set of prime words can be defined [1] as the set
$(D_{k}-\varepsilon)-(D_{k}-\varepsilon)^{2}$.

For future comparison with pictures, we introduce an equivalent definition of
the Dyck language by means of the following _neutralization rule_ instead of
the cancellation rule, since the latter does not work for pictures: erasing a
subpicture would not result in a picture. Let $N\notin\Gamma_{k}$ be a new
terminal character called _neutral_. For every word in
$(\Gamma_{k}\cup\\{N\\})^{*}$ define the congruence $\approx$, for all $1\leq
i\leq n$, and for all $m\geq 0$ as:

$a_{i}\,N^{m}a^{\prime}_{i}\approx N^{m+2}.$ (2)

A word $x\in\Gamma_{k}^{*}$ is in $D_{k}$ if it is $\varepsilon$ or it is
$\approx$-congruent to $N^{|x|}$. An equivalent definition of the Dyck
language is based on the observation that a Dyck word can be enlarged either
by surrounding it with a matching pair of parentheses, or by concatenating it
to another Dyck word. Therefore, the Dyck language over $\Gamma_{k}$ can be
defined through a nesting accretion rule: given a word $x\in\Gamma_{k}^{*}$, a
nesting accretion of $x$ is a word of the form $a_{i}xa^{\prime}_{i}$. The
language $D_{k}$ can then be defined as the smallest set including the empty
word and closed under concatenation and nesting accretion.

##  3 Box-based choices of Dyck picture languages

In this section we present two simple choices, called well-nested and
neutralizable, each one conserving one of the characteristic properties of
Dyck words.

To make the analogy with Dyck words more evident, we represent in 2D the
parentheses pair $[\,,\,]$ by a quadruple of corners
$\ulcorner,\,\urcorner,\,\llcorner,\,\lrcorner$. Then inside a picture such a
quadruple matches if it is laid on the four vertexes of a rectangle (i.e., a
subpicture), as we see in the picture
$\begin{array}[]{cccc}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ulcorner&\ulcorner&\urcorner&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\urcorner\\\
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\llcorner&\llcorner&\lrcorner&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\lrcorner\end{array}$
for each quadruple identified by a color.

First, we focus on the nesting accretion definition of Dyck words and extend
it to pictures by considering a quadruple of corners. The corresponding
picture languages are called _well-nested Dyck_ , denoted as $DW_{k}$.Then, we
extend the neutralization rule to 2D in a way that essentially preserves the
following property: two matching parentheses that encompass a neutral word can
be neutralized. Now, the two matching parentheses become a quadruple of
symbols representing the corners of a (rectangular) subpicture already
neutralized. The corresponding languages are called _neutralizable Dyck_
($DN_{k}$).

###  3.1 Well-nested Dyck language

The natural question of what should be considered a Dyck-like language in 2D
received a tentative answer in [5], where a language of well-embedded
rectangular boxes, called Chinese boxes, was presented as an example of the
generative power of the tile rewriting grammars there introduced.

The alphabet is
$\Gamma=\\{\ulcorner,\urcorner,\llcorner,\lrcorner,\bullet\\}$; the corner
symbols represent the four box vertexes and a horizontal/vertical string of
bullets represents a box side. Instead of the original grammar formalism, we
give a recursive definition.

######  Definition 1 (Chinese boxes [5])

Given a picture $p$ of size $(n,m)$, with $n,m\geq 0$, its Chinese accretion
is the picture:

$\left(\ulcorner\,\obar\,\bullet^{\obar
m}\,\obar\,\urcorner\right)\,\ominus\,\left(\bullet^{\ominus
n}\,\obar\,p\,\obar\,\bullet^{\ominus
n}\right)\ominus\left(\llcorner\,\obar\,\bullet^{\obar
m}\,\obar\,\lrcorner\right)$

i.e.,
$\begin{array}[]{ccccc}\ulcorner&\lx@intercol\hfil\bullet\dots\bullet\hfil\lx@intercol&\urcorner\\\
\bullet&\lx@intercol\hfil\hfil\lx@intercol&\bullet\\\ \vdots&\lx@intercol\hfil
p\hfil\lx@intercol&\vdots\\\
\bullet&\lx@intercol\hfil\hfil\lx@intercol&\bullet\\\
\llcorner&\lx@intercol\hfil\bullet\dots\bullet\hfil\lx@intercol&\lrcorner\\\
\end{array}\quad$ or the picture $\begin{array}[]{cc}\ulcorner&\urcorner\\\
\llcorner&\lrcorner\end{array}$ when $p$ is empty.

The Chinese boxes language, denoted by $DB$, is defined as the smallest set
including the empty picture and closed under horizontal and vertical
concatenations, and under Chinese accretion.

An example is in Figure 1 (middle). Initially erroneously believed not to be
recognizable, a tiling system for language $DB$ was later found (see [13])
thus proving the contrary. Therefore, if we agree with the opinion that the
analogue of regular 1D languages are the recognizable picture languages, then
$DB$ does not qualify as a good 2D analogue of the Dyck 1D languages since the
latter are not regular.

In addition we observe that a row word is similar to a Dyck word since the
pairs $[\ulcorner,\urcorner]$ and $[\llcorner,\lrcorner]$ act as matching
pairs, but it also contains the symbol $\bullet$ which has no matching
symbol111Such a matchless symbol, when is added to a Dyck alphabet, is usually
called _neutral_.; the case for column words is analogous, with the matching
pair $[\ulcorner,\llcorner]$ and $[\urcorner,\lrcorner]$.

The next definition extends to 2D the following property of Dyck 1D: a Dyck
word can be enlarged either by surrounding it with a matching pair of
parentheses, or by concatenating it to another Dyck word. Similarly, we are
going to define the well-nested 2D Dyck languages by means of accretion of a
well-nested picture, or by concatenations–actually by the more general Simplot
closure.

The alphabet consists of the corner symbols, that we prefer to represent by
Latin letters to simplify typography, with the correspondence:
$a=\,_{\big{\ulcorner}},\,b=\,_{\big{\urcorner}},\,c=\llcorner,\,d=\lrcorner$,
thus the picture  $\begin{array}[]{cc}\ulcorner&\urcorner\\\
\llcorner&\lrcorner\end{array}$ is the same as  $\begin{array}[]{cc}a&b\\\
c&d\end{array}$ . In general, as for Dyck word languages, we allow multiple
copies of the four symbols, i.e., the alphabet is
$\Delta_{k}=\\{a_{i},b_{i},c_{i},d_{i}\mid 1\leq i\leq k\\}$, $k\geq 1$, and
$\Delta_{1}=\\{a,b,c,d\\}$.

The following definition is similar to Definition 1 but substitutes corners to
the bullets “$\bullet$”.

######  Definition 2 (well-nested Dyck picture language)

Let $\Delta_{k}=\\{a_{i},b_{i},c_{i},d_{i}\mid 1\leq i\leq k\\}$. Define two
bijections: $h_{r}:\\{a_{i},b_{i}\\}\to\\{c_{i},d_{i}\\}$,
$h_{c}:\\{a_{i},c_{i}\\}\to\\{b_{i},d_{i}\\}$ with $h_{r}(a_{i})=c_{i}$,
$h_{r}(b_{i})=d_{i}$ and $h_{c}(a_{i})=c_{i}$, $h_{c}(c_{i})=d_{i}$.

For every picture $p\in\Delta_{k}^{++}$, for all rows $w_{r}$ in the (word)
Dyck language over the parentheses ${[a_{i},b_{i}]}$, and for all columns
$w_{c}$ in the Dyck language over the parentheses ${[a_{i},c_{i}]}$, such that
$|w_{r}|=|p|_{col}$, $|w_{c}|=|p|_{row}$, the nesting accretion of $p$ within
$w_{r},w_{c}$ is the picture:

$\left(a_{i}\,\obar\,w_{r}\,\obar\,b_{i}\right)\ominus\left(w_{c}\,\obar\,p\,\obar\,h_{c}\left(w_{c}\right)\right)\ominus\left(c_{i}\,\obar\,h_{r}\left(w_{r}\right)\,\obar\,d_{i}\right).$

The language $DW_{k}$ is the smallest set including the empty picture and
closed under nesting accretion and Simplot closure (see (1) in Section 2).

Figure 1 (right) illustrates accretion and (left) shows a picture in $DW_{1}$;
for comparison a Chinese box picture of the same size is shown in the middle.

$\begin{array}[]{c c c
c}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ulcorner&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\ulcorner&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\urcorner&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\urcorner\\\
\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\ulcorner&\ulcorner&\urcorner&\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\urcorner\\\
\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\llcorner&\llcorner&\lrcorner&\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\lrcorner\\\
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\llcorner&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\llcorner&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lrcorner&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\lrcorner\end{array}$
$\begin{array}[]{c c c c}\ulcorner&\bullet&\bullet&\urcorner\\\
\bullet&\ulcorner&\urcorner&\bullet\\\ \bullet&\llcorner&\lrcorner&\bullet\\\
\llcorner&\bullet&\bullet&\lrcorner\end{array}$
$\begin{array}[]{|ccc|ccc|c|}\hline\cr&a_{i}&&\lx@intercol\hfil
w_{r}\hfil\lx@intercol\vrule\lx@intercol&b_{i}\\\
\cline{1-7}\cr&&&\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol&\\\
&w_{c}&&\lx@intercol\hfil p\hfil\lx@intercol\vrule\lx@intercol&h_{c}(w_{c})\\\
&&&\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol&\\\
\cline{1-7}\cr&c_{i}&&\lx@intercol\hfil
h_{r}(w_{r})\hfil\lx@intercol\vrule\lx@intercol&d_{i}\\\ \hline\cr\end{array}$

Figure 1: (Left) An example of picture in $DW_{1}$ and (middle) the similar
Chinese box version. (Right) Scheme of nesting accretion.

The definition can be explained intuitively by considering two distinct
occurrences of a quadruple of matching corners: the subpictures delimited by
each quadruple (i.e., their bounding boxes) are either disjoint, or included
one into the other; or they overlap and a third box exists that “minimally”
bounds both boxes. The third case is illustrated in Figure 1, left, by the
overlapping blue and green boxes.

It is immediate to see that for any size $(2m,2n)$, $m,n\geq 1$, there is a
picture in $DW_{k}$.

###### Theorem 3.1

The language $DW_{k}$ is not (tiling system) recognizable, for every $k\geq
1$.

###### Proof

By contradiction, assume that $DW_{k}$ is recognizable. Without loss of
generality, we consider only the case $k=1$. Consider the following picture
$p$ in $DW_{1}$: $\begin{array}[]{cc}a&b\\\ c&d\end{array}$. From closure
properties of REC, the language $p^{\obar+}$ is recognizable, hence also the
language:

$R=\left(a^{\obar+}\,\obar\,b^{\obar+}\right)\ominus\left((a\,\ominus\,c)\obar\,p^{\obar+}\,\obar\,(b\,\ominus\,d)\right)\ominus\left(c^{\obar+}\,\obar\,d^{\obar+}\right).$

A picture in $R$ has $a^{+}b^{+}$ in the top row and $c^{+}d^{+}$ in the
bottom row. Let $T$ be the language obtained by intersection of $DW_{1}$ with
$R^{\ominus+}$. Therefore, both $T$ and $T^{\ominus+}$ are also recognizable;
moreover, the first row of every picture in $T^{\ominus+}$ has the form
$a^{n}b^{n}$. By applying the Horizontal Iteration Lemma of [8] (Lemma 9.1) to
$T^{\ominus+}$, there exists a (suitably large) picture $t$ in $T^{\ominus+}$
which can be written as the horizontal concatenation of the three (non empty)
pictures $x,q,y$, namely $t=x\obar q\obar y$, such that $x\obar
q^{i\obar}\obar y$ is also in $T^{\ominus+}$, a contradiction with the fact
that the top row of the pictures in $T^{\ominus+}$ must be of the form
$a^{n}b^{n}$.

###  3.2 Neutralizable Dyck language

We investigate a possible definition of Dyck picture languages by means of a
neutralization rule analogous to the congruence (2) of Dyck word languages.

######  Definition 3 (neutralizable Dyck language)

Let $N$ be a new symbol not in $\Delta_{k}$. The neutralization relation
$\stackrel{{\scriptstyle\nu}}{{\to}}\subseteq\left(\\{N\\}\cup\Delta_{k}\right)^{++}\times\left(\\{N\\}\cup\Delta_{k}\right)^{++}$,
is the smallest relation such that for every pair of pictures $p,p^{\prime}$
in $\left(\\{N\\}\cup\Delta_{k}\right)^{++}$,
$p\stackrel{{\scriptstyle\nu}}{{\to}}p^{\prime}$ if there are $m,n\geq 2$ and
$1\leq i\leq k$, such that $p^{\prime}$ is obtained from $p$ by replacing a
subpicture of $p$ of the form:

$(a_{i}\ominus N^{m-2,1}\ominus c_{i})\obar N^{m,n-2}\obar(b_{i}\ominus
N^{m-2,1}\ominus d_{i}).$ (3)

with the picture of the same size $N^{m,n}$.

The 2D _neutralizable Dyck language_ , denoted with
$DN_{k}\subseteq\Delta_{k}^{++}$, is the set of pictures $p$ such that there
exists $p^{\prime}\in N^{++}$ with
$p\stackrel{{\scriptstyle\nu}}{{\to}}^{+}p^{\prime}$.

In other words, a $DN_{k}$ picture is transformed into a picture in $N^{++}$
by a series of neutralizations. It is obvious that the order of application of
the neutralization steps is irrelevant for deciding if a picture is
neutralizable.

######  Example 1 (neutralizations)

The following picture $p_{1}$ on the alphabet $\Delta_{1}$ is in $DN_{1}$
since it reduces to the neutral one by means of a sequence of six
neutralization steps:

$p_{1}=\begin{array}[]{c c c c c
c}\ulcorner&\ulcorner&\urcorner&\ulcorner&\urcorner&\urcorner\\\
\ulcorner&\ulcorner&\urcorner&\llcorner&\lrcorner&\urcorner\\\
\llcorner&\llcorner&\lrcorner&\ulcorner&\urcorner&\lrcorner\\\
\llcorner&\llcorner&\lrcorner&\llcorner&\lrcorner&\lrcorner\end{array}\stackrel{{\scriptstyle\nu}}{{\to}}\begin{array}[]{c
c c c c c}\ulcorner&\ulcorner&\urcorner&\ulcorner&\urcorner&\urcorner\\\
\ulcorner&N&N&\llcorner&\lrcorner&\urcorner\\\
\llcorner&N&N&\ulcorner&\urcorner&\lrcorner\\\
\llcorner&\llcorner&\lrcorner&\llcorner&\lrcorner&\lrcorner\end{array}\stackrel{{\scriptstyle\nu}}{{\to}}\begin{array}[]{c
c c c c c}\ulcorner&N&N&\ulcorner&\urcorner&\urcorner\\\
\ulcorner&N&N&\llcorner&\lrcorner&\urcorner\\\
\llcorner&N&N&\ulcorner&\urcorner&\lrcorner\\\
\llcorner&N&N&\llcorner&\lrcorner&\lrcorner\end{array}\stackrel{{\scriptstyle\nu}}{{\to}}\begin{array}[]{c
c c c c c}\ulcorner&N&N&N&N&\urcorner\\\ \ulcorner&N&N&N&N&\urcorner\\\
\llcorner&N&N&\ulcorner&\urcorner&\lrcorner\\\
\llcorner&N&N&\llcorner&\lrcorner&\lrcorner\end{array}$

$\stackrel{{\scriptstyle\nu}}{{\to}}\begin{array}[]{c c c c c
c}\ulcorner&N&N&N&N&\urcorner\\\ \ulcorner&N&N&N&N&\urcorner\\\
\llcorner&N&N&N&N&\lrcorner\\\
\llcorner&N&N&N&N&\lrcorner\end{array}\stackrel{{\scriptstyle\nu}}{{\to}}\begin{array}[]{c
c c c c c}\ulcorner&N&N&N&N&\urcorner\\\ N&N&N&N&N&N\\\ N&N&N&N&N&N\\\
\llcorner&N&N&N&N&\lrcorner\end{array}\stackrel{{\scriptstyle\nu}}{{\to}}\begin{array}[]{c
c c c c c}N&N&N&N&N&N\\\ N&N&N&N&N&N\\\ N&N&N&N&N&N\\\ N&N&N&N&N&N\end{array}$

Neutralizations have been arbitrarily applied in top to bottom, left to right
order.

By a proof almost identical to the one of Theorem 3.1, since the language
$T^{\ominus+}$ can be obtained from $DN_{k}$ by intersection with a
recognizable language, we have:

###### Theorem 3.2

The language $DN_{k}$ is not (tiling system) recognizable for every $k\geq 1$.

Although $DW_{k}$ is defined by a diverse mechanism, the next inclusion is
immediate.

###### Theorem 3.3

The language $DW_{k}$ is strictly included in $DN_{k}$ for every $k\geq 1$.

###### Proof

The inclusion $DW_{k}\subseteq DN_{k}$ is obvious since any picture in
$DW_{k}$ can be neutralized in accordance with Definition 3. Then the thesis
follows since the neutralizable picture $p_{N}=\begin{array}[]{c c c
c}\ulcorner&\ulcorner&\urcorner&\urcorner\\\
\llcorner&\llcorner&\lrcorner&\lrcorner\\\ \end{array}$ cannot be obtained
using nesting accretion.

Another picture in $DN_{1}\setminus DW_{1}$ is in Figure 2.

##  4 Row-column combination of Dyck languages

We consider the pictures such that their rows and columns are Dyck languages,
more precisely, they are Dyck word languages over the same alphabet but with
different pairing of terminal characters. Such pictures, called Dyck
crosswords, may be viewed as analogous of Dyck word languages.

Following [8] we introduce the row-column combination operation that takes two
word languages and produces a picture language.

######  Definition 4 (row-column combination a.k.a. crossword)

Let $S^{\prime},S^{\prime\prime}\subseteq\Sigma^{*}$ be two word languages,
called _component languages_. The _row-column combination_ or _crossword_ of
$S^{\prime}$ and $S^{\prime\prime}$ is the picture language $L$ such that a
picture $p\in\Sigma^{++}$ belongs to $L$ if, and only if, the words
corresponding to each row (in left-to-right order) and to each column (in top-
down order) of $p$ belong to $S^{\prime}$ and $S^{\prime\prime}$,
respectively.

The row-column combination of regular languages has received attention in the
past since its alphabetic projection exactly coincide with the REC family [8];
some complexity issues for this case are addressed in the recent paper [7]
where the combinations are called “regex crosswords”. Moreover, given two
regular languages $S^{\prime},S^{\prime\prime}$, it is undecidable to
establish whether their composition is empty. In this section, we investigate
the properties of the row-column combination of a fundamental type of context-
free languages, the Dyck ones.

The picture alphabet is the same of $DW_{k}$ and $DN_{k}$ languages, here
preferably represented by letters instead of corner symbols.

######  Definition 5 (Dyck crossword alphabet and language)

Let $\Delta_{k}=\\{a_{i},b_{i},c_{i},d_{i}\mid 1\leq i\leq k\\}$, an alphabet.
We associate $\Delta_{k}$ with two different Dyck alphabets, the _Dyck row
alphabet_ $\Delta^{Row}_{k}$ and the _Dyck column_ _alphabet_
$\Delta^{Col}_{k}$ by means of the following matching pairs:

$\left\\{\begin{array}[]{ll}\text{for
}\Delta^{Row}_{k}:&\left\\{[a_{i},b_{i}]\mid i\leq 1\leq
k\right\\}\cup\left\\{[c_{i},d_{i}]\mid 1\leq i\leq k\right\\}\\\ \text{for
}\Delta^{Col}_{k}:&\left\\{[a_{i},c_{i}]\mid i\leq 1\leq
k\right\\}\cup\left\\{[b_{i},d_{i}]\mid 1\leq i\leq
k\right\\}\end{array}\right..$

The corresponding Dyck languages, without $\varepsilon$, are denoted by
$D^{Row}_{k}\subset{\Delta_{k}}^{+}$ and $D^{Col}_{k}\subset{\Delta_{k}}^{+}$.

The _Dyck crossword_ language $DC_{k}$ is the row-column combination of
$D^{Row}_{k}$ and $D^{Col}_{k}$.

In the following, we often consider only the language $DC_{1}$, over alphabet
$\\{a,b,c,d\\}$, when statements and properties of $DC_{k}$ are straighforward
generalizations of the $DC_{1}$ case.

###### Remark 1

The choice in Definition 5 that the $DC_{k}$ alphabet $\Delta_{k}$ consists of
one or more quadruples $a_{i},b_{i},c_{i},d_{i}$, $1\leq i\leq k$, is not just
for continuity with the alphabet of the well-nested and neutralizable cases,
but it is imposed by the following simple facts. For brevity we consider
$k=1$.

  1. (i)

Let $\Gamma$ be the binary alphabet $\\{e,e^{\prime}\\}$. Let $S^{\prime}$ and
$S^{\prime\prime}$ be the Dyck languages respectively for rows and for columns
based on $\Gamma$, with matching parentheses $(e,e^{\prime})$ for both rows
and columns. Then, it is easy to see that the row-column combination of
$S^{\prime}$ and $S^{\prime\prime}$ is empty, since it is impossible to
complete a $DC$ picture starting from a row containing word $ee^{\prime}$.
Moreover, the combination remains empty if we invert the matching for columns
to $(e^{\prime},e)$.

  2. (ii)

Let the alphabet for words be $\Gamma=\\{e,e^{\prime},f,f^{\prime}\\}$. Then,
to obtain a non-empty combination, there is only one way (disregarding
trivially equivalent letter permutations) of matching the letters, namely: for
rows, $(e,e^{\prime}),(f,f^{\prime})$ and for columns
$(e,f),(e^{\prime},f^{\prime})$. For instance, the choice
$(e,f^{\prime}),(e^{\prime},f)\\}$ for columns does not produce any $DC_{1}$
picture. By renaming the letters of $\Gamma$ as $\Delta_{1}=\\{a,b,c,d\\}$ we
regain the row/column Dyck alphabets of Definition 5; then, the matching
$\Delta^{Row}_{1}=\\{a,b\\}\cup\\{c,d\\}$ and
$\Delta^{Col}_{1}=\\{a,d\\}\cup\\{b,c\\}$ makes $DC_{1}$ empty.

  3. (iii)

Let the alphabet for words have six letters
$\Gamma=\\{e,e^{\prime},f,f^{\prime},g,g^{\prime}\\}$. From part (i) it is
easy to see that, no matter what matching is chosen for row and columns, two
of the letters cannot occur in any picture of $DC_{1}$. Therefore, it is
enough to consider an alphabet of size multiple of four.

  4. (iv)

A consequence of the previous items is that the following property of Dyck
words over a binary alphabet $\\{e,e^{\prime}\\}$ does not hold for $DC_{1}$:
any Dyck word, e.g., $e^{\prime}e$, occurs as a factor of some Dyck word,
e.g., $e\,e^{\prime}e\,e^{\prime}$; this is not true for the rows and the
columns of Dyck crosswords because each one of the row/column Dyck alphabets
contains two pairs of symbols, not just one. For instance the word $ad$ is a
forbidden factor of language $D^{Row}_{1}$.

We state and prove some basic properties. It is easy to notice that
$DN_{k}\subseteq DC_{k}$: for instance, when neutralizing a subpicture, the
neutralization of its two corners $(a_{i},b_{i})$ acts in that row as the
neutralization rule for words in $D_{k}^{row}$, and similarly for the other
corners. We later prove that this inclusion is proper.

The result of not being tiling recognizable holds also for $DC_{k}$:

###### Theorem 4.1

For every $k\geq 1$, the language $DC_{k}$ is not (tiling system)
recognizable.

###### Proof

The proof is essentially the same as of Theorem 3.1, since also in this case
the language $T^{\ominus+}$ can be obtained from $DC_{1}$ by intersection with
a recognizable language.

The next property of $DC_{k}$ is that any picture $p$ that is partitioned into
$DC_{k}$ subpictures is also in $DC_{k}$. This is obvious since each row of
$p$ is the concatenation of Dyck words, and similarly for columns. An
analogous result holds for each language $DN_{k}$ (for $DW_{k}$ this holds by
definition).

######  Theorem 4.2 (Invariance under Simplot operation)

$(DC_{k})^{++}=DC_{k}$ and $(DN_{k})^{++}=DN_{k}$.

Another question for any of the Dyck-like picture languages introduced is
whether its row and column languages respectively saturate the horizontal and
vertical Dyck word languages. We prove that this is the case for $DN_{k}$ and
$DC_{k}$, but this is not for $DW_{k}$. Let
$\Delta_{k}=\\{a_{i},b_{i},c_{i},d_{i}\mid 1\leq i\leq k\\}$. Let
$P\subseteq\Delta^{++}_{k}$ be a picture language and define the _row
language_ of $P$ as: $\text{ROW}(P)=\\{w\in\Delta^{+}_{k}\mid\text{ there
exist }p\in P,p^{\prime},p^{\prime\prime}\in\Delta_{k}^{++}\text{ such that
}p=p^{\prime}\ominus w\ominus p^{\prime\prime}\\}$. The column language of
$P$, $\text{COL}(P)$ is defined analogously.

######  Theorem 4.3 (row/column languages)

  1. 1.

$\text{ROW}(DC_{k})=\text{ROW}(DN_{k})=D^{Row}_{k}$,
$\text{COL}(DC_{k})=\text{COL}(DN_{k})=D^{Col}_{k}$.

  2. 2.

$\text{ROW}(DW_{k})\subsetneq D^{Row}_{k}$, $\text{COL}(DW_{k})\subsetneq
D^{Col}_{k}$.

###### Proof

Part (1): It is enough to prove that $D^{Row}_{k}\subseteq\text{ROW}(DN_{k})$,
since the other inclusion is obvious and the case for columns is symmetrical;
moreover, $DN_{k}\subseteq DC_{k}$, so there is no need to prove the statement
for $DC_{k}$. Without loss of generality, we consider only the case $k=1$. We
prove by induction on $n\geq 2$, that for every word $w\in D^{Row}_{1}$ of
length $n$ there exists a picture $p\in DN_{1}$ of the form $w_{1}\ominus
w_{2}\ominus w\ominus w_{3}$ for $w_{1},w_{2},w_{3}\in D^{Row}_{1}$. There are
two base cases, the words $ab$ and $cd$. The word $ab$ is (also) the third row
in the $DN_{1}$ picture $ab\ominus cd\ominus ab\ominus cd$, while $cd$ is
(also) the third row in the $DN_{1}$ picture $ab\ominus ab\ominus cd\ominus
cd$. The induction step has three cases: a word $w\in D^{Row}_{1}$ of length
$n>2$ has the form $w^{\prime}w^{\prime\prime}$, or the form $aw^{\prime}b$ or
the form $cw^{\prime}d$, for some $w^{\prime},w^{\prime\prime}\in D^{Row}_{1}$
of length less than $n$. Let $p^{\prime},p^{\prime\prime}$ the pictures
verifying the induction hypothesis for $w^{\prime}$ and $w^{\prime\prime}$
respectively. The case of concatenation $w^{\prime}w^{\prime\prime}$ is
obvious (just consider the picture $p^{\prime}\obar p^{\prime\prime}$). The
case $aw^{\prime}b$ can be solved by considering the picture $(a\ominus
c\ominus a\ominus c)\obar p^{\prime}\obar(b\ominus d\ominus b\ominus d)$,
which is in $DN_{1}$. Similarly, for the case $cw^{\prime}d$ just consider the
$DN_{1}$ picture $(a\ominus a\ominus c\ominus c)\obar p^{\prime}\obar(b\ominus
b\ominus d\ominus d)$.

Part (2): The Dyck word $abcd$ cannot be a row of a picture in $DW_{k}$. In
fact, every picture in $DW_{1}$ of width 4 must be in the vertical
concatenation closure of the set composed of the following two pictures, which
do not include an $abcd$ row :  $\begin{array}[]{c c c c}a&a&b&b\\\ a&a&b&b\\\
c&c&d&d\\\ c&c&d&d\\\ \end{array},\qquad\begin{array}[]{cc}a&b\\\
c&d\end{array}\begin{array}[]{cc}a&b\\\ c&d\end{array}.$

###  4.1 Matching-graph circuits

p11$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a$&p12$\mathbf{a}$p13$\mathbf{b}$p14$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}b$
p21ap22bp23$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\mathbf{a}$p24$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}b$
p31cp32dp33$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\mathbf{c}$p34$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\mathbf{d}$
p41$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c$p42$\mathbf{c}$p43$\mathbf{d}$p44$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d$

p11$a$&p12$a$p13$b$p14$b$
p21$a$p22$b$p23$a$p24$b$
p31$c$p32$d$p33$c$p34$d$
p41$c$p42$c$p43$d$p44$d$

[arcangle=30,linestyle=solid,linewidth=1.0pt]p11p14
[arcangle=0,linestyle=solid,linewidth=1.0pt]p12p13 [arcangle=-30,
linestyle=solid,linewidth=1.0pt]p11p41
[arcangle=30,linestyle=solid,linewidth=1.0pt]p14p44
[arcangle=25,linestyle=solid,linewidth=1.0pt]p12p42
[arcangle=-25,linestyle=solid,linewidth=1.0pt]p13p43

[arcangle=0,linestyle=solid,linewidth=1.0pt]p21p22
[arcangle=0,linestyle=solid,linewidth=1.0pt]p23p24
[arcangle=0,linestyle=solid,linewidth=1.0pt]p21p31
[arcangle=0,linestyle=solid,linewidth=1.0pt]p22p32
[arcangle=0,linestyle=solid,linewidth=1.0pt]p23p33
[arcangle=0,linestyle=solid,linewidth=1.0pt]p24p34

[arcangle=0,linestyle=solid,linewidth=1.0pt]p31p32
[arcangle=0,linestyle=solid,linewidth=1.0pt]p33p34

[arcangle=0,linestyle=solid,linewidth=1.0pt]p42p43
[arcangle=-30,linestyle=solid,linewidth=1.0pt]p41p44

Figure 2: (Left) A $DC_{1}$ picture whose cells are partitioned into 4
quadruples of matching symbols, identified by the same color (font). (Right)
An alternative visualization (right) by a graph using edges that connect
matching symbols.

We present some patterns that occur in $DC_{k}$ pictures. The simplest
patterns are found in pictures that are partitioned into rectangular circuits
connecting four elements, see, e.g., Figure 2, right, where an edge connects
two symbols on the same row (or column) which match in the row (column) Dyck
word. Notice that the graph made by the edges contains four disjoint circuits
of length four, called _rectangles_ for brevity. Three of the circuits are
nested inside the outermost one.

However, a picture in $DC_{1}$ may also include circuits longer than four. In
Figure 3 (left) we see a circuit of length 12, labeled by the word
$(abdc)^{3}$, and on the right a circuit of length 36. Notice that when a
picture on $\Delta_{1}$ is represented by circuits, the node labels are
redundant since they are uniquely determined on each circuit.

p11$a$&p12$b$p13$a$p14$b$
p21$c$p22$a$p23$b$p24$d$
p31$a$p32$c$p33$d$p34$b$
p41$c$p42$d$p43$c$p44$d$ [arcangle=0, linestyle=solid,linewidth=1.5pt]p11p12
[arcangle=-0, linestyle=solid,linewidth=1.5pt]p11p21 [arcangle=-20,
linestyle=solid,linewidth=1.5pt]p12p42 [arcangle=-0,
linestyle=solid,linewidth=1.5pt]p41p42 [arcangle=45,
linestyle=solid,linewidth=1.5pt]p21p24 [arcangle=-45,
linestyle=solid,linewidth=1.5pt]p31p34 [arcangle=-0,
linestyle=solid,linewidth=1.5pt]p31p41 [arcangle=-0,
linestyle=solid,linewidth=1.5pt]p34p44 [arcangle=0,
linestyle=solid,linewidth=1.5pt]p13p14 [arcangle=-0,
linestyle=solid,linewidth=1.5pt]p43p44 [arcangle=20,
linestyle=solid,linewidth=1.5pt]p13p43 [arcangle=0,
linestyle=solid,linewidth=1.5pt]p14p24 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p22p23 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p32p33 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p22p32 [arcangle=-0,
linestyle=solid,linewidth=0.5pt]p23p33

p11$a$&p12$b$p13$a$p14$b$ p15$a$p16$b$p17$a$p18$b$
p21$c$p22$a$p23$b$p24$d$ p25$c$p26$a$p27$b$p28$d$
p31$a$p32$c$p33$d$p34$a$ p35$b$p36$c$p37$d$p38$b$
p41$c$p42$d$p43$a$p44$a$ p45$b$p46$b$p47$c$p48$d$
p51$a$p52$b$p53$c$p54$c$ p55$d$p56$d$p57$a$p58$b$
p61$c$p62$a$p63$b$p64$c$ p65$d$p66$a$p67$b$p68$d$
p71$a$p72$c$p73$d$p74$b$ p75$a$p76$c$p77$d$p78$b$
p81$c$p82$d$p83$c$p84$d$ p85$c$p86$d$p87$c$p88$d$

[arcangle=0, linestyle=dashed,linecolor=red, linewidth=0.5pt]p11p12
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p11p21
[arcangle=-45, linestyle=dashed,linecolor=red,linewidth=0.9pt]p12p42

[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p14
[arcangle=45, linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p83

[arcangle=-0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p14p24

[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.9pt]p15p16
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.9pt]p15p25
[arcangle=-45, linestyle=dashed,linecolor=red,linewidth=0.9pt]p16p86

[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.9pt]p17p18
[arcangle=45, linestyle=dashed,linecolor=red,linewidth=0.9pt]p17p47
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.9pt]p18p28

[arcangle=45, linestyle=dashed,linecolor=red,linewidth=0.5pt]p21p24
[arcangle=0, linestyle=solid,linewidth=0.9pt]p22p23 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p22p32 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p23p33 [arcangle=45,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p25p28 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p26p27 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p26p36 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p27p37

[arcangle=-45, linestyle=dashed,linecolor=red,linewidth=0.5pt]p31p38
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p31p41
[arcangle=0, linestyle=solid,linewidth=0.9pt]p32p33 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p34p35 [arcangle=-45,
linestyle=solid,linewidth=0.9pt]p34p64 [arcangle=45,
linestyle=solid,linewidth=0.9pt]p35p65 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p36p37 [arcangle=0,
linestyle=dashed,linecolor=red,linewidth=0.9pt]p38p48

[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.9pt]p41p42
[arcangle=45, linestyle=solid,linewidth=0.9pt]p43p46 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p43p53 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p44p45 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p44p54 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p45p55 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p46p56 [arcangle=0,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p47p48

[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p51p52
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p51p61
[arcangle=-45, linestyle=dashed,linecolor=red,linewidth=0.9pt]p52p82
[arcangle=-45, linestyle=solid,linewidth=0.9pt]p53p56 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p54p55 [arcangle=0,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p57p58 [arcangle=45,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p57p87 [arcangle=0,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p58p68

[arcangle=45, linestyle=dashed,linecolor=red,linewidth=0.5pt]p61p68
[arcangle=0, linestyle=solid,linewidth=0.9pt]p62p63 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p62p72 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p63p73 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p64p65 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p66p67 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p66p76 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p67p77

[arcangle=-45, linestyle=dashed,linecolor=red,linewidth=0.5pt]p71p74
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p71p81
[arcangle=0, linestyle=solid,linewidth=0.9pt]p72p73 [arcangle=0,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p74p84 [arcangle=0,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p75p85 [arcangle=-45,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p75p78 [arcangle=0,
linestyle=solid,linewidth=0.9pt]p76p77 [arcangle=0,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p78p88

[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p81p82
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p83p84
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p85p86
[arcangle=0, linestyle=dashed,linecolor=red,linewidth=0.5pt]p87p88

Figure 3: Two pictures in $DC_{1}$. (Left) The picture is partitioned into two
circuits of length 12 and 4. (Right) The picture includes a circuit of length
36 and seven rectangular circuits. Its pattern embeds four partial copies
(direct or rotated) of the left picture; in, say, the NW copy the “triangle”
$bdc$ has been changed to $aaa$. Such a transformation can be reiterated to
grow a series of pictures.

We formally define the graph, situated on the picture grid, made by such
circuits.

######  Definition 6 (matching graph)

The _matching graph_ associated with a picture $p\in DC_{k}$, of size $(m,n)$,
is a pair $(V,E)$ where the set $V$ of nodes is the set $\\{1,\dots
n\\}\times\\{1\dots m\\}$ and the set $E$ of edges is partitioned in two sets
of _r_ ow and _c_ olumn edges defined as follows, for all $1\leq i\leq n,1\leq
j\leq m$:

  * •

for all pairs of matching letters $p_{i,j},p_{i,j^{\prime}}$ in
$\Delta^{Row}_{k}$, with $j<j^{\prime}\leq m$, there is a row (horizontal)
edge connecting $(i,j)$ with $(i,j^{\prime})$,

  * •

for all pairs of matching letters $p_{i,j},p_{i^{\prime},j}$ in
$\Delta^{Col}_{k}$, with $i<i^{\prime}\leq n$, there is a column (vertical)
edge connecting $(i,j)$ with $(i^{\prime},j)$,

Therefore, there is a horizontal edge connecting two matching letters
$a_{i},b_{i}$ or $c_{i},d_{i}$ that occur in the same row: e.g., the edge
$(2,1)\leftrightarrow(2,4)$ of Figure 3, left. Analogously, there is a
vertical edge connecting two matching letters $a_{i},c_{i}$ or $b_{i},d_{i}$,
that occur in the same column: e.g., the edge $(2,2)\leftrightarrow(3,2)$ of
Figure 3, left.

From elementary properties of Dyck languages it follows that the distance on
the picture grid between two nodes connected by an edge is an odd number.

######  Theorem 4.4 (matching-graph circuits)

Let $p$ be a picture in $DC_{k}$. Then:

  1. 1.

its matching graph $G$ is partitioned into disjoint simple circuits;

  2. 2.

the clockwise visit of any such circuit, starting from one of its nodes with
label $a_{j}$, yields a word in the language $(a_{j}b_{j}d_{j}c_{j})^{+}$, for
all $1\leq j\leq k$.

###### Proof

Part (1): By Definition 6, every node of $G$ has degree 2, with one row edge
and one column edge, since its corresponding row and column in picture $p$ are
Dyck words. Every node must be on a circuit, otherwise there would be a node
of degree 1. Each circuit must be simple and the sets of nodes on two circuits
are disjoint, else one of the nodes would have degree greater than 2. Part (2)
is obvious, since from a node labeled $a_{j}$ there is a row edge connecting
with a node labeled $b_{j}$, for which there is a column edge connecting with
a $d_{j}$, then a row edge connecting $d_{j}$ with $c_{j}$, etc., finally
closing the circuit with a column edge connecting a $c_{j}$ with the original
$a_{j}$.

Theorem 4.4 has a simple interpretation: to check that in a picture all rows
and columns are Dyck words of respectively $D^{Row}_{k}$ and $D^{Col}_{k}$, we
can proceed along each linear path. The process moves from an open parenthesis
(say $a$) to the closed matching letter ($b$) on the same row, then to the
closed matching letter ($d$) on the column of $b$, and so on, until the
circuit is closed, or interrupted causing rejection. Such a checking of
$DC_{k}$ membership corresponds to a way of checking Dyck membership for
words. Since a word is a picture of size $(1,n)$, its associated matching
graph is the well-known so-called rainbow representation, e.g.,
p11$a$&p12$a$p13$b$p14$a$p15$b$p16$b$
[nodesep=8pt,arcangle=40,linestyle=solid,linewidth=0.6pt]p11p16
[nodesep=6pt,arcangle=80,linestyle=solid,linewidth=0.6pt]p12p13
[nodesep=6pt,arcangle=80, linestyle=solid,linewidth=0.6pt]p14p15 of the syntax
tree of the word. A matching circuit then corresponds to the binary relation
between the two ends of a rainbow arc. However it is perhaps unexpected that
moving from 1D to 2D the length of circular paths increases not just to
$2\times 2$, but without an upper bound, as proved below.

&$p_{(1)}$
p11$a$p12$a$p13$a$p14$b$p15$b$p16$b$
p21$c$p22$a$p23$b$p24$d$p25$a$p26$b$
p31$a$p32$c$p33$d$p34$b$p35$c$p36$d$
p41$c$p42$c$p43$c$p44$d$p45$d$p46$d$ [arcangle=30,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p11p16 [arcangle=-30,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p11p21 [arcangle=30,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p14 [arcangle=-30,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p43 [arcangle=30,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p14p24 [arcangle=30,
linestyle=dashed,linecolor=red,linewidth=0.5pt]p16p46

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.9pt]p21p24

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p31p34
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p31p41
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p34p44

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p41p46
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p43p44

p01
p11$a$&p12$a$p13$a$p14$b$p15$b$p16$b$
p21$c$p22$a$p23$b$p24$d$p25$a$p26$b$
p31$a$p32$c$p33$d$p34$b$p35$c$p36$d$
p41$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c$p42$c$p43$c$p44$d$p45$d$p46$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}d$

0p01$p_{(1)}\ominus p_{(1)}$

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p11p16
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p11p21
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p14
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p43
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p14p24
[arcangle=30, linestyle=dashed,linecolor=green,linewidth=0.5pt]p16p46

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.9pt]p21p24

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p31p34
[arcangle=-30, linestyle=dashed,linecolor=green,linewidth=0.5pt]p31p41
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p34p44

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p41p46
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p43p44
p’11$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a$p’12$a$p’13$a$p’14$b$p’15$b$p’16$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b$
p’21$c$p’22$a$p’23$b$p’24$d$p’25$a$p’26$b$
p’31$a$p’32$c$p’33$d$p’34$b$p’35$c$p’36$d$
p’41$c$p’42$c$p’43$c$p’44$d$p’45$d$p’46$d$

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’11p’16
[arcangle=-30, linestyle=dashed,linecolor=green,linewidth=0.5pt]p’11p’21

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’13p’14
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’13p’43
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’14p’24
[arcangle=30, linestyle=dashed,linecolor=green,linewidth=0.5pt]p’16p’46

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.9pt]p’21p’24

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’31p’34
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’31p’41
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’34p’44

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’41p’46
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p’43p’44

&$p_{(2)}$
p11$a$p12$a$p13$a$p14$b$p15$b$p16$b$
p21$c$p22$a$p23$b$p24$d$p25$a$p26$b$
p31$a$p32$c$p33$d$p34$b$p35$c$p36$d$
p41$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a$p42$c$p43$c$p44$d$p45$d$p46$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b$
p51$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c$p52$a$p53$a$p54$b$p55$b$p56$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}d$
p61$c$p62$a$p63$b$p64$d$p65$a$p66$b$
p71$a$p72$c$p73$d$p74$b$p75$c$p76$d$
p81$c$p82$c$p83$c$p84$d$p85$d$p86$d$

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p11p16
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p11p21
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p14
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p13p43
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p14p24
[arcangle=30, linestyle=dashed,linecolor=blue,linewidth=0.5pt]p16p86*junction

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.9pt]p21p24

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p31p34
[arcangle=-45, linestyle=dashed,linecolor=blue,linewidth=0.5pt]p31p61*junction
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p34p44
[arcangle=-15, linecolor=blue,linewidth=0.5pt]p41p46 [arcangle=15,
linecolor=blue,linewidth=0.5pt]p51p56 [arcangle=0,
linecolor=blue,linewidth=0.5pt]p41p51 [arcangle=0,
linecolor=blue,linewidth=0.5pt]p46p56

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p43p44

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p53p54
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p53p83
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p54p64

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.9pt]p61p64

[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p71p74
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p71p81
[arcangle=30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p74p84

[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p81p86
[arcangle=-30, linestyle=dashed,linecolor=red,linewidth=0.5pt]p83p84

Figure 4: Left. Picture $p_{(1)}$ used as induction basis of Theorem 4.5. It
is covered by a circuit of length $4+8\cdot 1=12$ and by 3 rectangular
circuits. Middle. Picture $p_{(1)}\ominus p_{(1)}$, the four arcs to be
deleted are in green, and the four nodes to be relabeled are in blue. Right.
Inductive step: picture $p_{(2)}$ is obtained from $p_{(1)}\ominus p_{(1)}$ by
canceling the four green arcs, relabeling the four blue nodes as shown (the
corresponding rectangular circuit is in blue) and finally adding two arcs
(blue) that join the double-noose circuits. A circuit of length $4+8\cdot 2$
results. Notice that all length 4 circuits of $p_{(h-1)}$ and $p_{(1)}$ are
unchanged in $p_{(h)}$.

###### Theorem 4.5

(Unbounded circuit length) For all $h\geq 0$ there exist a picture in $DC_{k}$
that contains a circuit of length $4+8h$.

###### Proof

We prove the statement for $DC_{1}$, the general case being analogous. The
case $h=0$ is obvious. The case $h>0$ is proved by induction on a sequence of
pictures $p_{(1)},\ldots p_{(h)}$ using as basis the $DC_{1}$ picture
$p_{(1)}$ in Figure 4 (left), that has size $(m_{(1)},6)$, where $m_{(1)}=4$,
and contains a circuit of length $12=4+8$, referred to as double-noose.

Induction step. It extends picture $p_{(h-1)}$, $h>1$, by appending a copy of
$p_{(1)}$ underneath and making a few changes defined in Figure 4 (right). It
is easy to see that the result is a picture $p_{(h)}$ of size
$(m_{(h-1)}+4,6)$ such that: $p_{(h)}\in DC_{1}$ and $p_{(h)}$ contains a
circuit of length $4+8h$.

Another series of pictures that can be enlarged indefinitely is the one in
Figure 3, where the first two terms of the series are shown.

###  4.2 Quaternate Dyck crosswords

The next definition forbids any cycle longer than 4 and keeps, e.g., the
pictures in Figures 2 and 5.

######  Definition 7 (Quaternate $DC_{k}$)

A Dyck crossword picture such that all its circuits are of length 4 is called
_quaternate_ ; their language, denoted by $DQ_{k}$, is the _quaternate Dyck
language_.

p11$a$&p12$a$p13$b$p14$b$ p15$a$p16$a$p17$b$p18$b$
p21$a$p22$b$p23$a$p24$a$ p25$b$p26$b$p27$a$p28$b$
p31$c$p32$d$p33$a$p34$c$ p35$d$p36$b$p37$c$p38$d$
p41$c$p42$a$p43$b$p44$d$ p45$c$p46$a$p47$b$p48$d$
p51$a$p52$c$p53$d$p54$b$ p55$a$p56$c$p57$d$p58$b$
p61$a$p62$b$p63$c$p64$a$ p65$b$p66$d$p67$a$p68$b$
p71$c$p72$d$p73$c$p74$c$ p75$d$p76$d$p77$c$p78$d$
p81$c$p82$c$p83$d$p84$d$ p85$c$p86$c$p87$d$p88$d$

[arcangle=45, linestyle=solid,linewidth=1.5pt]p11p14 [arcangle=-45,
linestyle=solid,linewidth=1.5pt]p11p41 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p12p13 [arcangle=-45,
linestyle=solid,linewidth=0.5pt]p12p82 [arcangle=-45,
linestyle=solid,linewidth=1.5pt]p14p44 [arcangle=-45,
linestyle=solid,linewidth=0.5pt]p13p83 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p21p22 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p21p31 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p22p32 [arcangle=45,
linestyle=solid,linewidth=0.5pt]p23p26 [arcangle=-45,
linestyle=solid,linewidth=0.5pt]p23p73 [arcangle=-0,
linestyle=solid,linewidth=0.5pt]p24p25 [arcangle=-0,
linestyle=solid,linewidth=0.5pt]p24p34 [arcangle=-0,
linestyle=solid,linewidth=0.5pt]p25p35 [arcangle=45,
linestyle=solid,linewidth=0.5pt]p26p76

[arcangle=0, linestyle=solid,linewidth=0.5pt]p31p32 [arcangle=45,
linestyle=solid,linewidth=1.5pt]p33p63 [arcangle=45,
linestyle=solid,linewidth=1.5pt]p33p36 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p34p35 [arcangle=-45,
linestyle=solid,linewidth=1.5pt]p36p66

[arcangle=45, linestyle=solid,linewidth=1.5pt]p41p44 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p42p43 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p42p52 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p43p53

[arcangle=-45, linestyle=solid,linewidth=0.5pt]p51p54 [arcangle=-45,
linestyle=solid,linewidth=0.5pt]p51p81 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p52p53 [arcangle=-45,
linestyle=solid,linewidth=0.5pt]p54p84

[arcangle=0, linestyle=solid,linewidth=0.5pt]p61p62 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p61p71 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p62p72 [arcangle=45,
linestyle=solid,linewidth=1.5pt]p63p66 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p64p65 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p64p74 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p65p75

[arcangle=0, linestyle=solid,linewidth=0.5pt]p71p72 [arcangle=-45,
linestyle=solid,linewidth=0.5pt]p73p76 [arcangle=45,
linestyle=solid,linewidth=0.5pt]p33p36 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p74p75

[arcangle=-45, linestyle=solid,linewidth=0.5pt]p81p84 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p82p83

p11$a$&p12$a$p13$b$p14$b$ p15$b$p16$a$
p21$a$p22$b$p23$a$p24$c$ p25$d$p26$b$
p31$c$p32$d$p33$c$p34$a$ p35$b$p36$d$
p41$a$p42$c$p43$d$p44$b$ p45$a$p46$b$
p51$c$p52$a$p53$b$p54$d$ p55$c$p56$d$
p61$c$p62$c$p63$d$p64$c$ p65$d$p66$d$ [arcangle=25,
linestyle=solid,linewidth=0.5pt]p11p16 [arcangle=25,
linestyle=solid,linewidth=0.5pt]p16p66 [arcangle=25,
linestyle=solid,linewidth=0.5pt]p66p61 [arcangle=25,
linestyle=solid,linewidth=0.5pt]p61p11

[arcangle=0, linestyle=solid,linewidth=0.5pt]p14p15 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p15p25 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p25p24 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p24p14

[arcangle=0, linestyle=solid,linewidth=0.5pt]p21p22 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p22p32 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p32p31 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p31p21

[arcangle=0, linestyle=solid,linewidth=0.5pt]p45p46 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p46p56 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p56p55 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p55p45

[arcangle=0, linestyle=solid,linewidth=0.5pt]p52p53 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p53p63 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p63p62 [arcangle=0,
linestyle=solid,linewidth=0.5pt]p62p52
[arcangle=0,linestyle=solid,linewidth=1.5pt]p12p13
[arcangle=25,linestyle=solid,linewidth=1.5pt]p12p42
[arcangle=0,linestyle=solid,linewidth=1.5pt]p42p43
[arcangle=25,linestyle=solid,linewidth=1.5pt]p43p13

[arcangle=-25, linestyle=solid,linewidth=1.5pt]p23p26 [arcangle=0,
linestyle=solid,linewidth=1.5pt]p26p36 [arcangle=-25,
linestyle=solid,linewidth=1.5pt]p36p33 [arcangle=0,
linestyle=solid,linewidth=1.5pt]p33p23

[arcangle=-25, linestyle=solid,linewidth=1.5pt]p41p44 [arcangle=0,
linestyle=solid,linewidth=1.5pt]p44p54 [arcangle=-25,
linestyle=solid,linewidth=1.5pt]p54p51 [arcangle=0,
linestyle=solid,linewidth=1.5pt]p51p41

[arcangle=0,linestyle=solid,linewidth=1.5pt]p34p35
[arcangle=-25,linestyle=solid,linewidth=1.5pt]p35p65
[arcangle=0,linestyle=solid,linewidth=1.5pt]p65p64
[arcangle=-25,linestyle=solid,linewidth=1.5pt]p64p34

Figure 5: (Left). A quaternate picture (left) with two overlapping rectangles
(thicker lines) that mutually include only one node of the other. To avoid
clogging, the rectangles in the specular right half of the picture are not
drawn. Such a picture is not neutralizable (Definition 3). The precedence
relation (Definition 8) is not acyclic since $(1,1)\prec(3,3)\prec(1,1)$,
where each rectangle is identified by the coordinate of its north-west node.
Another quaternate picture (right) shows a cycle of length 4:
$(1,2)\prec(4,1)\prec(3,4)\prec(2,3)\prec(1,2)$.

##  5 Language inclusions

In this section we show the strict language inclusions existing between the
alternative definitions of 2D Dyck languages.

Since $DC_{k}$ pictures may contain circuits of length $>4$, (e.g., in Figure
3) quaternate Dyck languages are strictly included in Dyck crosswords.

It is obvious that $DN_{k}\subseteq DQ_{k}$; a natural question is then
whether the inclusion is strict. To answer, we define a precedence relation
between two rectangles of a $DQ_{k}$ picture such that the first must be
neutralized before the second.

######  Definition 8 (precedence in neutralization)

Let $p\in DQ_{k}$ and let $\alpha$ and $\beta$ two rectangles (i.e. length 4
circuits) occurring in $p$. Rectangle $\alpha$ has priority over $\beta$ if,
and only if, one, two or four nodes of $\alpha$ fall inside rectangle $\beta$
or on its sides. (For three nodes it is impossible.). Let $\prec$, the
precedence relation, be the transitive closure of the priority relation.

######  Example 2 (precedence relation)

The precedence relation for the picture in Figure 5, left, has the length-2
cycle $(1,1)\prec(3,3)\prec(1,1)$, blocking the neutralization process of the
two rectangles evidenced by thicker lines. The picture in Figure 5, right, has
a cycle of length 4.

######  Theorem 5.1 (neutralizable vs quaternate)

A picture in $DQ_{k}$ is neutralizable if and only if its precedence relation
is acyclic.

###### Proof

Let relation $\prec$ be acyclic. Then sort the rectangles in topological order
and apply neutralization starting from a rectangle without predecessors. When
a rectangle is checked, all of its predecessors have already been neutralized,
and neutralization can proceed until all rectangles are neutralized. The
converse is obvious: if relation $\prec$ has a cycle no rectangle in the cycle
can be neutralized.

From previous properties of the various 2D Dyck languages introduced in this
paper, we obtain a strict linear hierarchy with respect to language inclusion.

######  Corollary 1 (hierarchy)

$DW_{k}\subsetneq DN_{k}\subsetneq DQ_{k}\subsetneq DC_{k}.$

##  6 Conclusion

By introducing some definitions of 2D Dyck languages we have made the first
step towards a new characterization of 2D context-free languages by means of
the Chomsky-Schützenberger theorem suitably reformulated for picture
languages. But, in our opinion, the mathematical study of the properties of 2D
Dyck languages has independent interest, and much remains to be understood,
especially for the richer case of Dyck crosswords. Very diverse patterns may
occur in $DC_{k}$ pictures, that currently we are unable to classify. The
variety of patterns is related to the length of the circuits in the matching
graph and to the number of intersection points in a circuit or between
different circuits.

We mention two specific open problems. (i) The picture
${\genfrac{}{}{0.0pt}{2}{ab}{cd}}$ has just one circuit, which is therefore
Hamiltonian; it is not known whether there exist any other Hamiltonian
pictures in $DC_{1}$. (ii) By Theorem 4.5 the length of circuits in $DC_{1}$
pictures is unbounded. The question is whether, for all values $n>1$, there is
a $DC_{1}$ picture containing a circuit of length $4n$.

A related range of questions concerns the ”productivity” of a circuit, meaning
the existence of $DC_{k}$ pictures incorporating the circuit. A simple
formulation is: given a circuit situated in its bounding box, does a $DC_{k}$
picture exist of a size equal or larger than the bounding box, such that the
same circuit occurs within the picture?

Acknowledgment: We thank Matteo Pradella for helpful discussions.

## References

  * [1] J. Berstel.  Transductions and Context-Free Languages.  Teubner, Stuttgart, 1979.
  * [2] J. Berstel and L. Boasson.  Towards an algebraic theory of context-free languages.  Fundam. Informaticae, 25(3):217–239, 1996.
  * [3] N. Chomsky and M. Schützenberger.  The algebraic theory of context-free languages.  In Brafford and Hirschenber, editors, Computer programming and formal systems, pages 118–161. North-Holland, Amsterdam, 1963.
  * [4] S. Crespi Reghizzi, D. Giammarresi, and V. Lonati.  Two-dimensional models.  In J. Pin, editor, Handbook of Automata Theory, pages 303–333. European Mathematical Society Publishing House, 2021.
  * [5] S. Crespi-Reghizzi and M. Pradella.  Tile rewriting grammars and picture languages.  Theor. Comput. Sci., 340(1):257–272, 2005.
  * [6] F. Drewes.  Grammatical Picture Generation: A Tree-Based Approach.  Springer, 2006.
  * [7] S. A. Fenner, D. Padé, and T. Thierauf.  The complexity of regex crosswords.  Inf. Comput., 286:104777, 2022.
  * [8] D. Giammarresi and A. Restivo.  Two-dimensional languages.  In G. Rozenberg and A. Salomaa, editors, Handbook of formal languages, vol. 3, pages 215–267. Springer, 1997.
  * [9] M. Latteux and D. Simplot.  Recognizable picture languages and domino tiling.  Theor. Comput. Sci., 178(1-2):275–283, 1997.
  * [10] O. Matz.  Regular expressions and context-free grammars for picture languages.  In 14th Annual Symposium on Theoretical Aspects of Computer Science, volume 1200 of LNCS, pages 283–294, 1997.
  * [11] M. Nivat, A. Saoudi, K. G. Subramanian, R. Siromoney, and V. R. Dare.  Puzzle grammars and context-free array grammars.  Int. Journ. of Pattern Recognition and Artificial Intelligence, 5:663–676, 1991.
  * [12] A. Okhotin.  Non-erasing variants of the Chomsky—Schützenberger Theorem.  In Proc. of the 16th Intern. Conf. on Developments in Language Theory, DLT’12, pages 121–129, Berlin, Heidelberg, 2012. Springer-Verlag.
  * [13] M. Pradella and S. Crespi-Reghizzi.  A sat-based parser and completer for pictures specified by tiling.  Pattern Recognit., 41(2):555–566, 2008.
  * [14] D. Průša.  Two-dimensional Languages (PhD Thesis).  Charles University, Faculty of Mathematics and Physics, Czech Republic, 2004.
  * [15] D. Simplot.  A characterization of recognizable picture languages by tilings by finite sets.  Theor. Comput. Sci., 218(2):297–323, 1999.
  * [16] R. Siromoney, K. G. Subramanian, V. R. Dare, and D. G. Thomas.  Some results on picture languages.  Pattern Recognition, 32(2):295–304, 1999.


# Enabling knowledge discovery in Natural Hazard Engineering datasets on
DesignSafe

Chahak Mehta<EMAIL_ADDRESS>and  Krishna Kumar<EMAIL_ADDRESS>University of Texas at AustinAustinTexasUSA

(2018)

###### Abstract.

Data-driven discoveries require identifying relevant data relationships from a
sea of complex, unstructured, and heterogeneous scientific data. We propose a
hybrid methodology that extracts metadata and leverages scientific domain
knowledge to synthesize a new dataset from the original to construct knowledge
graphs. We demonstrate our approach’s effectiveness through a case study on
the natural hazard engineering dataset on “LEAP Liquefaction” hosted on
DesignSafe. Traditional lexical search on DesignSafe is limited in uncovering
hidden relationships within the data. Our knowledge graph enables complex
queries and fosters new scientific insights by accurately identifying relevant
entities and establishing their relationships within the dataset. This
innovative implementation can transform the landscape of data-driven
discoveries across various scientific domains.

datasets, semantic search, knowledge graphs

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Computing for the common good; July 23–27, 2023;
Portland, Oregon††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Software
and its engineering Search-based software engineering

##  1\. Introduction

The pursuit of knowledge discovery is fundamental to the advancement of
science. In today’s research landscape, efficiently managing and analyzing
large-scale experimental data has become a pivotal challenge. Extracting
meaningful insights from such data necessitates not only its efficient storage
but also the ability to access and query the data. One promising solution to
address the complexity of exploring new relations between entities in the
datasets is using graph databases, which excel at representing data
relationships and dependencies.

We present an innovative implementation 111All code written for the project is
open source and can be found at https://github.com/chahak13/tuitus.  of
extracting parameters and relationships from large datasets by constructing a
knowledge graph on heterogeneous scientific data to enable data-driven
discovery. We build a graph database on the DesignSafe Natural Hazard
Engineering Data Depot (Rathje et al., 2017) at the Texas Advanced Computing
Center (TACC). Integrating scientific domain knowledge and computing ability
is essential for accurately identifying the relevant entities within a dataset
to form a knowledge graph. This integration is critical for driving scientific
discovery. One of the main challenges is identifying the precise
representation of complex relationships and dependencies underlying scientific
phenomena. The choice of knowledge representation enables the deciphering of
vast amounts of data and transforming it into meaningful information resulting
in breakthroughs and deepening our understanding of the world. Our approach
involves a hybrid methodology that not only extracts metadata but also
exploits scientific domain knowledge to generate a new dataset that aggregates
or synthesizes the original dataset. This innovative implementation can
advance the frontiers of scientific knowledge discovery by providing a more
comprehensive and holistic view of the underlying relationships and
dependencies within the data.

We demonstrate the effectiveness of our approach through a case study on the
“LEAP Liquefaction” datasets (Lbibb and Manzari, 2022b, c, a; ElGhoraiby et
al., 2021; ElGhoraiby and Manzari, 2021a, b; Escoffier, 2023; Huang and Hung,
2023; Ma et al., 2023; Madabhushi et al., 2023; Manandhar et al., 2023; Mitsu
and Sjafruddin, 2023; Stone et al., 2023; Takemura and Hang, 2023; Ueda et
al., 2023; Zeghal, 2023) on DesignSafe. Liquefaction is a natural hazard that
involves a complex transition of granular soil from a solid-like response to a
fluid-like response with a dramatic loss of strength. Discovering the
fundamental science that describes this complex multiscale transitionary
behavior requires identifying and evaluating potential relationships between
different entities in the dataset. Although experimental datasets that capture
this complex transition exists on DesignSafe, the traditional lexical search
on DesignSafe only allows querying only on indexed items, which are often
restricted to published metadata, such as the author, title, date, and
description. The knowledge discovery task with only lexical search is even
more challenging when the individual experiments in the datasets, such as
“cyclic direct simple shear,” does not include the term “liquefaction” but is
buried within the data when the pore pressure ratio reaches 1.0. Unless we can
identify datasets where that specific condition is reached in the experiment,
we cannot create new science. Hence, our knowledge graph must support complex
queries such as “Identify cases of loose soil (relative density less than 70%)
where liquefaction was observed (i.e., the pore pressure ratio is 1.0)”.
Enabling such knowledge discoveries requires carefully identifying relevant
entities in a dataset and establishing their relationships. By creating a
knowledge graph on top of large scientific data repositories, we demonstrate
the significance of our approach in enabling data-driven discoveries.

##  2\. Current State of the Art and Challenges

To make data-driven discoveries, it is essential to identify the relevant data
that can create new science and models (Cutcher-Gershenfeld et al., 2016).
Lexical searchers are limited to indexed terms. Although powerful, text mining
and analytics engines like elastic search (Kononenko et al., 2014) lack
semantic understanding as they follow a lexical approach and fail to capture
the relationship between entities. Graph models are effective in finding
relationships or connections between data entities. Graph data model
inherently captures relationships as first-class citizens, allowing for more
powerful and efficient querying of complex connections between data entities.
Resource Description Framework (RDF), a graph model developed by (Berners-Lee
et al., 2001), captures the relationship between different entities of the
liquefaction dataset on DesignSafe (see fig. 1). Such a knowledge graph can be
constructed using RDF-encoded linked data capable of filtering through and
aggregating a diverse set of relevant metadata stored in a graph database
(Arenas et al., 2015; Nickel et al., 2016).

Identifying and synthesizing data to create new knowledge and relationship
requires scientific domain knowledge and a cyberinfrastructure (CI) skillset
to extract the relevant information. Fully automated systems can miss out on
crucial domain-specific information, such as failing to create a tag to
identify a particular dataset as “liquefied” when the pore water pressure
ratio column reaches 1.0. Summary statistics on the dataset, such as min,
mean, and max, will not capture this specific criterion. Additionally, the
heterogeneous and unstructured nature of the diverse dataset on natural
hazards poses another challenge in extracting data from different types and
file formats.

Figure 1. Knowledge graph of DesignSafe liquefaction datasets.

##  3\. Implementation

We need to identify and ingest pertinent scientific metadata and generate
summary statistics to establish data relationships to enable data-driven
discoveries. Implementing the knowledge graph involves two stages: first,
identifying and summarizing the experimental data, and second, creating the
graph database using an adapter that processes the generated summaries.

###  3.1. Parameters, metadata, and metadata engine

The first step involves identifying the relevant parameters and metadata for
each dataset, defined as a project in the DesignSafe data depot. We adopted a
hybrid human-assisted approach to defining the metadata tags. For this paper,
we limited our scope to tabular data in CSV files downloaded from 16 LEAP
datasets (Lbibb and Manzari, 2022b, c, a; ElGhoraiby et al., 2021; ElGhoraiby
and Manzari, 2021a, b; Escoffier, 2023; Huang and Hung, 2023; Ma et al., 2023;
Madabhushi et al., 2023; Manandhar et al., 2023; Mitsu and Sjafruddin, 2023;
Stone et al., 2023; Takemura and Hang, 2023; Ueda et al., 2023; Zeghal, 2023),
as XLSX files can be more free-flowing and unstructured. To summarize an
experimental result file, we store all the columns of the CSV file as a JSON
object along with summary statistics such as the mean, median, count, 25th
percentile, and 75th percentile for each numeric column. For ordinal columns,
we store the frequency of unique values. Additionally, we retrieve and store
the project metadata to enable standard queries that can be evaluated using
relational databases. We accomplish this summarization using Python and
several libraries, including the DesignSafe projects API, agavepy, pandas, and
requests.

###  3.2. Graph Database

The second step involves generating the graph database using the Neo4J graph
database platform, deployed on TACC. We use Cypher as a graph query language
and interact with the database using the py2neo Python library, which acts as
an ORM for Python and Neo4J.

###  3.3. Knowledge Graphs

We define various ‘nodes’ in the database based on the information type and
scientific domain knowledge. Table 1 lists the various types of nodes and data
that we store. These nodes are then connected by ‘edges’ that show various
types of relationships that can be used to create complex queries. Table 2
lists the different relationships implemented in the database.

Table 1. Description of Nodes present in the Database. Node | Data in Node | Description
---|---|---
Project | project_id | Stores the designsafe project ID.
Author | name | Stores information about PIs.
Hazard | name | Stores metadata about various hazards.
Project Type | name | Stores type of project (Experimental, Simulation etc.)
Experiment |  uuid, title | A node that contains experiment metadata.
Model |  uuid, title | Model configuration used in an experiment.
Event | title | Event information generated for various Models.
File | filepath | Files generated by Events.
Data |  name, mean, median etc. | A Node for every different type of data stored in the files.
Table 2. Description of Relationships present in the Database. Relationship | Nodes
---|---
SUPERVISES | (Author, Project)
NATURAL_HAZARD | (Project, Hazard)
TYPE | (Project, Project Type)
HAS_EXPERIMENT | (Project, Experiment)
HAS_MODEL | (Experiment, Model)
HAS_EVENT | (Experiment, Event), (Model, Event)
HAS_FILE | (Event, File)
RECORDS | (Project, Data), (Event, Data), (File, Data)

###  3.4. Querying the database

We query the database using Neo4J’s Cypher Query Language. Cypher Query
supports simple queries extracting information directly from the metadata
(such as project name or title) to more complex queries in identifying
behavior under specific conditions. Below are a few example queries on the
LEAP Liquefaction database, the results for which are shown in fig. 2.

  1. (1)

_Get all projects related to a particular natural hazard type_

        match (p:Project) -[:NATURAL_HAZARD]-> (h:Hazard) return p, h

  2. (2)

_Get all projects supervised by a specific author_

        match (p:Project) <-[:SUPERVISES]- (a:Author) where a.name = "mmanzari"
    return p, a

  3. (3)

_Get information about projects with experiments showing imminent
liquefaction, i.e., when the results have a mean pore pressure ratio value
between 0.5 and 0.7_

        match (p:Project)-->(ex:Experiment)-[:HAS_EVENT]->(ev:Event)-[:RECORDS]->(d:Data)
    where d.name = "pressureratio" and d.mean < 0.7 and d.mean > 0.5 return p, ex,ev,d

(a) Query 1

(b) Query 2

(c) Query 3

Figure 2. Results for Queries described in section 3.4

###  3.5. Extract Metadata using LLMs

To address the challenge of extracting metadata from unstructured XLSX files,
we turn to Large Language Models, such as OpenAI’s GPT-4 (OpenAI, 2023). Due
to the arbitrary structure of these files, understanding the relevant
summaries is a difficult task. Our solution involves preprocessing the xlsx
file using Python and then using the LLM to generate a JSON summary of the
file. In our initial runs, this approach has shown promising results (see fig.
3 and (Kumar and Mehta, 2023)), and we are currently working on integrating it
into the database engine described earlier. As LLMs are probabilistic models,
we plan to use a structured prompt to ensure a consistent format for the
output that enables us to have the entire pipeline automated.

Figure 3. LLM-based data extraction from unstructured XLSX files.

##  4\. Conclusion and Future Work

We developed a hybrid approach by creating a domain-specific data synthesis
and metadata extraction model. By representing the data relationships in
datasets of natural hazard engineering, we enable new science and support
data-driven discoveries. The proposed approach is generalizable to other
large-scale and heterogenous datasets, enabling new discoveries and knowledge.

Large-scale data-driven discoveries on complex heterogeneous datasets and
natural hazard types would require building extensive relationships across
complex experimental, field, and simulation datasets. We expect to see
knowledge graphs with millions of edges and node clusters. DesignSafe
currently hosts six petabytes of diverse natural hazard data. Mining such a
large dataset would require close collaboration between domain experts and
LLM-assisted metadata extraction. Building a knowledge graph on scientific
data sets offers the ability to construct data relationships and facilitate
knowledge discoveries and push the frontiers of data-driven science.

##  5\. Acknowledgments

This material is based upon work supported by the National Science Foundation
under Grant No. # 2103937. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the National Science Foundation. We thank
the compute allocations through TACC Frontera and DesignSafe (Rathje et al.,
2017).

## References

  * (1)
  * Arenas et al. (2015) Marcelo Arenas, , Bernardo Cuenca Grau, , Evgeny Kharlamov, , Sarunas Marciuska, , and Dmitriy Zheleznyakov. 2015.  Faceted search over RDF-based knowledge graphs.  _Journal of Web Semantics (JWS)_ (December 2015).  https://doi.org/10.1016/j.websem.2015.12.002
  * Berners-Lee et al. (2001) Tim Berners-Lee, James A. Hendler, and Ora Lassila. 2001\.  The Semantic Web” in Scientific American.
  * Cutcher-Gershenfeld et al. (2016) Joel Cutcher-Gershenfeld, Karen S. Baker, Nicholas Berente, Dorothy R. Carter, Leslie A. DeChurch, Courtney C. Flint, Gabriel Gershenfeld, Michael Haberman, John Leslie King, Christine Kirkpatrick, Eric Knight, Barbara Lawrence, Spenser Lewis, W. Christopher Lenhardt, Pablo Lopez, Matthew S. Mayernik, Charles McElroy, Barbara Mittleman, Victor Nichol, Mark Nolan, Namchul Shin, Cheryl A. Thompson, Susan Winter, and Ilya Zaslavsky. 2016.  Build it, but will they come? A geoscience cyberinfrastructure baseline analysis.  _Data Science Journal_ 15 (2016).  https://doi.org/10.5334/dsj-2016-008 Funding Information: Support from the National Science Foundation is deeply appreciated. Support for this research has been provided through NSF OCI RAPID 1229928, ”Stakeholder Alignment for EarthCube,” and NSF GEO-SciSIP-STS-OCI-INSPIRE 1249607, ”Enabling Transformation in the Social Sciences, Geosciences, and Cyberinfrastructure.” Publisher Copyright: © 2016 The Author(s)..
  * ElGhoraiby and Manzari (2021a) Mohamed ElGhoraiby and Majid Manzari. 2021a.  Cyclic Direct Simple Shear Tests - Nonuniform Loading.  https://doi.org/10.17603/DS2-DWT9-KE80
  * ElGhoraiby and Manzari (2021b) Mohamed ElGhoraiby and Majid Manzari. 2021b.  Cyclic Direct Simple Shear Tests - Uniform Loading.  https://doi.org/10.17603/DS2-DYPH-PF84
  * ElGhoraiby et al. (2021) Mohamed ElGhoraiby, Hanna Park, and Majid Manzari. 2021\.  Strain-Controlled Cyclic Triaxial Tests.  https://doi.org/10.17603/DS2-92C9-T496
  * Escoffier (2023) Sandra Escoffier. 2023\.  IFSTTAR-A1, IFSTTAR-A2, IFSTTAR-A3 - IFSTTAR Experiments.  https://doi.org/10.17603/DS2-EW3K-6F21
  * Huang and Hung (2023) Jun-Xue Huang and Wen-Yi Hung. 2023.  NCU-A2 and NCU-B - National Central University Experiments.  https://doi.org/10.17603/DS2-5YK0-Q734
  * Kononenko et al. (2014) Oleksii Kononenko, Olga Baysal, Reid Holmes, and Michael W Godfrey. 2014.  Mining modern repositories with elasticsearch. In _Proceedings of the 11th working conference on mining software repositories_. 328–331.
  * Kumar and Mehta (2023) Krishna Kumar and Chahak Mehta. 2023.  GPT + DesignSafe: AI-driven metadata extraction.  https://doi.org/10.5281/zenodo.7668209
  * Lbibb and Manzari (2022a) Sarra Lbibb and Majid Manzari. 2022a.  Cyclic Direct Simple Shear tests - Effect of overburden stress.  https://doi.org/10.17603/DS2-52DM-S780
  * Lbibb and Manzari (2022b) Sarra Lbibb and Majid Manzari. 2022b.  Cyclic Direct Simple Shear tests - Effect of relative density.  https://doi.org/10.17603/DS2-Z7ZB-BQ89
  * Lbibb and Manzari (2022c) Sarra Lbibb and Majid Manzari. 2022c.  Cyclic Direct Simple Shear tests - Effect of static shear stress.  https://doi.org/10.17603/DS2-Q3FZ-KQ91
  * Ma et al. (2023) Qiang Ma, Yan-Guo Zhou, Kai Liu, and Yun-Min Chen. 2023\.  ZJU-A and ZJU-B - Zhejiang University Experiments.  https://doi.org/10.17603/DS2-54DS-6206
  * Madabhushi et al. (2023) Gopal Madabhushi, Stuart Haigh, JAD BOKSMATI, Samy Garcia-Torres, and Alessandro Fusco. 2023.  CU-B - University of Cambridge Experiment.  https://doi.org/10.17603/DS2-Y7A1-7925
  * Manandhar et al. (2023) Satish Manandhar, Kim Seong-Nam, and Kim Dong-Soo. 2023\.  KAIST-A2 and KAIST-B - KAIST Experiments.  https://doi.org/10.17603/DS2-67TK-7281
  * Mitsu and Sjafruddin (2023) Okamura Mitsu and Asri Nurani Sjafruddin. 2023.  Ehime-1 - Ehime University Experiment.  https://doi.org/10.17603/DS2-WCKK-2425
  * Nickel et al. (2016) Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. 2016.  A Review of Relational Machine Learning for Knowledge Graphs.  _Proc. IEEE_ 104, 1 (2016), 11–33.  https://doi.org/10.1109/JPROC.2015.2483592
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  arXiv:2303.08774 [cs.CL]
  * Rathje et al. (2017) E. Rathje, C. Dawson, J.E. Padgett, J.-P. Pinelli, D. Stanzione, A. Adair, P. Arduino, S.J. Brandenberg, T. Cockerill, C. Dey, M. Esteva, F.L. Haan Jr, M. Hanlon, A. Kareem, L. Lowes, S. Mock, and G. Mosqueda. 2017.  DesignSafe: A New Cyberinfrastructure for Natural Hazards Engineering.  _ASCE Natural Hazards Review_ (2017).  https://doi.org/10.1061/(ASCE)NH.1527-6996.0000246
  * Stone et al. (2023) Nicholas Stone, Trevor Carey, Anthony Santana, and Bruce Kutter. 2023.  UCD4, UCD5 and UCD6 - UC Davis Experiments.  https://doi.org/10.17603/DS2-1A86-H371
  * Takemura and Hang (2023) Jiro Takemura and Lyu Hang. 2023.  TIT-MOD-A1, TIT-MOD-A2, TIT-MOD-B1, and TIT-MOD-B2 - Tokyo Tech Experiments.  https://doi.org/10.17603/DS2-QFEJ-GJ96
  * Ueda et al. (2023) Kyohei Ueda, Tetsuo Tobita, and Ruben Vargas. 2023\.  KyU-A1, KyU-GS1, KyU-GS1a, KyU-A2, and KyU-GS2 - Kyoto University Experiments.  https://doi.org/10.17603/DS2-ZAD5-RY27
  * Zeghal (2023) Mourad Zeghal. 2023\.  RPI-A and RPI-B - Rensselaer Polytechnic Institute Experiments.  https://doi.org/10.17603/DS2-HFDM-BP53