# Active Learning of Upward-Closed Sets of Words

Quentin Aristote

► To cite this version:

Quentin Aristote. Active Learning of Upward-Closed Sets of Words. 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025), Jun 2025, Glasgow- University of Strathclyde, United Kingdom. pp.16:1-16:12, 10.4230/LIPIcs.CALCO.2025.16 . hal-05051620v2

HAL Id: hal-05051620

https://hal.science/hal-05051620v2

Submitted on 29 Jul 2025

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

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

<figure><img src="image_1.png" /></figure>
# Active Learning of Upward-Closed Sets of Words

Quentin Aristote 📉 ID

Université Paris Cité, CNRS, Inria, IRIF, F-75013, Paris, France

## Abstract

We give a new proof of a result from well quasi-order theory on the computability of bases for upwards-closed sets of words. This new proof is based on Angluin's $L^*$ algorithm, that learns an automaton from a minimally adequate teacher. This relates in particular two results from the 1980s: Angluin's $L^*$ algorithm, and a result from Valk and Jantzen on the computability of bases for upwards-closed sets of tuples of integers.

Along the way, we describe an algorithm for learning quasi-ordered automata from a minimally adequate teacher, and extend a generalization of Valk and Jantzen's result, encompassing both words and integers, to finitely generated monoids.

**2012 ACM Subject Classification** Theory of computation → Formal languages and automata theory

**Keywords and phrases** active learning, well quasi-orders, Valk-Jantzen lemma, piecewise-testable languages, monoids

**Digital Object Identifier** 10.4230/LIPIcs.CALCO.2025.16

**Category (Co)algebraic pearl**

**Funding** This work has received financial support from the European Research Council (ERC) under the European Union's Horizon research and innovation program (grant agreement 101167526).

**Acknowledgements** The author thanks Daniela Petrişan and anonymous reviewers for their precious comments.

## 1 Introduction

### Active learning of automata

In 1987, Angluin published a seminal work in computational learning theory [1]. She proved that the minimal complete deterministic finite-state automaton (DFA) recognizing a regular language $L \subseteq \Sigma^*$ can be learned with the help of a *minimally adequate teacher (MAT)*, i.e. an oracle able to answer two kinds of queries:

- *membership queries* – given a word $w \in \Sigma^*$, the oracle decides whether $w \in L$ –

- *equivalence queries* – given an automaton $A$ which can be assumed to be minimal for the language it recognizes, the oracle decides whether this language is $L$, and, in the negative case, also outputs a counterexample word $w \in \Sigma^*$ such that $w$ is in $L$ but is not recognized by $A$, or conversely.

Angluin's algorithm, called $L^*$, computes the minimal DFA recognizing $L$. Its complexity is polynomial in the size of this minimal automaton and the maximum length of the counterexamples.

The $L^*$ algorithm has proven very versatile over time: it has been extended to a number of other families of automata, see e.g. [18, §1.2] for a survey. The similarities between these extensions and the need to unify them has motivated several categorical approaches to MAT learning [3, 6, 12, 15, 18], some of which have in turn been used to develop new extensions of Angluin's algorithm [2, 17]. In this work we will use yet another extension of the $L^*$ algorithm, for automata with ordered sets of states, to recover a proof of decidability in well quasi-order theory.

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

© Quentin Aristote;
licensed under Creative Commons License CC-BY 4.0

11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025).

Editors: Corina Cirstea and Alexander Knapp; Article No. 16; pp. 16:1–16:12

Leibniz International Proceedings in Informatics

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

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
The generalized Valk-Jantzen lemma

Two years before Angluin's 1987 result, Valk and Jantzen proved a seemingly unrelated theorem. Order $\mathbb{N}^k$ component-wise, and, for $z \in (\mathbb{N}_* \cup \{\infty\})^k$ (where $\mathbb{N}_*$ denotes the set of positive integers), write $I_z = \{(x_1, \dots, x_n) \in \mathbb{N}^k \mid \forall i, x_i < z_i\}$.

**► Theorem 1 (Valk-Jantzen lemma [16, Theorem 2.14], Fix an upwards-closed subset U $\subseteq$ $\mathbb{N}^k$.**
*Then, given an oracle that decides for any subset $I_z$ with $z \in (\mathbb{N}_* \cup \{\infty\})^k$ whether $U$ intersects $I_z$, there is an algorithm that computes a minimal basis $B$ of $U$ – a minimal $B \subseteq \mathbb{N}^k$ such that $U = \{u \in \mathbb{N}^k \mid \exists b \in B, u \ge b\}$.*

This result is used, by Valk and Jantzen themselves but also later by other authors,
to show the decidability of a number of problems regarding Petri nets and similar state
machines: see [9] for a list of these. In *ibid.*, Goubault-Larrecq extends Theorem 1 to a whole
grammar of *well quasi-orders*: this last result is called the *generalized Valk-Jantzen lemma*.

Recall that a quasi-order (QO), also called a *preorder*, is a set equipped with a reflexive and transitive relation. Given a QO $(X, \le)$, let $\downarrow A = \{x \in X \mid \exists y \in A, x \le y\}$ denote the *downward-closure* of $A \subseteq X$, $\uparrow A = \{x \in X \mid \exists y \in A, x \ge y\}$ its *upward-closure*, and for $x \in X$ let $\downarrow x = \{x\}$ and $\uparrow x = \{x\}$. An $x \in X$ is *minimal* in $(X, \le)$ when it is smaller than every other $y \in \downarrow x$. A subset $A$ of a QO $(X, \le)$ is called *downwards-closed* when $A = \downarrow A$, and *upwards-closed* when $A = \uparrow A$.

A QO $(X, \le)$ is *well (WQO)* when all its upwards-closed subsets $U$ have a finite *basis*, i.e. can be written $U = \uparrow A$ for some finite $A \subseteq X$. Such a basis is said to be *minimal* when it does not contain any strictly smaller basis of $U$. Finite QOs and well-founded linear orders such as $\mathbb{N}$ are basic examples of WQOs; more involved examples include finite products of WQOs, equipped with the component-wise ordering [10, Lemma 4.7], or free monoids thereon [*ibid.*, §4.4]: if $(\Sigma, \leq)$ is a WQO, then so is the set $\Sigma^*$ of finite words on $\Sigma$ equipped with the *subword ordering*, given inductively by $\varepsilon \leq_\ast w$ for all $w \in \Sigma^*$, $x \leq_\ast y$ when $x \leq y$ in $\Sigma$ and $uv \leq_\ast u'v'$ when $u \leq_\ast u'$ and $v \leq_\ast v'$ – informally, $w \leq_\ast w'$ if $w'$ can be obtained from $w$ by inserting new letters and upgrading existing ones. This last example of a WQO is the primary one this work is concerned with. When $(\Sigma, =)$ is a finite alphabet the upwards-closed sets of $(\Sigma^*, \leq_\ast)$ are called *piecewise-testable languages* in formal language theory: they are the ones specified by unions of regular expressions of the shape $\Sigma^* \sigma_1 \Sigma^* \cdots \Sigma^* \sigma_n \Sigma^*$ with $\sigma_i \in \Sigma$. It is easy to see that if $\Sigma$ is still finite but now equipped with a non-trivial QO structure, the upwards-closed sets of $(\Sigma^*, \leq_\ast)$ are still regular languages.

The last missing ingredient to understand Goubault-Larrecq's generalization of Valk and Jantzen's result is the notion of *ideal*: an ideal $I$ is a non-empty, downwards-closed and *directed* subset, the latter meaning that for every $x, y \in I$, there is a $z$ greater than both $x$ and $y$ in $I$. Denote by $\text{Idl}(X, \leq)$ the set of ideals of $(X, \leq)$ ordered by inclusion. Notice that for every $x \in D$, $\downarrow x$ is an ideal, called a *principal* one.

**► Theorem 2 (generalized Valk-Jantzen lemma, [9, Theorem 1]).** Let $(X, \leq)$ be a WQO, and $U$ an upwards-closed subset thereof. Given an oracle that decides for any $I \in \text{Idl}(X, \leq)$ whether $U$ intersects $I$, a minimal finite basis of $U$ is computable$^1$.

For $D = \mathbb{N}^k$, Theorem 2 is Valk and Jantzen's original result: the ideals of $\mathbb{N}^k$ are exactly the $I_z$'s for $z$ ranging in $(\mathbb{N}_* \cup \{\infty\})^k$ [10, §3.1.2 and 4.3]. Consider now the case $(\Sigma^*, \leq_\ast)$ where $(\Sigma, \leq)$ is a finite quasi-ordered alphabet. Then the ideals of $(\Sigma^*, \leq_\ast)$ are the regular languages

<footnote n="1">¹ Of course this theorem also assumes that $(X, \le)$ and $\text{Idl}(X, \le)$ are effective, in a way we do not describe here as all the instances we consider will indeed be so. The precise requirements are given in [9, Definitions 3 and 5].</footnote>
specified by the following class of regular expressions, called *-products [10, Theorem 4.11]. A
*-product is any finite concatenation $P := \mathfrak{A}_1 \dots \mathfrak{A}_n$ of atomic expressions, where an atomic
expression $\mathfrak{A} := \sigma^? | (\Sigma')^*$ is either some $\sigma^? = \{\varepsilon\} \cup \{\sigma' \in \Sigma \mid \sigma' \le \sigma\}$ for $\sigma \in \Sigma$, or some
$(\Sigma')^* = \{\sigma_1 \dots \sigma_n \mid n \in \mathbb{N}$ and $\forall i, \sigma_i \in \Sigma'$} \text{ for } \Sigma' \subseteq \Sigma \text{ non-empty and downwards-closed. By
abuse of language, we will often speak of a } *\text{-product to mean the ideal it specifies. The
instance of Theorem 2 for subword orderings now reads:

**Corollary 3** ([9, Theorem 2]). Fix a finite quasi-ordered alphabet $(\Sigma, \leq)$ and an upwards-closed subset $U$ of $(\Sigma^*, \leq_*)$. Given an oracle that decides for any $*\text{-product } P$ whether $U$ intersects $P$, a minimal finite basis of $U$ is computable.

This instance of Theorem 2 is especially interesting in that subword orderings are one of the
simplest example of WQOs for which computing intersections of ideals is not polynomial-
time [10, §6.3].

**Structure and contributions**

In this work we describe a new algorithm that proves Corollary 3, using active learning of automata. We then show that the 1985 result of Valk and Jantzen reduces to this Corollary 3, and thus to the 1987 result of Angluin.

In Section 2, we recall and discuss Goubault-Larrecq's original proof of Corollary 3.
On the way to a new proof, we describe in Section 3, as our first contribution, a new
$L^*$-like algorithm (Theorem 9) for learning quasi-ordered automata, a family of automata
corresponding to regular languages that are upwards-closed. In Section 4, we show as a
second contribution how this algorithm for actively learning quasi-ordered automata can
be used to prove Corollary 3 (Theorem 10). The automata-based approach and the active
learning procedure help alleviate the technical details of Goubault-Larrecq's original proof.
In Section 5, we finally show how Valk-Jantzen-style learnability of a WQO is stable under
quotients: in particular, because Corollary 3 holds for finitely generated free monoids, it
also holds for finitely generated monoids. As a third contribution, we thus extend the
class of WQOs for which Goubault-Larrecq's general Theorem 2 holds, and we retrieve in
particular Valk and Jantzen's original result as $\mathbb{N}^k$ is the free commutative monoid on $k$
letters (Example 13).

**2 A proof by rewriting of regular expressions**

In this section we first recall and discuss the proof of the generalized Valk-Jantzen lemma
in the case we focus on in this paper, subword orderings. This proof is obtained by
instantiating [9, Theorem 1]'s generic proof in this case.

**Corollary 3** ([9, Theorem 2]). Fix a finite quasi-ordered alphabet $(\Sigma, \leq)$ and an upwards-closed subset $U$ of $(\Sigma^*, \leq_*)$. Given an oracle that decides for any $*\text{-product } P$ whether $U$ intersects $P$, a minimal finite basis of $U$ is computable.

**Proof.** A minimal finite basis of $U$ can always be derived from a non-minimal one by removing redundant elements: if $U = \uparrow B$ and $b_1, b_2 \in B$ with $b_1 \leq b_2$, then still $U = \uparrow (B - \{b_2\})$. Hence, without loss of generality, we now describe a procedure that computes a non-necessarily minimal basis.

Start with $B = \emptyset$. Enumerate all the words in $\Sigma^*$. For each such $w = \sigma_1 \cdots \sigma_n$, check
if $w \in U$: because $U$ is upwards-closed, $w \in U$ if and only if $U$ intersects the $*$-product
$\downarrow w = \sigma_1^? \cdots \sigma_n^?$, and this can be checked by querying the oracle. If $w \in U$, add $w$ to $B$, and
just move on to the next word otherwise.
16:4 Active Learning of Upward-Closed Sets of Words

By construction, it is always true that $B \subseteq U$. Because $U$ is upwards-closed, it is hence also always true that $\uparrow B \subseteq \uparrow U = U$. On the other hand, every time a word is added to $B$ and $B$ changes, it is possible to check with the help of the oracle whether, conversely, $U \subseteq \uparrow B$. To check this, notice that it holds if and only if $U \cap (\uparrow B)^c = \emptyset$. But $(\uparrow B)^c$ is downwards-closed, and it is a general fact of WQOs that any downwards-closed set is a finite union of ideals [10, Lemma 2.6 and Proposition 2.10], so that $(\uparrow B)^c = P_1 \cup \cdots \cup P_n$ for some $n \in \mathbb{N}$ and some $*$-products $(P_i)_{1 \le i \le n}$. Hence if such $P_i$'s are computable from $B$, one can check whether $U \subseteq \uparrow B$ by asking the oracle whether $U$ intersects any of the $P_i$'s.

Let us now see how to compute these $P_i$'s. Note that the fact that this can be done means that $(\Sigma^*, \le_*)$ has the *effective complement property* [9, Definition 5], which is one of the effectivity conditions we omitted in the generic Theorem 2. We do not give the full construction here as it is a bit technical, and only recall the two main steps instead.

- For every $b \in B$, $(\uparrow b)^c$ can be written as a union of $*$-products, each informally obtained by disallowing one letter from $b$ to appear, see also [10, Lemma 4.14] for more details.

- Then $(\uparrow B)^c = \bigcap_{b \in B} (\uparrow b)^c$ can be rewritten as the union of all intersections of any two $*$-products appearing in the decompositions of two different $b, b' \in B$. The intersection of two $*$-products can always be rewritten as a union of $*$-products [10, Lemma 4.16], and hence $(\uparrow B)^c$ can be rewritten into a union of $*$-products.

All in all, we always have that $\uparrow B \subseteq U$, and every time $B$ changes we can check whether $U \subseteq \uparrow B$ and thus whether $U = \uparrow B$. This must be the case after having considered a finite number of words: $U$ has a finite basis $B'$ as $(\Sigma^*, \le_*)$ is a WQO, and it must be that $B' \subseteq B$ once all of $B'$'s words have been considered. $\quad$

The main appeal of the above proof is its genericity and modularity: it works in fact for any WQO that can be shown to be sufficiently effective, in particular having the aforementioned effective complement property – an effective way to transform the complement of an upwards-closed set into a union of ideals.

What hinders the algorithm from being polynomial-time is the rewriting of regular expressions into unions of $*$-products (which we did not describe in detail), and the brute-force enumeration of words. While we do not claim to give another algorithm with better asymptotic complexity, this brute-force enumeration seems particularly inefficient and it is natural to try to improve it, with heuristics for instance.

Another concern that could be raised is the use of bases to represent languages. These are usually represented by automata instead, and this can be exponentially more compact: consider for instance $U$ to be the set of all words of length at least $n$, whose minimal basis contains $|\Sigma|^n$ words but for which an $(n+1)$-state automaton is given in Figure 1a. Note that this is not always the case: the upwards-closed language $\uparrow\{\sigma_1, \sigma_2, \dots, \sigma_n\}$ has a much more compact representation in its minimal basis than in its minimal automaton. For instance in the case $n=3$, the minimal automaton for that language is depicted in Figure 1b. In general, converting between bases and automata may thus be costly, and it is all the more interesting to also have an algorithm for Corollary 3 that works with automata instead of bases.

In the rest of this work we address these two concerns by shedding the light of active learning of automata on the above proof of Corollary 3. It is quite reasonable to believe that MAT-based learning should be related to this result. Indeed, looking closely at the proof, we see that the oracle is really used in two distinct ways: for checking whether a word belongs to $U$ – which is reminiscent of the membership queries to an MAT – and for checking whether a set $B$ is a basis of $U$ – which is reminiscent of the equivalence queries to an MAT. While Angluin's $L^*$ algorithm is only concerned with DFAs and does not involve any QOs, the recent advances providing categorical frameworks for active learning of automata are a strong hint that this kind of learning is versatile enough to also be done in a quasi-ordered setting.
<figure><img src="image_4.png" /><figcaption>(a) An automaton recognizing the language $\uparrow(\Sigma^n)$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) An automaton recognizing the language $\uparrow\{a, bb, ccc\}$.</figcaption></figure>

■ **Figure 1** Examples of quasi-ordered automata (Definition 4). All the automata we consider are assumed to be complete: if a transition $q \xrightarrow{\sigma} \cdot$ is not depicted, then it is assumed to be looping, i.e. $\delta_\sigma(q) = q$. Initial states are depicted with an incoming arrow, accepting states with a double circle. The quasi-order on states is not explicitly depicted, but it always goes from left to right.

**3 Active learning of quasi-ordered automata**

We now describe how active learning of automata can indeed be done in a quasi-ordered setting. Because we are only trying to learn those languages that are upwards-closed, DFAs are too general for our purpose. We will focus on a more restricted family of automata:

► **Definition 4** (quasi-ordered automaton). Let $(\Sigma, \leq)$ be a finite quasi-ordered alphabet. A quasi-ordered automaton on $(\Sigma, \leq)$ is a tuple $((Q, \sqsubseteq), q_0, \delta, F)$ where:

■ $(Q, \sqsubseteq)$ is a finite QO of states;

■ $q_0 \in Q$ is the initial state;

■ $\delta: (\Sigma, \leq) \times (Q, \sqsubseteq) \to (Q, \sqsubseteq)$ is a monotone transition function such that $q \sqsubseteq \delta(\sigma, q)$ for every $(\sigma, q) \in \Sigma \times Q$;

■ $F \subseteq Q$ is an upwards-closed subset of accepting states.

The language recognized by a quasi-ordered automaton $((Q, \sqsubseteq), q_0, \delta, F)$ is the language recognized by its underlying DFA $(Q, q_0, \delta, F)$.

Note that the quasi-order on $(\Sigma, \leq) \times (Q, \sqsubseteq)$ is given by $(\sigma, q) \leq (\sigma', q')$ if and only if $\sigma \leq \sigma'$ and $q \sqsubseteq q'$, so that $\delta$ being monotone means: if $\sigma \leq \sigma'$ and $q \sqsubseteq q'$, then $\delta(\sigma, q) \sqsubseteq \delta(\sigma', q')$. $\delta$ extends to a monotone function $\delta^*: (\Sigma^*, \leq_*) \times (Q, \sqsubseteq) \to (Q, \sqsubseteq)$, and we also write $\delta_w^*: (Q, \sqsubseteq) \to (Q, \sqsubseteq)$ for the monotone function $q \mapsto \delta(w, q)$.

► **Remark 5.** The category-enclined reader may notice that quasi-ordered automata are equivalently certain **QO**-enriched functors, where **QO** is the category of quasi-orders and monotone functions between them. Let indeed $\mathbf{I}_{(\Sigma^*, \leq_*)}$ be the **QO**-enriched category freely generated by the **QO**-enriched quiver below (the QO of edges $st \to st$ is $(\Sigma, \leq$)), with the additional requirement that $\varepsilon: st \to st$ be smaller than every $w: st \to st$

<figure><img src="image_6.png" /></figure>
16:6 Active Learning of Upward-Closed Sets of Words

Then quasi-ordered automata are exactly enriched functors $I_{(\Sigma^*, \leq_*)} \to \mathbf{QO}$ that send in on the singleton QO and out on $2 = \{\perp < \top\}$. The active learning algorithm of Theorem 9 below could thus be obtained by extending the functorial framework of [5, 6] to enriched functors, but for the sake of conciseness we do not delve in this as we would only end up using the QO-enriched case here.

It seems the full expressiveness of enriched functors is needed to model quasi-ordered automata. Classical functors $I_{(\Sigma^*, \leq_*)} \to \mathbf{QO}$ indeed only encompass that each $\delta_\sigma: (Q, \sqsubseteq) \to (Q, \sqsubseteq)$ be monotone, but not that $\delta: (\Sigma^*, \leq) \times (Q, \sqsubseteq) \to (Q, \sqsubseteq)$ be monotone. The latter condition can be encompassed by considering instead pointed QO-coalgebras for the functor $2 \times \mathbf{QO}((\Sigma^*, \leq), -)$, but these in turn need not satisfy that $q \sqsubseteq \delta(\sigma, q)$ for every $(\sigma, q) \in \Sigma \times Q$, which is crucial in proving that $\delta^*: (\Sigma^*, \leq_*) \times (Q, \sqsubseteq) \to (Q, \sqsubseteq)$ is monotone, itself key in proving that quasi-ordered automata recognize upwards-closed languages (Lemma 6 below).

Quasi-ordered automata are indeed a sensible family of automata to consider when working with upwards-closed languages:

**Lemma 6.** The language recognized by a quasi-ordered automaton on $(\Sigma, \leq)$ is upwards-closed in $(\Sigma^*, \leq_*)$.

*Proof.* Let $L$ be a language recognized by a quasi-ordered automaton $((Q, \sqsubseteq), q_0, \delta, F)$ on $(\Sigma, \leq)$, and consider some $w \leq_* w'$ $\in \Sigma^*$. Because $\delta^*: (\Sigma^*, \leq_*) \times (Q, \sqsubseteq) \to (Q, \sqsubseteq)$ is monotone, $\delta^*(w, q_0) \sqsubseteq \delta^*(w', q_0)$. In particular if $\delta^*(w, q_0) \in F$ and $w \in L$, then because $F$ is upwards-closed $\delta^*(w', q_0) \in F$ and $w' \in L$ as well: $L$ is upwards-closed. $\quad \blacksquare$

**Proposition 7.** Let $(\Sigma, \leq)$ be a finite quasi-ordered alphabet. Given a reachable DFA $A$ on $\Sigma$, it can be decided whether $A$ recognizes a language that is upwards-closed in $(\Sigma^*, \leq_*)$. If this is the case, $A$ is in fact a quasi-ordered automaton and the corresponding QO is computable; otherwise two words $w \leq_* w'$ in $(\Sigma^*, \leq_*)$ such that $A$ accepts $w$ but not $w'$ are computable. All of this can moreover be done in polynomial time in the size of $A$.

*Proof.* Let $A = (Q, q_0, \delta, F)$. Define an order on $Q$ as follows:

$$q \sqsubseteq q' \iff \forall w \in \Sigma^*, \delta_w^*(q) \in F \Rightarrow \delta_w^*(q') \in F$$

Deciding whether $q \sqsubseteq q'$ amounts to checking whether the language $L_q$ recognized when making $q$ initial is included in the language $L_{q'}$ recognized when making $q'$ initial. It is standard that this can be done in polynomial time, see e.g. [14, Theorem 2.4]: compute an automaton recognizing $L_q \cap L_{q'}^c$, and decide whether it recognizes an empty language. If this is not the case, an additional $w \in L_q \cap L_{q'}^c$, i.e. such that $\delta_w^*(q) \in F$ but $\delta_w^*(q') \notin F$, is computable in polynomial time.

If this order makes $A$ into a quasi-ordered automaton, then by Lemma 6 $A$ recognizes an upwards-closed language. Otherwise, we show next that the language recognized by $A$ cannot be upwards-closed, and construct two words $w \leq_* w'$ such that $A$ accepts $w$ but not $w'$.

Here we use that $A$ is reachable so that for every $q \in Q$, there is a $u \in \Sigma^*$ such that $q = \delta_u^*(q_0)$. If $\sqsubseteq$ fails to make into $A$ into a quasi-ordered automaton, then either

- $F$ is not upwards-closed: this is in fact not possible, as $q \in F$ means $\delta_\epsilon(q) \in F$ and thus, if $q \sqsubseteq q'$, $q' = \delta_\epsilon(q') \in F$ as well;

- there are some $q \sqsubseteq q' \in Q$, $\sigma \in \Sigma$ such that $\delta(\sigma, q) \sqsupseteq \delta(\sigma, q')$: this is not possible neither, since $q \sqsubseteq q'$ implies that for every $v \in \Sigma^*$, $\delta_v^*(\delta_\sigma(q)) \in F \Rightarrow \delta_v^*(\delta_\sigma(q')) \in F$, and thus that $\delta_\sigma(q) \sqsubseteq \delta_\sigma(q')$;
- there are some $q \in Q$, $\sigma \preceq \sigma' \in \Sigma$ such that $\delta(\sigma, q) \nsubseteq \delta(\sigma', q)$: taking $u, v \in \Sigma^*$ respectively such that $\delta_u^*(q_0) = q$ and $\delta_v^*(\delta_\sigma(q)) \in F$ but $\delta_v^*(\delta_\sigma(q)) \notin F$, then A accepts $u\sigma v$ but not $u\sigma'v$, yet $u\sigma v \preceq_* u\sigma'v$;

- there are some $q \in Q$, $\sigma \in \Sigma$ such that $q \nsubseteq \delta_\sigma(q)$: taking $u, v \in \Sigma^*$ respectively such that $\delta_u^*(q_0) = q$ and $\delta_v^*(q) \in F$ but $\delta_v^*(\delta_\sigma(q)) \notin F$, then A accepts $uv$ but not $u\sigma v$, yet $uv \preceq_* u\sigma v$. ◀

Given an upwards-closed language $U$, we call minimal quasi-ordered automaton the minimal DFA recognizing $U$, equipped with the quasi-order described in the proof of Proposition 7. The minimal quasi-ordered automaton is state-minimal among all quasi-ordered automata recognizing $U$, and it has a very specific structure, simple examples of which are given by the automata in Figure 1:

**Lemma 8 (structure of the minimal quasi-ordered automata).** Let $A = ((Q, \sqsubseteq), q_0, \delta, F)$ be the minimal quasi-ordered automaton for an upwards-closed language $U$. Then

1. $(Q, \sqsubseteq)$ is not just a quasi-order, but an order, so that, except for transitions $q \stackrel{\sigma}{\to} q$ that loop on a state, the underlying graph of the automaton is acyclic;

2. the initial state is the minimum of $(Q, \sqsubseteq)$;

3. unless $U$ is empty, an accepting state is reachable from any state;

4. there is at most one accepting state, and it is the maximum of $(Q, \sqsubseteq)$.

**Proof.** We implicitly use the Myhill-Nerode theorem, and the quasi-order constructed in the proof of Proposition 7.

1. If two states $q$ and $q'$ are such that $q \sqsubseteq q'$ and $q' \sqsubseteq q$, then for every $w \in \Sigma^*$, $\delta_w^*(q) \in F \iff \delta_w^*(q) \in F$. In a minimal DFA, this can never be true of two distinct states (otherwise the two states could be merged).

2. For every $q = \delta_u^*(q_0) \in Q$ and $v \in \Sigma^*$ such that $\delta_v^*(q_0) \in F$, $v \in U$. $U$ is upwards-closed, hence $uv \succeq v$ is in $U$ as well and $\delta_v^*(q) = \delta_{uv}^*(q_0) \in F: q_0 \sqsubseteq q$.

3. Pick some $q \in Q$ and $v \in U$. The argument for item 2 above applies.

4. Because the language recognized by the automaton is upwards-closed, any accepting state $q$ is such that $\delta_w^*(q) \in F$ for every $w \in \Sigma^*$. Hence the uniqueness of such an accepting state, and its maximality. ◀

We now consider the problem of learning such a minimal quasi-ordered automaton from an MAT. For a fixed upwards-closed subset $U$ of $(\Sigma^*, \preceq_*)$, suppose given an oracle able to answer two kinds of queries:

- *membership queries* – given a word $w \in \Sigma^*$, the oracle decides whether $w \in U$ –

- *equivalence queries* – given a quasi-ordered automaton $A$ that is minimal for the upwards-closed language it recognizes, the oracle decides whether this language is $U$, and, in the negative case, also outputs a counterexample word $w \in \Sigma^*$ such that $w$ is in $U$ but is not recognized by $A$, or conversely.

Can $U$ be learned by querying this oracle a finite number of times? We answer this in the positive:

**Theorem 9 (active learning of quasi-ordered automata).** Suppose given an MAT as above. There is an algorithm that computes the minimal quasi-ordered automaton recognizing $U$, and its complexity is polynomial in the size of this minimal automaton and the maximum length of a counterexample outputted by the oracle.

**Proof.** We prove this by giving a polynomial-time reduction to the active learning problem for DFAs, where $U$ is only seen as a regular language, the complexity result being that of the classical active learning algorithm of Angluin [1]. We therefore explain how to implement
16:8 Active Learning of Upward-Closed Sets of Words

an oracle in the classical setting, call it ORACLE$_U$, from the oracle in the quasi-ordered setting, call it ORACLE$_{(U,\leq_*)}$: one can then learn the minimal DFA recognizing the regular language $U$ in polynomial-time using the classical active learning algorithm, and then equip this minimal DFA with a quasi-order in polynomial-time as explained in Proposition 7.

First, any membership query to ORACLE$_U$ can simply be forwarded to ORACLE$_{(U,\leq_*)}$: when it comes to membership queries, the two oracles have the same computing power. Consider now a DFA $A$ minimal for the language it recognizes, given to ORACLE$_U$ for an equivalence query. By Proposition 7, one can then check in polynomial-time whether $A$ is in fact a quasi-ordered automaton:

- if it is the case we also get the QO structure on $A$, and can then forward $A$ to ORACLE$_{(U,\leq_*)}$ for an equivalence query;

- otherwise, we get some $w \leq_* w'$ such that $A$ recognizes $w$ but not $w'$, and one of these two words must then be a counterexample to $A$ recognizing $U$. ◀

4 A proof by active learning of automata

We now give a new proof of Corollary 3, by reducing it to the problem of actively learning quasi-ordered automata.

**Theorem 10.** Fix a finite quasi-ordered alphabet $(\Sigma, \leq)$ and an upwards-closed subset $U$ of $(\Sigma^*, \leq_*)$. Given an oracle that decides for any $*-product P$ whether $U$ intersects $P$, a minimal quasi-ordered automaton recognizing $U$ is computable.

**Proof.** We reduce this problem to that of actively learning quasi-ordered automata, for which we gave a polynomial time algorithm in Theorem 9. In other words, we describe how to implement an MAT in the quasi-ordered setting by checking whether $U$ intersects some well-chosen $*-products.

Answering a membership query for a $w = \sigma_1 \cdots \sigma_n \in \Sigma^*$ can be done by checking whether $U$ intersects $\sigma_1^? \cdots \sigma_n^?$: because $U$ is upwards-closed, this is the case if and only if $w \in U$. Consider now some minimal quasi-ordered automaton $A = ((Q, \sqsubseteq), q_0, \delta, F)$ submitted to the MAT for an equivalence query. We decide whether $A$ recognizes $U$ in two steps, implicitly using the properties of $A$ described in Lemma 8 and assuming $A$ does not recognize the empty language.

- First, we check whether $U$ contains the language recognized by $A$. For this, enumerate all the paths $q_0 \xrightarrow{\sigma_1} \cdots \xrightarrow{\sigma_n} q_n$ in $A$ that go from the initial state $q_0$ to the accepting state $q_n \in F$, that are *strictly increasing* – $q_0 \sqsubseteq q_1 \sqsubseteq \cdots \sqsubseteq q_{n-1} \sqsubseteq q_n$ – and that are *minimal* – for every $q_i \xrightarrow{\sigma_i} q_{i+1}$, $\sigma_i$ is minimal among the letters $\sigma$ such that $\delta_\sigma(q_i) = q_{i+1}$ (see Figure 2a for an example within the automaton of Figure 1b). Check whether $\sigma_1 \cdots \sigma_n \in U$ with a membership query. If this is not the case, $\sigma_1 \cdots \sigma_n$ is a counterexample. Otherwise, if no path yields such a counterexample, then all the words accepted by $A$ are in $U$ as well: if $A$ accepts $w$, then, for one of the paths $q_0 \xrightarrow{\sigma_1} \cdots \xrightarrow{\sigma_n} q_n$ enumerated above, $w \succeq_* \sigma_1 \cdots \sigma_n$ and $w \in U$ as $U$ is upwards-closed.

- Second, we check whether $U$ is contained in the language recognized by $A$, i.e. whether every word not accepted by $A$ is not in $U$ neither. For this, enumerate all the strictly increasing paths $q_0 \xrightarrow{\sigma_1} \cdots \xrightarrow{\sigma_n} q_n$ in $A$ that go from the initial state $q_0$ to a non-accepting state $q_n \notin F$ one transition away from the accepting state (see Figure 2b for an example within the automaton of Figure 1b). Let $\Sigma_i \subseteq \Sigma$ be the subset of these letters $\sigma$ for which $\delta_\sigma(q_i) = q_i$. Then any word $w$ that is not accepted by $A$ must be in one of the $*-products \Sigma_0^* \sigma_1^? \Sigma_1^* \cdots \Sigma_{n-1}^* \sigma_n^? \Sigma_n^*$ corresponding to one of these paths: the run for $w$ in $A$ must stop.
in a non-accepting state, and, since $ww'$ is accepted by $A$ for any $w'$ accepted by $A$, the run for $w$ can be completed into a run that ends in the accepting state. It is thus enough to check whether $U$ intersects any of these $*$-products. If this is the case for one of these $*$-products $P$, then enumerating the words in $P$ will end up producing a counterexample $w \in \Sigma^*$ such that $w \in U$ but $w$ is not accepted by $A$. ◀

<figure><img src="image_7.png" /><figcaption>(a) Two strictly increasing paths to the accepting state. They are minimal as soon as $a \preceq b \Rightarrow b \preceq a$ in $(\Sigma, \preceq)$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(b) Two strictly increasing paths to non-accepting states one transition away from the accepting state.</figcaption></figure>

Figure 2 Strictly increasing paths in the automaton of Figure 1b.

Note that a finite basis of $U$ can then be obtained from its minimal quasi-ordered automaton by enumerating words labelling minimal strictly increasing paths.

This new proof partially addresses the two concerns highlighted in Section 2: upwards-closed languages are now represented using automata, and not finite bases, and the MAT learning procedure (that we leave as a black box) takes care of efficiently enumerating words and constructing guesses to submit for an equivalence query. The reduction we provide is where the non-polynomial-time part happens: what now makes the algorithm exponential-time is the enumeration of paths to the accepting state in a minimal quasi-ordered automaton, and the brute-force enumeration of words in a $*$-product to produce a counterexample.

## 5 The Valk-Jantzen lemma for quotients of WQOs

We now move on from quasi-orders on the finitely generated free monoid $\Sigma^*$ of words, to quasi-orders on finitely generated monoids. We thus consider a monoid $M$ equipped with a quasi-order $\leq_M$, and generated by a finite quasi-ordered alphabet $(\Sigma, \preceq)$: we assume there is a surjective homomorphism of monoids $e_M: \Sigma^* \to M$ that is also a monotone function $(\Sigma^*, \preceq_*) \to (M, \preceq_M)$. The surjectivity and monotonicity of $e_M$ automatically makes $(M, \preceq_M)$ into a WQO, and $e_M$ can be used to describe the ideals of $(M, \preceq_M)$:

**Lemma 11 (ideals of a quasi-ordered monoid).** The ideals of a quasi-ordered monoid $(M, \preceq_M)$ generated by $(\Sigma, \preceq)$ are exactly the downward-closures of images of languages specified by $*$-products:

$$ \mathrm{Idl}(M, \preceq_M) = \{ \downarrow e_M[I] \mid I \in \mathrm{Idl}(\Sigma^*, \preceq_*) \} $$

*Proof.* This result is an instance of [10, Proposition 5.1], but the phrasing differs slightly so we repeat the proof here for completeness.

On the one hand, if $I$ is an ideal of $(\Sigma^*, \preceq_*)$ (a language described by a $*$-product) then $\downarrow e_M[I]$ is an ideal of $(M, \preceq_M)$. Indeed, $e_M[I]$ is non-empty and directed because $I$ is: for every $x, y \in e_M[I]$, write $x = e_M(x')$ and $y = e_M(y')$ with $x', y' \in I$; then there
16:10 Active Learning of Upward-Closed Sets of Words

is a $z' \in I$ such that $z' \succeq_* x'$ and $z' \succeq_* y'$, so that $e_M(z') \in e_M[I]$, $e_M(z') \succeq_M e_M(x')$ and $e_M(z') \succeq_M e_M(y')$. $\downarrow e_M[I]$ is thus also non-empty and directed, and it is of course downwards-closed: it is an ideal.

On the other hand, we show that every ideal of $(M, \preceq_M)$ is of the shape $\downarrow e_M[I]$ for some $I \in \mathrm{Idl}(\Sigma^*, \preceq_*)$. To see this, we use the following characterization of ideals in a WQO: a downwards-closed subset $D$ can always be written as a finite union $D = \bigcup_{i=1}^n I_i$ of ideals [10, Lemma 2.6(2)], and $D$ is an ideal if and only if it is join-irreducible, i.e. for every finite family of downwards-closed subsets $D_1, \dots, D_n$, if $D = \bigcup_{i=1}^n D_i$ then $D = D_i$ for some $1 \le i \le n$ [10, Lemma 2.5]. Consider thus a downwards-closed subset $D$ of $(M, \preceq_M)$. Then $e_M^{-1}[D]$ is downwards-closed in $(\Sigma^*, \preceq_*)$, hence $e_M^{-1}[D] = \bigcup_{i=1}^n I_i$ for some $I_1, \dots, I_n \in \mathrm{Idl}(\Sigma^*, \preceq_*)$. But then

$$D = \downarrow e_M[e_M^{-1}[D]] = \left\downarrow e_M\left[\bigcup_{i=1}^{n} I_i\right] = \left\downarrow \bigcup_{i=1}^{n} e_M[I_i] = \bigcup_{i=1}^{n} \downarrow e_M[I_i]$$

hence when $D$ is an ideal it must be equal to $\downarrow e_M[I_i]$ for some $1 \le i \le n$.

If $P$ is a $*$-product that specifies an ideal $I$ of $(\Sigma^*, \preceq_*)$, write by abuse of notation $e_M[P]$ for the downward-closed set $e_M[I]$ of $(M, \preceq_M)$. Finitely generated quasi-ordered monoids also enjoy a Valk-Jantzen-like result:

**Theorem 12.** Fix a finite quasi-ordered alphabet $(\Sigma, \preceq)$ and an upwards-closed subset $U$ of a quasi-ordered monoid $(M, \preceq_M)$ generated by $(\Sigma, \preceq)$. Given an oracle that decides for any $*$-product $P$ whether $U$ intersects $\downarrow e_M[P]$, a finite basis of $U$ is computable as soon as $e_M$ is.

**Proof.** We reduce this problem to that of computing a finite basis of the upwards-closed subset $e_M^{-1}[U]$ of $(\Sigma^*, \preceq_*)$. For this it is enough, by Corollary 3, to decide, given a $*$-product $P$, whether $e_M^{-1}[U]$ intersects $P$. But $e_M^{-1}[U]$ intersects $P$ if and only if $U$ intersects $\downarrow e_M[P]$; if $x \in e_M^{-1}[U] \cap P$, then $e_M(x) \in U \cap \downarrow e_M[P]$; conversely, if $x \in U \cap \downarrow e_M[P]$, then there is a $y \in P$ such that $x \le e_M(y)$, and of course $e_M(y) \in U \cap \downarrow e_M[P]$ as $U$ is upwards-closed, so that $y \in e_M^{-1}[U] \cap P$.

Once a minimal finite basis $B$ of $e_M^{-1}[U]$ is computed, $e_M[B]$ is a finite basis of $U$. Note that $e_M[B]$ need not be a minimal basis, and need not be effectively reducable to a minimal one, as that would require the quasi-order $\preceq_M$ on $M$ to be decidable, an assumption we have not made.

Theorem 12 is not just an instance of Goubault-Larrecq's [9, Theorem 1]. Indeed, the latter result requires an effectivity assumption (namely, the effective complement property we mentioned in the proof in Section 2) which need not be true of any quotient of the free monoid, as discussed in [10, Theorem 5.2].

We restricted ourselves to monoids, but the careful reader may have noticed that nowhere in the proofs of Lemma 11 and Theorem 12 we actually use the fact that $(\Sigma^*, \preceq_*)$ is a subword ordering or that $M$ is a monoid. We could in fact have stated Theorem 12 more generally, and it would then informally read as follows. Fix a WQO $(X, \leq)$ for which Theorem 2 holds, a monotone surjection $e: (X, \leq) \to (Y, \leq')$, and an upwards-closed subset $U$ of $(Y, \leq')$. Then $(Y, \leq')$ is a WQO and, given an oracle that decides for any $I \in \mathrm{Idl}(X, \leq)$ whether $U$ intersects $\downarrow e[I]$, a finite basis of $U$ is computable. Again, we do not make this any more formal to avoid delving in the topic of effective representations of WQOs and their ideals.
**► Example 13.** Let $(\Sigma, =)$ be an alphabet with $k$ letters. Then $\mathbb{N}^k$, also known as the free commutative monoid with $k$ generators, is a quotient of $\Sigma^*$: the surjection $|-| : \Sigma^* \to \mathbb{N}^k$, written $|w| = (|w|_1, \dots, |w|_k)$ counts the number of appearances of each letter in a word. This surjection is monotone from the subword ordering on $\Sigma^*$ to the component-wise ordering on $\mathbb{N}^k$. Given a $*$-product $\Sigma'_0\sigma'_1\Sigma'_1 \cdots \Sigma'_{n-1}\sigma'_n\Sigma'_n$, the downward-closure of its image by $|-|$ is the subset of elements $(x_1, \dots, x_k) \in \mathbb{N}^k$ such that, for every $1 \le i \le k$,

- $x_i \in \mathbb{N}$ if the $i$-th letter appears in $\bigcup_{j=0}^n \Sigma'_j$;

- $x_i \le |\sigma_1 \cdots \sigma_n|_i$ otherwise.

Hence the corresponding instance of Theorem 12 is Valk and Jantzen's original 1985 result, except we have now proved it by reducing it to Angluin's 1987 active learning algorithm.

Representing elements of $\mathbb{N}^k$ as $k$-letter words is of course not very efficient, and what is interesting in Example 13 is how it reduces the result of Valk and Jantzen to that of Angluin. But for other non-trivial monoids, using word representations may still be a sensible choice: a trace monoid where only a few pairs of letters are allowed to commute, for instance, is very close to a monoid of words.

# 6 Conclusion and further work

In this work we have provided a new proof, relying on active learning of automata, of the generalized Valk-Jantzen lemma for subword orderings. This reduces in particular the original 1985 result by Valk and Jantzen for $\mathbb{N}^k$ to Angluin's 1987 $L^*$ algorithm. Along the way, we have described a new MAT-based learning algorithm, for quasi-ordered automata, and have extended Goubault-Larrecq's generalized Valk-Jantzen lemma to finitely generated monoids.

We have restricted ourselves to words on finite alphabets, but there are other WQOs for which the generalized Valk-Jantzen lemma could reduce to an MAT-based learning algorithm.

- Words on infinite (or very large) alphabets: this would require regrouping transitions in quasi-ordered automata by upwards-closed subsets, so that they can still be finitely represented. This use of an additional structure to represent infinite alphabets finitely also comes up with *nominal automata* [4]. More generally, enriched functors could provide a unifying framework for such state-machines on infinite alphabets: a Myhill-Nerode theorem for topos-enriched automata is notably given in [11].

- Tree orderings: trees on well quasi-ordered families of terms can naturally be well quasi-ordered themselves [13], their ideals can be characterized as regular tree expressions [8, §10], but “the technicalities are daunting” [10]. Perhaps an approach based on the active learning algorithm for tree automata described in [7] can soothe out these technicalities.

# References

1. Dana Angluin. Learning regular sets from queries and counterexamples. *Information and Computation*, 75(2):87-106, November 1987. doi:10.1016/0890-5401(87)90052-6.

2. Quentin Aristote. Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids. In *32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)*, volume 288 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 11:1–11:20, Dagstuhl, Germany, 2024. Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi:10.4230/LIPIcs.CSL.2024.11.

3. Simone Barlocco, Clemens Kupke, and Jurriaan Rot. Coalgebra Learning via Duality. In *Mikołaj Bojańczyk and Alex Simpson, editors, Foundations of Software Science and Computation Structures*, Lecture Notes in Computer Science, pages 62–79, Cham, 2019. Springer International Publishing. doi:10.1007/978-3-030-17127-8_4.

4. Mikołaj Bojańczyk, Bartek Klin, and Sławomir Lasota. Automata theory in nominal sets. *Logical Methods in Computer Science*, Volume 10, Issue 3, August 2014. doi:10.2168/LMCS-10(3:4)2014.
16:12 Active Learning of Upward-Closed Sets of Words

5 Thomas Colcombet and Daniela Petrisan. Automata Minimization: A Factorial Approach. Logical Methods in Computer Science, Volume 16, Issue 1, March 2020. doi:10.23638/LMCS-16(1:32)2020.

6 Thomas Colcombet, Daniela Petrisan, and Riccardo Stabile. Learning Automata and Transducers: A Categorical Approach. In Christel Baier and Jean Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021), volume 183 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CSL.2021.15.

7 Frank Drewes and Johanna Högberg. Learning a Regular Tree Language from a Teacher. In Zoltán Ésik and Zoltán Fülöp, editors, Developments in Language Theory, Lecture Notes in Computer Science, pages 279–291, Berlin, Heidelberg, 2003. Springer. doi:10.1007/3-540-45007-6_22.

8 Alain Finkel and Jean Goubault-Larrecq. Forward analysis for WSTS, part I: Completions. Mathematical Structures in Computer Science, 30(7):752–832, August 2020. doi:10.1017/S0960129520000195.

9 Jean Goubault-Larrecq. On a Generalization of a Result by Valk and Jantzen. Research Report LSV-09-09, École Normale Supérieure de Cachan, Cachan, May 2009. URL: https://hal.science/hal-03195658.

10 Jean Goubault-Larrecq, Simon Halfon, Prateek Karandikar, K. Narayan Kumar, and Philippe Schnoebelen. The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings. In Peter M. Schuster, Monika Seisenberger, Andreas Weiermann, Henrich Wansing, and Henrich Wansing, editors, Well-Quasi Orders in Computation, Logic, Language and Reasoning: A Unifying Concept of Proof Theory, Automata Theory, Formal Languages and Descriptive Set Theory, number 53 in Trends in Logic, pages 55–105. Springer Nature, Switzerland, 1 edition, 2020. doi:10.1007/978-3-030-30229-0_3.

11 Victor Iwaniack. Automata in W-Toposes, and General Myhill-Nerode Theorems. In Barbara König and Henning Urbat, editors, Coalgebraic Methods in Computer Science, volume 14617 of Lecture Notes in Computer Science, pages 93–113, Cham, 2024. Springer Nature Switzerland. doi:10.1007/978-3-031-66438-0_5.

12 Bart Jacobs and Alexandra Silva. Automata Learning: A Categorical Perspective. In Franck van Breugel, Elham Kashefi, Catuscia Palamidessi, and Jan Rutten, editors, Horizons of the Mind. A Tribute to Prakash Panangaden: Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday, pages 384–406. Springer International Publishing, Cham, 2014. doi:10.1007/978-3-319-06880-0_20.

13 J. B. Kruskal. Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture. Transactions of the American Mathematical Society, 95(2):210–225, 1960. doi:10.2307/1993287.

14 Christof Löding and Wolfgang Thomas. Automata on finite trees. In Jean-Éric Pin, editor, Handbook of Automata Theory, volume 1, pages 235–264. EMS Press, 1 edition, 2021. doi:10.4171/AUTOMATA-1/7.

15 Henning Urbat and Lutz Schröder. Automata Learning: An Algebraic Approach. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '20, pages 900–914, New York, NY, USA, July 2020. Association for Computing Machinery. doi:10.1145/3373718.3394775.

16 Rüdiger Valk and Matthias Jantzen. The residue of vector sets with applications to decidability problems in Petri nets. Acta Informatica, 21(6):643–674, March 1985. doi:10.1007/BF00289715.

17 Gerco van Heerdt, Clemens Kupke, Jurriaan Rot, and Alexandra Silva. Learning Weighted Automata over Principal Ideal Domains. In Jean Goubault-Larrecq and Barbara König, editors, Foundations of Software Science and Computation Structures, pages 602–621, Cham, 2020. Springer International Publishing. doi:10.1007/978-3-030-45231-5_31.

18 Gerrit K. van Heerdt. CALF - Categorical Automata Learning Framework. PhD thesis, University College London, London, UK, 2020. URL: https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.819869.