Universität Stuttgart, Formal Methods in Informatics, Germany and
https://fmi.uni-stuttgart.de/ti/team/diekert/<EMAIL_ADDRESS>https://orcid.org/0000-0002-5994-3762 Universität Trier, Fachbereich IV,
Informatikwissenschaften, Germany and https://www.uni-
trier.de/index.php?id=49861<EMAIL_ADDRESS>https://orcid.org/0000-0002-4444-3220 Universität Trier, Fachbereich IV,
Informatikwissenschaften, Germany and https://www.wolfp.net/
<EMAIL_ADDRESS>https://orcid.org/0000-0003-3097-3906 DFG
project FE 560/9-1 Volker Diekert et al. [500]Theory of computation Formal
languages and automata theory John Q. Open and Joan R. Access 2 42nd
Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December
24–27, 2016 Little Whinging, United Kingdom 42 23

# Properties of Graphs Specified by a Regular Language

Volker Diekert  Henning Fernau  Petra Wolf

(Otober 11th, 2021)

###### Abstract

Traditionally, graph algorithms get a single graph as input, and then they
should decide if this graph satisfies a certain property $\Phi$. What happens
if this question is modified in a way that we get a possibly infinite family
of graphs as an input, and the question is if there is a graph satisfying
$\Phi$ in the family? We approach this question by using formal languages for
specifying families of graphs, in particular by regular sets of words. We show
that certain graph properties can be decided by studying the syntactic monoid
of the specification language $L$ if a certain torsion condition is satisfied.
This condition holds trivially if $L$ is regular. More specifically, we use a
natural binary encoding of finite graphs over a binary alphabet $\Sigma$, and
we define a regular set $\mathbb{G}\subseteq\Sigma^{*}$ such that every
nonempty word $w\in\mathbb{G}$ defines a finite and nonempty graph. Also,
graph properties can then be syntactically defined as languages over $\Sigma$.
Then, we ask whether the automaton $\mathcal{A}$ specifies some graph
satisfying a certain property $\Phi$. Our structural results show that we can
answer this question for all “typical” graph properties.

In order to show our results, we split $L$ into a finite union of subsets and
every subset of this union defines in a natural way a single finite graph $F$
where some edges and vertices are marked. The marked graph in turn defines an
infinite graph $F^{\infty}$ and therefore the family of finite subgraphs of
$F^{\infty}$ where $F$ appears as an induced subgraph. This yields a geometric
description of all graphs specified by $L$ based on splitting $L$ into
finitely many pieces; then using the notion of graph retraction, we obtain an
easily understandable description of the graphs in each piece.

###### keywords:

Graphs, Regular languages, Satisfiability of graph properties

## Preamble

The conference abstract of the present paper appeared in [7]. Here, we give
full proofs and we correct some mistakes.

##  1 Introduction

The paper is about families of finite graphs specified by a regular language,
and their properties. When dealing with algorithms, a graph is often specified
by its adjacency matrix or by its induced edge-list together with the number
of isolated vertices, if there are any. In either representation, a graph
comes with a linear order on the vertices and the edges are directed.
Moreover, an adjacency matrix ignores multiple edges, but self-loops may
occur. We follow these conventions in our paper. We encode111We briefly
discuss our encoding of graphs as words (and some related work) in Section
1.2. a finite graph $G=(V,E)$ as a word over the binary alphabet
$\Sigma=\\{a,b\\}$ as follows: the $i$-th vertex $u_{i}$ of a graph is encoded
by $ab^{i}a$ and the edge $(u_{i},u_{j})$ is encoded by $ab^{i}aaab^{j}a$.
Thus, every word $w$ in $\mathbb{G}=\\{ab^{+}a,ab^{+}aaab^{+}a\\}^{+}$
represents in a natural way a unique graph $\rho(w)$ because
$\\{ab^{+}a,ab^{+}aaab^{+}a\\}$ is a regular code. Given a finite graph
$G=(V,E)$ with any linear order on the vertices, we obtain a code word
$\gamma(G)$ in $\mathbb{G}$ as follows. We write $V$ as $\\{1,\ldots,|V|\\}$
using an arbitrary but fixed bijection, and then we write the edges and the
isolated vertices in the order which yields the short-lex normal form of $G$
in ${\rho}^{-1}(G)$. This means that first, all edges are listed and then,
possible isolated vertices follow. We are interested in abstract graphs, only.
Thus, isomorphic graphs are treated as equal. Therefore, several $\gamma(G)$’s
are possible, although even then, the short-lex normal form would give a
unique syntactic representation of $G$ if necessary.

We cannot avoid that every nonempty graph $G$ has infinitely many
representations $w\in\mathbb{G}$ such that $\rho(w)=G$. For example, the one-
point graph $(\\{\star\\},\emptyset)$ is represented by all words in the
regular set $L_{i}=(ab^{i}a)^{+}$ as soon as $i\geq 1$, i.e., for all $w\in
L_{i}$ we have $\rho(w)=G$.

Given any $L\subseteq\mathbb{G}$, it defines a set of graphs $\rho(L)$. The
main interest is when $\rho(L)$ is infinite but $L\subseteq\mathbb{G}$ is
regular. The aim is to “understand” the infinite set of graphs in $\rho(L)$.
It is far from obvious that this is possible. If $L$ is finite, then $\rho(L)$
is finite, too. But the converse is false. As we will see, if $L$ is regular,
then we can decide finiteness of $\rho(L)$; and if $\rho(L)$ is finite, then
we can compute all its graphs. If however, $\rho(L)$ is infinite, then a
global understanding of $\rho(L)$ is, a priori, not easy.

###  1.1 A sketch of our approach and our results

Let us try to give a high-level explanation of the underlying geometric idea
how to approach $\rho(L)$. Remotely, it is like understanding the geometry of
a topological manifold using the fact that it locally resembles an Euclidean
space. For example, it is possible to realize a torus (which is a compact
$2$-dimensional surface) as a unit square where opposite edges are identified.
Every point has on open neighborhood which looks like $\mathbb{R}^{2}$ and
from that one easily derive that the so-called _fundamental group_ (which is a
global property) is the group $\mathbb{Z}\times\mathbb{Z}$. Therefore we
cannot transform a torus neither into a sphere nor into a soup tureen with two
or more handles.

In our case, we deal with purely combinatorial objects. Nevertheless, we wish
to understand the set of graphs $\rho(L)$ by constructing a finite subset of
graphs together with an “open neighborhood” around these graphs such that
$\rho(L)$ is covered by that construction. Thus, if we want to check whether a
certain property $\Phi$ is satisfied by some graph in $\rho(L)$, then it is
enough that we are able to check that locally. The key idea is to cut first
$L$ into pieces using the algebraic property that a regular language $L$ has a
finite syntactic monoid $M_{L}$. Hence, $L$ is a finite union of congruence
classes; and we obtain an important saturation property: whenever $w\in L$,
then we define the set of words $[w]$ to be all words in the same congruence
class of $w$. So, $\rho([w])$ plays the role of an open neighborhood around
the graph $\rho(w)$. Inside each $\rho([w])$, we define finitely many
“smallest” graphs. Thereby, we find a finite set of finite graphs
$\mathcal{F}$ such that the collection of these finitely many graphs still has
the entire information about $\rho(L)$. In order to reveal that information,
we construct for each $F\in\mathcal{F}$ a (possibly infinite) graph
$F^{\infty}$. The graph $F^{\infty}$ contains $F$ as an induced subgraph; and
$F^{\infty}$ comes with a graph morphism onto the graph $F\in\mathcal{F}$. The
structure of that infinite graph is fully explicit and actually easy to
understand. For example, it might happen that $F$ consists of a single edge
between two endpoints and $F^{\infty}$ is the complete infinite bipartite
graph $(\mathbb{N},\mathbb{N},\mathbb{N}\times\mathbb{N})$. Our result shows
that, for every regular language $L$, we have $G\in\rho(L)$ if and only if for
some $F$, $G\in\rho(L)$ appears as a finite subgraph of $F^{\infty}$
containing $F$.

Our geometric approach to $\rho(L)$ has two steps. First, we use the algebraic
notion of syntactic monoid. The second step is a graph theoretical definition
of $F^{\infty}$. The outcome of following this road map is Corollary 4.23. It
tells us that (with respect to our positive and negative decidable results) it
is enough to consider only four different classes
$\mathcal{C}_{1}\subset\cdots\subset\mathcal{C}_{4}$ of graphs $\rho(L)$.

  1. 1.

$\rho(L)\in\mathcal{C}_{1}$ if and only if the set $\rho(L)$ is finite.

  2. 2.

$\rho(L)\in\mathcal{C}_{2}$ implies that $\rho(L)$ has bounded tree-width.

  3. 3.

$\rho(L)\in\mathcal{C}_{3}$ implies that every connected finite bipartite
graph appears as a connected component of some $G\in\rho(L)$.

  4. 4.

$\rho(L)\in\mathcal{C}_{4}$ implies that every connected finite graph appears
as a connected component of some $G\in\rho(L)$.

Moreover, if $L$ is regular, then we can compute the largest $\ell$ such that
$\rho(L)\in\mathcal{C}_{\ell}$. Caveat: it may happen that $\rho(L)$ is in
$\mathcal{C}_{3}$ and in addition it contains arbitrarily large connected non-
bipartite graphs, but nevertheless $\rho(L)\notin\mathcal{C}_{4}$.

Since the syntactic monoid of a regular language is finite, we find some
$t,p\in\mathbb{N}$ with $p\geq 1$, _threshold_ and _period_ , such that for
every $n\in\mathbb{N}$ there is some $c\leq t+p-1$ with $b^{c}\equiv_{L}b^{n}$
where $\equiv_{L}$ denotes the _syntactic equivalence_. The pair $(t,p)$ tells
us that $b^{c}\equiv_{L}b^{n}$ implies first, $n=c$ for all $0\leq c<t$ and
second, $b^{n}\equiv_{L}b^{n+p}\iff n\geq t$. This is the key observation when
proving that we have no more than these four classes above. If
$L\subseteq\mathbb{G}$ is not regular, then the syntactic monoid $M_{L}$ is
infinite. Still there are interesting examples where $M_{L}$ satisfies the
_Burnside condition_ that all cyclic submonoids of $M_{L}$ are finite. If so,
then there exist $t,p\in\mathbb{N}$ with $p\geq 1$ such that the syntactic
properties stated above hold for the powers of the letter $b$. In this case,
we say that $L$ satisfies the _$(b,t,p)$ -torsion property_. Theorem 4.6 shows
that for every subset $L\subseteq\mathbb{G}$ satisfying the $(b,t,p)$-torsion
property, there exists a regular set $R\subseteq\mathbb{G}$ such that
$\rho(L)=\rho(R)$. This is quite an amazing result. Its proof relies on the
fact that $\rho(L)$ is determined once we know the Parikh-image of
$\mathrm{rf}(L)$ in $\mathbb{N}^{t+p-1}$, where for $w\in\mathbb{G}$, the
_reduced form_ $\mathrm{rf}(w)$ is obtained by replacing every $b^{n}$ by
$b^{c}$, where $c$ is the smallest $0\leq c\leq t+p-1$ such that
$b^{c}\equiv_{L}b^{n}$. Hence, for deciding whether some graph $G\in\rho(L)$
satisfies a property, we can assume that $L$ is regular. We are interested in
decidable properties $\Phi$, only. Thus, we assume that the set
$\left\\{G\text{ is a finite graph}\,\middle|\,G\models\Phi\right\\}$ is
decidable. If $\rho(L)$ is finite, then we can compute all graphs in $\rho(L)$
and we can output all $G\in\rho(L)$ satisfying $\Phi$.

Finiteness of $\rho(L)$ is actually quite interesting and important. It is a
case where a representation of $L$ by a DFA or a regular expression can be
used for data compression. The minimal size of a regular expression (or the
size of a DFA) for $L$ is never worse than listing all graphs in $\rho(L)$,
but it might be exponentially better. For a concrete case, we refer to Example
4.2. The compression rate becomes even better if we use a context-free grammar
which produces a finite set $L$ of words in $\Sigma^{*}$, only. In the extreme
case, $L$ is a single word $w$. Then it might happen that the grammar (or
_straight-line program_) is exponentially more succinct than writing $w$ as a
word in $\Sigma^{*}$. Thus, possibly we can decide the existence of a graph in
$\rho(L)$ satisfying $\Phi$ even though $L$ is highly compressed by the chosen
graph representation.

If $L$ is regular, the existence of planar graphs in $\rho(L)$ is conceptually
easy to decide: Given $L$, we can can compute a number $n(L)\in\mathbb{N}$
such that $\rho(L)$ contains a planar graph if and only if there is some $w\in
L$ of length at most $n(L)$ such that $\rho(w)$ is planar. On a meta-level,
whenever we were able to decide whether some $G\in\rho(L)$ satisfies $\Phi$,
then we found effectively a corresponding number $n(L)$. Moreover, positive
decidability results are easy to establish for typical graph properties like
“planarity” and many other graph properties.

The second class $\mathcal{C}_{2}$ implies that $\rho(L)$ has bounded tree-
width. In this case, by [4, 5, 23] we know that given any property $\Phi$
which is definable in Monadic Second-Order logic, _MSO_ for short, then it is
decidable whether there is a graph in $\rho(L)$ satisfying $\Phi$. Languages
$L\subseteq\mathbb{G}$ such that first, $\rho(L)$ has finite tree-width and
second, the $(b,t,p)$-torsion property holds can be visualized as a set of
graphs sharing some finite subgraph as a backbone structure to which
arbitrarily large stars can be glued. This observation leads to Theorem 5.4:
The satisfiability problem for MSO-sentences is decidable for language in the
second class. Not surprisingly, the proof of Theorem 5.4 uses Theorem 4.6.

For the other two classes, the picture changes drastically: the First-Order
theory (_FO_ for short) becomes undecidable [24]. Conversely, we are not aware
of any “natural” graph property $\Phi$ (which is not encoding Turing machine
computations) where the satisfiability problem for $\Phi$ is not trivial for
$\mathcal{C}_{3}$ and $\mathcal{C}_{4}$. For example, for these classes
$\rho(L)$ contains non-planar graphs, because $\rho(L)$ contains a graph where
the complete bipartite graph $K_{2,3}$ is a connected component. For a similar
reason, $\rho(L)$ contains graphs without any perfect matching. It is
therefore more interesting to know whether some $G\in\rho(L)$ allows a perfect
matching. This problem is decidable, as we show, but the decision procedure is
more involved.

###  1.2 Encoding of graphs and related work

Our encoding of graphs by using words over a binary alphabet is quite natural
but obviously not unique. For instance, one could use larger alphabets, say, a
unique letter per vertex, in writing down vertex or edge lists. As we use a
code to write down vertex and edge names, we could interpret our encoding also
as using a larger alphabet. However, in the context of the questions that we
discuss in this paper, this would lead to automata over infinite alphabets,
and we wanted to avoid discussing these here.

The bit complexity of $\gamma(G)$ (encoding an edge-graph $G$ with $n$
vertices and $m$ edges) is $\mathcal{O}(n\cdot m)$ and hence as good as
traditional incidence matrices. More compact representations seem to lead to
encodings that are not fit to be tested by finite automata and are hence
avoided.

With the idea of using larger alphabets, still completely different encodings
are possible. For instance, Kitaev and Seif introduced in [13] a
representation of directed acyclic graphs by associating vertices to sets of
letters of a word. This is also interesting for our discussions, as [13, Thm.
1.8]) yields a characterization of the Word Problem of Perkins’s semigroup
$\mathbf{B}_{\mathbf{2}}^{\mathbf{1}}$ in terms of graph problems. In [3],
again different interpretations of words as graphs and also typical graph
problems are investigated for these encodings. Also, Bera and Mahalingam [3]
draw connections to Parikh images.

In [15], Kuske generalizes results of de Malo and de Oliveira Oliveira in [6]
on _Second-Order Finite Automata_ by using automatic structures. As an
application, Kuske shows in [15, Thm. 3.6] how to decide typical properties of
languages classes accepted by second-order finite automata.

Although our results go beyond regular sets $L$, the focus and the motivation
comes from a situation when $L$ is regular. A typical question could be
whether there exists some planar graph in $\rho(L)$. Solving this type of
decision problems was the motivation to study _regular realizability problems_
in [1, 25] and, independently, calling them
$\mathit{int_{\mathrm{Reg}}}$-problems222The notation
$\mathit{int_{\mathrm{Reg}}}$ refers to _intersection non-emptiness with
regular_ languages. in [11, 26, 27].

##  2 Notation and preliminaries

Some of the following notation was introduced and explained in the
introduction, Section 1. For convenience, we repeat them. We let
$\mathbb{N}=\\{0,1,2,\ldots\\}$ be the set of natural numbers and
$\mathbb{N}_{\infty}=\mathbb{N}\cup\\{\infty\\}$. Throughout, if $S$ is a set,
then we identify a singleton set $\\{x\\}\subseteq S$ with the element $x\in
S$. The power set of $S$ is identified with $2^{S}$ (via characteristic
functions). If $E\subseteq X\times Y$ is a relation, then ${E}^{-1}$ denotes
its inverse relation ${E}^{-1}=\left\\{\,\mathinner{(y,x)\in Y\times
X}\vphantom{(x,y)\in E}\;\left|\;\vphantom{(y,x)\in Y\times
X}\mathinner{(x,y)\in E}\right.\,\right\\}$. By $\mathrm{id}_{X}$, we mean the
identity relation. Recall that $Y^{X}$ denotes the set of mappings from a set
$X$ to a set $Y$. If $f:X\to Y$ and $g:Y\to Z$ are mappings, then $gf:X\to Z$
denotes the mapping defined by $gf(x)=g(f(x))$. If convenient, we abbreviate
$f([x])$ as $f[x]$.

Henceforth, $\Gamma$ denotes a finite alphabet. For a word $w=a_{1}\cdots
a_{n}\in\Gamma^{*}$ with $a_{i}\in\Gamma$, we let
$\overleftarrow{w}=a_{n}\cdots a_{1}$ be the _reversal_ of $w$. That is, we
read the word $w$ from right to left.

Each alphabet is equipped with a linear order on its letters333This convention
is standardized in DIN 44300 and ISO 2382.. The linear order on $\Gamma$
induces the _short-lex linear order_ $\mathrel{\leq_{\mathrm{slex}}}$ on
$\Gamma^{*}$. That is, for $u,v\in\Gamma^{*}$, we let
$u\mathrel{\leq_{\mathrm{slex}}}v$ if either
$\left|\mathinner{u}\right|<\left|\mathinner{v}\right|$ or
$\left|\mathinner{u}\right|=\left|\mathinner{v}\right|$, $u=pcu^{\prime}$, and
$v=pdv^{\prime}$ where $c,d\in\Gamma$ with $c<d$. Here,
$\left|\mathinner{u}\right|$ denotes the length of $u$. Similarly, $|u|_{c}$
counts the number of occurrences of letter $c$ in $u$. We also fix the
notation $\Sigma=\\{a,b\\}$ with $a\neq b$.

###  2.1 Monoids

A monoid $M$ is a semigroup $(M,\cdot)$ with a neutral element $1\in M$. If we
use a multiplicative notation, then $1$ denotes the neutral element of a
monoid. In particular, the empty word in free monoids is denoted by $1$ as
well. In commutative monoids, we might use an additive operation, and then the
neutral element is denoted as $0$. This is standard and there will be no risk
of confusion. Cyclic monoids are commutative because, by definition, they are
generated by a single element. Every finite cyclic monoid $M$ is defined by
two numbers $t,p\in\mathbb{N}$ with $p\geq 1$ (where $t$ is the _threshold_
and $p$ is the _period_) such that $M$ is isomorphic to the quotient monoid
$C_{t,p}$ of $(\mathbb{N},+,0)$ with the defining relation $t=t+p$. Hence, the
carrier set of $C_{t,p}$ equals $\\{0,1,\dots,t+p-1\\}$. If $t=0$ and $p=1$,
then $C_{t,p}$ is the trivial monoid $\\{0\\}$.

If $M$ is a monoid, then $u\leq v$ means in our paper $v\in MuM$. That is, $u$
is a _factor_ of $v$. This notation applies, in particular, to the monoids
$\Gamma^{*}$ and $\mathbb{N}^{\Gamma}$. Here, $\mathbb{N}^{\Gamma}$ denotes
the free commutative monoid over $\Gamma$. Since $\Gamma$ is finite,
$\mathbb{N}^{\Gamma}$ is the set of mappings from $\Gamma$ to $\mathbb{N}$.
Its elements are called _vectors_.

####  2.1.1 Syntactic monoids, congruences, and the Word Problem

Every subset $L\subseteq\Gamma^{*}$ has a _syntactic monoid_ $M=M_{R}$, see
for example [9]. The elements of $M_{L}$ are the congruence classes
$[u]=\left\\{\,\mathinner{v\in\Sigma^{*}}\vphantom{v\equiv_{L}u}\;\left|\;\vphantom{v\in\Sigma^{*}}\mathinner{v\equiv_{L}u}\right.\,\right\\}$
w.r.t. the _syntactic congruence_ $\equiv_{L}$ which is defined by the
following equivalence.

$\displaystyle u\equiv_{L}u^{\prime}\text{\; if and only if \; }\forall
x,y\in\Sigma^{*}:\,xuv\in L\iff xu^{\prime}v\in L$

If $L$ is regular, then $M_{L}$ is finite. Later, we do not need that $M_{L}$
is finite, but we will relax this condition. It will suffice that the letter
$b$ appears in $\Gamma$ and is generating a finite submonoid.444According to
Section 3, we will call this the $b$-torsion property.

Let $\varphi:\Gamma^{*}\to G$ be a surjective homomorphism onto a finitely
generated group $G$. Then the _Word Problem_ of $G$ denotes the set
$\mathop{\mathrm{missing}}{WP}(G)=\left\\{w\in\Gamma^{*}\,\middle|\,\varphi(w)=1\right\\}$.
If this set is decidable, then we say that Word Problem of $G$ is decidable
because on input $u,v\in\Gamma^{*}$ we can decide whether
$\varphi(u)=\varphi(v)$. It is a classical fact (and an easy exercise) that
decidability of Word Problem does not depend on the generating set and that
the syntactic monoid of $\mathop{\mathrm{missing}}{WP}(G)$ is the group $G$
itself, [2].

####  2.1.2 Burnside groups

Recall that $|\Sigma|=2$. The _free Burnside group_ $\mathcal{B}(2,p)$ is
defined as the quotient

$\displaystyle\mathcal{B}(2,p)=\Sigma^{*}/\left\\{x^{p}=1\,\middle|\,x\in\Sigma^{*}\right\\}$

where $p\geq 1$. It is a group, because every $x$ has the inverse element
$x^{p-1}$ thanks to $p\geq 1$. For $p$ large enough, Adjan has shown in the
1970s that $\mathcal{B}(2,p)$ is infinite, answering a question of Burnside
dating back in its original form to 1902. Actually, Adjan also showed the
decidability of the Word Problem of $\mathcal{B}(2,p)$ if $p$ is large enough.
Here, a group (with two generators) is called _$p$ -periodic_ if it is the
homomorphic image of some $\mathcal{B}(2,p)$. Kharlampovich constructed in
[12] a periodic group $B(2,p)$ with a generating set $\Sigma$ and a finite set
of words $w_{1},\ldots,w_{r}\in\Sigma^{*}$ such that the group $B(2,p)$ has
the monoid presentation
$B(2,p)=\Sigma^{*}/\left\\{w_{i}=1,w^{p}=1\,\middle|\,1\leq i\leq r\wedge
w\in\Gamma^{+}\right\\}$ (as an abstract group) and where the Word Problem
$\mathop{\mathrm{missing}}{WP}(B(2,p))$ is undecidable. Thus, the language
$L=\mathop{\mathrm{missing}}{WP}(B(2,p))$ is undecidable, nevertheless
$w^{p}\equiv_{L}1$ for all $w\in\Sigma^{*}$. We use this example to illustrate
that there are undecidable languages satisfying the $b$-torsion property which
will be defined in Section 3.

###  2.2 Parikh-images

If $v,w\in\Gamma^{*}$, then $|w|_{v}$ denotes the number how often $v$ appears
as a factor in $w$, i. e.,
$|w|_{v}=\left|\mathinner{\left\\{u\in\Gamma^{*}\,\middle|\,\exists
s:uvs=w\right\\}}\right|$. If $P\subseteq\Gamma^{*}$, then the _Parikh-mapping
w.r.t. $P$_ is defined by $\pi_{P}:\Gamma^{*}\to\mathbb{N}^{P}$, mapping a
word $w\in\Gamma^{*}$ to its _Parikh-vector_ $(|w|_{v})_{v\in
P}\in\mathbb{N}^{P}$. The classical case is $P=\Gamma$; then the Parikh-vector
becomes $(|w|_{a})_{a\in\Gamma}$ and the Parikh-mapping is the canonical
homomorphism from the free monoid $\Gamma^{*}$ to the free commutative monoid
$\mathbb{N}^{\Gamma}$. As usual, $\mathbb{N}^{\Gamma}$ is partially ordered
such that

$\displaystyle u\leq v\iff\forall z\in\Gamma:\;u(z)\leq v(z).$

Subsets $L\subseteq\mathbb{N}^{\Gamma}$ which can be written as
$L=q+\sum_{i\in I}\mathbb{N}p_{i}$ are called _linear_ and a finite union of
linear sets is called _semi-linear_. Use the following classical results.

######  Proposition 2.1.

  1. (a)

The complement of a semi-linear set $L\subseteq\mathbb{N}^{\Gamma}$ is
effectively semi-linear. Hence, the family on semi-linear sets is an effective
Boolean algebra, see [10].

  2. (b)

The Parikh-image of a context-free language is effectively semi-linear, see
[20].

A subset $S\subseteq\mathbb{N}^{\Gamma}$ is called _positively downward-
closed_ if first $v(z)\geq 1$ for all $v\in S$, $z\in\Gamma$ and second,
$u\leq v\in S$ and $u(z)\geq 1$ for all $z\in\Gamma$ imply $u\in S$. The
complement of a positively downward-closed set $S\subseteq\mathbb{N}^{\Gamma}$
is _upward-closed_ , i. e., $u\geq v\in S$ implies $u\in S$. An upward-closed
set $S$ is determined by its set $\min(S)$ of minimal elements. Dickson’s
Lemma says that the set $\min(S)$ is finite for all
$S\subseteq\mathbb{N}^{\Gamma}$. Hence, every upward-closed subset is semi-
linear. It follows by Proposition 2.1 (a) that every positively downward-
closed set $S\subseteq\mathbb{N}^{\Gamma}$ is semi-linear, too. This
observation is crucial for proving Theorem 4.6.

###  2.3 Graphs

All graphs are assumed to be (at most) countable, given as a pair $G=(V,E)$
where $E\subseteq V\times V$. An _undirected graph_ is the special case where
$E={E}^{-1}$, so that $E$ describes the adjacency relation. If $G=(V,E)$ is a
directed graph, then $G$ also defines the _undirected graph_
$(V,E\cup{E}^{-1})$; and it defines the _undirected graph without self-loops_
$(V,(E\cup{E}^{-1})\setminus\mathrm{id}_{V})$. A graph without isolated
vertices is called an _edge-graph_. Hence, the set of edges determines an
edge-graph. If $G^{\prime}=(V^{\prime},E^{\prime})$ and $G=(V,E)$ are graphs
such that $V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$, then
$G^{\prime}$ is a _subgraph_ of graph $G$ and we denote this fact by
$G^{\prime}\leq G$. If $U\subseteq V$ is any subset, then $G[U]=(U,E\cap
U\times U)$ denotes the _induced subgraph_ of $U$ in $G$. _A subset $U$ is
called _independent_ if $G[U]$ is without any edge._ A _graph morphism_
$\varphi:(V^{\prime},E^{\prime})\to(V,E)$ is given by a mapping
$\varphi:V^{\prime}\to V$ such that $(u,v)\in E^{\prime}$ implies
$(\varphi(u),\varphi(v))\in E$. If $(V^{\prime},E^{\prime})$ and $(V,E)$ are
undirected graphs without self-loops, then
$\varphi:(V^{\prime},E^{\prime})\to(V,E)$ is a graph morphism as soon as
$(\varphi(u),\varphi(v))\in E\cup\mathrm{id}_{V}$. We say that $\varphi$ is a
_projection_ if $\varphi$ is surjective on vertices and edges, i.e.,
$\varphi(V^{\prime})=V$ and $\varphi(E^{\prime})=E$. We consider graphs up to
isomorphism, only. Hence, writing $G=G^{\prime}$ means that graphs $G$ and
$G^{\prime}$ are isomorphic. According to the following Section 2.4, a graph
$F=(V,E)$ is a _retract_ of a graph $F^{\prime}=(V^{\prime},E^{\prime})$ if
there are morphisms $\varphi:F^{\prime}\to F$ and $\gamma:F\to F^{\prime}$
such that $\varphi\gamma$ is the identity on vertices and edges of $(V,E)$.
Hence, $F$ appears in $F^{\prime}$ as the induced subgraph
$F^{\prime}[\gamma(V)]$. Another way to say this is that $F$ is an induced
subgraph of $F^{\prime}$ and there is a morphism $\varphi:F^{\prime}\to F$
which is the identity on $F$.

We consider several special graphs (and graph properties) in our paper. By a
_star_ , we denote a graph $(V,E)$ such that there exists a vertex $z\in V$
with the property $E=\left\\{\,\mathinner{(z,s)}\vphantom{s\in
V\setminus\\{z\\}}\;\left|\;\vphantom{(z,s)}\mathinner{s\in
V\setminus\\{z\\}}\right.\,\right\\}$. Thus, a star has a _center_ $z$ and the
directed edges are the outgoing _rays_ of the star. We also use this notion to
refer to an undirected connected graph where all but possibly one vertex have
degree one. Let $G=(V,E)$ be an undirected graph. $G$ is called a clique if
all possible edges (apart from self-loops) are contained in $E$. $G$ is called
bipartite if $V$ can be partitioned into $V_{1}$ and $V_{2}$ such that there
are no edges between vertices of the same class of the partition. A bipartite
graph is called complete if no further edges can be added without violating
bipartiteness. By $K_{n}$ we denote a clique with $n$ vertices, and $K_{n,m}$
denotes the complete bipartite graph with $n$ vertices in one of the classes
and $m$ vertices in the other one. A vertex set is _independent_ if its
vertices are pairwise non-adjacent. A vertex set $C$ is a _vertex cover_ if
for each edge, at least one endpoint belongs to $C$.

Some of our results revolve _tree-width_. The notation is due to Robertson and
Seymour and was one of the cornerstones in their famous graph minor project. A
formal definition of tree-width is, for example, in [8] and in many other
modern textbook on graph theory or graph algorithms.

In our paper, every word $w\in\Sigma^{*}$ represents a directed finite graph
$\rho(w)=(V(w),E(w))$ together with a linear order on vertices as follows.

$\displaystyle V(w)$ $\displaystyle=\left\\{\,\mathinner{ab^{m}a\in
ab^{+}a}\vphantom{ab^{m}a\leq w}\;\left|\;\vphantom{ab^{m}a\in
ab^{+}a}\mathinner{ab^{m}a\leq w}\right.\,\right\\}$ $\displaystyle E(w)$
$\displaystyle=\left\\{\,\mathinner{(ab^{m}a,ab^{n}a)\in ab^{+}a\times
ab^{+}a}\vphantom{ab^{m}aaab^{n}a\leq
w}\;\left|\;\vphantom{(ab^{m}a,ab^{n}a)\in ab^{+}a\times
ab^{+}a}\mathinner{ab^{m}aaab^{n}a\leq w}\right.\,\right\\}$

The empty word represents the empty graph: there are no vertices and no edges.
We extend $\rho$ to $2^{\Sigma^{*}}$ by $\rho(L)=\\{\rho(w)\mid w\in L\\}$.
Vice versa, if $G=(V,E)$ denotes a finite graph with a linear order on its
vertices, then, for $1\leq i,j\in\mathbb{N}$, the $i$-th vertex is represented
by the factor $ab^{i}a$, and an edge from the $i$-th vertex to the $j$-th
vertex is represented by the factor $ab^{i}aaab^{j}a$. Thus, vertices are
encoded by elements in the set
$\mathbb{V}=\left\\{\,\mathinner{ab^{i}a}\vphantom{1\leq
i\in\mathbb{N}}\;\left|\;\vphantom{ab^{i}a}\mathinner{1\leq
i\in\mathbb{N}}\right.\,\right\\}$ and edges are encoded by elements is the
set $\mathbb{E}=\left\\{\,\mathinner{ab^{i}aaab^{j}a}\vphantom{1\leq
i,j\in\mathbb{N}}\;\left|\;\vphantom{ab^{i}aaab^{j}a}\mathinner{1\leq
i,j\in\mathbb{N}}\right.\,\right\\}$. Note that
$\mathbb{V}\cap\mathbb{E}=\emptyset$ and $\mathbb{V}\cup\mathbb{E}$ is an
infinite regular code. Using these conventions, the regular set
$\mathbb{G}=(\mathbb{V}\cup\mathbb{E})^{*}$ as well as its subset
$\mathbb{E}^{*}\mathbb{V}^{*}$ represents all finite graphs. The same property
holds for the complement $\Sigma^{*}\setminus\mathbb{G}$: it represents all
finite graphs, too. Indeed, $\mathbb{G}\cap a\mathbb{G}=\emptyset$ but
$\rho(\mathbb{G})=\rho(a\mathbb{G})$, since the words $w\in\mathbb{G}$ and
$aw\notin\mathbb{G}$ share the same set of factors from
$\mathbb{V}\cup\mathbb{E}$. In contrast to $\mathbb{G}$, infinitely many
nonempty words in $\Sigma^{*}\setminus\mathbb{G}$ represent the empty graph,
for example all words without any $b$ or with at most one $a$. The set
$\mathbb{E}^{*}$ represents all edge-graphs, i. e., all graphs without
isolated vertices. Every nonempty finite graph has infinitely many
representations in $\mathbb{G}$. For example, there are uncountably many
subsets $L\subseteq(aba)^{+}\subseteq\mathbb{V}^{+}$ and each $\rho(L)$
represents nothing but the one-point graph without self-loop. In order to
choose a unique (and minimal) representation for a finite graph $G=(V,E)$, we
choose the minimal word $\gamma(G)=u_{1}\cdots u_{m}v_{1}\cdots
v_{n}\in\mathbb{G}$ in the short-lex ordering on $\Sigma^{*}$ such that
$\rho\gamma(G)=G$, $u_{k}\in\mathbb{E}$ for $1\leq k\leq m$ and
$v_{\ell}\in\mathbb{V}$ for $1\leq\ell\leq n$. Each $u_{k}$ is of the form
$ab^{i}aaab^{j}a$ representing an edge and each $v_{\ell}$ is of the form
$ab^{i}a$ representing an isolated vertex. We call $\gamma(G)$ the _short-lex
representation_ of $G$. Since $\gamma(G)$ is minimal w.r.t.
$\mathrel{\leq_{\mathrm{slex}}}$, we have $m=\left|\mathinner{E}\right|$ and
$n$ is the number of isolated vertices. For a graph without isolated vertices,
i. e., an edge-graph, this means that it is given by its edge list. The set of
all $\gamma\rho(\mathbb{G})$ is context-sensitive but not context-free. The
$uvwxy$-Theorem (i. e., the context-free pumping lemma) does not hold for
$\gamma\rho(\mathbb{G})$. For instance, all edge-graphs in
$\gamma\rho(\mathbb{G})$ with $n$ vertices must be represented by vertex names
$ab^{i}a$ with $1\leq i\leq n$, admitting no ‘holes’ in this vertex name
interval, as otherwise there would be a smaller short-lex representation of
some graph. Such a property is not maintained by pumping.

###  2.4 Retractions and retracts

Let $\rho:X\to Y$ and $\gamma:Y\to X$ be mappings between sets. (This holds
more general for mappings which are morphisms in some category.) If
$\rho(\gamma(y))=y$ for all $y\in Y$, then $\rho$ is called a _retraction_ and
$Y$ is called a _retract_ of $X$ with _section_ $\gamma$. We also say that
${\rho}^{-1}(y)$ is the _fiber_ of $y\in Y$. For example, if $\rho:X\to Y$ is
a homomorphism of groups $X$ and $Y$ and $H=\ker(\rho)$ is the kernel, then
$\rho$ is a retraction if and only if $X$ is a semi-direct product of $H$ by
$Y$. Another example comes from formal languages: let $X$ be the set of
deterministic finite automata (DFAs) where every state is reachable. Then the
minimization process defines a retraction to the set of minimal DFAs.

Later in Section 4.5, we define a _marked graph_ as a triple
$(V_{F},E_{F},\mu)$, where $(V_{F},E_{F})$ is a finite graph and $\mu\subseteq
V_{F}\cup E_{F}$ is the set of marked vertices and edges. Then,
$(V_{F},E_{F},\mu)\mapsto(V_{F},E_{F})$ defines a retraction by letting
$\gamma(V_{F},E_{F})=(V_{F},E_{F},\emptyset)$.

Let $\mathcal{G}$ be the set of finite graphs, $\rho:\mathbb{G}\to\mathcal{G}$
be the representation of graphs by words, and
$\gamma:\mathcal{G}\to\mathbb{G}$ the encoding of a graph by its short-lex
normal form. Then $\rho$ is a retraction. Retractions are a main tool to
understand $\rho(L)$ if $L$ is regular or more general, if $L$ satisfies the
$b$-torsion property, as defined in the next section.

##  3 The $b$-torsion property

We are interested in properties of graphs which are specified by languages
$L\subseteq\mathbb{G}$. If $L$ can be arbitrary, then we can specify
uncountably many families of graphs. So, we cannot expect any interesting and
general positive (decidability) results. As a minimal request, we restrict our
attention to subsets $L\subseteq\mathbb{G}$ where membership for $\rho(L)$ is
decidable. As a matter of fact, membership for $\rho(L)$ might be decidable
although membership for $L$ is undecidable. As we will see in Corollary 4.8,
the following definition yields a sufficient condition that membership for
$\rho(L)$ becomes decidable.

######  Definition 3.1.

Let $\Gamma$ be a finite alphabet containing the letter $b$. A subset
$L\subseteq\Gamma^{*}$ satisfies the _$(b,t,p)$ -torsion property_ if we have:
$b^{t}\equiv_{L}b^{t+p}.$ It satisfies the _$b$ -torsion property_ if there
are $t,p\in\mathbb{N}$ with $p\geq 1$ such that $L$ satisfies the
$(b,t,p)$-torsion property.

Every regular language $L\subseteq\Gamma^{*}$ satisfies the $b$-torsion
property because the syntactic monoid $M_{L}$ is finite. The $b$-torsion
property is a strong restriction if $L$ is not regular. For example,
$K=\left\\{\,\mathinner{a^{n}b^{n}}\vphantom{n\in\mathbb{N}}\;\left|\;\vphantom{a^{n}b^{n}}\mathinner{n\in\mathbb{N}}\right.\,\right\\}$
does not have that property since $b^{k}\equiv_{L}b^{m}\iff k=m$. The context-
free language $L=\\{wa\overleftarrow{w}\mid w\in\\{aba,ab^{2}a\\}^{+}\\}$ is
not regular, but it satisfies the $b$-torsion property for $t=3$ and $p=1$. In
this case, $\rho(L)$ is a not very interesting set of a few small graphs. The
next example shows that there are (non-regular) context-free languages
satisfying a $(b,t,p)$-torsion property where $\rho(L)$ is infinite.

######  Example 3.2.

Let $C$ be a nonempty finite alphabet and $K\subseteq C^{*}$ be context-free.
Let $h:C^{*}\to\mathbb{E}^{*}$ be a homomorphism. That is, $h$ is defined by
words $h(c)\in(ab^{+}aaab^{+}a)^{*}$ for $c\in C$. Suppose that $h(K)$ is
infinite. Still, the set $\rho(h(K))$ is finite. Indeed, let
$t=\max\left\\{i\in\mathbb{N}\,\middle|\,\exists c\in C:\,ab^{i}a\leq
h(c)\right\\}$, then graphs in $\rho(h(K))$ have at most $t$ vertices. Let us
make the language $h(K)$ larger by closing $h(K)$ under rewriting rules $b\to
b^{1+p}$. Context-free languages are closed under adding context-free
rewriting rules. Therefore, $h(K)$ is context-free, too. We obtain a new
context-free language $L$ with $h(K)\subseteq L$ and where $L$ satisfies the
$(b,t,p)$-torsion property. We claim that $\rho(h(L))$ is a very rich and an
infinite family of graphs (in contrast to the finite set $\rho(h(K))$).

We content ourselves to consider the case $p=1$. For $p=1$ it is rather easy
to see that every non-empty finite edge-graph appears in $\rho(h(L))$: we have
$\rho(h(L))=\rho(\mathbb{E}^{*})$. Let
$G=(V_{G},E_{G})\in\rho(\mathbb{E}^{*})$ and $m=|E_{G}|$ be the number of
edges. Since $h(K)$ is infinite, there is some edge $e=ab^{i}aaab^{j}a$ with
$1\leq i,j\leq t$ such that $e$ appears in some $w_{f}\in h(L)$ at least $m$
times as a factor. Then, thanks to $p=1$, we have
$w=(ab^{t}aaab^{t}a)^{\ell}\in L$, where $m\leq\ell$ and $\ell$ is very large.
The graph $\rho(w)$ is a one-point graph with a self-loop. Let us come back
the graph $G$. Without restriction, we have
$V_{G}\subseteq\\{t,\ldots,\ell\\}$. Now, for each $(u,v)\in E_{G}$, one after
the other, we replace one factor $ab^{t}aaab^{t}a$ in $w$ by the factor
$ab^{u}aaab^{v}a$. This changes the word $w$, but the new word $w$ still
belongs to $L$, again thanks to $p=1$. By creating, if necessary, several
copies of the same edge, the procedure yields a word $w_{G}$ such that
$w_{G}\in L$ and $\rho(w_{G})=G$. ∎

As soon as all cyclic submonoids of $M_{L}$ are finite, $L$ satisfies the
$b$-torsion property for all letters $b\in\Gamma$. For example, consider the
Word Problem of any free Burnside group $\mathcal{B}(2,p)$. All of them
satisfy the $b$-torsion property. Almost all of the groups $\mathcal{B}(2,p)$
are infinite and therefore the corresponding Word Problems are not regular. If
it is not regular, then the Word Problem of $\mathcal{B}(2,p)$ is even not
context-free, since a periodic group cannot have any non-trivial free group of
finite index by [19].

For the rest of the paper, if $L\subseteq\Sigma^{*}$ satisfies the $b$-torsion
property, then $t,p\in\mathbb{N}$, standing for _threshold_ and _period_ ,
denote those natural numbers such that the cyclic submonoid generated by the
letter $b$ in the syntactic monoid $M_{L}$ is isomorphic to $C_{t,p}$. That
is, we have $t,p\in\mathbb{N}$ with $p\geq 1$, where $t+p$ is minimal such
that

$\displaystyle\left\\{\,\mathinner{[b^{n}]}\vphantom{n\in\mathbb{N}}\;\left|\;\vphantom{[b^{n}]}\mathinner{n\in\mathbb{N}}\right.\,\right\\}=\left\\{\,\mathinner{[b^{c}]}\vphantom{0\leq
c\leq t+p-1}\;\left|\;\vphantom{[b^{c}]}\mathinner{0\leq c\leq
t+p-1}\right.\,\right\\}\,.$ (1)

Moreover, we assume that $L$ is specified such that on input $n\in\mathbb{N}$,
we can compute the value $0\leq c\leq t+p-1$ with $b^{n}\equiv_{L}b^{c}$. This
assumption is satisfied if $L$ is regular and specified, say, by some NFA. For
$L\subseteq\mathbb{G}$, we have $[ab^{c}a]=a[b^{c}]a$ and
$[ab^{c}aaab^{d}a]=a[b^{c}]aaa[b^{d}]a$. The tacit assumption is important for
the next definition to compute, for example, the reduced form according to the
next defintion.

######  Definition 3.3.

Let $L\subseteq\mathbb{G}$ satisfy the $(b,t,p)$-torsion property according to
Definition 3.1. For every $[b^{n}]$, we define its _reduced form_ by
$\mathrm{rf}{[b^{n}]}=b^{c}$ if $[b^{c}]=[b^{n}]$ and $0\leq c\leq t+p-1$.
Given $w\in\mathbb{G}$, we define the _reduced form_ $\mathrm{rf}(w)$ by
replacing every factor $ab^{m}a\leq w$ by $a\,\mathrm{rf}{[b^{m}]}a$. The
_saturation_ $\widehat{w}$ of $w$ is defined by replacing every factor
$ab^{m}a\leq w$ by the set $a[b^{m}]a$. Hence,
$\mathrm{rf}(w)\in\widehat{w}\subseteq\mathbb{G}$.

######  Remark 3.4.

Let $L\subseteq\mathbb{G}$ satisfy the $(b,t,p)$-torsion property. By possibly
decreasing $t$ and/or $p$, we may assume that for every $1\leq c\leq t+p-1$,
there is some $w\in L$ such that $ab^{c}a\leq\mathrm{rf}(w)$. Moreover, we
have $[b^{c}]=\\{b^{c}\\}$ if and only if $c<t$. ∎

######  Lemma 3.5.

Let $L\subseteq\mathbb{G}$ satisfy the $(b,t,p)$-torsion property. Then for
every $w\in\mathbb{G}$,

$\displaystyle w\in L\iff\widehat{w}\subseteq L\iff\mathrm{rf}(w)\in L\,.$

######  Proof 3.6.

Trivial, by definition of the $(b,t,p)$-torsion property.

##  4 Main results

The main results of the paper are: (1) for $L\subseteq\mathbb{G}$ satisfying
the $b$-torsion property (see Section 3), there is a regular language
$R\subseteq\mathbb{G}$ with $\rho(L)=\rho(R)$ and (2) for a context-free
language satisfying the $b$-torsion property (e.g., any regular language)
$R\subseteq\mathbb{G}$, we have an effective ‘geometric description’ of the
graphs in $\rho(R)$. From these representations, we can deduce our
classification and (un)decidability results as already mentioned in the
introduction. The (un)decidability results are detailed in the next section.

This geometric description is obtained as follows. Using the fact that $R$ is
regular (or context-free satisfying the $(b,t,p)$-torsion property), in a
first step, we find effectively a semi-linear description of $\rho(R)$. In a
second step, we compute a finite set of finite graphs. Each member $F$ in that
finite family is a retraction of some possibly infinite graph $F^{\infty}$.
The description of each $G\in\rho(L)$ is given by selecting some $F$ and the
cardinality of every fiber. The precise meaning will become clear later. As a
consequence of the description, we are able to show various decidability
results.

###  4.1 Examples

The following examples serve as an introduction to a more general situation we
will face later.

######  Example 4.1.

In the following, we let $R\subseteq\mathbb{G}$ and $t,p\in\mathbb{N}$ with
$p\geq 1$ such that $b^{n}\equiv_{R}b^{n+p}$ for all $n\geq t$. Moreover, we
let $1\leq c<t$ such that $[b^{c}]=\\{b^{c}\\}$.

  1. 1.

Let $w\in R\subseteq(ab^{c}aaab^{n}(b^{p})^{*}a)^{+}\subseteq\mathbb{G}$ with
$t\leq n$. This implies $t\leq n<t+p$ and $w$ contains a factor
$ab^{c}aaab^{d}a$ with $t\leq d<t+p$ and $[b^{d}]=b^{d+\mathbb{N}p}$. We have
$w\in(ab^{c}aaab^{n}(b^{p})^{*}a)^{m}$ for $m=|w|_{a}/5$. Hence,
$w=(ab^{c}aaab^{d_{1}}a)\cdots(ab^{c}aaab^{d_{m}}a)$ where $d_{i}=n+k_{i}p$
with $k_{i}\in\mathbb{N}$ for $1\leq i\leq m$. The set
$\left\\{\,\mathinner{d_{i}}\vphantom{1\leq i\leq
m}\;\left|\;\vphantom{d_{i}}\mathinner{1\leq i\leq m}\right.\,\right\\}$ can
have any cardinality $s$ in $\\{1,\ldots,m\\}$. Therefore, $\rho(w)$ is a
single star with at least one ray and at most $m$ rays. If $R$ is finite, then
$\mathcal{F}=\rho(R)$ is an effective finite collection of stars with at least
one ray and at most $r$ rays where
$r=\max\left\\{\,\mathinner{|w|_{a}/5}\vphantom{w\in
R}\;\left|\;\vphantom{|w|_{a}/5}\mathinner{w\in R}\right.\,\right\\}$.

We claim that $\mathcal{F}$ is infinite if and only if there is some
$M\geq|M_{R}|$ such that $(ab^{c}aaab^{n}a)^{M}\in R$. Moreover, if
$\mathcal{F}$ is infinite, then $\mathcal{F}$ is the set of all finite stars
with at least one ray. The claim holds if
$\sup\left\\{\,\mathinner{|w|_{a}/5}\vphantom{w\in
R}\;\left|\;\vphantom{|w|_{a}/5}\mathinner{w\in R}\right.\,\right\\}<\infty$,
as in this case $\mathcal{F}$ is finite. Thus, let
$\sup\left\\{\,\mathinner{|w|_{a}/5}\vphantom{w\in
R}\;\left|\;\vphantom{|w|_{a}/5}\mathinner{w\in R}\right.\,\right\\}=\infty$.
Then there is some $w\in R$ such that $ab^{c}aaab^{t}a$ appears at least
$|M_{R}|$-times as a factor. This implies that there is some $M\geq|M_{R}|$
such that $(ab^{c}aaab^{t}a)^{M}\in R$. The claim follows.

One can show that $S=(abaaab^{2}b^{*}a)^{*}(aba)$ is locally testable and
therefore star-free. Hence, the set of all finite stars is specified by a
star-free subset of $\Sigma^{*}$.

  2. 2.

If $R\subseteq(ab^{c}aaab^{c}b^{+}a)^{*}ab^{c}a\subseteq\mathbb{G}$, then
$\rho(R)$ is set of stars with center $ab^{c}a$ and outgoing rays to vertices
$ab^{d}a$ where $d>c$. Moreover, the following dichotomy holds: The set of
stars in $\rho(R)$ is either finite or it contains almost all finite stars.
Indeed, $\rho(R)$ is a set of stars with center $c$, possibly without rays. If
$\rho(R)$ is finite we are done. Otherwise, let $\rho(R)$ be infinite. Then,
for each $r\in\mathbb{N}$, there is a star in $\rho(R)$ with more than $r$
rays. This implies that for all $r\in\mathbb{N}$ there is some $\ell\geq r$
and a word $w\in R$ which has more than $\ell$ pairwise different factors
$ab^{c}aaab^{d_{i}}a$ with $r\leq d_{i}$. If $r$ is large enough, then each of
these factors can be replaced by a factor $ab^{c}aaab^{c_{i}}a$ where we have
that $t<c_{i}\leq t+p$. This yields a word $w^{\prime}\in R$. Now,
$w^{\prime}$ is very long as $\ell$ is very large. Hence, we can factorize the
word $w^{\prime}=uw^{\prime\prime}v$ such that first, $w^{\prime\prime}$
contains one of these factors $ab^{c}aaab^{c_{i}}a$ and second,
$S=u(w^{\prime\prime})^{+}v\subseteq R$. Since
$ab^{c}aaab^{c_{i}}a\equiv_{R}ab^{c}aaab^{c_{i}+pk}a$ for all
$k\in\mathbb{N}$, we conclude that $\rho(S)$ contains almost all stars, i.e.,
all stars but finitely many that are missing. ∎

The $(b,t,p)$-torsion property is trivially satisfied if
$L\subseteq\mathbb{G}$ is a finite set. An interesting case motivated by data
compression. As mentioned in Section 1: if $L$ is finite, then the minimal
size of a regular expression for $L$ is never worse than listing all graphs in
$\rho(L)$, but it might be exponentially better. This type of data compression
is important and well-known [16, 17]. It is used in DNA-computing and bio-
inspired modeling, frequently, and it is the basis of practical algorithms
like RePair.

(a) A full crown around a cycle of length $10$.

(b) A mutation with six cusps, only.

Figure 1: An $2$-dimensional illustration of Example 4.2: A small regular
expression defines a crown with $n$ cusps (in the picture: $n=10$) as well as
an exponential number of possible mutations.

######  Example 4.2.

Let $G=(V,E)$ be a connected planar graph with vertex set $V=\\{1,\ldots,n\\}$
with $n\geq 3$ together with an embedding into the $2$-dimensional sphere For
every subset $S\subseteq\\{n+1,\ldots,2n\\}$, let $G_{S}$ denote the graph
$G_{S}=(V\cup S,E\cup\left\\{(s,s-n)\,\middle|\,s\in S\right\\}).$ The family
$\mathcal{C}_{n}=\left\\{G_{S}\,\middle|\,S\subseteq\\{n+1,\ldots,2n\\}\right\\}$
might contain exponentially many graphs in $n$. This happens, for example, if
$G$ is a cycle of $n$ nodes. Then $\mathcal{C}_{n}$ has more than $2^{n}/2n\in
2^{\Omega(n)}$ connected planar graphs. If we embed $G$ in the 2-dimensional
sphere where the additional edges are spikes pointing out of the sphere, then
$G_{S}$ can be visualized as a discrete model of a 3-dimensional “crown with
at most $n$ cusps”. A $2$-dimensional representation of a full crown (having
all possible cusps) is depicted in Figure 1(a), while Figure 1(b) shows the
situation when some cusps were chosen to be removed. It is straightforward to
write down a $2n$-fold concatenation of finite sets which describes a finite
set $L_{n}\subseteq\mathbb{G}$ such that $\rho(L_{n})=\mathcal{C}_{n}$. The
size of the corresponding regular expression is $\mathcal{O}(n^{2})$. Thus, we
have a polynomial-size blueprint potentially _producing a family of
exponentially many mutations of single “corona”_ , the Latin word for “crown”.
∎

###  4.2 Introducing new alphabets

After seeing a couple of examples, we introduce certain subsets of
$\mathbb{G}$ as alphabets to express subsets of graphs. This prepares the
geometric viewpoint to view a graph as a point in the $d$-dimensional space
$\mathbb{N}^{d}$ if the size of the chosen alphabet is $d$. If $L$ is regular,
then the dimension depends on $L$ and it can be quite large, but it is
computable by using the reduced form of words in $L$. Below, all this will be
explained in details.

Let $\ell\in\mathbb{N}$. Depending on $\ell$, we define two finite and
disjoint sets that we consider as alphabets:

$\displaystyle A_{\ell}$
$\displaystyle=\left\\{\,\mathinner{ab^{m}aaab^{n}a}\vphantom{1\leq
m,n\leq\ell}\;\left|\;\vphantom{ab^{m}aaab^{n}a}\mathinner{1\leq
m,n\leq\ell}\right.\,\right\\}\subseteq\mathbb{E},$ (2) $\displaystyle
B_{\ell}$ $\displaystyle=\left\\{\,\mathinner{ab^{m}a}\vphantom{1\leq
m\leq\ell}\;\left|\;\vphantom{ab^{m}a}\mathinner{1\leq
m\leq\ell}\right.\,\right\\}\subseteq\mathbb{V}.$ (3)

Note that $A_{\ell}=B_{\ell}aB_{\ell}$. By $C_{\ell}$, we denote the union of
$A_{\ell}$ and $B_{\ell}$, which is also a finite alphabet with a linear order
between letters given by the following definition:

$x\leq_{\ell}y\iff xy\in A_{\ell}B_{\ell}\vee(xy\in(A_{\ell}A_{\ell}\cup
B_{\ell}B_{\ell})\wedge x\mathrel{\leq_{\mathrm{slex}}}y).$ (4)

We have $A_{\ell}\cap B_{\ell}=\emptyset$ and $\mathbb{N}^{C_{\ell}}$ has
dimension $d=\ell(\ell+1)$. Actually, $C_{\ell}$ is a code, i. e.,
$c_{1}\cdots c_{m}=d_{1}\cdots d_{n}\in\Sigma^{*}$ with $c_{i},d_{j}\in
C_{\ell}$ implies $m=n$ and $c_{i}=d_{i}$ for all $1\leq i\leq m$. Hence,
$\leq_{\ell}$ is well-defined by Equation (4).

######  Definition 4.3.

Let $L\subseteq\mathbb{G}$ satisfy the $b$-torsion property. Then we define an
alphabet $C_{L}\subseteq C_{\ell}$ where $\ell$ is large enough such that for
every $w\in L$ its reduced form $\mathrm{rf}(w)$ can be written as a word in
$C_{\ell}^{*}$. To make the definition unique, we choose $C_{L}$ to be the
smallest set $C_{L}\subseteq\bigcup_{\ell\in\mathbb{N}}C_{\ell}$ which has
this property.

If the context to $L$ is clear, then we drop the index $L$ and we denote by
$C$ any subset of some $C_{\ell}$ such that $C_{L}\subseteq C\subseteq
C_{\ell}$. This flexibility is useful if we wish to introduce new vertices or
new edges and we need “fresh” names in $C$ for them. In order to distinguish
the factor ordering and the linear ordering defined by Equation (4), we denote
the latter by $\leq_{C}$.

The linear order $\leq_{C}$ on $C$ defines a corresponding short-lex ordering
on $C^{*}$. Moreover, if $uxv\in C^{+}$ with $x\in A$ and $u,v\in\Sigma^{*}$,
then $u,v\in C^{*}$. The analogue for $y\in B$ does not hold, in general. For
example, $aba\in B$ and $abaaaba\in C$, but $aaba\notin C$. As $C$ is a code,
the inclusion $C\subseteq\Sigma^{*}$ yields an embedding
$h_{C}:C^{+}\to\Sigma^{+}$. Let $w\in C^{*}$ and $G=\rho(w)$. If
$L={\rho}^{-1}(G)$, then the minimal element in ${h}^{-1}_{C}(L)$ w.r.t. the
short-lex ordering for words in $C^{*}$ is a word in $A^{*}B^{*}$. It is the
same as the minimal element in $h_{C}({h}^{-1}_{C}(L))$ w.r.t. the ordering
$a<b$.

###  4.3 The power of $b$-torsion

Recall that for any subset $P\subseteq\Sigma^{*}$ and $c\in\Sigma^{*}$ we
denote by $\pi_{P}(v)\in\mathbb{N}^{P}$ its Parikh image as defined in Section
2.2. The following lemma shows a crucial “downward-closure-property” used in
Theorem 4.6.

######  Lemma 4.4.

Let $L$, $C$, and $\mathrm{rf}$ as in Definition 3.3 and in Definition 4.3.
Let $v\in C^{*}$ and $w\in L$ such that
$\pi_{C}(v)\leq\pi_{C}(\mathrm{rf}(w))$. If $\pi_{\\{z\\}}(v)\geq 1$ for all
$z\in C$, then we have $\rho(v)\in\rho(L)$.

######  Proof 4.5.

If $\pi_{\\{z\\}}(v)=\pi_{\\{z\\}}(\mathrm{rf}(w))$ for all $z\in C$, then
$\rho(v)=\rho(w)$ and therefore $\rho(v)\in\rho(L)$ because
$\rho(w)\in\rho(L)$ thanks to $w\in L$. Thus, we may assume that
$1\leq\pi_{\\{z\\}}(v)<\pi_{\\{z\\}}(\mathrm{rf}(w))$ for some $z\in C$. Thus,
without restriction we have $\mathrm{rf}(w)=uzu^{\prime}zu^{\prime\prime}$
with $z\in C$ and $u,u^{\prime},u^{\prime\prime}\in C^{*}$ and
$\pi_{C}(v)\leq\pi_{C}(\mathrm{rf}(w^{\prime}))$ where
$w^{\prime}=uu^{\prime}zu^{\prime\prime}$. We have
$\mathrm{rf}(w^{\prime})=w^{\prime}$ by Definition 3.3. Moreover, a repetition
of some $z\in C$ does not change the specified graph. Let
$\widehat{w}^{\prime}$ denote the saturation of $w^{\prime}$. By Lemma 3.5, we
have $\rho(\widehat{w}^{\prime})\subseteq\rho(L)$. Define
$L^{\prime}=L\cup\widehat{w}^{\prime}$. Then we have $w^{\prime}\in
L^{\prime}$ and $\rho(L)=\rho(L^{\prime})$; moreover, $L^{\prime}$ satisfies
the same $(b,t,p)$-torsion property as $L$ does. We can work with the same
$C$, too. Since $w^{\prime}$ is shorter than $w$, we conclude that by
induction on the length of $w$ that $\rho(v)\in\rho(L^{\prime})=\rho(L)$.

######  Theorem 4.6.

Let $L\subseteq\mathbb{G}$ be any language satisfying the $b$-torsion
property. Then there is a regular set $R\subseteq\mathbb{G}$ such that
$\rho(L)=\rho(R)\,.$

######  Proof 4.7.

The proof relies on Dickson’s Lemma. We have
$\rho(L)=\bigcup\left\\{\rho(\widehat{v})\,\middle|\,v\in L\right\\}$ by Lemma
3.5. The set $\rho(\mathrm{rf}(L))$ is finite, as $L$ satisfies the
$b$-torsion property. Thus, there is a finite subset $K\subseteq L$ such that
$\rho(\mathrm{rf}(L))=\bigcup\left\\{\rho(v)\,\middle|\,v\in K\right\\}$. Let
$C\subseteq\mathbb{E}\cup\mathbb{V}$ be the finite subset such that

$C=\left\\{z\in\mathbb{E}\cup\mathbb{V}\,\middle|\,\exists v\in
K:\pi_{\mathbb{E}\cup\mathbb{V}}(v)(z)\geq 1\right\\}\,.$

Splitting $L$ into disjoint subsets and replacing $C$ by various subsets of
$C$ we may assume without restriction that for all $w\in L$, the corresponding
$C$ contains (after the split) exactly all letters that are factors of
$\mathrm{rf}(w)$ and moreover, for all $v\in C^{*}$, we have
$z\leq\mathrm{rf}(w)\iff\pi_{C}(w)(z)\geq 1$. After this modification, there
are no vectors in $\pi_{C}(\mathrm{rf}(L))$ with zero-entries. The crucial
observation is stated in Lemma 4.4. The lemma tells us that we do not change
$\rho(L)$ if we augment $L$ by all words $v\in C^{*}$ where there is some
$w\in L$ such that $1\leq\pi_{C}(v)(z)\leq\pi_{C}(\mathrm{rf}(w))(z)$ for all
$z\in C$. Therefore, we may assume without restriction that
$\pi_{C}(\mathrm{rf}(L))$ is positively downward-closed according to Section
2.2. We also explained in Section 2.2 that Dickson’s Lemma implies that
$\pi_{C}(\mathrm{rf}(L))$ is semi-linear. By Parikh’s Theorem, see Proposition
2.1 (b), there is a regular set $R^{\prime}\subseteq C^{*}$ of words such that
$\pi_{C}(R^{\prime})=\pi_{C}(\mathrm{rf}(L))$. The class of regular sets is
closed under regular substitutions. The inclusion
$C\subseteq(\mathbb{V}\cup\mathbb{E})^{*}$ defines a canonical homomorphism
$h:C^{*}\to(\mathbb{V}\cup\mathbb{E})^{*}$. Hence, if we substitute in
$R^{\prime}$ every letter $z$ by $[h(z)]$, then we obtain $\rho(R)=\rho(L)$,
where $R=\bigcup\left\\{\widehat{w}\,\middle|\,w\in R^{\prime}\right\\}$.

######  Corollary 4.8.

Let $L\subseteq\mathbb{G}$ satisfy the $b$-torsion property. Then, given a
finite graph $G=(V_{G},E_{G})$ as an input, it is decidable whether
$G\in\rho(L)$.

The contents of Corollary 4.8 inspired the title of this subsection.

######  Proof 4.9.

By Theorem 4.6, we may replace $L$ by some regular set $R$ where
$\rho(R)=\rho(L)$. In particular, we can calculate the threshold $t$ and the
period $p$ such that $R$ satisfies the $(b,t,p)$-torsion property. The set
$\rho(\mathrm{rf}(R))$ is finite and effectively computable. For every
$F\in\rho(\mathrm{rf}(R))$, we compute the short-lex normal-form $\gamma(F)$
as defined above. We obtain a finite set $W$ of words containing all those
$\gamma(F)$. Thus, the set
$\widehat{W}=\bigcup\left\\{\widehat{w}\,\middle|\,w\in W\right\\}$ is
effectively regular and it holds that $\rho(\widehat{W})=\rho(R)$. Let
$m=\max\left\\{|aua|\,\middle|\,u\in\Sigma^{*}\wedge\exists w\in W:aua\leq
w\right\\}$. Let $M=m|V_{G}||E_{G}|$. Hence, $G\in\rho(R)$ if and only if
there is word $w\in\widehat{W}$ of length at most $M$ such that $G=\rho(w)$.

######  Corollary 4.10.

Let $L\subseteq\mathbb{G}$ be context-free satisfying the $(b,t,p)$-torsion
property. Then, we can effectively calculate a regular set
$R\subseteq\mathbb{G}$ such that $\rho(R)=\rho(L)$.

######  Proof 4.11.

Let $C=\left\\{z\in\mathbb{V}\cup\mathbb{E}\,\middle|\,\forall
m\in\mathbb{N}:ab^{m}a\leq z\implies m\leq t+p-1\right\\}$. The inclusion of
$C\subseteq(\mathbb{V}\cup\mathbb{E})^{*}$ defines a homomorphism $h$ from the
free monoid $C^{*}$ to $(\mathbb{V}\cup\mathbb{E})^{*}$. Hence,
$L^{\prime}={h}^{-1}(L)$ is effectively context-free. Therefore,
$\pi_{C}(L^{\prime})=\pi_{C}({h}^{-1}(L))$ is effectively semi-linear. The
semi-linear set can be represented by a regular language $R^{\prime}\subseteq
C^{*}$. As in the proof of Theorem 4.6, we obtain $R$ as the image of
$R^{\prime}$ under the regular substitution which replaces every letter $z\in
C$ by $[h(z)]$.

Let $R\subseteq\mathbb{G}$ be regular. It is well-known that there might be a
much more concise representation by some context-free language
$K\subseteq\mathbb{G}$ such that $\pi_{C}(K)=\pi_{C}(R)$ and hence
$\rho(K)=\rho(R)$. Therefore, we might describe graph families even more
concisely using context-free grammars than using NFAs.

###  4.4 Switching the alphabet and Parikh images

By Theorem 4.6, we know that regular languages suffice to describe all sets
$\rho(L)$ where $L\subseteq\mathbb{G}$ satisfies the $b$-torsion property.
Therefore, we restrict ourselves to regular languages. Throughout this
section, $R\subseteq\mathbb{G}$ denotes a regular language. Hence, we can
calculate a threshold $t$ and a period $p\geq 1$ such that $R$ satisfies the
$(b,t,p)$-torsion property. Since $R$ is regular, the set
$L={h}^{-1}_{C}(R)\cap A^{*}B^{*}$ is regular, too; its _Parikh-image_
$\pi_{C}(L)\subseteq\mathbb{N}^{C}$ is effectively semi-linear. (This is
always true as soon as $R$ and hence $L$ is context-free.) Hence, for some
finite index sets $J$ and $I_{j}$ we can write

$\pi_{C}(L)=\bigcup_{j\in J}\left(q_{j}+\sum_{i\in
I_{j}}\mathbb{N}p_{i}\right)\,,$ (5)

where $q_{j},p_{i}\in\mathbb{N}^{C}$ are vectors. Splitting $\pi_{C}(L)$ into
more linear sets by making the index set $J$ larger and the sets $I_{j}$
smaller (if necessary), we can assume without restriction that, for all $j\in
J$ and $z\in C$, we have $\sum_{i\in I_{j}}p_{i}(z)\leq q_{j}(z)$. To see
this, let $1\in I_{j}$. Then, we have

$\displaystyle q_{j}+\sum_{i\in I_{j}}\mathbb{N}p_{i}=\left(q_{j}+\sum_{i\in
I_{j}\setminus\\{1\\}}\mathbb{N}p_{i}\right)\cup\left(q_{j}+p_{1}+\sum_{i\in
I_{j}}\mathbb{N}p_{i}\right)\,.$

Splitting $L$ into even more but finitely many cases, we can assume without
restriction (for simplifying the notation) that the set $J$ is a singleton.
Thus, $\pi(L)=q+\sum_{i\in I}\mathbb{N}p_{i}$ for some
$q,p_{i}\in\mathbb{N}^{C}$ such that $\sum_{i\in I}p_{i}(z)\leq q(z)$ for all
$z\in C$. Moreover, making $A,B,C$ perhaps smaller, we may assume without
restriction that $q(z)\geq 1$ for all $z\in C$ and $C=A\cup B$. (A similar
argument was used in the proof of Theorem 4.6 above.)

In order to understand the set of graphs in $\rho(R)$, it suffices to
understand the set of finite graphs defined by linear sets of the form
$S=q+\sum_{i\in I}\mathbb{N}p_{i}\subseteq\mathbb{N}^{C}$, where $q(z)\geq 1$
for all $z\in C$ and $\sum_{i\in I}p_{i}\leq q$. For that purpose, we let
$r=\sum_{i\in I}p_{i}\leq q$ and we define a function
$\alpha:C\to\mathbb{N}_{\infty}$ as follows.

$\alpha(z)=\begin{cases}q(z)&\text{if }r(z)=0\wedge\exists
m\in\mathbb{N}:t\leq m\wedge ab^{m}a\leq z\\\ \infty&\text{if }r(z)\geq
1\wedge\exists m\in\mathbb{N}:t\leq m\wedge ab^{m}a\leq z\\\
1&\text{otherwise. That is: }\forall m\in\mathbb{N}:ab^{m}a\leq z\implies
m<t.\end{cases}$ (6)

For all $z\in C$, let $L_{z}\subseteq\Sigma^{*}$. Then, we introduce the
following notation.

$\displaystyle\prod_{z\in C}L_{z}=L_{z_{1}}\cdots
L_{z_{\left|\mathinner{C}\right|}}$ (7)

where $z_{i}\leq z_{j}$ for all $i\leq j$ according to the linear order
defined in Equation (4). Observe that $\prod_{z\in C}L_{z}$ is regular if all
$L_{z}$ are regular. With this notation, we define regular sets
$R_{\alpha}\subseteq\Sigma^{*}$ and $L_{\alpha}\subseteq\Sigma^{*}$ by

$\displaystyle R_{\alpha}=\prod_{z\in C}z^{\alpha(z)}\quad\text{and}\quad
L_{\alpha}=\prod_{z\in C}[z]^{\alpha(z)}$ (8)

Here and in the following, $L^{\infty}$ is just another notation for $L^{+}$
if $L$ is any set of words.

######  Theorem 4.12.

The sets $R_{\alpha}$ and $L_{\alpha}$ are regular sets with
$R_{\alpha}\subseteq L_{\alpha}$ and $\rho(L_{\alpha})=\rho(R)$.

######  Proof 4.13.

Without restriction, Equation (5) reads as $\pi_{C}(L)=q+\sum_{i\in
I}\mathbb{N}p_{i}$. As $z\in[z]$, the inclusions $R_{\alpha}\subseteq
L_{\alpha}$ and $\rho(R_{\alpha})\subseteq\rho(R)$ follow by definition. For
the converse, let $v\in R$ and $G=\rho(v)$. Choose some $w\in L_{\alpha}$ with
$\pi_{C}(w)=q+\sum_{i\in I}m_{i}p_{i}$. Choosing $m\in\mathbb{N}$ large
enough, we find $\pi_{C}(v)\leq q+mr\in\pi_{C}(\mathrm{rf}(L_{\alpha}))\,$
where, as above, $r=\sum_{i\in I}p_{i}$. Hence, we can apply Lemma 4.4 to
finish the argument.

###  4.5 Marked graphs

In the next steps, we define for $\alpha$ a finite family of finite graphs
$\mathcal{F}_{\beta}$, together with a marking on vertices and edges. Each
member of $\mathcal{F}_{\beta}$ is just a singleton of a marked graph. The
family $\mathcal{F}_{\beta}$ still depends on $\alpha$, only, but it might be
more indices $\beta$ than indices $\alpha$ for defining
$\mathcal{F}_{\alpha}$. Then, for each $F\in\mathcal{F}_{\beta}$, we define a
possibly infinite graph $F^{\infty}$, using the notion of a marked graph.

######  Definition 4.14.

For $z\in C$ let $\alpha^{\prime}(z)=\alpha(z)$ if $\alpha(z)<\infty$ and
$\alpha^{\prime}(z)=1$, otherwise. We let $w_{\alpha}=\prod_{z\in
C}z^{\alpha^{\prime}(z)}$, and we define $\mathcal{F}_{\alpha}$ by
$\mathcal{F}_{\alpha}=\rho(R_{\alpha})$ where $R_{\alpha}$ is as in (8).

Since $w_{\alpha}$ is a single word, the set $\mathcal{F}_{\alpha}$ is a
finite set of finite graphs. We are now defining the crucial notion of a
marked graph, where some vertices and edges are marked.

######  Definition 4.15.

A _marked graph_ is a tuple $F=(V_{F},E_{F},\mu)$, where $(V_{F},E_{F})$ is a
finite graph and $\mu\subseteq V_{F}\cup E_{F}$ denotes the set of marked
vertices and edges. Isolated vertices may appear, but if an isolated vertex is
marked, then there is exactly one isolated vertex. We also require that
whenever an edge $(u,v)$ is marked, then at least one of its endpoints is
marked, too. A _marked edge-graph_ is a marked graph without isolated
vertices.

In a first step we let the word $w_{\alpha}$ and the set $R_{\alpha}$ as
defined above in Definition 4.14. Performing another splitting, we can write
$R_{\alpha}$ as a finite union of sets $R_{\alpha,k}$ such that each
$R_{\alpha,k}$ defines exactly one graph $(V_{\alpha,k},E_{\alpha,k})$. By
making, if necessary, the alphabet $C$ as well as the threshold $t$ larger
(but keeping the period $p$), we assume that for each $(\alpha,k)$, there is
some $\beta:C\to\mathbb{N}_{\infty}$ such that

$\rho(\prod_{z\in C}z^{\beta(z)})=(V_{\alpha,k},E_{\alpha,k})$ (9)

where $\beta(z)\in\\{0,1,\infty\\}$ with the requirements that first,
$\beta(z)=\infty\implies[z]\neq\\{z\\}$ and second, if $z=uav$ denotes an edge
with $[z]\neq\\{z\\}$, then
$\beta(z)=\infty\iff([u]\neq\\{u\\}\vee[v]\neq\\{v\\})$. In order to simplify
the notation, we concentrate on one $(\alpha,k)$ and we denote
$(V_{\alpha,k},E_{\alpha,k})$ as $(V_{F^{\prime}},E_{F^{\prime}})$.

We are ready to define the marking for $(V_{F^{\prime}},E_{F^{\prime}})$. We
mark exactly those vertices and edges $z$ in $V_{F^{\prime}}\cup
E_{F^{\prime}}$ where $\beta(z)=\infty$. Note that therefore an edge is marked
only if at least one of its endpoints is marked. It might be, however, that
there is an unmarked edge $(u,v)$ where $u$ and $v$ are marked. In the final
step, if an isolated vertex is marked, then remove all isolated marked
vertices $y$ except one isolated vertex $y$ which is marked. In particular,
after that procedure if a marked isolated vertex $y$ appears, then
$\beta(y)=\infty$. This reduces the number of marked graphs without changing
the set $\rho(R)$ we were interested in.

We denote by $\mathcal{F}_{\beta}$ this family of marked graphs which was
defined through the function $\alpha$.

Let us switch to a more abstract viewpoint. We let $\mathcal{F}$ be any finite
family of marked graphs. For each $F=(V_{F},E_{F},\mu)\in\mathcal{F}$, we
define a possibly infinite graph $F^{\infty}$ where $(V_{F},E_{F})$ appears as
an induced subgraph, and we define a family $\mathcal{G}_{F}$ of finite
graphs. In the application, we consider finitely many $\mathcal{F}_{\beta}$,
and then we study
$\bigcup\left\\{\mathcal{G}_{F}\,\middle|\,F\in\mathcal{F}_{\beta}\right\\}$,
where $F=(V_{F},E_{F},\mu)$ is the marked graph obtained by the canonical
marking procedure above (which might have removed isolated vertices). It turns
out that, for a full description of $\rho(R)$, it is enough to describe sets
$\mathcal{G}_{F}$ for marked graphs $F=(V_{F},E_{F},\mu)$. This requires to
define $F^{\infty}$.

######  Definition 4.16.

Let $F=(V_{F},E_{F},\mu)$ be a marked graph as in Definition 4.15. Then, the
graph $F^{\infty}=(V_{F}^{\infty},E_{F}^{\infty})$ is defined as follows.

$\displaystyle V^{\infty}_{F}$
$\displaystyle=V_{F}\times\\{0\\}\cup\bigcup_{u\in
V_{F}}\left\\{(u,k)\,\middle|\,u\text{ is marked }\wedge
k\in\mathbb{N}\right\\}\,,$ $\displaystyle E^{\infty}_{F}$
$\displaystyle=E_{F}\times\\{0\\}\cup\\{((u,k),(v,\ell))\in
V_{F}^{\infty}\times V_{F}^{\infty}\mid(u,v)\in E_{F}\wedge(u,v)\text{ is
marked}\\}\,,$

with $E_{F}\times\\{0\\}=\\{((u,0),(v,0))\mid(u,v)\in E_{F}\\}$. The family
$\mathcal{G}_{F}$ is the set of finite subgraphs of $F^{\infty}$ containing
$(V_{F}\times\\{0\\},E_{F}\times\\{0\\})$ as an induced subgraph.

Observe that $F^{\infty}=(V_{F},E_{F})$ if and only if there is no marking, i.
e., if $\mu=\emptyset$. We embed $F$ into $F^{\infty}$ by a graph morphism
$\gamma$ which maps each vertex $u\in V_{F}$ to the pair $\gamma(u)=(u,0)\in
V^{\infty}_{F}$. The projection onto the first component $\varphi(u,k)=u$
yields a retraction for every $G\in\mathcal{G}_{F}$ with retract $F$. If no
isolated vertex is marked, then $F^{\infty}$ has at most $|V_{F}|$ isolated
vertices, but if there are marked vertices, then for every sufficiently large
$k$, there is some graph in $\mathcal{G}_{F}$ which has exactly $k$ isolated
vertices. In order to understand the graphs in $\mathcal{G}_{F}$ (which is our
goal), it is enough to understand the graphs $G$ satisfying $F\leq G\leq
F^{\infty}$. For $F=F^{\infty}$, we have the full information about that set.
Thus, we focus on $F\neq F^{\infty}$. Theorem 4.17 shows that $\rho(R)$ is
rather rich as soon as some $F\in\mathcal{F}_{\beta}$ satisfies $F\neq
F^{\infty}$.

$\vdots$$\ast$ | $\vdots$$\ast$ | $\vdots$$\vdots$$\ast$$\ast$ | $\vdots$$\ast$ | $\vdots$$\vdots$$\vdots$$\ast$$\ast$$\ast$
---|---|---|---|---
(a) | (b) | (c) | (d) | (e)
Figure 2: The four basic situations how a marked graphs $F=(V_{F},E_{F})$ can
lead to a graph $F^{\infty}$ are shown in (a) through (d). The right-most
picture (e) combines various situations. The marked graphs $F$ are shown in
the lower line, and above each marked graph the graphs $F^{\infty}$ are shown
in black. The lowest line in each graph $F^{\infty}$ shows the embedding of
$(V_{F},E_{F})$ into $F^{\infty}$.

The reader might find it helpful to look at the examples of Figure 2 to
understand the building of the graph $F^{\infty}$ from a marked graph $F$ if
at least one vertex is marked. The pictures show five different situations:
(a) a graph $F$ with a single isolated marked vertex: it gives rise to an
arbitrary number of isolated vertices in $F^{\infty}$; (b) a graph $F$ with a
single marked vertex incident to a marked edge yields an infinite star in
$F^{\infty}$; (c) a graph $F$ with a marked edge with different endpoints
where both are marked. It yields an infinite complete bipartite graph in
$F^{\infty}$; (d) a graph $F$ with a marked self-loop gives rise to an
infinite clique in $F^{\infty}$; (e) The rightmost figure combines the last
three situations in a single marked graph, plus the effect of an unmarked
edge.

######  Theorem 4.17.

Let $F=(V_{F},E_{F},\mu)$ be any marked graph.

  1. 1.

If there is no marking, then $\mathcal{G}_{F}=\\{(V_{F},E_{F})\\}$.

  2. 2.

If $F$ contains a marked edge $(u,v)$ where the endpoint $v$ is marked, then
every finite star with center $(u,0)$ appears as an induced subgraph of some
$G\in\mathcal{G}_{F}$.

  3. 3.

Suppose we represent a bipartite graph as a triple $(U,V,E)$ where $U\cap
V=\emptyset$ and $E\subseteq U\times V$. Let $H$ be any finite bipartite edge-
graph. If $F$ contains a marked edge $(u,v)$ where $u$ and $v$ are marked,
then a disjoint union of $F$ and $H$ appears in $\mathcal{G}_{F}$.

  4. 4.

Let $H$ be any finite graph. If $F$ contains a marked self-loop $(u,u)$, then
the disjoint union of $F$ and $H$ belongs to $\mathcal{G}_{F}$.

  5. 5.

Let $F$ be any marked graph such that at most two vertices are marked. Then
the following holds. A disjoint union of $F$ and a triangle (or any other non-
bipartite graph) appears in $\mathcal{G}_{F}$ if and only if there is some
marked self-loop in $F$.

######  Proof 4.18.

Define the vertex sets $V_{0}=V_{F}\times\\{0\\}$ and $V_{\geq 1}=\\{(u,k)\mid
u\in V_{F}\land k\geq 1\\}$. We consider the five cases separately.

1.

By definition.

2.

In the graph $F^{\infty}$, there are directed edges from $(u,0)$ to all
$(v,k)$, where $k\in\mathbb{N}$. In particular, every finite star with center
$(u,0)$ appears as an induced subgraph of some $G\in\mathcal{G}_{F}$.

3\. and 4.

Consider a marked edge $(u,v)$ with both endpoints marked. In the graph
$F^{\infty}$, there are directed edges from $(u,k)$ to all $(v,\ell)$, where
$k,\ell\in\mathbb{N}$. Consider the induced subgraph $F^{\infty}[U]$ where
$U=V_{\geq 1}$. By definition, $F^{\infty}[U]$ is disjoint from the subgraph
$F=F^{\infty}[V_{0}]$. For $u=v$, the graph $F^{\infty}[U]$ is an infinite
complete graph; for $u\neq v$, the graph $F^{\infty}[U]$ is an infinite
complete bipartite graph. The claims follow.

5.

If $F$ contains a marked self-loop, then, by definition, it is a self-loop
around a marked vertex. Hence, we are done since every disjoint union of $F$
and any other finite graph $G$ appears in $\mathcal{G}_{F}$. For the other
direction, assume that $F$ has no marked self-loop. If a disjoint union of $F$
and a finite non-bipartite graph $G$ appears in $\mathcal{G}_{F}$, then we
need at least three marked vertices to produce $G$.

The following lemma uses the notions of vertex cover and of bag-size. Recall
that the tree-width was actually defined by bag-size - 1 by Robertson and
Seymour in [21].

######  Lemma 4.19.

Let $F=(V_{F},E_{F},\mu)$ be a nonempty marked graph such that each marked
edge has at least one unmarked vertex incident to it. Then for every
$G\in\mathcal{G}_{F}$ both, the size of a minimal vertex cover and its bag-
size are bounded by $|V_{F}|$.

The following proof is based on well-known and standard techniques.

######  Proof 4.20.

Let $G=(V_{G},E_{G})\in\mathcal{G}_{F}$. Since every marked edge has at most
one marked vertex incident to it, $V_{G}$ is the disjoint union of $V_{F}$ and
an independent set $U$. Clearly, $V_{F}$ is a vertex cover of $G$. We now
construct a tree-decomposition as follows. We begin with single bag $B$
defined by the vertex cover $V_{F}$. Then for every $u\in U$ we define a bag
$B_{u}$ by $N(u)\cup\\{u\\}$ where $N(u)$ is the set of neighbors of $u$. Note
that $N(u)\subseteq V_{F}$. A bag $B_{u}$ connected to $B$ if and only if
$N(u)\neq\emptyset$. This is tree decomposition of $G$ where the connected
component of $G$ (in the underlying tree) is a star with $|U|$ rays.

For an illustration of our construction, we refer to Figure 3.

######  Remark 4.21.

The construction in the proof of Lemma 4.19 is optimal with respect to the
minimal vertex cover and to the bag-size if $(V_{F},E_{F})$ is a clique and
$S=(V_{F},S_{F})$ is its subgraph of marked edges such that $S$ is a star,
where the center of the star is not marked. In general, we might achieve
smaller vertex covers and bag-sizes by beginning with a tree decomposition of
$F$.

$\ast$$\vdots$

$\ddots$

$\ddots$

Figure 3: An illustration of Lemma 4.19 with $n=4$. The graph $F$ is a
$K_{4}$, but the marked edges induce a star with three rays. In $F^{\infty}$,
the star sends three streams of rays into infinity.

######  Definition 4.22.

For $i=1,\ldots,4$, we define classes $\mathcal{C}_{i}$ containing the sets
$\rho(L)$ where $L\subseteq\mathbb{G}$ is regular. If $\mathcal{G}$ denotes
such a set $\rho(L)$, then:

  1. 1.

We let $\mathcal{G}\in\mathcal{C}_{1}$ if $\mathcal{G}$ is a finite set of
graphs.

  2. 2.

We let $\mathcal{G}\in\mathcal{C}_{2}$ if the set $\mathcal{G}$ has bounded
tree-width.

  3. 3.

We let $\mathcal{G}\in\mathcal{C}_{3}$ if $\mathcal{G}\in\mathcal{C}_{2}$ or
if there exists a finite set of graphs $\mathcal{F}^{\prime}$ such that for
every finite bipartite graph $G^{\prime}$ there is some
$F^{\prime}\in\mathcal{F}^{\prime}$ such that the disjoint union of
$F^{\prime}$ and $G^{\prime}$ appears in $\mathcal{G}$.

  4. 4.

We let $\mathcal{G}\in\mathcal{C}_{4}$ if $\mathcal{G}\in\mathcal{C}_{3}$ if
there exists a finite set of graphs $\mathcal{F}^{\prime}$ such that for every
finite graph $G^{\prime}$ there is some $F^{\prime}\in\mathcal{F}^{\prime}$
such that the disjoint union of $F^{\prime}$ and $G^{\prime}$ appears in
$\mathcal{G}$.

Note that our definition enforces $\mathcal{C}_{i}\subseteq\mathcal{C}_{j}$
for $1\leq i\leq j\leq 4$. The reason is driven by our motivation to find
graphs in sets $\rho(L)$ satisfying some property given $\Phi$. For that, let
us consider a marked graph $F=(V_{F},E_{F},\mu)$. Recall that $\mu$ is a
subset of $V_{F}\cup E_{F}$. Now, if $\mu^{\prime}\subseteq\mu$, then
$\mathcal{G}_{F^{\prime}}\subseteq\mathcal{G}_{F}$ where
$F^{\prime}=(V_{F},E_{F},\mu^{\prime})$. Thus, increasing the marking
increases $\mathcal{G}_{F}$, and this makes it more likely to find a graph
satisfying $\Phi$. If there is no marking at all, then $\mathcal{G}_{F}$ is
finite, hence of bounded tree-width. As long as $\mu$ is without any marked
edge, we remain in the class $\mathcal{C}_{2}$. Suppose that $\mu$ contains a
marked edge which is not a self-loop, then we mark first one of its endpoints
but not the other one. We remain in $\mathcal{C}_{2}$. If according to $\mu$
both endpoints are marked, we mark the second endpoint, too. The result is
that we are now in $\mathcal{C}_{3}$. In the final step we mark all self-
loops. If there is at least one, we are in the class $\mathcal{C}_{4}$. Thus,
step by step, starting with $(V_{F},E_{F},\emptyset)$ we can make the
intermediate families $\mathcal{G}_{F^{\prime}}$ larger; and we end in the
largest family $\mathcal{G}_{F}$.

######  Corollary 4.23.

Let $F=(V_{F},E_{F},\mu)$ is a marked graph. Then the following holds.

  1. 1.

We have $\rho(\mathcal{G}_{F})\in\mathcal{C}_{1}$ if and only if there is no
marked vertex.

  2. 2.

If there is no marked edge $(u,v)$ where both $u$ and $v$ are marked, then
$\rho(\mathcal{G}_{F})\in\mathcal{C}_{2}$. This implies that
$\rho(\mathcal{G}_{F})$ has bounded tree-width. The tree-width and the the
minimal size of a vertex cover are bounded by $|V_{F}|$.

  3. 3.

If there is a marked edge $(u,v)$ where $u$ and $v$ are marked, then
$\rho(\mathcal{G}_{F})\in\mathcal{C}_{3}$. This implies that every connected
finite bipartite graph appears as a connected component of some
$G\in\rho(\mathcal{G}_{F})$. In particular, for every $k\in\mathbb{N}$ there
some $G\in\mathcal{G}_{F}$ where its tree-width and the minimal size of a
vertex cover are both greater than $k$.

  4. 4.

We have $\rho(\mathcal{G}_{F})\in\mathcal{C}_{4}$ if and only if every
connected finite graph appears as a connected component of some $G\in\rho(L)$.

######  Proof 4.24.

It is enough to prove the lemma when $\rho(L)=\mathcal{G}_{F}$ where
$F=(V_{F},E_{F},\mu)$ is a marked graph. The result is now a direct
consequence of Theorem 4.17 and Lemma 4.19 for the second item concerning the
bounded tree-width.

We now show in Corollary 4.25 that for star-free languages, the classification
only contains three cases. As an example, consider $R=(ab^{+}aaab^{+}a)^{+}$;
then $R$ is star-free555The minimal DFA accepting $R$ is easily seen to be
_counter-free_ in the sense of [18]. Alternatively, one can check with a FO-
sentence that a word $w$ contains the factor $aaa$, but no factor $bab$. Every
occurrence of the factor $aaa$ of $w$ is preceded by $ab^{+}$ and succeeded by
$b^{+}a$. Moreover, the word $w$ has a prefix in $ab^{+}aaa$ and a suffix in
$aaab^{+}a$ and if there is a factor $baab$ in $w$, then this factor is
(immediately) preceded and followed by the factor $aaa$. and
$\rho(R)\in\mathcal{C}_{4}$, because $\rho(R)=\mathcal{G}_{F}$, where $F$ is a
marked self-loop around a marked vertex. Hence, $\rho(R)\in\mathcal{C}_{4}$.
Therefore, if $\rho(L)$ equals $\rho(R)$ for a star-free regular language $R$,
then Corollary 4.25 states that $\rho(L)\in\mathcal{C}_{3}$ implies
$\rho(L)\in\mathcal{C}_{4}$. Hence, if $R$ is star-free, then $\rho(R)$
belongs to three classes, only.666Corollary 4.25 corrects a misprint in [7,
Cor. 3].

######  Corollary 4.25.

Let $R$ be a star-free language such that $\rho(R)$ is infinite. Then, we have
either $\rho(R)\in\mathcal{C}_{2}$ or $\rho(R)\in\mathcal{C}_{4}$.

######  Proof 4.26.

Recall Schützenberger’s classical theorem that a language $R$ is star-free if
and only if first, it is regular and second, its syntactic monoid $M_{R}$ is
aperiodic, see [22]. Therefore, $R$ satisfies the $(b,t,p)$-torsion property
for some threshold $t\geq 0$ with period $p=1$. We may assume that $\rho(R)$
is infinite. Then, we find a marked graph $F$ such that
$\mathcal{G}_{F}\subseteq\rho(R)$ and $\mathcal{G}_{F}$ is infinite. 777The
construction of the marked graphs changed perhaps the threshold, but not the
period which is therefore still $1$. For simplicity, the new threshold is
still called $t$. Hence, $F$ contains a marked edge where at least one
endpoint is marked. This marked vertex is defined by the word $ab^{t+1}a$.
Thus, it is unique because every vertex in $F$ has the form $ab^{i}a$ for
$1\leq{t+1}$ and the vertices $aba,\ldots,ab^{t}$ are not marked. Since
$\mathcal{G}_{F}\notin\mathcal{C}_{2}$, the marked graph $F$ contains a marked
self-loop $ab^{t+1}aaab^{t+1}a$. We now apply Theorem 4.17 and Corollary 4.23.
A marked self-loop implies $\rho(R)\in\mathcal{C}_{4}$.

##  5 Graph properties

A _graph property_ is a decidable subset $\Phi\subseteq\mathbb{G}$. For a
finite graph $G$, we write $G\models\Phi$ if the short-lex representation
$\gamma(G)$ belongs to $\Phi$.888Recall that $\rho(w)$ is realized as a graph
with a natural linear order on the vertices: we have $ab^{c}a\leq ab^{d}a\iff
c\leq d$. Given a word $w\in\mathbb{G}$, we can compute $\gamma\rho(w)$.
Hence, we can assume without restriction that $\Phi$ is saturated:
${\rho}^{-1}(\rho(\Phi))=\Phi.$ To simplify our presentation, we focus on
properties of undirected finite graphs (without self-loops). This can be
achieved by making the set $\Phi$ larger such that $\Phi$ has the following
desired property: If $u\in\mathbb{G}$ represents the graph $\rho(u)=(V,E)$ and
$\Phi$ speaks about undirected graphs (resp. undirected graphs without self-
loops) then $\rho(u)\models\Phi\iff(V,E\cup{E}^{-1})\models\Phi$ (resp.
$\rho(u)\models\Phi\iff(V,(E\cup{E}^{-1})\setminus\mathrm{id}_{V})\models\Phi$).

We are interested in the following (uniform) satisfiability problem
$\mathop{\mathrm{missing}}{Sat}(\mathcal{G}_{F},\Phi)$.

  * •

Input: A marked graph $F$ and a graph property $\Phi\subseteq\mathbb{G}$.

  * •

Question: “$\exists G\in\mathcal{G}_{F}:G\models\Phi$?”

Throughout this section, $F$ denotes a marked graph and $\mathcal{G}_{F}$
denotes the family of graphs defined in Definition 4.16. Sometimes, it will be
crucial in the following that $F$ or $\Phi$ are fixed. We will clarify this by
writing $\mathop{\mathrm{missing}}{Sat}_{F}(\cdot)$ or
$\mathop{\mathrm{missing}}{Sat}_{\Phi}(\cdot)$, respectively.

For various well-studied graph properties, the satisfiability problem is
always decidable. This includes problems where $\Phi$ states that a graph is
planar (resp. is closed under graph-minors, resp. perfect, $k$-colorable,
etc.). This is a direct consequence of the following fact.

######  Theorem 5.1.

Let either $\mathcal{G}_{F}$ be finite (i. e., a singleton) or $\Phi$ be any
graph property which is closed under taking induced subgraphs (or both). Then,
$\mathop{\mathrm{missing}}{Sat}(\mathcal{G}_{F},\Phi)$ is decidable.

######  Proof 5.2.

Since $F$ is an induced subgraph for every $G\in\mathcal{G}_{F}$, it is enough
to check whether $F\models\Phi$. This is possible, because $\Phi$ is decidable
by definition.

In many cases, graph properties are expressible either in monadic second-order
logic (MSO for short) or in first-order logic (FO for short). MSO is a rich
and versatile class to define graph properties. Moreover, we allow
quantification over both, sets of vertices and sets of edges. Since
$w\in\mathbb{G}$ defines graphs with a linear order, we can express in MSO,
for example, that the number of vertices is even. We use the following well-
known results as a black box. First, given an MSO-sentence $\Phi$ and
$k\in\mathbb{N}$, it is decidable whether there exists a graph of tree-width
at most $k$ satisfying $\Phi$, see, e. g., [4, 5, 23]. As a second black box,
we use Trakhtenbrot’s Theorem [24]: on input of an FO-sentence $\Phi$, it is
undecidable whether there exists a finite graph satisfying $\Phi$.

######  Remark 5.3.

Trakhtenbrot’s Theorem also holds in the following smaller family
$\mathcal{B}_{t}$ of finite bipartite graphs. More precisely, we mean the
following. Let $t\in\mathbb{N}$ be any fixed constant. Then, $\mathcal{B}_{t}$
denotes the family of connected finite bipartite graphs which have at least
$t$ vertices. Then, on input of an FO-sentence $\Phi$, it is undecidable
whether there exists a graph in $\mathcal{B}_{t}$ satisfying $\Phi$. ∎

######  Theorem 5.4.

Let $\Phi$ be an MSO-sentence. Then,
$\mathop{\mathrm{missing}}{Sat}_{\Phi}(\cdot)$ is decidable for marked graphs
$F=(V_{F},E_{F},\mu)$ as inputs where at most one endpoint of each edge is
marked.

######  Proof 5.5.

The family $\mathcal{G}_{F}$ yields a family of graphs of bounded tree-width.
Indeed, the bag size is uniformly bounded by $|V_{F}|$. The result follows
from the papers cited above.

The next theorem shows in particular that the FO-theory is undecidable if
there is an edge where both endpoints are marked, using Trakhtenbrot’s
Theorem.

######  Theorem 5.6.

Let $F$ be a marked graph where both endpoints of some marked edge are marked.
Then, $\mathop{\mathrm{missing}}{Sat}_{F}(\cdot)$ is undecidable.

######  Proof 5.7.

Let $G$ be any finite connected bipartite graph with at least $n+1$ vertices.
According to Theorem 4.17, the family $\mathcal{G}_{F}$ contains a graph
$G^{\prime}$ which is the disjoint union of $G$ and $F$. Let $\Psi$ be a
first-order sentence which expresses that $F$ appears and that every vertex
outside $F$ is part of a connected component which has more vertices than $F$.
As $F$ is fixed, $\Psi$ is also of constant size, with $\mathcal{O}(n)$ many
vertex variables. In particular, we can assume that $\Psi$ is of the form
$\exists x_{1},\dots,x_{n}\Psi^{\prime}$, this way fixing the vertices of $F$
in $G^{\prime}$. Moreover, on input $\Phi\in\mathrm{FO}$ we can construct
another FO-sentence $\Phi^{\prime}$ such that $G\models\Phi\iff
G^{\prime}\models\exists x_{1},\dots,x_{n}(\Psi^{\prime}\wedge\Phi^{\prime})$.
Namely, $\Phi^{\prime}$ speaks about the graph $G^{\prime}$, disregarding the
vertices of $F$. Let us denote $\exists
x_{1},\dots,x_{n}(\Psi^{\prime}\wedge\Phi^{\prime})$ by $\varphi_{F}(\Phi)$.
Then
$\mathrm{FO}^{\prime}=\left\\{\varphi_{F}(\Phi)\,\middle|\,\Phi\in\mathrm{FO}\right\\}$
is a subset of $\mathrm{FO}$. This renders the satisfiability problem
$\left\\{\varphi(\Phi)\in\mathrm{FO}^{\prime}\,\middle|\,\exists
G^{\prime}\in\mathcal{G}_{F}:G^{\prime}\models\varphi_{F}(\Phi)\right\\}$ to
be undecidable by Trakhtenbrot’s Theorem as stated in Remark 5.3. Indeed, if
it was decidable, then we could decide whether $G\models\Phi$ for any
$G\in\mathcal{B}_{n+1}$.

Some graph properties where the problem
$\mathop{\mathrm{missing}}{Sat}(\mathcal{G}_{F},\Phi)$ is trivially decidable
are covered by the next theorem, including the problem whether
$\mathcal{G}_{F}$ contains a non-planar graph, and various parametrized
problems like: “Is there some $(V_{G},E_{G})\in\mathcal{G}_{F}$ with a clique
bigger than $\sqrt{|V_{G}|}$?”.999Questions like this one save us from
discussing encodings of numbers as a second input parameter.

######  Theorem 5.8.

Let $F$ be any marked graph and $\Phi$ be a non-trivial graph property such
that $G\models\Phi$ if and only if there is a connected component $G^{\prime}$
of $G$ such that $G^{\prime}\models\Phi$. Then, the answer to the
satisfiability problem $\mathop{\mathrm{missing}}{Sat}(\mathcal{G}_{F},\Phi)$
is always “Yes” in the following two cases.

  1. 1.

There is some marked self-loop.

  2. 2.

The property $\Phi$ is true for some bipartite edge-graph and there is some
marked edge where both endpoints are marked.

######  Proof 5.9.

Since $\Phi$ is non-trivial, there is some finite graph $G$ modeling $\Phi$.
If there is some marked self-loop, then there is some $K\in\mathcal{G}_{F}$
such that $K$ is a disjoint union of $F$ and $G$ by Theorem 4.17. In the
second case, we can choose $G$ to be a bipartite edge-graph. By assumption,
$F$ contains a marked edge where both endpoints are marked. Again, there is
some $K\in\mathcal{G}_{F}$ such that $K$ is a disjoint union of $F$ and $G$,
so that we can apply Theorem 4.17.

Example 5.10 lists a few graph properties which are not covered by Theorem
5.8, but nevertheless the satisfiability problem is decidable. Recall that
graph $G=(V_{G},E_{G})$ possesses a Hamiltonian cycle if the cycle on
$|V_{G}|$ vertices is a subgraph of $G$. A matching is a collection of edges
of a graph such that no pair of these has any common vertices. A matching is
perfect if it contains $|V_{G}|/2$ many edges. A set $T$ of vertices of a
graph $G=(V_{G},E_{G})$ is called a dominating set101010The notation $T$
refers to the German notion _Träger_. if each vertex $u\in V_{G}$ has a vertex
of $T$ in its _closed neighborhood_
$N_{G}[u]=\\{u\\}\cup\left\\{v\,\middle|\,(u,v)\in E\right\\}$. A set $D$ of
vertices of a graph $G=(V_{G},E_{G})$ is called a a _defensive alliance_ in
[14] if it is non-empty and each vertex $u\in D$ has at least half of its
closed neighborhood within $D$.

######  Example 5.10.

Let $F=(V_{F},E_{F},\mu)$ denote a marked graph as input. Then the following
problems are decidable.

  1. 1.

Is there some $G\in\mathcal{G}_{F}$ with a Hamiltonian cycle?

  2. 2.

Is there some $G\in\mathcal{G}_{F}$ with a perfect matching?

  3. 3.

Is there some $G\in\mathcal{G}_{F}$ with a dominating set of size at most
$\log_{2}|V_{G}|$?

  4. 4.

Is there some $G\in\mathcal{G}_{F}$ with a defensive alliance of size at most
$\log_{2}|V_{G}|$?

We explain these concrete examples one by one.

Hamiltonian cycle. In order to decide the existence of some
$G\in\mathcal{G}_{F}$ with a Hamiltonian cycle, we proceed as follows. Without
restriction, we may assume that $F$ has no Hamiltonian cycle, because
otherwise we are done. If there is any $G=(V_{G},E_{G})\in\mathcal{G}_{F}$
with a Hamiltonian cycle $Z=(V_{G},Z_{G})$, then starting at any fixed vertex
of $F$, the cycle yields a linear order on the vertices in $G$ and, by
restriction, a linear order on $V_{F}$. Since $F$ is without any Hamiltonian
cycle, the cycle leaves $F$ at some vertex $u_{1}\in V_{F}$ and reenters $F$
at some vertex $v_{1}\in V_{F}$. Continuing this way, we obtain a sequence of
pairs $(u_{1},v_{1}),\ldots,(u_{k},v_{k})$ with $1\leq k\leq|V_{F}|$ before
the cycle is closed. Let us look at the directed path
$u_{i}=w_{0},w_{1},\ldots,w_{\ell}=v_{i}$ on the cycle starting at some
$u_{i}$ and ending in $v_{i}$ for some pair $(u_{i},v_{i})$ with $1\leq i\leq
k$. Suppose that $w_{r}=ab^{c}a$ and $w_{s}=ab^{d}a$ for $1\leq r<s<\ell$ with
$t\leq c<d$ and $[b^{c}]=[b^{d}]$. Then we can modify the graph $G$ as
follows: we remove all vertices $w_{r+1},\ldots,w_{s}$ from $G$, and we
introduce an edge $(w_{r},w_{s+1})$. In this way, we obtain a smaller graph
$G^{\prime}\in\mathcal{G}_{F}$ which still has a Hamiltonian cycle. Thus, if
$\mathcal{G}_{F}$ contains any graph with a Hamiltonian cycle, then
$\mathcal{G}_{F}$ contains a graph with at most $p|V_{F}|$ vertices. Hence, it
is enough to enumerate all graphs that have at most $p|V_{F}|$ vertices which
have a Hamiltonian cycle and to check if any of them appears in
$\mathcal{G}_{F}$.

Perfect matching. Let $V_{F}=\\{x_{1},\ldots,x_{n}\\}$ and suppose that some
$G=(V_{G},E_{G})\in\mathcal{G}_{F}$ has a perfect matching. We have
$V_{F}\subseteq V_{G}$. Hence, all $x_{i}\in V_{F}$ are matched by vertices
$y_{i}\in V_{G}$. The induced subgraph $G[V_{F}\cup\\{y_{1},\ldots,y_{n}\\}]$
has a perfect matching with at most $2|V_{F}|$ vertices. As in the precedent
example, we enumerate and check all these graphs.

Dominating set. If there is no marked edge in $F=(V_{F},E_{F},\mu)$, then
decide whether a dominating set with the desired property exists in
$(V_{F},E_{F})$. In the second case, there is a marked vertex which is is an
endpoint of a marked edge. Then, $\mathcal{G}_{F}$ contains a graph $G$ which
is the (not disjoint) union of $F$ and an arbitrarily large star. The
intersection of $F$ and the star is just one point. Thus, we find a graph $G$
in $\mathcal{G}_{F}$ where $G$ has a dominating set of size $D(G)$ such that
$D(G)\leq\log_{2}|V_{G}|$. Actually, for every $\varepsilon>0$, there is some
$G\in\mathcal{G}_{F}$ such that $D(G)/|V_{G}|<\varepsilon$. Thus, in the
second case, we return “Yes.”

Defensive alliance. If $F=(V_{F},E_{F},\mu)$ contains no marked vertex at all,
then $\mathcal{G}_{F}=\\{(V_{F},E_{F})\\}$, so we have to check if
$(V_{F},E_{F})$ contains a sufficiently small defensive alliance. Otherwise,
we return “Yes.” Namely, in this case $\mathcal{G}_{F}$ contains a graph $G$
that consists of $(V_{F},E_{F})$ plus $2^{|V_{F}|}$ many isolated vertices.
Now, one of these isolated vertices forms a sufficiently small defensive
alliance by itself. ∎

Frequently, we are not only interested in decision problems, but in
computational problems. We illustrate this by computing the supremum (in
$\mathbb{N}_{\infty}$) of the chromatic numbers over all the graphs in
$\mathcal{G}_{F}$. Recall that a graph $G=(V,E)$ is _$k$ -colorable_ if there
is a function $c:V\to\\{1,\ldots,k\\}$ such that $(u,v)\in
E\setminus\mathrm{id}_{V}$ implies $c(u)\neq c(v)$. Indeed, self-loops should
not have any influence on the chromatic number, because otherwise a graph with
a self-loop could not be colored at all. For a finite graph, its _chromatic
number_ $\chi(G)$ is the minimal possible $k\in\mathbb{N}$ such that $G$ is
$k$-colorable.

######  Proposition 5.11.

Let $F=(V_{F},E_{F},\mu)$ be a marked graph. Then,
$\sup\left\\{\chi(G)\,\middle|\,G\in\mathcal{G}_{F}\right\\}=\infty$ if and
only if $F$ contains a marked self-loop. If $F$ is without any marked self-
loop, then
$\chi(V_{F},E_{F})=\max\left\\{\chi(G)\,\middle|\,G\in\mathcal{G}_{F}\right\\}$
is a natural number.
Moreover, if $L\subseteq\mathbb{G}$ is regular, then
$\sup\left\\{\chi(G)\,\middle|\,G\in\rho(L)\right\\}$ is effectively
computable.

######  Proof 5.12.

Since $F\in\mathcal{G}_{F}$, we have
$\chi(V_{F},E_{F})\leq\sup\left\\{\chi(G)\,\middle|\,G\in\mathcal{G}_{F}\right\\}$.
If $F=(V_{F},E_{F},\mu)$ has a marked self-loop, then $\mathcal{G}_{F}$
contains for each $k\in\mathbb{N}$ a graph having a clique of size $k$ as a
subgraph. Hence,
$\sup\left\\{\chi(G)\,\middle|\,G\in\mathcal{G}_{F}\right\\}=\infty$.
Therefore, for the rest of the proof, we may assume that $F=(V_{F},E_{F},\mu)$
has no marked self-loops. For every $G\in\mathcal{G}_{F}$, there is a graph
morphism $\varphi:G\to(V_{F},E_{F})$. If $F=(V_{F},E_{F},\mu)$ has no self-
loops at all, then we have $\chi(G)\leq\chi(F)$, because every fiber
${\varphi}^{-1}(v)$ is without any edge for $v\in V_{F}$. Thus, a $k$-coloring
of $(V_{F},E_{F})$ induces a $k$-coloring of $G$. If there is a self-loop
around a vertex $v$, then the loop is not marked by assumption. This loop is
the only edge in ${\varphi}^{-1}(v)$, but, by definition, this has no
influence on the chromatic number.

Together with the results above, we have a meta-theorem for graph properties
$\Phi$ with a decidable satisfiability problem, covering all cases where we
have positive results.

######  Theorem 5.13.

Let $r:\mathbb{N}\to\mathbb{N}$ be a non-decreasing computable function and
$\Phi$ be a graph property such that, for each marked graph $F$, the following
property holds. If some graph $G=(V,E)\in\mathcal{G}_{F}$ satisfies $\Phi$,
then there is some graph $G=(V,E)\in\mathcal{G}_{F}$ such that $G$ satisfies
$\Phi$ and $G$ has at most $r(|V_{F}|)$ vertices. Then, given as input a
context-free grammar for a language $L\subseteq\mathbb{G}$ satisfying the
$(b,t,p)$-torsion property, the following satisfiability problem

$\displaystyle\mathop{\mathrm{missing}}{Sat}(\rho(L),\Phi)=\text{``}\exists
G\in\rho(L):\,G\models\Phi\text{?''}$

is decidable.

######  Proof 5.14.

Since $L$ is context-free satisfying the $(b,t,p)$-torsion property, we find a
regular language $R$ such that $\rho(R)=\rho(L)$. Splitting $R$ into finitely
many cases, we are reduced to show the claim when the input is a single marked
graph $F=(V_{F},E_{F},\mu)$. Taking $F$ as input, we compute $n=r(|V_{F}|)$
and we compute the list of all graphs with at most $n$ vertices. Then, we
check whether any graph in that list belongs to the family $\mathcal{G}_{F}$
and satisfies $\Phi$, which is possible thanks to Corollary 4.8 (and as $\Phi$
is decidable).

##  6 Conclusion and open problems

The starting point of our paper was the following idea: Decide a graph
property $\Phi$ not for a single instance as in traditional algorithmic graph
theory, but generalize this question to a set of graphs specified by a regular
language over a binary alphabet. “Let’s talk about a regular family of
graphs111111A first song about a remotely similar theme was released in 1991
by Salt ’n’ Pepa., reader”. We chose a natural representation of graphs by
words over a binary alphabet $\Sigma$. Our results are rather robust, other
“natural choices” work as well. Next, pick your favorite graph property
$\Phi$. For example, $\Phi$ says that the number of vertices is a prime
number. The property does not look very regular, there is no way to express
the property, say, in MSO. Still, given a context-free language
$L\subseteq\Sigma^{*}$ which satisfies the $b$-torsion property and which
encodes sets of graphs, we can answer the question if there exists a graph
represented by $L$ and which satisfies $\Phi$. This is a consequence of
Theorem 5.13 and Bertrand’s postulate that for all $n\geq 1$, there is a prime
between $n$ and $2n$.

Still, various problems are open. For example, is the satisfiability problem
decidable for graph properties which are not covered by Theorem 5.13? This
could mean that on input of a marked graph $(F,\mu)$, we can say “YES, there
is such a graph in $\mathcal{G}_{F}$” without producing a witness graph in
$\mathcal{G}_{F}$ for this claim.

Another type of problems relates to model checking. Given a graph property
$\Phi$, we can define $\mathcal{G}(\Phi)=\left\\{G\text{ is a finite
graph}\,\middle|\,G\models\Phi\right\\}$. Suppose that
${\rho}^{-1}(\mathcal{G}(\Phi))$ is regular. Given a regular language
$R\subseteq\Sigma^{*}$, can we decide whether
$\mathcal{G}(\Phi)\subseteq\rho(R)$? What about the equality
$\mathcal{G}(\Phi)=\rho(R)$? We can ask the same two questions if $R$ is
context-free.

Another area which we did not touch at all concerns complexity. We can state
however an $\mathbf{NP}$ lower bound for $\mathbf{NP}$-hard graph properties.
Observe that our encoding of graphs by words is essentially optimal if we
write exponents $i$ which appear in factors $ab^{i}a$ in binary. We let
$|\mathinner{ab^{i}a}|_{\text{bin}}=2+\log_{2}(i)$, and this induces a binary
length $|\mathinner{w}|_{\text{bin}}$ for $w\in\mathbb{G}$ and also a natural
binary length $|\mathinner{F}|_{\text{bin}}$ for marked graphs
$F=(V_{F},E_{F},\mu)$. If $\Phi$ denotes an $\mathbf{NP}$-hard graph property,
then the problem $\left\\{F=(V_{F},E_{F},\mu)\,\middle|\,\exists
G\in\mathcal{G}_{F}:\,G\models\Phi\right\\}$ (with binary input size for $F$)
is $\mathbf{NP}$-hard. It is however not clear that it can be solved within
$\mathbf{NP}$ assuming that $\Phi$ is in $\mathbf{NP}$.

### Acknowledgement

We thank Dietrich Kuske for pointing out that the formulation of [7, Thm. 3]
is not correct as published in the proceedings. The correct statement is now
Theorem 5.6. We also thank the anonymous referees of DLT’21 for various
suggestions to improve the presentation.

## References

  * [1] T. Anderson, J. Loftus, N. Rampersad, N. Santean, and J. Shallit.  Detecting palindromes, patterns and borders in regular languages.  Information and Computation, 207:1096–1118, 2009.
  * [2] A. V. Anisimov.  Group languages.  Kibernetika, 4:18–24, 1971.  English translation in Cybernetics and Systems Analysis 4 (1973), 594-601.
  * [3] S. Bera and K. Mahalingam.  Structural properties of word representable graphs.  Mathematics in Computer Science, 10:209–222, 2016.
  * [4] B. Courcelle.  The expression of graph properties and graph transformations in Monadic Second-Order Logic.  In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1: Foundations, pages 313–400. World Scientific, 1997.
  * [5] B. Courcelle and J. Engelfriet.  Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications.  Cambridge University Press, 2012.
  * [6] A. A. de Melo and M. de Oliveira Oliveira.  Second-order finite automata.  In H. Fernau, editor, Computer Science - Theory and Applications \- 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 - July 3, 2020, Proceedings, volume 12159 of Lecture Notes in Computer Science, pages 46–63. Springer, 2020.
  * [7] V. Diekert, H. Fernau, and P. Wolf.  Properties of graphs specified by a regular language.  In N. Moreira and R. Reis, editors, Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings, volume 12811 of Lecture Notes in Computer Science, pages 117–129. Springer, 2021.
  * [8] R. Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [9] S. Eilenberg.  Automata, Languages, and Machines, volume A.  Academic Press, New York and London, 1974.
  * [10] S. Ginsburg and E. H. Spanier.  Semigroups, Presburger formulas and languages.  Pacific Journal of Mathematics, 16:285–296, 1966.
  * [11] D. Güler, A. Krebs, K. Lange, and P. Wolf.  Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy.  In S. T. Klein, C. Martín-Vide, and D. Shapira, editors, Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings, volume 10792 of Lecture Notes in Computer Science, pages 156–168. Springer, 2018.
  * [12] O. Kharlampovich.  The Word Problem for the Burnside Varieties.  Journal of Algebra, 173:613–621, 1995.
  * [13] S. Kitaev and S. Seif.  Word problem of the Perkins semigroup via directed acyclic graphs.  Order, 25:177–194, 2008.
  * [14] P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi.  Alliances in graphs.  Journal of Combinatorial Mathematics and Combinatorial Computing, 48:157–177, 2004.
  * [15] D. Kuske.  Second-order finite automata: Expressive power and simple proofs using automatic structures.  In N. Moreira and R. Reis, editors, Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings, volume 12811 of Lecture Notes in Computer Science, pages 242–254. Springer, 2021.
  * [16] N. J. Larsson and A. Moffat.  Off-line dictionary-based compression.  Proceedings of the IEEE, 88:1722–1732, 2000.
  * [17] M. Lohrey, S. Maneth, and R. Mennicke.  XML tree structure compression using RePair.  Information Systems, 38:1150–1167, 2013.
  * [18] R. McNaughton and S. Papert.  Counter-Free Automata.  The MIT Press, Cambridge, Mass., 1971.
  * [19] D. E. Muller and P. E. Schupp.  Groups, the theory of ends, and context-free languages.  Journal of Computer and System Sciences, 26:295–310, 1983.
  * [20] R. J. Parikh.  On context-free languages.  Journal of the ACM, 13:570–581, 1966.
  * [21] N. Robertson and P. D. Seymour.  Graph minors. III. Planar tree-width.  Journal of Combinatorial Theory, 36:49–64, 1984.
  * [22] M.-P. Schützenberger.  On finite monoids having only trivial subgroups.  Information and Control, 8:190–194, 1965.
  * [23] D. Seese.  The structure of the models of decidable monadic theories of graphs.  Annals of Pure and Applied Logic, 53:169–195, 1991.
  * [24] B. A. Trahtenbrot.  The impossibility of an algorithm for the decision problem for finite domains (in Russian).  Doklady Akademii Nauk SSSR, New Series, 70:569–572, 1950.  English Translation in American Mathematical Society, Translations (1963), Vol. 23, pages 1-5.
  * [25] M. N. Vyalyi and A. A. Rubtsov.  On regular realizability problems for context-free languages.  Problems of Information Transmission, 51:349–360, 2015.
  * [26] P. Wolf.  On the decidability of finding a positive ILP-instance in a regular set of ILP-instances.  In M. Hospodár, G. Jirásková, and S. Konstantinidis, editors, Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17-19, 2019, Proceedings, volume 11612 of Lecture Notes in Computer Science, pages 272–284. Springer, 2019.
  * [27] P. Wolf.  From decidability to undecidability by considering regular sets of instances.  In G. Cordasco, L. Gargano, and A. A. Rescigno, editors, Proceedings of the 21st Italian Conference on Theoretical Computer Science, Ischia, Italy, September 14-16, 2020, volume 2756 of CEUR Workshop Proceedings, pages 33–46. CEUR-WS.org, 2020.