Humboldt-Universität zu Berlin, Germanysteffen.van.bergerem@hu-
berlin.dehttps://orcid.org/0000-0002-5212-8992This work was funded by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) — project
number 431183758 (gefördert durch die Deutsche Forschungsgemeinschaft (DFG) —
Projektnummer 431183758). RWTH Aachen<EMAIL_ADDRESS>aachen.dehttps://orcid.org/0000-0002-0292-9142Funded by the European Union
(ERC, SymSim, 101054974). Views and opinions expressed are however those of
the author(s) only and do not necessarily reflect those of the European Union
or the European Research Council. Neither the European Union nor the granting
authority can be held responsible for them. RWTH Aachen,
Germanyrunde@lics.rwth-aachen.dehttps://orcid.org/0009-0000-4547-1023This work
was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) — project number 453349072 (gefördert durch die Deutsche
Forschungsgemeinschaft (DFG) — Projektnummer 453349072). Jane Open Access and
Joan R. Public <ccs2012> <concept> <concept_id>10003752.10003790</concept_id>
<concept_desc>Theory of computation Logic</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003777.10003787</concept_id> <concept_desc>Theory of
computation Complexity theory and logic</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10010052.10010053</concept_id>
<concept_desc>Theory of computation Fixed parameter
tractability</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept>
<concept_id>10010147.10010257.10010293.10010297</concept_id>
<concept_desc>Computing methodologies Logical and relational
learning</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept>
<concept_id>10010147.10010257.10010258.10010259</concept_id>
<concept_desc>Computing methodologies Supervised learning</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>
[500]Theory of computation Logic [500]Theory of computation Complexity theory
and logic [500]Theory of computation Fixed parameter tractability
[500]Computing methodologies Logical and relational learning [300]Computing
methodologies Supervised learning 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

# On the Parameterized Complexity of Learning Monadic Second-Order Formulas

Steffen van Bergerem  Martin Grohe  Nina Runde

###### Abstract

Within the model-theoretic framework for supervised learning introduced by
Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning
concepts definable in monadic second-order logic (MSO). We show that the
problem of learning a consistent MSO-formula is fixed-parameter tractable on
structures of bounded tree-width and on graphs of bounded clique-width in the
1-dimensional case, that is, if the instances are single vertices (and not
tuples of vertices). This generalizes previous results on strings and on
trees. Moreover, in the agnostic PAC-learning setting, we show that the result
also holds in higher dimensions. Finally, via a reduction to the MSO-model-
checking problem, we show that learning a consistent MSO-formula is para-NP-
hard on general structures.

###### keywords:

monadic second-order definable concept learning, agnostic probably
approximately correct learning, parameterized complexity, tree-width, clique-
width, fixed-parameter tractable, Boolean classification, supervised learning,
monadic second-order logic, Courcelles Theorem

###### category:

##  1 Introduction

We study Boolean classification problems. The input elements for the
classification task come from a set $\mathbb{X}$, the _instance space_. A
_classifier_ on $\mathbb{X}$ is a function $c\colon\mathbb{X}\to\\{+,-\\}$.
Given a _training sequence_ $S$ of labeled examples
$(x_{i},\lambda_{i})\in\mathbb{X}\times\\{+,-\\}$, we want to find a
classifier, called a _hypothesis_ , that explains the labels given in $S$ and
that can also be used to predict the labels of elements from $\mathbb{X}$ not
given as examples.

In this paper, we study problems in a model-theoretic framework that was
introduced by Grohe and Turán [31] and further studied in [28, 30, 29, 57, 59,
60, 58]. There, the instance space $\mathbb{X}$ is a set of tuples from a
(relational) structure, called the _background structure_ , and classifiers
are described using parametric models based on logics. More specifically, in
this paper, we consider classifiers that can be specified in monadic second-
order logic (MSO).

We study these problems within the following well-known settings from
computational learning theory. In Angluin’s model of _exact learning_ [4], the
examples are assumed to be generated using an unknown classifier, the _target
concept_ , from a known _concept class_. The task is to find a hypothesis that
is consistent with the training sequence $S$, i.e. a function
$h\colon\mathbb{X}\to\\{+,-\\}$ such that $h(x_{i})=\lambda_{i}$ for all $i$.
In Haussler’s model of _agnostic probably approximately correct (PAC)
learning_ [34], a generalization of Valiant’s _PAC learning_ model [56], an
(unknown) probability distribution $\mathcal{D}$ on
$\mathbb{X}\times\\{+,-\\}$ is assumed and training examples are drawn
independently from this distribution. The goal is to find a hypothesis that
generalizes well, i.e. one is interested in algorithms that return with high
probability a hypothesis with a small expected error on new instances drawn
from the same distribution. For more background on PAC learning, we refer to
[36, 47]. In both settings, we require our algorithms to return a hypothesis
from a predefined _hypothesis class_.

#### Our Contributions

In this paper, we study the parameterised complexity of the consistent-
learning problem MSO-Consistent-Learn and the PAC-learning problem MSO-PAC-
Learn. In both problems, we are given a background structure $\mathcal{A}$.
The labeled training examples are of the form $(\bar{v},\lambda)$, where
$\bar{v}$ is a $d$-tuple of elements of $\mathcal{A}$ and
$\lambda\in\\{-,+\\}$. The goal is to find a hypothesis of the form
$h_{\varphi,\bar{w}}$ for an MSO-formula $\varphi(\bar{x};\bar{y})$ and a
tuple $\bar{w}$ with $h_{\varphi,\bar{w}}(\bar{v})=+$ if
$\mathcal{A}\models\varphi(\bar{v};\bar{w})$ and
$h_{\varphi,\bar{w}}(\bar{v})=-$ otherwise. For MSO-Consistent-Learn, this
hypothesis should be consistent with the given training examples. For MSO-PAC-
Learn, the hypothesis should generalize well. We restrict the complexity of
allowed hypotheses by giving a bound $q$ on the quantifier rank of $\varphi$
and a bound $\ell$ on the length of $\bar{w}$. Both $q$ and $\ell$ as well as
the dimension $d$ of the problem, that is, the length of the tuples to
classify, are part of the parameterization of the problems. A detailed
description of MSO-Consistent-Learn is given in Section 3. The problem MSO-
PAC-Learn is formally introduced in Section 5.

######  Example 1.1.

Assume we are given the background structure depicted by the graph
$\mathcal{G}$ in Figure 1, the training sequence
${S=((v_{1},+),(v_{6},+),(v_{4},-),(v_{5},-))}$, and ${d=1}$, ${q=3}$,
${\ell=1}$. Then a consistent hypothesis could state that there is a bipartite
partition of the graph such that $x$ is on the same side as $v_{2}$. Formally,
this would be a hypothesis $h_{\varphi,\bar{w}}$ with the MSO-formula
${\varphi(x;y)}$ ${=\exists Z\leavevmode\nobreak\ Z(x)\wedge
Z(y)\leavevmode\nobreak\ \wedge}$ ${\forall z_{1}\forall
z_{2}\leavevmode\nobreak\
E(z_{1},z_{2})\rightarrow\neg\bigl{(}Z(z_{1})\leftrightarrow
Z(z_{2})\bigr{)}}$ and the parameter setting $\bar{w}=(v_{2})$.

$v_{1}$ $v_{2}$ $v_{5}$ $v_{6}$ $v_{3}$ $v_{4}$ Figure 1: Graph $\mathcal{G}$
for Example 1.1.

For the $1$-dimensional case of the consistent-learning problem MSO-
Consistent-Learn, called 1D-MSO-Consistent-Learn, [29, 28] gave fixed-
parameter tractability results for the case that the background structure is a
string or a tree. We generalize the results to structures of bounded tree-
width in Section 3 and to graphs of bounded clique-width in Section 4.

######  Theorem 1.2.

The problem 1D-MSO-Consistent-Learn, when additionally parameterized by the
tree-width of the input structure, is fixed-parameter tractable.

######  Theorem 1.3.

The problem 1D-MSO-Consistent-Learn, when additionally parameterized by the
clique-width of the input graph, is fixed parameter tractable on graphs.

The results rely on the model-checking techniques due to Courcelle and Seese
for graphs of bounded tree-width [20, 46] and Courcelle, Makowsky, and Rotics
for graphs of bounded clique-width [19]. To make use of them, we encode the
training examples in the background structure. While this construction works
for $d=1$, it fails for higher dimensions if there are too many examples to
encode.

For the PAC-learning problem MSO-PAC-Learn, however, as we discuss in Section
5, we can restrict the number of examples to consider to a constant. Hence, we
obtain fixed-parameter tractability results for learning MSO-definable
concepts also for higher dimensions, similar to results for first-order logic
on nowhere dense classes [59, 58].

######  Theorem 1.4.

The problem MSO-PAC-Learn is fixed-parameter tractable when additionally
parameterized by the tree-width of the input structure.

######  Theorem 1.5.

The problem MSO-PAC-Learn is fixed-parameter tractable on graphs when
additionally parameterized by the clique-width of the input graph.

Lastly, analogously to the hardness of learning FO-definable concepts and the
relation to the FO-model-checking problem discussed in [59], we are interested
in the hardness of learning MSO-definable concepts and specifically in the
relation to the MSO-model-checking problem MSO-Mc. We show that MSO-Mc can
already be reduced to the 1-dimensional case of MSO-Consistent-Learn, yielding
the following hardness result that we prove in Section 6.

######  Theorem 1.6.

1D-MSO-Consistent-Learn is para-NP-hard under fpt Turing reductions.

#### Related Work

The model-theoretic learning framework studied in this paper was introduced in
[31]. There, the authors give information-theoretic learnability results for
hypothesis classes that can be defined using first-order and monadic second-
order logic on restricted classes of relational structures, such as the class
of planar graphs, graphs of bounded degree, structures of bounded tree-width,
and structures of bounded clique-width. Those results were purely about
statistical learning theory and neither algorithmic nor complexity theoretic.

Algorithmic aspects of the framework were first studied in [30], where it was
proved that concepts definable in first-order logic can be learned in time
polynomial in the degree of the background structure and the number of labeled
examples the algorithm receives as input, independently of the size of the
background structure. This was generalized to first-order logic with counting
[57] and with weight aggregation [60]. On structures of polylogarithmic
degree, the results yield learning algorithms running in time sublinear in the
size of the background structure. It was shown in [29, 57] that sublinear-time
learning is no longer possible if the degree is unrestricted. To address this
issue, in [29], it was proposed to introduce a preprocessing phase where,
before seeing any labeled examples, the background structure is converted to a
data structure that supports sublinear-time learning later. This model was
applied to monadic second-order logic on strings [29] and trees [28].

The parameterized complexity of learning first-order logic was first studied
in [59]. Via a reduction to the model-checking problem, the authors show that
on arbitrary relational structures, learning hypotheses definable in FO is
$\textup{{AW}}[*]$-hard. In contrast to this, they show that the problem is
fixed-parameter tractable on nowhere dense graph classes. This result has been
extended to nowhere dense structure classes in [58]. Although not stated as
fpt results, the results in [29, 28] yield fixed-parameter tractability for
learning MSO-definable concepts on strings and trees if the problem is
restricted to the 1-dimensional case where the tuples to classify are single
vertices. The logical learning framework is related to, but different from the
framework of _inductive logic programming_ (see, e. g., [18, 42, 43]), which
may be viewed as the classical logic-learning framework. In the database
literature, there are various approaches to learning queries from examples [8,
7, 33, 35, 37, 12, 49, 1, 2, 13, 48, 50]. Many of these are concerned with
active learning scenarios, whereas we are in a statistical learning setting.
Moreover, most of the results are concerned with conjunctive queries or
queries outside the relational database model, whereas we focus on full first-
order and monadic second-order logic. Another related subject in the database
literature is the problem of learning schema mappings from examples [3, 14,
51, 52, 26]. In formal verification, related logical learning frameworks [17,
23, 25, 40, 62] have been studied as well. In algorithmic learning theory,
related works study the parameterized complexity of several learning problems
[6, 39] including, quite recently, learning propositional CNF and DNF formulas
and learning solutions to graph problems in the PAC setting [15].

##  2 Preliminaries

With $[n]$ we denote the set of natural numbers $\\{1,...,n\\}$. For the power
set of a set $V$ we write $2^{V}=\\{V^{\prime}\leavevmode\nobreak\
|\leavevmode\nobreak\ V^{\prime}\subseteq V\\}$.

#### Relational Structures and MSO

We consider monadic second-order (MSO) logic which is a fragment of second-
order logic where we only quantify over unary relations (sets). In MSO we
consider two kinds of free variables, which we call set variables (uppercase
$X,Y,X_{i}$) and element variables (lowercase $x,y,x_{i}$). The _quantifier
rank_ $qr(\varphi)$ of a formula $\varphi$ is the depth of nesting of its
quantifiers. Usually, we look at subsets of all MSO formulas, where
$\textup{{MSO}}[\tau]$ is the set of all MSO formulas over vocabulary $\tau$,
and we define $\textup{{MSO}}[\tau,q,\ell_{1},\ell_{2}]$ as the set of all MSO
formulas over vocabulary $\tau$, of quantifier rank at most $q$, with at most
$\ell_{1}$ free element variables, and at most $\ell_{2}$ free set variables.
Note that for fixed $\tau,q,\ell_{1},\ell_{2}$, we can define a normal form
such that this set is finite, and the size can be described by some function
$s(\tau,q,\ell_{1},\ell_{2})$.

MSO-formulas are evaluated over relational $\tau$-structures $\mathcal{A}$
with a _universe_ $A$ and an _interpretation_ $R^{\mathcal{A}}\subseteq
A^{\operatorname*{arity}(R)}$ of each relation symbol $R\in\tau$. For a set
$B\subseteq A$, the _induced substructure_ of $\mathcal{A}$ on $B$ is the
$\tau$-structure $\mathcal{A}[B]$ with universe B and $R^{\mathcal{A}[B]}$ =
$R^{\mathcal{A}}\cap B^{\operatorname*{arity}(R)}$ for every relation symbol
$R\in\tau$. For a $\tau$-structure $\mathcal{A}$ with universe $A$, the _$q$
-type_ of a vertex $a\in A$ is the set of formulas
$\textup{tp}^{\mathcal{A}}_{q}(a)=\\{\varphi\in\textup{{MSO}}[\tau,q,1,0]\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{A}\models\varphi(a)\\}$. For sets
$A^{\prime}\subseteq A$, we define the $q$-type as
$\textup{tp}^{\mathcal{A}}_{q}(A^{\prime})=\\{\varphi\in\textup{{MSO}}[\tau,q,0,1]\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{A}\models\varphi(A^{\prime})\\}.$

#### Graphs, Trees and Tree Automata

A directed graph is a relational structure denoted by $\mathcal{G}=(V,E)$,
where $V$ is called the set of _vertices_ , and $E\subseteq V\times V$ is
referred to as _edges_. An edge $(v_{1},v_{2})\in E$ is an _outgoing_ edge of
$v_{1}$ and an _incoming_ edge of $v_{2}$. A _tree_ $\mathcal{T}=(T,F)$ is a
directed graph with one distinguished vertex $t_{r}\in T$ called the _root_
such that for every $t\in T$ there is exactly one path from $t_{r}$ to $t$. We
call the vertices of a tree _nodes_ and a node with no outgoing edges is
called a _leaf_. For an edge $(v_{1},v_{2})\in E$, we call $v_{1}$ the parent
and $v_{2}$ the child.

An _alphabet_ $\Sigma$ is a non-empty set of symbols. A _$\Sigma$ -labeled
ordered binary tree_ $\mathcal{T}$ is a relational structure with universe $T$
and vocabulary $\tau_{\Sigma}^{b}$ consisting of two binary relation symbols
$E_{1},E_{2}$ (first child and second child) and unary relation symbols
$P_{a}$ for every $a\in\Sigma$. We further assume that there is a labeling
function $\sigma:T\rightarrow\Sigma$ that associates each tree node with
exactly one symbol from $\Sigma$. A (bottom-up) nondeterministic finite tree
automaton (NTA) is a tuple $\mathfrak{A}=(Q,\Sigma,\Delta,q_{0},Q_{F})$ where
$Q$ is a set of states, $\Sigma$ is the alphabet, $q_{0}\in Q$ is a special
state that is used as a placeholder for transitions where a node has less than
two children, and $Q_{F}\subseteq Q$ is the set of accepting states. The
transition relation is a set $\Delta\subseteq Q\times Q\times\Sigma\times Q$.
A run of $\mathfrak{A}$ on a $\Sigma$-labeled ordered binary tree
$\mathcal{T}$ is a mapping $\rho:T\rightarrow Q$ such that for a leaf $u$ it
holds that $(q_{0},q_{0},\sigma(u),\rho(u))\in\Delta$, and for $u$ with two
children $u_{1}$ and $u_{2}$ we have that
$(\rho(u_{1}),\rho(u_{2}),\delta(u),\rho(u))\in\Delta$. A run $\rho$ is
accepting if the root $t_{r}$ of a tree is associated with $\rho(r)\in Q_{F}$.
Further, a tree $\mathcal{T}$ is accepted if it has an accepting run. The
language of an NTA $\mathfrak{A}$ is the set of all trees that are accepted by
$\mathfrak{A}$.

A classic result by Büchi, Elgot and Trakhtenbrot [16, 22, 55], showing
equivalent expressive power of finite automata and MSO-formulas on strings,
was extended to trees by Doner and Thatcher and Wright [21, 53]. We make use
of their result showing that for every MSO formula $\varphi$, there is an NTA
that accepts a tree $\mathcal{T}$ if and only if $\mathcal{T}\models\varphi$.
To evaluate a formula with $\ell$ free set variables on a tree, a parameter
assignment $V_{1},...,V_{\ell}$ needs to be given. We use notations as in [54,
27] where the alphabet $\Sigma$ of the tree is extended to
$\Sigma\times\\{0,1\\}^{\ell}$ such that each node $t_{i}$ in the tree is
assigned a vector $(v_{1},...,v_{\ell})\in\\{0,1\\}^{\ell}$ where $v_{i}=1$ if
and only if $t_{i}\in V_{i}$.

#### Tree-width

For a graph $\mathcal{G}=(V,E)$, a tree decomposition [45, 5] is a pair
$\mathcal{D}=(\mathcal{T},(B_{t})_{t\in T})$ consisting of a tree
$\mathcal{T}=(T,F)$ and $(B_{t})_{t\in T}$, which is a family of subsets of
$V$. $B_{t}$ is called the bag of node $t$. We define $B^{-1}(v)=\\{t\in T\mid
v\in B_{t}\\}$ as the function assigning a set of nodes to each vertex $v\in
V$. $\mathcal{D}$ is a tree decomposition of $\mathcal{G}=(V,E)$ if the
following two properties hold.

  1. (1)

For every $v\in V$, the set $B^{-1}(v)$ is non-empty, and the induced subgraph
is connected.

  2. (2)

For each edge $(u,v)\in E$, there is a node $t\in T$ with $u,v\in B_{t}$.

The width of a tree decomposition $\mathcal{D}=(\mathcal{T},(B_{t})_{t\in T})$
is $\max\\{|B_{t}|\leavevmode\nobreak\ |\leavevmode\nobreak\ t\in T\\}-1$. The
tree width $\textsf{tw}(\mathcal{G})$ of a graph $\mathcal{G}$ is the minimum
width of any tree decompositions of $\mathcal{G}$. The _Gaifman graph_ of a
$\tau$-structure $\mathcal{A}$ is the graph
$\mathcal{G}(\mathcal{A})\coloneqq(V,E)$, where $V\coloneqq A$ and
$E\coloneqq\bigl{\\{}\\{a,b\\}\mathrel{\big{|}}\text{there is $R\in\tau$ such
that $a$ and $b$ appear together in $R^{\mathcal{A}}$}\bigr{\\}}$. For a
relational structure $\mathcal{A}$, we define $\textsf{tw}(\mathcal{A})$ =
$\textsf{tw}\bigl{(}\mathcal{G}(\mathcal{A})\bigr{)}$. We work on ordered tree
decomposition where the bag is a tuple, instead of a set. The nodes in the set
can be ordered arbitrarily and if there are less than $k+1$ vertices in a bag,
we fill the tuple by repeating nodes. This allows us to access the node at a
specific position in the tuple. With $b_{i}^{t}$ we denote the vertex at
position $i$ in the tuple of tree node $t$. We define the function
$\bar{U}(v)\coloneqq(U_{1}(v),...,U_{k+1}(v))$ where $U_{i}(v)\coloneqq\\{t\in
T\mid b_{i}^{t}\ =v\\}$.

Computing the tree width of a graph is NP-complete, but for a graph of a given
tree-width $k$, Lemma 2.1 states that we can compute a decomposition
efficiently. The original algorithm is due to [10], and there are also newer
results with lower bounds or approximations [11, 38].

######  Lemma 2.1 (Bodlaender’s Theorem [10]).

For a graph $\mathcal{G}$ of size $n$ and of tree-width
$\textsf{tw}(\mathcal{G})\leq k$, there is an algorithm that computes a tree
decomposition of width $k$ in time $2^{\mathcal{O}(k^{3})}\cdot n$.

#### Clique-width

Similar to tree-width, we can also measure the structural complexity of a
graph in terms of clique-width. Graph classes of bounded clique-width may also
include dense graphs. We define labeled graphs, called _$p$ -graphs_
$\mathcal{G}=(V,E,L_{1},...,L_{p})$ where $V$ is the set of vertices, $E$ is
the binary edge relation, and $L_{1},...,L_{p}$ are sets of vertices
$L_{i}\subseteq V$ also called _labels_. Every vertex has exactly one label.
The clique-width of an unlabeled graph $\mathcal{G}=(V,E)$ is the clique-width
of the $1$-graph $\mathcal{G}^{\prime}=(V,E,L_{1})$ where all nodes have the
label $L_{1}$.

The _clique-width_ of a $p$-graph $\mathcal{G}$ is the minimum number of
labels that are used to build $\mathcal{G}$ using only the following 4
operations:

  * •

i(v): create a graph $\mathcal{G}=(\\{v\\},\emptyset,L_{i})$ consisting only
of the node $v$ labeled with $i$

  * •

$\mathcal{G}\oplus\mathcal{H}$: disjoint union of two graphs $\mathcal{G}$ and
$\mathcal{H}$

  * •

$\eta(i,j)$: add an edge between every two vertices, where one vertex is
labeled $i$ and the other is labeled $j$

  * •

$\rho(i,j)$: change the label of all vertices that are labeled $i$ to label
$j$

A combination of these operations that uses $k$ labels and results in a
$p$-graph $\mathcal{G}$ is called a _$k$ -expression_ of said graph. We will
think of these $k$-expressions as trees and refer to a $k$-expression of
$\mathcal{G}$ by $\mathcal{T}^{k}_{\mathcal{G}}$ where every node of this tree
is labeled with one of the operations defined above.

######  Lemma 2.2 ([44]).

For a graph $\mathcal{G}$ with $n$ vertices and clique-width $k^{\prime}$,
there is an algorithm that outputs a $k$-expression for $\mathcal{G}$ where
${k=2^{3k^{\prime}+2}-1}$. The algorithm has a running time of
$\mathcal{O}(n^{9}\log n)$.

#### Parameterized Complexity

A _parameterization_ $\kappa$ is a function mapping the input $x$ of a problem
to a natural number $\kappa(x)\in\mathbb{N}$. An algorithm $\mathbb{A}$ is an
_fpt algorithm with respect to $\kappa$_ if there is a computable function
$f\colon\mathbb{N}\rightarrow\mathbb{N}$ and a polynomial $p$ such that for
every input $x$ the running time of $\mathbb{A}$ is at most $f(\kappa(x))\cdot
p(|x|)$.

A _parameterized problem_ is a tuple $(Q,\kappa)$. We say
$(Q,\kappa)\in\textup{{FPT}}$ or $(Q,\kappa)$ is _fixed-parameter tractable_
if there is an fpt algorithm with respect to $\kappa$ for $Q$. We say
$(Q,\kappa)\in\text{para-NP}$ if there is a nondeterministic fpt algorithm
with respect to $\kappa$ for $Q$. If the parameterization is clear from the
context, then we omit it.

For two parameterized problems $(Q,\kappa),(Q^{\prime},\kappa^{\prime})$, an
_fpt Turing reduction_ from $(Q,\kappa)$ to $(Q^{\prime},\kappa^{\prime})$ is
an algorithm $\mathbb{A}$ with oracle access to $Q^{\prime}$ such that
$\mathbb{A}$ decides $Q$, $\mathbb{A}$ is an fpt algorithm with respect to
$\kappa$, and there is a computable function $g\colon\mathbb{N}\to\mathbb{N}$
such that on input $x$, $\kappa^{\prime}(x^{\prime})\leq
g\bigl{(}(\kappa(x)\bigr{)}$ for all oracle queries with oracle input
$x^{\prime}$.

For additional background on parameterized complexity, we refer to [24].

##  3 MSO Learning on Structures of Bounded Tree-width

We start by formalizing the parameterized version of the problem MSO-
Consistent-Learn described in the introduction. The remainder of the section
is dedicated to the proof of Theorem 1.2, showing that the $1$-dimensional
version of the problem is fixed-parameter tractable when additionally
parameterized by the tree-width of the input structure. The problem is defined
as follows.

MSO-Consistent-Learn
Input: relational $\tau$-structure $\mathcal{A}$ with universe $A$, numbers
$d,q,\ell\in\mathbb{N}$, training sequence $S\in(A^{d}\times\\{+,-\\})^{m}$
Parameter: $\kappa:=|\tau|+d+q+\ell$ Problem: Return a hypothesis
$h_{\varphi,\bar{w}}$ consisting of  • an MSO formula
$\varphi\in\textup{{MSO}}[\tau,q,d+\ell,0]$ and • a parameter assignment
$\bar{w}\in A^{\ell}$ such that $h_{\varphi,\bar{w}}$ is consistent with the
training sequence, if such a hypothesis exists. Reject if there is no
consistent hypothesis.

The values of $|\tau|,d,q$, and $\ell$ can be expected to be small and are
therefore used for the parameterization. Note that for Theorems 1.2 and 1.3,
we also add the tree-width or clique-width of the input structure to the
parameterization. The problem 1D-MSO-Consistent-Learn refers to MSO-
Consistent-Learn with dimension $d=1$.

Recall that, for an MSO-formula $\varphi(\bar{x};\bar{y})$ and a parameter
assignment $\bar{w}\in A^{\ell}$, the hypothesis $h_{\varphi,\bar{w}}$ is
defined by $h_{\varphi,\bar{w}}(\bar{v})=+$ if
$\mathcal{A}\models\varphi(\bar{v};\bar{w})$ and
$h_{\varphi,\bar{w}}(\bar{v})=-$ otherwise. A hypothesis $h_{\varphi,\bar{w}}$
is called _consistent_ with a training sequence $S$ if
$h_{\varphi,\bar{w}}(\bar{v})=\sigma$ for all $(\bar{v},\sigma)\in S$. The
class of all possible hypotheses for MSO-Consistent-Learn on input
$\mathcal{A}$ and numbers $d,q,\ell$ is denoted by
$\mathcal{H}_{d,q,\ell}(\mathcal{A})=\bigl{\\{}h_{\varphi,\bar{w}}\mathrel{\big{|}}\varphi\in\textup{{MSO}}[\tau,q,d+\ell,0],\bar{w}\in
A^{\ell}\bigr{\\}}$.

Note that the number of (non-equivalent) formulas in
$\textup{{MSO}}[\tau,q,d+\ell,0]$ only depends on $\tau$, $q$, $d$, and
$\ell$, which are parameters of MSO-Consistent-Learn. Hence, to solve MSO-
Consistent-Learn with an fpt algorithm, it suffices to provide an fpt
algorithm that, for a given formula $\varphi$, computes a parameter assignment
$\bar{w}$ such that $h_{\varphi,\bar{w}}$ is consistent with the given
training sequence if such an assignment exists, and rejects otherwise. With
such an algorithm, we can simply iterate over all possible formulas $\varphi$,
use the algorithm to find a correct parameter assignment $\bar{w}$, and return
$h_{\varphi,\bar{w}}$ once we found one. Hence, in the remainder of this
section and also in Section 4, we assume that we are already given a formula
$\varphi$, and we will describe fpt algorithms to find the right parameter
assignment.

To provide this algorithm for $d=1$ and structures of bounded tree-width and
thereby prove Theorem 1.2, we proceed as follows. In Section 3.1, we describe
how to encode the input structure and the training sequence into a labeled
tree. Here, we make use of the fact that the training examples are only single
vertices and not tuples of vertices. Then, in Section 3.2, we describe a
procedure to find a consistent parameter setting based on the tree automaton
corresponding to the given formula $\varphi$.

###  3.1 Preprocessing the Input Structure

To find a parameter setting for the given formula $\varphi$ with $\ell$ free
parameter variables, we first process the input structure by encoding the
training sequence into the structure and then transforming it into a tree.

######  Lemma 3.1.

Given a relational $\tau$-structure $\mathcal{A}$ with universe $A$, an MSO-
formula $\varphi$ of quantifier rank $q_{\varphi}$, and a training sequence
$S\in\bigl{(}A\times\\{+,-\\}\bigr{)}^{m}$, there is

  * •

a vocabulary $\tau^{\prime}$ of size $|\tau|+2$,

  * •

a relational $\tau^{\prime}$-structure $\mathcal{A}_{S}$ of the same tree-
width as $\mathcal{A}$, and

  * •

an MSO-formula $\varphi^{\prime}$ of quantifier rank $q_{\varphi}+1$,

such that for all $\bar{w}\in A^{\ell}$, we have
$\mathcal{A}_{S}\models\varphi^{\prime}(\bar{w})$ if and only if
$h_{\varphi,\bar{w}}$ is consistent with $S$ on $\mathcal{A}$.

######  Proof 3.2.

Let $\tau^{\prime}\coloneqq\tau\uplus\\{P,N\\}$ for two new unary relation
symbols $P,N$. Furthermore, let $\mathcal{A}_{S}$ be the
$\tau^{\prime}$-structure with universe $A$,
$R^{\mathcal{A}_{S}}:=R^{\mathcal{A}}$ for all $R\in\tau$,
$P^{\mathcal{A}_{S}}=\\{v\in A\mid(v,+)\in S\\}$, and
$N^{\mathcal{A}_{S}}=\\{v\in A\mid(v,-)\in S\\}$. Note that
$\textsf{tw}(\mathcal{A}_{S})=\textsf{tw}(\mathcal{A})$ as we only add unary
relations and therefore add no new edges in the Gaifman graph of
$\mathcal{A}_{S}$. Based on the
$\textup{{MSO}}[\tau,q_{\varphi},\ell+1,0]$-formula $\varphi(x;\bar{y})$, we
define the $\textup{{MSO}}[\tau,q_{\varphi}+1,\ell,0]$-formula
$\varphi^{\prime}(\bar{y})$ as

$\varphi^{\prime}(y_{1},\dots,y_{\ell})\coloneqq\forall
x\Bigl{(}\bigl{(}P(x)\rightarrow\varphi(x,y_{1},\dots,y_{\ell})\bigr{)}\land\bigl{(}N(x)\rightarrow\neg\varphi(x,y_{1},\dots,y_{\ell})\bigr{)}\Bigr{)}.$

Then, we have $\mathcal{A}_{S}\models\varphi^{\prime}(\bar{w})$ if and only if
$h_{\varphi,\bar{w}}$ is consistent with the training sequence.

In the following, we translate the relational structure into a tree that can
be processed using a tree automaton. First, we compute a tree decomposition
$\mathcal{D}$ of width $\textsf{tw}(\mathcal{A}_{S})$ of $\mathcal{A}_{S}$.
Then, the following lemma enables us to compute a labeled ordered unranked
tree $\mathcal{T}_{u}$ and an MSO-formula $\varphi_{u}$ such that we can
translate satisfying assignments of $\varphi^{\prime}$ on $\mathcal{A}_{S}$ to
satisfying assignments for $\varphi_{u}$ on $\mathcal{T}_{u}$ and vice versa.
The result goes back to the work of Courcelle and Seese in the late 1980s [20,
46]. In this exact form, the result can be found in [24, Lemma 11.39 and Lemma
11.42].

######  Lemma 3.3.

Let $\mathcal{A}_{S}$ be a $\tau^{\prime}$-structure and let
$\mathcal{D}=\bigl{(}(T,F),(B_{t})_{t\in T}\bigr{)}$ be a tree decomposition
of $\mathcal{A}_{S}$ of width $k\coloneqq\textsf{tw}(\mathcal{A}_{S})$. Then,
we can compute a labeling function $\sigma\colon T\to\Sigma$ for an alphabet
$\Sigma$ such that the following holds for the labeled ordered unranked tree
$\mathcal{T}_{u}\coloneqq(T,F,\sigma)$. For every
$\textup{{MSO}}[\tau^{\prime}]$-formula
$\varphi^{\prime}(y_{1},\dots,y_{\ell})$, we can compute an
$\textup{{MSO}}[\tau_{\Sigma}^{u}]$-formula
$\varphi_{u}(Y_{1,1},\dots,Y_{k+1,\ell})$ for a vocabulary $\tau_{\Sigma}^{u}$
such that, for all $v_{1},\dots,v_{\ell}\in\mathcal{A}_{S}$, we have

$\mathcal{A}_{S}\models\varphi^{\prime}(a_{1},\dots,a_{\ell})\iff\mathcal{T}_{u}\models\varphi_{u}\bigl{(}\bar{U}(v_{1}),\dots,\bar{U}(v_{\ell})\bigr{)}.$

Computing $\mathcal{T}_{u}$ and $\varphi_{u}$ can be done in time
$f(k+|\varphi^{\prime}|)\cdot|\mathcal{A}_{S}|$ for a computable function $f$.
Moreover, $\Sigma$, $\tau_{\Sigma}^{u}$, and
$\left\lvert\varphi_{u}\right\rvert$ only depend on
$\left\lvert\varphi^{\prime}\right\rvert$,
$\left\lvert\tau^{\prime}\right\rvert$, $k$, and $\ell$.

Note that the length $|\varphi^{\prime}|$ can be bounded by some function in
$\left\lvert\tau\right\rvert$, $q$, $\ell$, and $d$. Applying Lemma 3.3
results in a formula $\varphi_{u}$ that has $\ell^{\prime}:=\ell\cdot(k+1)$
($k$ being the tree-width) free set variables. In the construction of
$\varphi_{u}$, we guarantee that any satisfying assignment
$\bar{w}\in(2^{T})^{\ell}$ of $\varphi_{u}$ may be translated into an
analogous satisfying assignment of $\varphi^{\prime}$.

It is convenient for us to define tree automata on binary trees, so we convert
the unranked tree $\mathcal{T}_{u}$ into a binary tree $\mathcal{T}_{b}$ and
choose any node as the root $t_{r}$. We can apply a standard construction,
where we build a binary tree on which we read the left child as the first
child of the parent node and the right child of a node as the next sibling of
that node.

######  Lemma 3.4.

For every $\textup{{MSO}}[\tau_{\Sigma}^{u}]$-formula $\varphi_{u}$, there is
a vocabulary $\tau_{\Sigma}^{b}$ and an
$\textup{{MSO}}[\tau_{\Sigma}^{b}]$-formula $\varphi_{b}$ such that the
following holds. For every $\Sigma$-labeled ordered unranked tree
$\mathcal{T}_{u}$, there is a $\Sigma$-labeled ordered binary tree
$\mathcal{T}_{b}$ such that for all $\bar{V}_{i}\in(2^{T_{u}})^{(k+1)}$, it
holds that

$\mathcal{T}_{u}\models\varphi_{u}((\bar{V}_{1},\dots,\bar{V}_{\ell}))\iff\mathcal{T}_{b}\models\varphi_{b}((\bar{V}_{1},\dots,\bar{V}_{\ell})).$

An overview of the steps that were performed on the structure and the formula
can be found in Table 1. The resulting structure is a labeled ordered binary
tree $\mathcal{T}_{b}$ and an MSO-formula $\varphi_{b}$, which will now be
used to compute a consistent parameter setting.

Structure | Formula | Vocabulary | Lemma | Explanation
---|---|---|---|---
$\mathcal{A}$, $S$ | $\varphi(x,\bar{y})$ | $\tau$ |  | Input
$\mathcal{A}_{S}$ | $\varphi^{\prime}(\bar{y})$ | $\tau\cup\\{P,N\\}$ | 3.1 | Examples coded into structure
$\mathcal{T}_{u}$ | $\varphi_{u}(Y_{1,1},...,Y_{k+1,\ell})$ | $\tau_{\Lambda}^{u}$ | 3.3 | Transformation into tree
$\mathcal{T}_{b}$ | $\varphi_{b}(Y_{1,1},...,Y_{k+1,\ell})$ | $\tau_{\Lambda}^{b}$ | 3.4 | Binary tree construction
Table 1: Structure overview

###  3.2 Computing the Parameters

Recall that every satisfying assignment to the free variables of $\varphi_{b}$
corresponds to a satisfying parameter assignment $\bar{w}$ for the original
formula $\varphi$ (and vice versa). For the MSO-formula $\varphi_{b}$ with
$\ell^{\prime}$ free set variables, as described in Section 2, we can build a
finite non-deterministic tree automaton (NTA)
$\mathfrak{A}=(Q,\Sigma,q_{0},\Delta,Q_{F})$ that accepts the same trees as
$\varphi_{b}$. When evaluating an NTA that corresponds to a formula with free
set variables, we assume that the assignment to the free variables is encoded
in an extension of the alphabet of the tree. Using $\mathfrak{A}$, we can
evaluate trees over the alphabet
$\Sigma^{\prime}=\Sigma\times\\{0,1\\}^{\ell^{\prime}}$ where $\Sigma$ is the
alphabet of the tree and $\\{0,1\\}^{\ell^{\prime}}$ encodes the variable
assignment. Note that such an automaton has a number of states $|Q|$ that is
bounded in terms of $\left\lvert\varphi_{b}\right\rvert$ and therefore bounded
by some function $f(|\tau|,q,\ell)$.

We now start from a tree without a parameter assignment and construct a tree
with a parameter assignment that is accepted by $\mathfrak{A}$. Let
$\sigma\colon T\to\Sigma$ assign a symbol to any node in the tree. We define
the _extension_ of a symbol $s\in\Sigma$ as the set of symbols
$e(s)=\\{s\\}\times\\{0,1\\}^{\ell^{\prime}}$ that can result from adding any
parameter setting to $s$. We now execute multiple tree automata runs with
different parameter settings in parallel. Instead of assigning a state
$\rho:T\rightarrow Q$ to each node, we assign a set of states
$\pi:T\rightarrow 2^{Q}$ to each tree node. For $t\in T$, we can view $\pi(t)$
as the set of all states that are reachable with any parameter settings for
the subtree of $t$.

$\pi(t_{l})=\bigl{\\{}q\mathrel{\big{|}}(q_{0},q_{0},s^{\prime},q)\in\Delta,\leavevmode\nobreak\
s^{\prime}\in e(\sigma(t_{l}))\bigr{\\}}.$

For every inner node $t_{i}$ with two children $t_{1}$ and $t_{2}$ (that have
already been evaluated), we assign

$\pi(t_{i})=\bigl{\\{}q\mathrel{\big{|}}(q_{1},q_{2},s^{\prime},q)\in\Delta,\leavevmode\nobreak\
s^{\prime}\in e(\sigma(t_{i})),\ q_{1}\in\pi(t_{1}),\
q_{2}\in\pi(t_{2})\bigr{\\}}.$

The state of a parent node is derived from all possible combinations of states
of the two children nodes. Lastly, we evaluate the root $t_{r}$. If we
associate an accepting state $q\in Q_{F}$ with the root, i. e.
$q\in\pi(t_{r})$, then there is an accepting parameter setting for
$\varphi_{b}$, which we construct below. Otherwise, we reject the given
formula $\varphi$.

Now for $\mathcal{T}_{b}=(T,E_{1}.E_{2},\sigma)$, let us construct a labeling
with encoded parameters $\sigma_{F}\colon
T\to\Sigma\times\\{0,1\\}^{\ell^{\prime}}$ such that
$(T,E_{1},E_{2},\sigma_{F})$ has an accepting run $\rho_{F}:T\rightarrow Q$.
We choose a single accepting state $q_{F}\in\pi(t_{r})$ at the root and assign
$\rho_{F}(t_{r})=q_{F}$. Now continue recursively as follows: For a tree node
$t$ with a symbol $\sigma(t)=s$ and an assigned state $\rho_{F}(t)=q$, choose
a transition $(q_{1},q_{2},s^{\prime},q)\in\Delta$ such that $s^{\prime}\in
e(s)$. Assign $\sigma_{F}(t):=s^{\prime}$ and for the children $t_{1}$ and
$t_{2}$ of $t$ let $\rho_{F}(t_{1})=q_{1}$ and $\rho_{F}(t_{2})=q_{2}$.
Continue on $t_{1}$ and $t_{2}$.

The run $\rho_{F}$ is an accepting run of $\mathfrak{A}$ on $\mathcal{T}_{b}$
with the new labeling $\sigma_{F}$ which is the original labeling extended by
parameter assignments. The labeling function $\sigma_{F}$ of the binary tree
now holds an encoded parameter setting that can be translated into sets
$W_{1,1},...,W_{\ell,(k+1)}$, giving an accepting parameter assignment for
$\varphi_{b}$. In the final step, we revert the set variables on the tree
decomposition back into a parameter setting $\bar{w}\in V^{\ell}$ (through
$\bar{U}^{-1}$) for the original structure $\mathcal{A}$ and return the
consistent hypothesis $h_{\varphi,\bar{w}}$. All in all, the described
procedure is an fpt algorithm to find a consistent parameter setting for a
given formula. As argued in the beginning of this section, this proves Theorem
1.2.

##  4 MSO Learning on Graphs of Bounded Clique-width

This section proves tractability of 1D-MSO-Consistent-Learn on graphs when the
clique-width of the graph is added to the parameterization (Theorem 1.3). As
argued in Section 3, we may assume that a formula $\varphi$ for the hypothesis
is already given. In the remainder of this section, we describe an fpt
algorithm to find a consistent parameter setting for this formula, if one
exists.

###  4.1 Preprocessing the Input Graph

For an input graph $\mathcal{G}$ of clique-width $k^{\prime}$, we construct a
$k$-expression corresponding to the input graph $\mathcal{G}$ using Lemma 2.2,
where $k\coloneqq f(k^{\prime})$. This $k$-expression can be viewed as a tree
of operations referred to by $\mathcal{T}_{\mathcal{G}}^{k}$. From now on, we
view the graph $\mathcal{G}$ as the $k$-labeled graph generated by the
$k$-expression. Next, we encode the given training sequence into $\mathcal{G}$
and update the $k$-expression accordingly. We create $3k$ new labels
$L_{(i,c)}$ with $i\in[k]$ and $c\in\\{+,-,?\\}$. In the new graph
$\mathcal{G}_{S}$, let $v\in L_{(i,+)}$ if and only if $v\in L_{i}$ and
$(v,+)\in S$. We assign labels analogously for negative examples, and we
assign $L_{(i,?)}$ to $v$ if $v\in L_{i}$ and $v$ does not appear in the
training sequence. We also adapt the expression to these new labels, creating
a $k_{S}$-expression where $k_{S}\leq 9k$. The disjoint union operations stay
the same. Initializing a node now depends on the training sequence. For a node
$v$, the second part $c\in\\{+,-,?\\}$ of its label $L_{(i,c)}$ stays the same
through every rename operation. Therefore, the rename operation
$\rho_{i,j}(\mathcal{G})$ is replaced by three nested operations
$\rho_{(i,+),(j,+)}(\rho_{(i,-),(j,-)}(\rho_{(i,?),(j,?)}(\mathcal{G})))$. For
the connection operation $\eta_{i,j}$, we need to connect every vertex of
label $i$ with every vertex of label $j$. This results in a total of nine
operations, as we perform $\eta_{(i,c_{1}),(j,c_{2})}$ once for each
$c_{1},c_{2}\in\\{+,-,?\\}$. The given formula $\varphi(x;\bar{y})$ is
translated, analogously to Lemma 3.1, to the $\textup{{MSO}}[\tau]$-formula

$\varphi_{2}(\bar{y})=\forall
x\biggl{(}\Bigl{(}\bigvee_{i\in[k]}L_{(i,+)}(x)\Bigr{)}\rightarrow\varphi(x;\bar{y})\land\Bigl{(}\bigvee_{i\in[k]}L_{(i,-)}(x)\Bigr{)}\rightarrow\neg\varphi(x;\bar{y})\biggr{)}$

with vocabulary $\tau\coloneqq\\{E,L_{1},\dots,L_{k}\\}$. The length of
$\varphi_{2}$ is in $\mathcal{O}(k+|\varphi|)$. Further, we construct a
formula $\varphi_{3}$ corresponding to $\varphi_{2}$, but with free set
variables instead of free element variables. This allows us to directly use
the results from [19].

######  Lemma 4.1.

For a $k$-labeled graph $\mathcal{G}_{S}=(V,E,L_{1},\dots,L_{k})$ and a
formula $\varphi_{2}(y_{1},\dots,y_{\ell})\in$
$\textup{{MSO}}[\tau,q,\ell,0]$, there is a formula
$\varphi_{3}\in\textup{{MSO}}[\tau,q^{\prime},0,\ell]$ with quantifier rank
$q^{\prime}=q+\ell+2$ and $\ell$ free set variables (and no free element
variables), such that for all $v_{1},\dots,v_{\ell}\in V$, we have that

$\mathcal{G}_{S}\models\varphi_{2}(v_{1},\dots,v_{\ell})\iff\mathcal{G}_{S}\models\varphi_{3}(\\{v_{1}\\},\dots,\\{v_{\ell}\\}).$

and, for all $V_{1},\dots,V_{\ell}\subseteq V$,
$\mathcal{G}_{S}\not\models\varphi_{3}(V_{1},\dots,V_{\ell})$ if $\left\lvert
V_{i}\right\rvert\neq 1$ for some $i\in[\ell]$

######  Proof 4.2.

Let

$Sing(Y_{i},y_{i})=Y_{i}(y_{i})\land\forall x\forall
y\Bigl{(}\bigl{(}Y_{i}(x)\land Y_{i}(y)\bigr{)}\rightarrow x=y\Bigr{)}$

be the formula that enforces that the set variable $Y_{i}$ has only one
element, which is $y_{i}$. Now we can bind all free element variables and
replace them by free set variables as follows.

$\varphi_{3}(Y_{1},\dots,Y_{\ell})\coloneqq\exists y_{1}\dots\exists
y_{\ell}\bigwedge_{i\in[\ell]}Sing(Y_{i},y_{i})\land\varphi_{2}(y_{1},\dots,y_{\ell})$

This formula satisfies the requirements stated in the lemma.

###  4.2 Computing the Parameters

For every MSO-formula $\psi(X_{1},\dots,X_{\ell})$ and every $p$-labeled graph
$\mathcal{G}$, we define

$\textsf{sat}(\mathcal{G},\psi)\coloneqq\bigl{\\{}(V_{1},\dots,V_{\ell})\mathrel{\big{|}}\mathcal{G}\models\psi(V_{1},\dots,V_{\ell})\bigr{\\}}$

as the set of all parameter settings for which $\psi$ holds in $\mathcal{G}$.
Note that any
$(V_{1},...,V_{\ell})\in\textsf{sat}(\mathcal{G}_{S},\varphi_{3})$ yields a
consistent parameter setting for $\varphi$. Computing all possible parameter
settings is intractable, as the size of
$\textsf{sat}(\mathcal{G}_{S},\varphi_{3})$ might be up to $n^{\ell}$.
Instead, we follow the construction from [19] to compute a subset of
$\textsf{sat}(\mathcal{G},\varphi_{3})$ that is empty if and only if
$\textsf{sat}(\mathcal{G},\varphi_{3})$ is empty. We use the following two
results to recursively compute the subset.

######  Lemma 4.3 ([19]).

For every $p\in\mathbb{N}$, each operation
$f\in\bigl{\\{}\rho(i,j),\eta(i,j)\mathrel{\big{|}}i,j\in[p],i\neq
j\bigr{\\}}$ over $p$-labeled graphs, and for every formula
$\psi\in\textup{{MSO}}[\tau,q,0,\ell]$, there is an MSO-formula
$\psi^{\prime}\in\textup{{MSO}}[\tau,q,0,\ell]$ of the same quantifier rank
such that for all $p$-labeled graphs $\mathcal{G}$

$\textsf{sat}(f(\mathcal{G}),\psi)=\textsf{sat}(\mathcal{G},\psi^{\prime}).$

######  Lemma 4.4 ([19], Feferman-Vaught for MSO, see also [32]).

For each $p\in\mathbb{N}$ and for every
$\textup{{MSO}}[\tau,q,0,\ell]$-formula $\psi$, two lists of
$\textup{{MSO}}[\tau,q,0,\ell]$-formulas $\theta_{1},\dots,\theta_{m}$ and
$\chi_{1},\dots,\chi_{m}$ can be constructed such that all formulas have the
same free variables as $\psi$ and have quantifier rank no larger than the
quantifier rank of $\psi$, and for every two $p$-graphs $\mathcal{G}$ and
$\mathcal{H}$ presented over $\tau$, such that $\mathcal{G}$ and $\mathcal{H}$
are disjoint,

$\textsf{sat}(\mathcal{G}\oplus\mathcal{H},\psi)=\bigcup_{i=1}^{m}\textsf{sat}(\mathcal{G},\theta_{i})\boxtimes\textsf{sat}(\mathcal{H},\chi_{i}),$

where $A\boxtimes B\coloneqq\bigl{\\{}(A_{1}\cup B_{1},\dots,A_{n}\cup
B_{n})\mathrel{\big{|}}(A_{1},\dots,A_{n})\in A,(B_{1},\dots,B_{n})\in
B\bigr{\\}}$.

We start with assigning the formula $\varphi_{3}$ to the root of the tree
$\mathcal{T}_{\mathcal{G}_{S}}^{k_{S}}$, which represents the
$k_{S}$-expression of $\mathcal{G}_{S}$. From there, we assign formulas to
each inner node of the tree. If a node represents an operation $\rho(i,j)$ or
$\eta(i,j)$, then we apply Lemma 4.3 to every formula assigned to the node and
assign these to the child node. If the node represents an operation
$\bigoplus$, then we apply Lemma 4.4 to every formula assigned to the node and
assign the formulas $\theta_{1},\dots,\theta_{m}$ to the first child and
$\chi_{1},\dots,\chi_{m}$ to the second child. Note that the quantifier rank,
the number of free variables, and the vocabulary stay the same in each step.
As the number of formulas in $\textup{{MSO}}[\tau,q^{\prime},0,\ell]$ can be
bounded, we can limit the number of formulas assigned to each node to a
constant (depending on $\tau$, $q^{\prime}$, and $\ell$).

After this step, we have a list of formulas $\Psi$ assigned to each node of
$\mathcal{T}_{\mathcal{G}_{S}}^{k_{S}}$ corresponding to the
$k_{S}$-expression. Starting at the leafs, which correspond to graphs
$\mathcal{G}_{v}$ that only have a single node $v$, we compute the sets of
consistent parameter settings $\textsf{sat}(\mathcal{G}_{v},\psi)$ for each
formula $\psi\in\Psi$. On a graph with a single node,
$\textsf{sat}(\mathcal{G}_{v},\psi)$ can be computed by a simple brute force
algorithm in $\mathcal{O}\bigl{(}2^{\ell}\cdot
2^{q}\cdot\left\lvert\varphi\right\rvert\bigr{)}$. We then construct a
parameter setting bottom up from the leafs, following Lemmas 4.3 and 4.4.

######  Lemma 4.5.

With the above-described procedure, we find a consistent parameter setting
$\bar{V}\in\textsf{sat}(\mathcal{G}_{S},\varphi_{3})$ if and only if we find a
consistent parameter setting in an analogous procedure where, in each node
$\mathcal{G}^{\prime}$ of $\mathcal{T}_{\mathcal{G}_{S}}^{k}$, we only keep
one parameter setting
$\bar{V}^{\prime}\in\textsf{sat}(\mathcal{G}^{\prime},\varphi^{\prime})$ for
every formula $\varphi^{\prime}$ assigned to $\mathcal{G}^{\prime}$.

######  Proof 4.6.

We show that if we can find a parameter setting in the root using all possible
parameter settings, we can also find a parameter setting in the root using
only a single representative setting per node and formula. Unary operations
$\rho(i,j)$ and $\eta(i,j)$ do not change the number of parameter settings in
a node, and the initialization operation is executed only on leafs. Now
consider the case of $\mathcal{G}\oplus\mathcal{H}$ with formula $\psi$ and
with corresponding formulas $\theta_{1},\dots,\theta_{m}$ and
$\chi_{1},\dots,\chi_{m}$ in the children. Let $\bar{g}_{1},\dots,\bar{g}_{m}$
be the single representative parameter setting saved per node, with
$\bar{g}_{i}\in\textsf{sat}(\mathcal{G},\theta_{i})$, or
$\bar{g}_{i}=\emptyset$ if and only if
$\textsf{sat}(\mathcal{G},\theta_{i})=\emptyset$. Define
$\bar{h}_{1},\dots,\bar{h}_{m}$ analogously for
$\textsf{sat}(\mathcal{H},\chi_{i})$.

In the above-described procedure, we find a consistent parameter setting if
and only if $\textsf{sat}(\mathcal{G}\oplus\mathcal{H},\psi)\neq\emptyset$. By
Lemma 4.4, this holds if and only if
$\textsf{sat}(\mathcal{G},\theta_{i})\boxtimes\textsf{sat}(\mathcal{H},\chi_{i})\neq\emptyset$,
or, equivalently, $\textsf{sat}(\mathcal{G},\theta_{i})\neq\emptyset$ and
$\textsf{sat}(\mathcal{H},\chi_{i})\neq\emptyset$, for some $i\in[m]$. This
holds if and only if $\bar{g}_{i}\neq\emptyset$ and $\bar{h}_{i}\neq\emptyset$
for some $i\in[m]$. These are precisely the cases in which we find a
consistent parameter setting if we only keep one parameter setting for every
formula in every node.

Now, we can reconstruct a parameter setting for the root, following Lemmas 4.3
and 4.4. Since there is only a constant number of formulas assigned to each
node, say $c$, and we only save at most one parameter setting per formula and
node, we compute at most $c$ settings for each node using Lemma 4.3, and at
most $c^{2}$ settings for each node using Lemma 4.4, which we can then again
reduce to $c$ settings. Hence, all in all, a consistent hypothesis can be
computed by an fpt algorithm with respect to
$\left\lvert\tau\right\rvert+q+\ell+k^{\prime}$, where $k^{\prime}$ is the
clique-width of the input graph. This proves Theorem 1.3.

##  5 PAC Learning in Higher Dimensions

So far, we considered the exact-learning setting, where the goal is to return
a hypothesis that is consistent with the given examples. In this section, we
study the MSO-learning problem in the agnostic PAC-learning setting. There,
for an instance space $\mathbb{X}$, we assume an (unknown) probability
distribution $\mathcal{D}$ on $\mathbb{X}\times\\{+,-\\}$. The learner’s goal
is to find a hypothesis $h\colon\mathbb{X}\to\\{+,-\\}$, using an oracle to
draw training examples randomly from $\mathcal{D}$, such that $h$
(approximately) minimizes the generalization error

$\operatorname{err}_{\mathcal{D}}(h)\coloneqq\Pr_{(x,\lambda)\sim\mathcal{D}}\bigl{(}h(x)\neq\lambda\bigr{)}.$

Formally, we define the MSO PAC-learning problem as follows.

MSO-PAC-Learn
Input: Relational $\tau$-structure $\mathcal{A}$ with universe $A$, numbers
$d,\ell,q\in\mathbb{N}$, $\delta,\varepsilon\in(0,1)$, oracle access to
probability distribution $\mathcal{D}$ on $A^{d}\times\\{+,-\\}$ Parameter:
$d+\ell+q+\left\lvert\tau\right\rvert+1/\delta+1/\varepsilon$ Problem: Return
a hypothesis $h_{\varphi,\bar{w}}\in\mathcal{H}_{d,\ell,q}(\mathcal{A})$ such
that, with probability of at least $1-\delta$ over the choice of examples
drawn i.i.d. from $\mathcal{D}$, it holds that
$\operatorname{err}_{\mathcal{D}}(h_{\varphi,\bar{w}})\leq\min_{h\in\mathcal{H}_{d,\ell,q}(\mathcal{A})}\operatorname{err}_{\mathcal{D}}(h)+\varepsilon.$

The remainder of this section is dedicated to the proof of Theorems 1.4 and
1.5, that is, we want to show that MSO-PAC-Learn is fixed-parameter tractable
when additionally parameterized by the tree-width of the input structure or by
the clique-width of the input graph. To solve the problem algorithmically, we
can follow the _Empirical Risk Minimization (ERM)_ rule [61, 47], that is, our
algorithm should minimize the _training error_ (or _empirical risk_)

$\operatorname{err}_{S}(h)\coloneqq\frac{1}{\left\lvert
S\right\rvert}\cdot\left\lvert\\{(\bar{v},\lambda)\in S\mid
h(\bar{v})\neq\lambda\\}\right\rvert$

on the training sequence $S$ of queried examples. Roughly speaking, an
algorithm can solve MSO-PAC-Learn by querying a sufficient number of examples
and then following the ERM rule. To bound the number of needed examples, we
can combine a fundamental result of statistical learning [9, 47], which bounds
the number of needed examples in terms of the so-called VC dimension of a
hypothesis class, with results due to Grohe and Turán [31], which bound the VC
dimension of MSO-definable hypothesis classes on structures of bounded tree-
width and on graphs of bounded clique-width.

######  Lemma 5.1 ([31]).

There is a computable function $b\colon\mathbb{N}^{5}\to\mathbb{N}$ such that
the following holds. Let $\tau$ be a signature, $k\geq 1$ and let
$\mathcal{C}$ be a class of $\tau$-structures of tree-width at most $k$ or a
class of graphs of clique-width at most $k$. Then, for every structure
$\mathcal{A}\in\mathcal{C}$, the VC dimension of the hypothesis class
$\mathcal{H}_{d,q,\ell}(\mathcal{A})=\bigl{\\{}h_{\varphi,\bar{w}}\mathrel{\big{|}}\varphi\in\textup{{MSO}}[\tau,q,d+\ell,0],\bar{w}\in
A^{\ell}\bigr{\\}}$ is at most $b(d,k,\ell,q,\left\lvert\tau\right\rvert)$.

######  Lemma 5.2 ([9, 47]).

A hypothesis class $\mathcal{H}$ is (agnostically) PAC-learnable if and only
if it has finite VC dimension. Furthermore, if $\mathcal{H}$ has finite VC
dimension, then $\mathcal{H}$ can be learned by any algorithm that follows the
Empirical Risk Minimization rule with sample complexity (i. e., the number of
queried examples needed to fulfil the bounds required for agnostic PAC
learnability)
$m_{\mathcal{H}}(\varepsilon,\delta)\in\mathcal{O}\left(\frac{\operatorname*{VC}(\mathcal{H})+\log(1/\delta)}{\varepsilon^{2}}\right)$.

As a direct consequence, we obtain the following result.

######  Lemma 5.3.

There is a computable function
$m\colon\mathbb{N}^{5}\times(0,1)^{2}\to\mathbb{N}$ such that any algorithm
that proceeds as follows solves MSO-PAC-Learn. Given a $\tau$-structure
$\mathcal{A}$ of tree-width at most $k$ or a graph $\mathcal{A}$ (with
$\tau=\\{E\\}$) of clique-width at most $k$, numbers $d,\ell,q\in\mathbb{N}$,
$\delta,\varepsilon\in(0,1)$, and oracle access to a probability distribution
$\mathcal{D}$ on $A^{d}\times\\{+,-\\}$, where $A$ is the universe of
$\mathcal{A}$, the algorithm queries at least
$m(d,k,\ell,q,\left\lvert\tau\right\rvert,\delta,\varepsilon)$ many examples
from $\mathcal{D}$ and then follows the ERM rule.

Using this lemma, we can now prove Theorem 1.4, showing that MSO-PAC-Learn is
fixed-parameter tractable when additionally parameterized by the tree-width of
the input structure, even for dimensions $d>1$.

######  Proof 5.4 (Proof of Theorem 1.4).

Let $\mathcal{A}$ be a $\tau$-structure with universe $A$, let
$d,\ell,q\in\mathbb{N}$, $\delta,\varepsilon\in(0,1)$, and assume we are given
oracle access to a probability distribution $\mathcal{D}$ on
$A^{d}\times\\{+,-\\}$.

First, using Lemma 2.1, we compute the tree-width $k$ of $\mathcal{A}$ by an
fpt-algorithm with parameter $k$. Let $s\coloneqq
m(d,k,\ell,q,\left\lvert\tau\right\rvert,\delta,\varepsilon)$, where $m$ is
the function from Lemma 5.3. We sample $s$ examples from $\mathcal{D}$ and
call the resulting sequence of training examples $S$. Then, for every
subsequence $S^{\prime}$ of $S$, we will make use of the techniques in Section
3 and compute a hypothesis $h_{S^{\prime}}\in\mathcal{H}_{d,\ell,q}$ that is
consistent with $S^{\prime}$ if such a hypothesis exists. Finally, from all
subsequences with a consistent hypothesis, we choose a subsequence $S^{*}$ of
maximum length and return $h_{S^{*}}$. Note that this procedure minimizes the
training error on the training sequence $S$, i. e.,
$\operatorname{err}_{S}(h_{S^{*}})=\min_{h\in\mathcal{H}_{d,\ell,q}}\operatorname{err}_{S}(h)$.
Hence, the procedure follows the ERM rule and by Lemma 5.3, it solves MSO-PAC-
Learn.

To apply the techniques from Section 3, we first need to encode the training
examples into the structure. For that, we extend the signature $\tau$ by
$d\cdot s$ new unary relation symbols $S_{i,j}$ for $i\in[s]$ and $j\in[d]$,
and we call the resulting signature $\tau^{\prime}$. Let
$S^{\prime}=\Bigl{(}\bigl{(}(v_{1,1},\dots,v_{1,d}),\lambda_{1}\bigr{)},\dots,\bigl{(}(v_{s^{\prime},1},\dots,v_{s^{\prime},d}),\lambda_{s^{\prime}}\bigr{)}\Bigr{)}$
be a subsequence of $S$ for which we want to find a consistent hypothesis.
Furthermore, let $\mathcal{A}_{S^{\prime}}$ be the $\tau^{\prime}$-structure
with universe $A$, $R^{\mathcal{A}_{S^{\prime}}}=R^{\mathcal{A}}$ for all
$R\in\tau$, $S_{i,j}=\\{v_{i,j}\\}$ for all $i\in[s^{\prime}]$ and $j\in[d]$,
and $S_{i,j}=\emptyset$ for all $i\in[s^{\prime}+1,s]$ and $j\in[d]$.

Then, for every formula
$\varphi(x_{1},\dots,x_{d},y_{1},\dots,y_{\ell})\in\textup{{MSO}}[\tau,q,d+\ell,0]$,
we consider the $\textup{{MSO}}[\tau^{\prime},q+d,\ell,0]$-formula

$\displaystyle\varphi^{\prime}(y_{1},\dots,y_{\ell})=\forall x_{1}\dots\forall
x_{d}\Biggl{(}$
$\displaystyle\quad\biggl{(}\bigvee_{\begin{subarray}{c}i\in[s^{\prime}]\\\
\lambda_{i}=+\end{subarray}}\bigwedge_{j=1}^{d}S_{i,j}(x_{j})\biggr{)}\rightarrow\varphi(x_{1},\dots,x_{d},y_{1},\dots,y_{\ell})$
$\displaystyle\land\biggl{(}\bigvee_{\begin{subarray}{c}i\in[s^{\prime}]\\\
\lambda_{i}=-\end{subarray}}\bigwedge_{j=1}^{d}S_{i,j}(x_{j})\biggr{)}\rightarrow\neg\varphi(x_{1},\dots,x_{d},y_{1},\dots,y_{\ell})\Biggr{)}.$

Now, for every $w_{1},\dots,w_{\ell}\in A$, we have
$\mathcal{A}_{S^{\prime}}\models\varphi^{\prime}(w_{1},\dots,w_{\ell})$ if and
only if $h_{\varphi,\bar{w}}$ with $\bar{w}=(w_{1},\dots,w_{\ell})$ is
consistent with $S^{\prime}$. Hence, analogously to the procedure described in
Section 3, we can find a consistent hypothesis, if it exists, by going through
all possible formulas $\varphi$ and computing $w_{1},\dots,w_{\ell}\in A$ with
$\mathcal{A}_{S^{\prime}}\models\varphi^{\prime}(w_{1},\dots,w_{\ell})$.

We have $\textsf{tw}(\mathcal{A}_{S^{\prime}})=\textsf{tw}(\mathcal{A})$.
Moreover, $\mathcal{A}_{S^{\prime}}$ and $\mathcal{A}$ have the same universe,
and $\left\lvert\tau^{\prime}\right\rvert$ only depends on
$\left\lvert\tau\right\rvert$, $d$, and
$s=m(d,k,\ell,q,\left\lvert\tau\right\rvert,\delta,\varepsilon)$. Thus,
analogously to Section 3, a consistent hypothesis for a single subsequence
$S^{\prime}$ can be computed by an fpt-algorithm with parameters
$d,k,\ell,q,\left\lvert\tau\right\rvert,\delta$, and $\varepsilon$. The number
of subsequences to check can be bounded by $2^{s}$. Hence, all in all, the
described procedure is an fpt-algorithm that solves MSO-PAC-Learn.

Theorem 1.5 can be proved analogously to Theorem 1.4 by applying the
techniques described in Section 4.

##  6 Hardness

Previously, we restricted the input structure of MSO-Consistent-Learn to
certain classes with nice properties. Now, we consider the problem MSO-
Consistent-Learn without any restrictions. Van Bergerem, Grohe, and Ritzert
showed in [59] that there is a close relation between first-order model
checking (FO-Mc) and learning first-order formulas. The fpt-reduction in [59]
from model checking to learning yields $\textup{{AW}}[*]$-hardness for
learning first-order formulas on classes of structures that are not nowhere
dense. It is simple to show (and not surprising) that MSO-Consistent-Learn is
at least as hard as FO-Mc. The more interesting question is whether MSO-
Consistent-Learn is at least as hard as the model-checking problem for MSO-
sentences (MSO-Mc), which is defined as follows.

MSO-Mc
Input: $\tau$-structure $\mathcal{A}$ for some signature $\tau$,
$\textup{{MSO}}[\tau]$-sentence $\varphi$ Parameter:
$\left\lvert\varphi\right\rvert$ Problem: Decide whether
$\mathcal{A}\models\varphi$ holds.

MSO-Mc is para-NP-hard under fpt Turing reductions as even for some fixed
formula $\varphi$, the corresponding model-checking problem can be NP-hard
(for example for a formula defining 3-Colorability, see [24] for details).
Hence, the following reduction from MSO-Mc to 1D-MSO-Consistent-Learn proves
Theorem 1.6.

######  Lemma 6.1.

MSO-Mc is fpt Turing reducible to 1D-MSO-Consistent-Learn.

######  Proof 6.2.

We describe an fpt algorithm with access to a 1D-MSO-Consistent-Learn oracle
that solves MSO-Mc. Let $\tau$ be a relational signature, let $\mathcal{A}$ be
a $\tau$-structure with universe $A$, and let $\varphi$ be an
$\textup{{MSO}}[\tau]$-sentence. Let $n\coloneqq\left\lvert A\right\rvert$.
W.l.o.g., we may assume that $\tau$ only contains relation symbols that appear
in $\varphi$ and hence, we have
$\left\lvert\tau\right\rvert\leq\left\lvert\varphi\right\rvert$. We decide
whether $\mathcal{A}\models\varphi$ holds recursively by decomposing the input
formula. While handling negation and Boolean connectives is easy, the crucial
part of the computation is handling quantification. Thus, we assume that
$\varphi=\exists x\psi$ or $\varphi=\exists X\psi$ for some
$\textup{{MSO}}[\tau]$-formula $\psi$. For both types of quantifiers, we use
the 1D-MSO-Consistent-Learn oracle to identify a small set of candidate
vertices or sets such that $\psi$ holds for any vertex or set if and only if
it holds for any of the identified candidates. Then, since the number of
candidates will only depend on $\left\lvert\psi\right\rvert$, we can check
recursively whether $\psi$ holds for any of them and thereby decide MSO-Mc
with an fpt algorithm.

First, assume that $\varphi=\exists x\psi$. For every pair of distinct
vertices $u,v\in A$, we call the 1D-MSO-Consistent-Learn oracle with input
structure $\mathcal{A}$, $q=\operatorname*{qr}(\psi)$, $\ell=0$, and training
sequence $S=\bigl{(}(u,+),(v,-)\bigr{)}$. Since $\ell=0$, the learning
algorithm may not use any vertices as parameters in the hypothesis. Thus, the
oracle returns a hypothesis if and only if
$\textup{tp}^{\mathcal{A}}_{q}(u)\neq\textup{tp}^{\mathcal{A}}_{q}(v)$. Note
that the oracle answers induce a partition on $A$ where two vertices $u$ and
$v$ are in the same class if and only if the oracle does not return a
hypothesis on the input as specified above. The number of classes is the
number of vertex $q$-types in $\mathcal{A}$, which only depends on $q$ and
$\left\lvert\tau\right\rvert$ and can thus be bounded in terms of
$\left\lvert\varphi\right\rvert$. Finally, since $\mathcal{A}\models\psi(u)$
if and only if $\mathcal{A}\models\psi(v)$ for all vertices $u$ and $v$ in the
same class, it suffices to check a single candidate per class. Let $v\in A$ be
the candidate for which we want to check whether $\mathcal{A}\models\psi(v)$
holds. To be able to run our algorithm for MSO-Mc recursively, we encode our
choice in the structure and then turn the formula $\psi$ into a sentence.

######  Claim 1.

There is a signature $\tau^{\prime}$ with
$\left\lvert\tau^{\prime}\right\rvert\leq\left\lvert\varphi\right\rvert\cdot
2^{\left\lvert\varphi\right\rvert}$ such that, for every $v\in A$, there is a
$\tau^{\prime}$-structure $\mathcal{A}_{v}$ with universe $A$ and an
$\textup{{MSO}}[\tau^{\prime}]$-sentence $\psi_{v}$ with
$\operatorname*{qr}(\psi)=\operatorname*{qr}(\psi_{v})$ and
$\mathcal{A}\models\psi(v)$ if and only if $\mathcal{A}_{v}\models\psi_{v}$.
Moreover, $\tau^{\prime}$, $\mathcal{A}_{v}$, and $\psi_{v}$ can be computed
by an fpt algorithm.

Let
$\tau^{\prime}=\bigl{\\{}R_{w}\mathrel{\big{|}}k\in\mathbb{N},R\in\tau\text{
with }\operatorname*{arity}(R)=k,w\in\\{0,1\\}^{k}\bigr{\\}}\uplus\\{V\\}$.
For $v\in A$, let $\mathcal{A}_{v}$ be the $\tau^{\prime}$-structure with
universe $A$ and, for every $k\in\mathbb{N}$, $R\in\tau$ with
$\operatorname*{arity}(R)=k$, and $w\in\\{0,1\\}^{k}$, let

$R_{w}^{\mathcal{A}_{v}}=\bigl{\\{}(a_{i})_{i\in[k],w_{i}=0}\mathrel{\big{|}}(a_{1},\dots,a_{k})\in
R^{\mathcal{A}},a_{i}=v\text{ for all }i\in[k]\text{ with }w_{i}=1\bigr{\\}}.$

The word $w$ can be seen as a labeling of the positions of tuples in
$R^{\mathcal{A}}$, and the relation $R_{w}^{\mathcal{A}_{v}}$ is the
projection of $R^{\mathcal{A}}$ to the positions labeled with $0$ for tuples
that contain $v$ at all positions labeled with $1$. Furthermore, we set
$V^{\mathcal{A}_{v}}=\\{v\\}$. W.l.o.g., we assume that the formula $\psi(x)$
does not contain atoms of the form $x=x$. The formula can then be transformed
into the sentence $\psi_{v}$ by replacing every atom of the form $y=x$ or
$x=y$ by $V(y)$, and by replacing atoms of the form $R(y_{1},\dots,y_{k})$ by
$R_{w}(z_{1},\dots,z_{k^{\prime}})$ for $w\in\\{0,1\\}^{k}$, $w_{i}=1$ if and
only if $y_{i}=x$, and $(z_{j})_{j\in[k^{\prime}]}=(y_{j})_{j\in[k],w_{j}=0}$.
We have $\mathcal{A}\models\psi(v)$ if and only if
$\mathcal{A}_{v}\models\psi_{v}$. Moreover,
$\left\lvert\tau^{\prime}\right\rvert\leq\left\lvert\varphi\right\rvert\cdot
2^{\left\lvert\varphi\right\rvert}$, and $\tau^{\prime}$, $\mathcal{A}_{v}$,
and $\psi_{v}$ can be computed by an fpt algorithm. Note that for now,
considering only first-order quantifiers, the depth and the degree of the
recursion tree can be bounded in terms of $\left\lvert\varphi\right\rvert$.
Moreover, in all oracle queries, the universe of the input structure is $A$,
and the parameter of the problem 1D-MSO-Consistent-Learn can be bounded in
terms of $\left\lvert\varphi\right\rvert$.

In the remainder of this proof, we describe how to handle second-order
quantifiers. Assume that $\varphi=\exists X\psi$. Similarly to the first case,
we want to find a small set of candidate sets for $X$. However, in contrast to
the first-order quantifier, querying the oracle for every possible choice
would lead to a running time that is exponential in the size of the input
structure. To overcome this issue, intuitively, we proceed as follows. We go
through the possible choices in $n$ rounds, where in round $i$, we only
consider candidate sets of size $i$. Overall, we compute $n$ families
$V_{1},\dots,V_{n}$ of candidates, where every single family $V_{i}$ is small,
that is, the size of $V_{i}$ only depends on $\left\lvert\varphi\right\rvert$,
say $f(\left\lvert\varphi\right\rvert)$. In the first round, we compute
$V_{1}$ by going through all sets of size $1$. Based on answers of the 1D-MSO-
Consistent-Learn oracle, we keep only $f(\left\lvert\varphi\right\rvert)$ many
candidates. Then, in round $i+1$ for $i>0$, we consider all extensions of the
sets in $V_{i}$ by a single element, which are
$f(\left\lvert\varphi\right\rvert)\cdot n$ many possible choices to consider.
Again, using the oracle, we keep only $f(\left\lvert\varphi\right\rvert)$ many
candidates and call the resulting family of candidates $V_{i+1}$. After $n$
rounds, all in all, we have $f(\left\lvert\varphi\right\rvert)\cdot n$ many
candidates. In a last step, we then also compare candidates of different
sizes, ending up with at most $f(\left\lvert\varphi\right\rvert)$ candidates.
Similarly to the first-order quantifier, for every candidate, we can encode
the candidate in the structure and run our algorithm for MSO-Mc recursively.
In the following, we formalize every single step of the described procedure.

First, we describe how to find the small number of candidates in each round.
For every $\textup{{MSO}}[q]$-formula $\gamma(X)$, consider the
$\textup{{MSO}}[q+2]$-formula

$\gamma^{\prime}(X)=\exists Y\bigl{(}\forall x(X(x)\rightarrow
Y(x))\land\gamma(Y)\bigr{)}.$

This formula checks whether any superset of $X$ (including $X$ itself)
satisfies $\gamma$. Thus, if two sets $C_{1},C_{2}$ have the same
$(q+2)$-type, then for every superset $C_{1}^{\prime}\supseteq C_{1}$, there
is a superset $C_{2}^{\prime}\supseteq C_{2}$ of the same type. Thus, when
computing the families $V_{i}$, it suffices to keep only one of the two sets.

To check for two sets $C_{1},C_{2}\subseteq A$ whether they have the same
$(q+2)$-type, we use the 1D-MSO-Consistent-Learn oracle. As the input
structure, we choose the $\tau^{\prime}$-structure $\mathcal{B}$ with
$\tau^{\prime}\coloneqq\tau\uplus\\{E,C\\}$ and universe
$B\coloneqq\\{(v,0),(v,1)\mid v\in A\\}\uplus\\{w_{1},w_{2}\\}$. For every
$k\in\mathbb{N}$ and every $k$-ary relation symbol $R\in\tau$, we set
$R^{\mathcal{B}}\coloneqq\Bigl{\\{}\bigl{(}(v_{1},i),\dots,(v_{k},i)\bigr{)}\mathrel{\Big{|}}(v_{1},\dots,v_{k})\in
R^{\mathcal{A}},i\in\\{1,2\\}\Bigr{\\}}$. Moreover, we set
$E^{\mathcal{B}}\coloneqq\bigl{\\{}\bigl{(}w_{i},(v,i)\bigr{)}\mathrel{\big{|}}v\in
A,i\in\\{1,2\\}\bigr{\\}}$ and
$C^{\mathcal{B}}\coloneqq\bigl{\\{}(v,1)\mathrel{\big{|}}v\in
C_{1}\bigr{\\}}\cup\bigl{\\{}(v,2)\mathrel{\big{|}}v\in C_{2}\bigr{\\}}$.
Intuitively, $\mathcal{B}$ contains two copies of $\mathcal{A}$. For each
copy, there is vertex $w_{i}$ that is connected to every vertex in the copy.
Furthermore, the relation $C$ encodes the set $C_{1}$ in the first copy and
$C_{2}$ in the second copy. The construction is depicted in Figure 2.

$v_{1}$ $v_{2}$ $v_{5}$ $v_{6}$ $v_{3}$ $v_{4}$ $w_{1}$ $w_{2}$
$\mathcal{A}$$\mathcal{A}$ $C_{1}$ $C_{2}$ $\mathcal{B}$ Figure 2: Input
structure $\mathcal{B}$ of the 1D-MSO-Consistent-Learn oracle.

######  Claim 2.

For an algorithm solving 1D-MSO-Consistent-Learn, given $\mathcal{B}$ as the
input structure, $2q+6$ as the quantifier rank, $\ell=0$, and
$S=\bigl{(}(w_{1},+),(w_{2},-)\bigr{)}$ as the training sequence, the
following holds.

  1. (1)

If the algorithm rejects, then
$\textup{tp}^{\mathcal{A}}_{q+2}(C_{1})=\textup{tp}^{\mathcal{A}}_{q+2}(C_{2})$.

  2. (2)

If
$\textup{tp}^{\mathcal{A}}_{2q+6}(C_{1})=\textup{tp}^{\mathcal{A}}_{2q+6}(C_{2})$,
then the algorithm rejects.

We prove (1) by showing that the algorithm returns a hypothesis for all
$C_{1},C_{2}$ of different $(q+2)$-types. Let $C_{1},C_{2}\subseteq A$ with
$\textup{tp}^{\mathcal{A}}_{q+2}(C_{1})\neq\textup{tp}^{\mathcal{A}}_{q+2}(C_{2})$.
Let $\alpha(X)\in\textup{{MSO}}[\tau,q+2,0,1]$ such that
$\mathcal{A}\models\alpha(C_{1})$ and $\mathcal{A}\not\models\alpha(C_{2})$.
Now let

$\beta(x)=\exists X\Bigl{(}\forall y\bigl{(}Xy\leftrightarrow(Sy\land
Exy)\bigr{)}\land\alpha^{\prime}(x,X),$

where $\alpha^{\prime}(x,X)$ is computed recursively from $\alpha(X)$ by
replacing every subformula of the form $\exists Y\xi$ by $\exists
Y\bigl{(}\forall y(Yy\rightarrow Exy)\land\xi^{\prime}\bigr{)}$ and replacing
every subformula of the form $\exists y\,\xi$ by $\exists
y(Exy\land\xi^{\prime})$. Then, it holds that
$\mathcal{A}\models\alpha(C_{i})$ if and only if
$\mathcal{B}\models\beta(w_{i})$ for $i\in[2]$. Furthermore,
$\operatorname*{qr}(\beta)\leq 2\operatorname*{qr}(\alpha)+2=2q+6.$ Hence, an
algorithm solving 1D-MSO-Consistent-Learn will return a hypothesis (for
example $h_{\beta}$).

To prove (2), we assume that
$\textup{tp}^{\mathcal{A}}_{2q+6}(C_{1})=\textup{tp}^{\mathcal{A}}_{2q+6}(C_{2})$.
It suffices to show that
$\textup{tp}^{\mathcal{B}}_{2q+6}(w_{1})=\textup{tp}^{\mathcal{B}}_{2q+6}(w_{2})$,
since an algorithm solving 1D-MSO-Consistent-Learn will not be able to return
a consistent hypothesis in that case and reject. Let
$A_{i}\coloneqq\bigl{\\{}(a,i)\mathrel{\big{|}}a\in
A\bigr{\\}}\cup\\{w_{i}\\}$ and $B_{i}\coloneqq A_{i}\cup\\{w_{i}\\}$ for
$i\in[2]$. Then, for every $\textup{{MSO}}[\tau^{\prime},2q+6,0,0]$-sentence
$\chi$, we have $\mathcal{B}[A_{1}]\models\chi$ if and only if
$\mathcal{B}[A_{2}]\models\chi$. To see this, assume that there is an
$\textup{{MSO}}[\tau^{\prime},2q+6,0,0]$-sentence $\chi$ with
$\mathcal{B}[A_{1}]\models\chi$ and $\mathcal{B}[A_{2}]\not\models\chi$. Then
$\chi^{\prime}(C)=\chi$ is an $\textup{{MSO}}[\tau,2q+6,0,1]$-formula that is
contained in $\textup{tp}^{\mathcal{A}}_{2q+6}(C_{1})$ and not contained in
$\textup{tp}^{\mathcal{A}}_{2q+6}(C_{2})$, which contradicts
$\textup{tp}^{\mathcal{A}}_{2q+6}(C_{1})=\textup{tp}^{\mathcal{A}}_{2q+6}(C_{2})$.

From this result on $\mathcal{B}[A_{1}]$ and $\mathcal{B}[A_{2}]$, for example
by considering the corresponding Ehrenfeucht–Fraïssé games, we obtain that
$\mathcal{B}[B_{1}]\models\chi$ if and only if $\mathcal{B}[B_{2}]\models\chi$
and
$\textup{tp}^{\mathcal{B}[B_{1}]}_{2q+6}(w_{1})=\textup{tp}^{\mathcal{B}[B_{2}]}_{2q+6}(w_{2})$.
Since $\mathcal{B}$ is the disjoint union of $\mathcal{B}[B_{1}]$ and
$\mathcal{B}[B_{2}]$, by the Feferman-Vaught Theorem for MSO [41], we have
$\textup{tp}^{\mathcal{B}}_{2q+6}(w_{1})=\textup{tp}^{\mathcal{B}}_{2q+6}(w_{2})$.

To compute the families of candidate sets $V_{1},\dots,V_{n}$, in the first
round, we set $V_{1}=\bigl{\\{}\\{a\\}\mathrel{\big{|}}a\in A\bigr{\\}}$.
Then, for every pair $C_{1},C_{2}\in V_{1}$, we query the oracle as described
above. If the algorithm rejects, because of Item (1) of 2, for every superset
of $C_{1}$, there is a superset of $C_{2}$ of the same $q$-type. Hence,
$C_{2}$ is not needed anymore in the following computation, and we remove it
from $V_{1}$. Because of Item (2) of 2, after running the oracle for every
pair in $V_{1}$, there is at most one set in $V_{1}$ for every $(2q+6)$-type
of sets in $\mathcal{A}$. Thus, the number of remaining sets in $V_{1}$ can be
bounded in terms of $\left\lvert\varphi\right\rvert$ without any dependence on
$\left\lvert A\right\rvert$.

Next, in round $i+1$ for $i>0$, we set
$V_{i+1}=\bigl{\\{}C\cup\\{a\\}\mathrel{\big{|}}C\in V_{i},a\in A\bigr{\\}}$.
As in the first round, we run the oracle for every pair $C_{1},C_{2}\in
V_{i+1}$, and we remove $C_{2}$ from $V_{i+1}$ if the oracle rejects. After
the $n$th round, we set $W=\bigcup_{i=1}^{n}V_{i}$. Again, we call the oracle
for every pair of sets in $W$, and we remove one of the two sets if the oracle
rejects. At the end, the number of sets in $W$ only depends on
$\left\lvert\varphi\right\rvert$. Furthermore, for every set
$A^{\prime}\subseteq A$, there is a candidate $C\in W$ of the same $q$-type.
The number of oracle calls is quadratic in $\left\lvert A\right\rvert$, the
size of the input structures for the oracle calls is linear in the size of
$\mathcal{A}$, and the parameters of the oracle calls can be bounded in terms
of $\left\lvert\varphi\right\rvert$.

Recall that we assumed the input formula $\varphi$ to be of the form $\exists
X\psi$. For every candidate $C\in W$, we recursively want to check whether
$\mathcal{A}\models\psi(C)$ holds. For that, we extend the signature $\tau$ by
a new unary relation symbol $X$, and we let $\mathcal{A}_{C}$ be the
relational structure over the new signature with $X^{\mathcal{A}_{C}}=C$. We
can then consider $\psi$ as a sentence over the new signature and recursively
run our algorithm to check whether $\mathcal{A}_{C}\models\psi$ holds.

Overall, considering both first-order and second-order quantification, we have
a recursion tree where both the depth and the degree of the tree can be
bounded in terms of $\left\lvert\varphi\right\rvert$. In every single
recursive call, the number of oracle queries is at most quadratic in
$\left\lvert A\right\rvert$, the size of the input structures for the oracle
queries is linear in the size of $\mathcal{A}$, and the parameter
$\left\lvert\tau\right\rvert+d+q+\ell$ for the oracle queries can also be
bounded in terms of $\left\lvert\varphi\right\rvert$. Thus, the described
procedure yields an fpt Turing reduction from MSO-Mc to 1D-MSO-Consistent-
Learn.

##  7 Conclusion

We studied the parameterized complexity of learning hypotheses formalized in
monadic second-order logic. Just like the model-checking problem and the
associated counting and enumeration problems, the learning problem we study
here is a natural algorithmic problem for logics on finite structures. All
these problems are related, but each has its own challenges requiring
different techniques. Where model-checking and enumeration are motivated by
automated verification and database systems, we may view our work as part of a
descriptive complexity theory of machine learning [58].

The first problem we studied is 1D-MSO-Consistent-Learn, where the instances
to classify consist of single vertices, and we extended the previous fixed-
parameter tractability results for strings and trees [29, 28] to relational
structures of bounded tree-width and graphs of bounded clique-width. Secondly,
we studied the agnostic PAC-learning problem MSO-PAC-Learn, where we obtained
a fixed-parameter tractable learning algorithm working in arbitrary
dimensions. On general relational structures, we showed that MSO-Consistent-
Learn, even in the $1$-dimensional case, is at least as hard as the
corresponding model-checking problem MSO-Mc.

In the consistent-learning setting and on classes of bounded tree-width or of
bounded clique-width, the parameterized complexity of learning in higher
dimensions remains as an interesting open question. Furthermore, regarding the
hardness result presented in this paper, we think that an in-depth analysis of
our reduction might also yield hardness results for more restricted classes of
relational structures with a hard MSO-model-checking problem.

In the learning problems considered so far, hypotheses are built using MSO-
formulas and tuples of vertices as parameters. We think that the algorithms
presented in this paper could also be extended to hypothesis classes that
allow tuples of sets as parameters.

Finally, utilizing the full power of MSO logic, one could also consider a
learning problem where, instead of classifying tuples of vertices, we are
interested in classifying sets of vertices. That is, for a relational
structure $\mathcal{A}$ with universe $A$, we are given labeled subsets of $A$
and want to find a hypothesis $h\colon 2^{A}\to\\{+,-\\}$ that is consistent
with the given examples. It is easy to see that the techniques used in our
hardness result also apply to this modified problem, proving that it is para-
NP-hard. However, it remains open whether our tractability results could also
be lifted to this version of the problem.

## References

  * [1] Azza Abouzied, Dana Angluin, Christos H. Papadimitriou, Joseph M. Hellerstein, and Avi Silberschatz.  Learning and verifying quantified boolean queries by example.  In Richard Hull and Wenfei Fan, editors, Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 49–60. ACM, 2013\.  doi:10.1145/2463664.2465220.
  * [2] Howard Aizenstein, Tibor Hegedüs, Lisa Hellerstein, and Leonard Pitt.  Complexity theoretic hardness results for query learning.  Comput. Complex., 7(1):19–53, 1998.  doi:10.1007/PL00001593.
  * [3] Bogdan Alexe, Balder ten Cate, Phokion G. Kolaitis, and Wang Chiew Tan.  Characterizing schema mappings via data examples.  ACM Trans. Database Syst., 36(4):23:1–23:48, 2011.  doi:10.1145/2043652.2043656.
  * [4] Dana Angluin.  Queries and concept learning.  Machine Learning, 2(4):319–342, 1987.  doi:10.1007/BF00116828.
  * [5] Stefan Arnborg and Andrzej Proskurowski.  Linear time algorithms for NP-hard problems restricted to partial k-trees.  Discrete Applied Mathematics, 23(1):11–24, April 1989.  doi:10.1016/0166-218X(89)90031-0.
  * [6] Vikraman Arvind, Johannes Köbler, and Wolfgang Lindner.  Parameterized learnability of _k_ -juntas and related problems.  In Marcus Hutter, Rocco A. Servedio, and Eiji Takimoto, editors, Algorithmic Learning Theory, 18th International Conference, ALT 2007, Sendai, Japan, October 1-4, 2007, Proceedings, volume 4754 of Lecture Notes in Computer Science, pages 120–134. Springer, 2007.  doi:10.1007/978-3-540-75225-7\\_13.
  * [7] Pablo Barceló, Alexander Baumgartner, Victor Dalmau, and Benny Kimelfeld.  Regularizing conjunctive features for classification.  J. Comput. Syst. Sci., 119:97–124, 2021.  doi:10.1016/j.jcss.2021.01.003.
  * [8] Pablo Barceló and Miguel Romero.  The complexity of reverse engineering problems for conjunctive queries.  In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, volume 68 of LIPIcs, pages 7:1–7:17. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ICDT.2017.7.
  * [9] Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth.  Learnability and the Vapnik-Chervonenkis dimension.  Journal of the ACM, 36(4):929–965, October 1989.  doi:10.1145/76359.76371.
  * [10] Hans L. Bodlaender.  A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.  doi:10.1137/S0097539793251219.
  * [11] Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk.  A c${}^{\mbox{k}}$ n 5-approximation algorithm for treewidth.  SIAM J. Comput., 45(2):317–378, 2016.  doi:10.1137/130947374.
  * [12] Angela Bonifati, Radu Ciucanu, and Aurélien Lemay.  Learning path queries on graph databases.  In Gustavo Alonso, Floris Geerts, Lucian Popa, Pablo Barceló, Jens Teubner, Martín Ugarte, Jan Van den Bussche, and Jan Paredaens, editors, Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, March 23-27, 2015, pages 109–120. OpenProceedings.org, 2015.  doi:10.5441/002/edbt.2015.11.
  * [13] Angela Bonifati, Radu Ciucanu, and Slawek Staworko.  Learning join queries from user examples.  ACM Trans. Database Syst., 40(4):24:1–24:38, 2016.  doi:10.1145/2818637.
  * [14] Angela Bonifati, Ugo Comignani, Emmanuel Coquery, and Romuald Thion.  Interactive mapping specification with exemplar tuples.  ACM Trans. Database Syst., 44(3):10:1–10:44, 2019.  doi:10.1145/3321485.
  * [15] Cornelius Brand, Robert Ganian, and Kirill Simonov.  A parameterized theory of PAC learning.  In Brian Williams, Yiling Chen, and Jennifer Neville, editors, Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 6834–6841. AAAI Press, 2023.  URL: https://ojs.aaai.org/index.php/AAAI/article/view/25837.
  * [16] J. Richard Büchi.  Weak Second-Order Arithmetic and Finite Automata.  Mathematical Logic Quarterly, 6(1-6):66–92, 1960.  doi:10.1002/malq.19600060105.
  * [17] Adrien Champion, Tomoya Chiba, Naoki Kobayashi, and Ryosuke Sato.  ICE-based refinement type discovery for higher-order functional programs.  J. Autom. Reason., 64(7):1393–1418, 2020.  doi:10.1007/s10817-020-09571-y.
  * [18] William W. Cohen and C. David Page.  Polynomial learnability and Inductive Logic Programming: Methods and results.  New Generation Computing, 13(3-4):369–409, December 1995.  doi:10.1007/BF03037231.
  * [19] B. Courcelle, J. A. Makowsky, and U. Rotics.  Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width.  Theory of Computing Systems, 33:125–150, 1999.
  * [20] Bruno Courcelle.  Graph Rewriting: An Algebraic and Logic Approach.  In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics, 1990.
  * [21] John Doner.  Tree Acceptors and Some of Their Applications.  J. Comput. Syst. Sci., 4(5):406–451, 1970.  doi:10.1016/S0022-0000(70)80041-1.
  * [22] Calvin C. Elgot.  Decision problems of finite automata design and related arithmetics.  Transactions of the American Mathematical Society, 98(1):21–51, 1961.  doi:10.1090/S0002-9947-1961-0139530-9.
  * [23] P. Ezudheen, Daniel Neider, Deepak D’Souza, Pranav Garg, and P. Madhusudan.  Horn-ICE learning for synthesizing invariants and contracts.  Proc. ACM Program. Lang., 2(OOPSLA):131:1–131:25, 2018.  doi:10.1145/3276501.
  * [24] Jörg Flum and M. Grohe.  Parameterized complexity theory.  Texts in theoretical computer science. Springer, Berlin ; New York, 2006\.
  * [25] Pranav Garg, Christof Löding, P. Madhusudan, and Daniel Neider.  ICE: A robust framework for learning invariants.  In Armin Biere and Roderick Bloem, editors, Computer Aided Verification - 26th International Conference, CAV 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 18-22, 2014. Proceedings, volume 8559 of Lecture Notes in Computer Science, pages 69–87. Springer, 2014.  doi:10.1007/978-3-319-08867-9_5.
  * [26] Georg Gottlob and Pierre Senellart.  Schema mapping discovery from data instances.  J. ACM, 57(2):6:1–6:37, 2010.  doi:10.1145/1667053.1667055.
  * [27] Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors.  Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002.  doi:10.1007/3-540-36387-4.
  * [28] Émilie Grienenberger and Martin Ritzert.  Learning Definable Hypotheses on Trees.  In Pablo Barceló and Marco Calautti, editors, 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, volume 127 of LIPIcs, pages 24:1–24:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICDT.2019.24.
  * [29] Martin Grohe, Christof Löding, and Martin Ritzert.  Learning MSO-definable hypotheses on strings.  In Proceedings of the 28th International Conference on Algorithmic Learning Theory, pages 434–451. PMLR, October 2017.  ISSN: 2640-3498.  URL: https://proceedings.mlr.press/v76/grohe17a.html.
  * [30] Martin Grohe and Martin Ritzert.  Learning first-order definable concepts over structures of small degree.  In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, Reykjavik, Iceland, June 2017. IEEE.  doi:10.1109/LICS.2017.8005080.
  * [31] Martin Grohe and Gy. Turán.  Learnability and Definability in Trees and Similar Structures.  Theory of Computing Systems, 37(1):193–220, January 2004.  doi:10.1007/s00224-003-1112-8.
  * [32] Y. Gurevich.  Monadic Second-Order Theories.  In J. Barwise and S. Feferman, editors, Model-Theoretic Logics, pages 479–506. Cambridge University Press, 1 edition, March 2017.  doi:10.1017/9781316717158.019.
  * [33] David Haussler.  Learning conjunctive concepts in structural domains.  Mach. Learn., 4:7–40, 1989.  doi:10.1007/BF00114802.
  * [34] David Haussler.  Decision theoretic generalizations of the PAC model for neural net and other learning applications.  Inf. Comput., 100(1):78–150, 1992.  doi:10.1016/0890-5401(92)90010-D.
  * [35] Kouichi Hirata.  On the hardness of learning acyclic conjunctive queries.  In Hiroki Arimura, Sanjay Jain, and Arun Sharma, editors, Algorithmic Learning Theory, 11th International Conference, ALT 2000, Sydney, Australia, December 11-13, 2000, Proceedings, volume 1968 of Lecture Notes in Computer Science, pages 238–251. Springer, 2000.  doi:10.1007/3-540-40992-0_18.
  * [36] Michael J. Kearns and Umesh V. Vazirani.  An Introduction to Computational Learning Theory.  MIT Press, 1994.  URL: https://mitpress.mit.edu/books/introduction-computational-learning-theory.
  * [37] Benny Kimelfeld and Christopher Ré.  A relational framework for classifier engineering.  ACM Trans. Database Syst., 43(3):11:1–11:36, 2018.  doi:10.1145/3268931.
  * [38] Tuukka Korhonen.  A single-exponential time 2-approximation algorithm for treewidth.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 184–192. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00026.
  * [39] Yuanzhi Li and Yingyu Liang.  Learning mixtures of linear regressions with nearly optimal complexity.  In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1125–1144. PMLR, 2018.  URL: http://proceedings.mlr.press/v75/li18b.html.
  * [40] Christof Löding, P. Madhusudan, and Daniel Neider.  Abstract learning frameworks for synthesis.  In Marsha Chechik and Jean-François Raskin, editors, Tools and Algorithms for the Construction and Analysis of Systems - 22nd International Conference, TACAS 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings, volume 9636 of Lecture Notes in Computer Science, pages 167–185. Springer, 2016.  URL: https://doi.org/10.1007/978-3-662-49674-9_10, doi:10.1007/978-3-662-49674-9_10.
  * [41] Johann A. Makowsky.  Algorithmic uses of the Feferman-Vaught theorem.  Ann. Pure Appl. Log., 126(1-3):159–213, 2004.  doi:10.1016/j.apal.2003.11.002.
  * [42] Stephen Muggleton.  Inductive logic programming.  New Generation Computing, 8(4):295–318, February 1991.  doi:10.1007/BF03037089.
  * [43] Stephen Muggleton and Luc De Raedt.  Inductive Logic Programming: Theory and Methods.  J. Log. Program., 19/20:629–679, 1994.
  * [44] Sang-il Oum and Paul D. Seymour.  Approximating clique-width and branch-width.  J. Comb. Theory, Ser. B, 96(4):514–528, 2006.  URL: https://koasas.kaist.ac.kr/handle/10203/90201, doi:10.1016/j.jctb.2005.10.006.
  * [45] Neil Robertson and P. D Seymour.  Graph minors. II. Algorithmic aspects of tree-width.  Journal of Algorithms, 7(3):309–322, September 1986.  URL: https://www.sciencedirect.com/science/article/pii/0196677486900234, doi:10.1016/0196-6774(86)90023-4.
  * [46] Detlef Seese.  The structure of models of decidable monadic theories of graphs.  Ann. Pure Appl. Log., 53(2):169–195, 1991.  doi:10.1016/0168-0072(91)90054-P.
  * [47] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning: From Theory to Algorithms.  Cambridge University Press, Cambridge, 2014.  URL: https://www.cambridge.org/core/books/understanding-machine-learning/3059695661405D25673058E43C8BE2A6, doi:10.1017/CBO9781107298019.
  * [48] Robert H. Sloan, Balázs Szörényi, and György Turán.  Learning Boolean functions with queries.  In Yves Crama and Peter L. Hammer, editors, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pages 221–256. Cambridge University Press, 2010.  doi:10.1017/cbo9780511780448.010.
  * [49] Slawek Staworko and Piotr Wieczorek.  Learning twig and path queries.  In Alin Deutsch, editor, 15th International Conference on Database Theory, ICDT 2012, Berlin, Germany, March 26-29, 2012, pages 140–154. ACM, 2012.  doi:10.1145/2274576.2274592.
  * [50] Balder ten Cate and Victor Dalmau.  Conjunctive queries: Unique characterizations and exact learnability.  In Ke Yi and Zhewei Wei, editors, 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, volume 186 of LIPIcs, pages 9:1–9:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ICDT.2021.9.
  * [51] Balder ten Cate, Victor Dalmau, and Phokion G. Kolaitis.  Learning schema mappings.  ACM Trans. Database Syst., 38(4):28:1–28:31, 2013.  doi:10.1145/2539032.2539035.
  * [52] Balder ten Cate, Phokion G. Kolaitis, Kun Qian, and Wang-Chiew Tan.  Active learning of GAV schema mappings.  In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 355–368. ACM, 2018.  doi:10.1145/3196959.3196974.
  * [53] J. W. Thatcher and J. B. Wright.  Generalized finite automata theory with an application to a decision problem of second-order logic.  Mathematical Systems Theory, 2(1):57–81, March 1968.  doi:10.1007/BF01691346.
  * [54] Wolfgang Thomas.  Languages, Automata, and Logic.  In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages: Volume 3 Beyond Words, pages 389–455. Springer, Berlin, Heidelberg, 1997.  doi:10.1007/978-3-642-59126-6_7.
  * [55] B. Trahtenbrot.  Finite automata and the logic of one-place predicates.  In Twelve Papers on Logic and Algebra, volume 59 of American Mathematical Society Translations: Series 2. American Mathematical Society, 1966.  ISSN: 0065-9290, 2472-3193.  URL: http://www.ams.org/trans2/059, doi:10.1090/trans2/059.
  * [56] L. G. Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, November 1984.  URL: https://dl.acm.org/doi/10.1145/1968.1972, doi:10.1145/1968.1972.
  * [57] Steffen van Bergerem.  Learning Concepts Definable in First-Order Logic with Counting.  In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–13, Vancouver, BC, Canada, June 2019\. IEEE.  URL: https://ieeexplore.ieee.org/document/8785811/, doi:10.1109/LICS.2019.8785811.
  * [58] Steffen van Bergerem.  Descriptive Complexity of Learning.  PhD thesis, RWTH Aachen University, Germany, 2023.  URL: https://publications.rwth-aachen.de/record/953243, doi:10.18154/RWTH-2023-02554.
  * [59] Steffen van Bergerem, Martin Grohe, and Martin Ritzert.  On the Parameterized Complexity of Learning First-Order Logic.  In Leonid Libkin and Pablo Barceló, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 337–346. ACM, 2022.  doi:10.1145/3517804.3524151.
  * [60] Steffen van Bergerem and Nicole Schweikardt.  Learning concepts described by weight aggregation logic.  In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, Ljubljana, Slovenia (Virtual Conference), January 25-28, 2021, volume 183 of LIPIcs, pages 10:1–10:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.CSL.2021.10.
  * [61] Vladimir Vapnik.  Principles of risk minimization for learning theory.  In Advances in Neural Information Processing Systems 4, NIPS 1991, Denver, Colorado, USA, December 2-5, 1991, pages 831–838, 1991.  URL: https://proceedings.neurips.cc/paper_files/paper/1991/file/ff4d5fbbafdf976cfdc032e3bde78de5-Paper.pdf.
  * [62] He Zhu, Stephen Magill, and Suresh Jagannathan.  A data-driven CHC solver.  In Jeffrey S. Foster and Dan Grossman, editors, Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, Philadelphia, PA, USA, June 18-22, 2018, pages 707–721. ACM, 2018.  doi:10.1145/3192366.3192416.