Active Learning of Upward-Closed Sets of Words

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\le 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=\mathrm{\varnothing }$. Enumerate all the words in ${\mathrm{\Sigma }}^{\ast }$. For each such $w={\sigma }_1\mathrm{\cdots }{\sigma }_n$, check if $w\in U$: because $U$ is upwards-closed, $w\in U$ if and only if $U$ intersects the $\ast$-product $\downarrow w={\sigma }_1^{\mathrm{?}}\mathrm{\cdots }{\sigma }_n^{\mathrm{?}}$, 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.

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=\mathrm{\varnothing }$. 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 \mathrm{\cdots }\cup P_n$ for some $n\in \mathbb{N}$ and some $\ast$-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 $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$ 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.

• $\mathrm{■}$

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

• $\mathrm{■}$

  Then $({\uparrow B)}^c={\bigcap }_{b\in B}({\uparrow b)}^c$ can be rewritten as the union of all intersections of any two $\ast$-products appearing in the decompositions of two different $b,b^{\prime }\in B$. The intersection of two $\ast$-products can always be rewritten as a union of $\ast$-products [10, Lemma 4.16], and hence $({\uparrow B)}^c$ can be rewritten into a union of $\ast$-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^{\prime }$ as $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$ is a WQO, and it must be that $B^{\prime }\subseteq B$ once all of $B^{\prime }$’s words have been considered. $◀$

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 aforementionned 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 $\ast$-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 ${\left|\mathrm{\Sigma }\right|}^n$ words but for which an $(n+1)$-state automaton is given in Figure 1(a). Note that this is not always the case: the upwards-closed language $\uparrow \{{\sigma }_1,{\sigma }_2^2,\mathrm{\dots },{\sigma }_n^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 1(b). 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 reminescent of the membership queries to an MAT – and for checking whether a set $B$ is a basis of $U$ – which is reminescent of the equivalence queries to an MAT. While Angluin’s $L^{\ast }$ 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.

Let $L$ be a language recognized by a quasi-ordered automaton $((Q,⊑),q_0,\delta ,F)$ on $(\mathrm{\Sigma },⪯)$, and consider some $w{⪯}_{\ast }{w}^{\prime }\in {\mathrm{\Sigma }}^{\ast }$. Because ${\delta }^{\ast }:({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })\times (Q,⊑)\to (Q,⊑)$ is monotone, ${\delta }^{\ast }(w,q_0)⊑{\delta }^{\ast }(w^{\prime },q_0)$. In particular if ${\delta }^{\ast }(w,q_0)\in F$ and $w\in L$, then because $F$ is upwards-closed ${\delta }^{\ast }(w^{\prime },q_0)\in F$ and $w^{\prime }\in L$ as well: $L$ is upwards-closed. $◀$

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

Deciding whether $q⊑q^{\prime }$ amounts to checking whether the language $L_q$ recognized when making $q$ initial is included in the language $L_{q^{\prime }}$ recognized when making $q^{\prime }$ 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^{\prime }}^c$, and decide whether it recognizes an empty language. If this is not the case, an additional $w\in L_q\cap L_{q^{\prime }}^c$, i.e. such that ${\delta }_w^{\ast }(q)\in F$ but ${\delta }_w^{\ast }(q^{\prime })\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{⪯}_{\ast }{w}^{\prime }$ such that $A$ accepts $w$ but not $w^{\prime }$.

Here we use that $A$ is reachable so that for every $q\in Q$, there is a $u\in {\mathrm{\Sigma }}^{\ast }$ such that $q={\delta }_u^{\ast }(q_0)$. If $⊑$ fails to make into $A$ into a quasi-ordered automaton, then either

• $\mathrm{■}$

  $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⊑q^{\prime }$, $q^{\prime }={\delta }_{\epsilon }(q^{\prime })\in F$ as well;

• $\mathrm{■}$

  there are some $q⊑q^{\prime }\in Q$, $\sigma \in \mathrm{\Sigma }$ such that $\delta (\sigma ,q)⋢\delta (\sigma ,q^{\prime })$: this is not possible neither, since $q⊑q^{\prime }$ implies that for every $v\in {\mathrm{\Sigma }}^{\ast }$, ${\delta }_v^{\ast }({\delta }_{\sigma }(q))\in F\Rightarrow {\delta }_v^{\ast }({\delta }_{\sigma }(q^{\prime }))\in F$, and thus that ${\delta }_{\sigma }(q)⊑{\delta }_{\sigma }(q^{\prime })$;

• $\mathrm{■}$

  there are some $q\in Q$, $\sigma ⪯{\sigma }^{\prime }\in \mathrm{\Sigma }$ such that $\delta (\sigma ,q)⋢\delta ({\sigma }^{\prime },q)$: taking $u,v\in {\mathrm{\Sigma }}^{\ast }$ respectively such that ${\delta }_u^{\ast }(q_0)=q$ and ${\delta }_v^{\ast }({\delta }_{\sigma }(q))\in F$ but ${\delta }_v^{\ast }({\delta }_{\sigma }(q))\notin F$, then $A$ accepts $u\sigma v$ but not $u{\sigma }^{\prime }v$, yet $u\sigma v{⪯}_{\ast }u{\sigma }^{\prime }v$;

• $\mathrm{■}$

  there are some $q\in Q$, $\sigma \in \mathrm{\Sigma }$ such that $q⋢{\delta }_{\sigma }(q)$: taking $u,v\in {\mathrm{\Sigma }}^{\ast }$ respectively such that ${\delta }_u^{\ast }(q_0)=q$ and ${\delta }_v^{\ast }(q)\in F$ but ${\delta }_v^{\ast }({\delta }_{\sigma }(q))\notin F$, then $A$ accepts $uv$ but not $u\sigma v$, yet $uv{⪯}_{\ast }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:

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

1. 1.

   If two states $q$ and $q^{\prime }$ are such that $q⊑q^{\prime }$ and $q^{\prime }⊑q$, then for every $w\in {\mathrm{\Sigma }}^{\ast }$, ${\delta }_w^{\ast }(q)\in F\iff {\delta }_w^{\ast }(q)\in F$. In a minimal DFA, this can never be true of two distinct states (otherwise the two states could be merged).

2. 2.

   For every $q={\delta }_u^{\ast }(q_0)\in Q$ and $v\in {\mathrm{\Sigma }}^{\ast }$ such that ${\delta }_v^{\ast }(q_0)\in F$, $v\in U$. $U$ is upwards-closed, hence $uv⪰v$ is in $U$ as well and ${\delta }_v^{\ast }(q)={\delta }_{uv}^{\ast }(q_0)\in F$: $q_0⊑q$.

3. 3.

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

4. 4.

   Because the language recognized by the automaton is upwards-closed, any accepting state $q$ is such that ${\delta }_w^{\ast }(q)\in F$ for every $w\in {\mathrm{\Sigma }}^{\ast }$. 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 $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$, suppose given an oracle able to answer two kinds of queries:

• $\mathrm{■}$

  membership queries – given a word $w\in {\mathrm{\Sigma }}^{\ast }$, the oracle decides whether $w\in U$ –

• $\mathrm{■}$

  and 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 {\mathrm{\Sigma }}^{\ast }$ 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:

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 an oracle in the classical setting, call it ${\text{Oracle}}_U$, from the oracle in the quasi-ordered setting, call it ${\text{Oracle}}_{(U,{⪯}_{\ast })}$: 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 ${\text{Oracle}}_U$ can simply be forwarded to ${\text{Oracle}}_{(U,{⪯}_{\ast })}$: 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 ${\text{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:

• $\mathrm{■}$

  if it is the case we also get the QO structure on $A$, and can then forward $A$ to ${\text{Oracle}}_{(U,{⪯}_{\ast })}$ for an equivalence query;

• $\mathrm{■}$

  otherwise, we get some $w{⪯}_{\ast }{w}^{\prime }$ such that $A$ recognizes $w$ but not $w^{\prime }$, and one of these two words must then be a counterexample to $A$ recognizing $U$.

$◀$

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 $\ast$-products.

Answering a membership query for a $w={\sigma }_1\mathrm{\cdots }{\sigma }_n\in {\mathrm{\Sigma }}^{\ast }$ can be done by checking whether $U$ intersects ${\sigma }_1^{\mathrm{?}}\mathrm{\cdots }{\sigma }_n^{\mathrm{?}}$: 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,⊑),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.

• $\mathrm{■}$

  First, we check whether $U$ contains the language recognized by $A$. For this, enumerate all the paths $q_0\stackrel{{\sigma }_1}{\to }\mathrm{\cdots }\stackrel{{\sigma }_n}{\to }{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⊏q_1⊏\mathrm{\cdots }⊏q_{n-1}⊏q_n$ – and that are minimal – for every $q_i\stackrel{{\sigma }_i}{\to }{q}_{i+1}$, ${\sigma }_i$ is minimal among the letters $\sigma$ such that ${\delta }_{\sigma }(q_i)=q_{i+1}$ (see Figure 2(a) for an example within the automaton of Figure 1(b)). Check whether ${\sigma }_1\mathrm{\cdots }{\sigma }_n\in U$ with a membership query. If this is not the case, ${\sigma }_1\mathrm{\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\stackrel{{\sigma }_1}{\to }\mathrm{\cdots }\stackrel{{\sigma }_n}{\to }{q}_n$ enumerated above, $w{⪰}_{\ast }{\sigma }_1\mathrm{\cdots }{\sigma }_n$ and $w\in U$ as $U$ is upwards-closed.

• $\mathrm{■}$

  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\stackrel{{\sigma }_1}{\to }\mathrm{\cdots }\stackrel{{\sigma }_n}{\to }{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 2(b) for an example within the automaton of Figure 1(b)). Let ${\mathrm{\Sigma }}_i\subseteq \mathrm{\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 $\ast$-products ${\mathrm{\Sigma }}_0^{\ast }{\sigma }_1^{\mathrm{?}}{\mathrm{\Sigma }}_1^{\ast }\mathrm{\cdots }{\mathrm{\Sigma }}_{n-1}^{\ast }{\sigma }_n^{\mathrm{?}}{\mathrm{\Sigma }}_n^{\ast }$ corresponding to one of these paths: the run for $w$ in $A$ must stop in a non-accepting state, and, since $w{w}^{\prime }$ is accepted by $A$ for any $w^{\prime }$ 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 $\ast$-products. If this is the case for one of these $\ast$-products $P$, then enumerating the words in $P$ will end up producing a counterexample $w\in {\mathrm{\Sigma }}^{\ast }$ such that $w\in U$ but $w$ is not accepted by $A$.

$◀$

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 $\ast$-product to produce a counterexample.

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 $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$ (a language described by a $\ast$-product) then $\downarrow e_M[I]$ is an ideal of $(M,{⪯}_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^{\prime })$ and $y=e_M(y^{\prime })$ with $x^{\prime },y^{\prime }\in I$; then there is a $z^{\prime }\in I$ such that $z^{\prime }{⪰}_{\ast }{x}^{\prime }$ and $z^{\prime }{⪰}_{\ast }{y}^{\prime }$, so that $e_M(z^{\prime })\in e_M[I]$, $e_M(z^{\prime }){⪰}_M{e}_M(x^{\prime })$ and $e_M(z^{\prime }){⪰}_M{e}_M(y^{\prime })$. $\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,{⪯}_M)$ is of the shape $\downarrow e_M[I]$ for some $I\in \mathrm{Idl}({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$. 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,\mathrm{\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,{⪯}_M)$. Then $e_M^{-1}[D]$ is downwards-closed in $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$, hence $e_M^{-1}[D]={\bigcup }_{i=1}^n{I}_i$ for some $I_1,\mathrm{\dots },I_n\in \mathrm{Idl}({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$. But then

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 $\ast$-product that specifies an ideal $I$ of $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$, write by abuse of notation $e_M[P]$ for the downard-closed set $e_M[I]$ of $(M,{⪯}_M)$. Finitely generated quasi-ordered monoids also enjoy a Valk-Jantzen-like result:

We reduce this problem to that of computing a finite basis of the upwards-closed subset $e_M^{-1}[U]$ of $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$. For this it is enough, by Corollary 3, to decide, given a $\ast$-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 ${⪯}_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 Lemmas 11 and 12 we actually use the fact that $({\mathrm{\Sigma }}^{\ast },{⪯}_{\ast })$ 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,\le )$ for which Theorem 2 holds, a monotone surjection $e:(X,\le )\to (Y,{\le }^{\prime })$, and an upwards-closed subset $U$ of $(Y,{\le }^{\prime })$. Then $(Y,{\le }^{\prime })$ is a WQO and, given an oracle that decides for any $I\in \mathrm{Idl}(X,\le )$ 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.

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.