betaFeedback

WorksComputer Science

Learning Erasing Equal-Length Relational Pattern Languages in the Limit from Positive Data over Binary Alphabets

Abstract

Relational pattern languages generalize Angluin's pattern languages by requiring the strings substituted for repeated occurrences of a variable to stand in a given relation, rather than to be identical. We study erasing pattern languages under the equal-length relation, where all occurrences of a variable must be replaced by strings of the same length. Over alphabets with at least three letters, this class is known to be learnable in the limit from positive data. We show that over a binary alphabet it is not, which resolves an open question from earlier work. Our proof reveals that non-learnability already holds for the restricted subclass of languages generated by patterns that have exactly three maximal substrings of variables. We then show that patterns with at most two maximal substrings of variables are learnable in the limit from positive data for every alphabet of size at least two. If the target pattern is known to have at most one maximal substring of variables, this can even be achieved by an iterative learner, which updates its hypothesis using only the current example and its previous hypothesis.

Introduction

Pattern languages, introduced by Angluin [1], have been an object of study in algorithmic learning theory for decades. A pattern is a finite string of terminal symbols and variables. Its language consists of all words obtained by replacing each variable with a string over the terminal alphabet, where all occurrences of the same variable are replaced by the same string. The literature distinguishes non-erasing pattern languages [1], in which variables cannot be replaced with the empty string, from erasing pattern languages, where empty substitutions are allowed [2]. Both variants have been studied extensively in Gold’s model of learning in the limit from positive data [3], where a learner is gradually presented with a sequence of all strings in an unknown target language LL and must eventually settle on a correct description for LL. The class of non-erasing pattern languages is learnable in this model [1], even by an iterative learner, which updates its hypothesis based only on the previous hypothesis and the current example [4]. By contrast, erasing pattern languages are not learnable in the limit from positive data, when the underlying alphabet has size 2, 3, or 4 [5, 6].

Relational pattern languages [7] are a generalization of the notion of pattern language, in which repeated variables need not be replaced by the same string, but instead by strings that are in a specified relation. Natural choices for this relation are, for example, equality, reversal, equal length, or abelian equivalence [8, 9, 10]; the equality relation here recovers the original notion of pattern language.

The equal-length relation is arguably the simplest of the relations considered in the literature [8, 9]. All occurrences of a variable must be replaced by strings of the same length, but the strings themselves can be chosen independently. As a result, the language generated by a pattern under this relation depends only on its terminal symbols and on the admissible lengths of the strings between them. Non-erasing equal-length relational pattern languages are trivially learnable in the limit from positive data; moreover it is known that they can be distinguished by small sets of short strings when the alphabet size is at least three [8]. In the erasing case, it was observed that the positive learnability result for alphabets with at least three letters carries over from the non-erasing case [9]. However, binary alphabets posed a challenge. It was shown that many specific forms of patterns generate erasing equal-length relational languages that have so-called telltales even for binary alphabets [9]. A telltale of a language LL with respect to a family L\mathcal{L} of languages is a finite subset of LL that is not contained in any language L′∈LL' \in\mathcal{L} with L′⊂LL' \subset L. The uniform enumerability of a system of telltales is a necessary and sufficient condition for the learnability of a family L\mathcal{L} with uniformly decidable membership [11]. Despite numerous results on the existence of telltales for subclasses of erasing equal-length relational pattern languages, it was left open whether the full class ELlen\mathcal{E}_{L\mathrm{len}} of erasing equal-length relational pattern languages has telltales and thus whether it is learnable in the limit from positive data, given a binary alphabet.

We resolve this open question by presenting a pattern p∗p^* whose erasing equal-length relational language ELlen(p∗)\mathcal{E}_{L\mathrm{len}}(p^*) over a binary alphabet does not have a telltale with respect to ELlen\mathcal{E}_{L\mathrm{len}}. Consequently, for alphabets of only two letters, the class ELlen\mathcal{E}_{L\mathrm{len}} is not learnable in the limit from positive data. We complement this result with positive learnability results for languages generated by patterns with a small number of maximal substrings of variables.

The first technical ingredient is to represent every language ELlen(p)∈ELlen\mathcal{E}_{L\mathrm{len}}(p) \in\mathcal{E}_{L\mathrm{len}} by the sequence of terminals in the underlying pattern pp and by a finitely generated monoid of gap vectors.1 Roughly speaking, a word belongs to εLlen(p)\varepsilon L_{\mathrm{len}}(p) if it can be cut around the terminals of pp so that the lengths of the pieces form a vector of the monoid. Suppose a learning algorithm is presented with positive examples only, i.e., words in the language εLlen(p)\varepsilon L_{\mathrm{len}}(p), and has to identify pp. Any single positive example shows a word, but not where it has to be cut. The question we study is how much of the monoid can nevertheless be recovered from the examples. Over an alphabet of three or more letters, every gap vector has a word that can be cut in only one way, so that positive examples reveal the monoid and we obtain learnability in the limit from positive examples. Our focus is the binary alphabet case. The main results of our paper are:

  • Over a binary alphabet, a word can sometimes be cut differently, when shifting two equal adjacent terminals by one position. This allows one variable of a pattern to be “imitated” by other variables, and learning from positive data becomes impossible (§ 3). We prove this by providing a pattern pp such that εLlen(p)\varepsilon L_{\mathrm{len}}(p) does not possess a telltale with respect to the class εLlen\varepsilon L_{\mathrm{len}}.

  • The pattern pp, as well as all the patterns that witness the fact that pp does not have a telltale, have exactly three variable blocks, i.e., they can be factored into substrings of only terminal symbols and substrings of only variable symbols, such that exactly three substrings of variable symbols are used. We therefore obtain the corollary that the patterns with exactly three variable blocks generate a class of erasing equal-length relational pattern languages that is not learnable in the limit from positive data, when the alphabet size is 2.

  • We contrast this by showing that the corresponding class is learnable in the limit from positive data, when the underlying patterns contain at most two variable blocks, regardless of the alphabet size (§ 4).

  • If it is known that the underlying pattern pp has at most one variable block, we obtain an even stronger positive learnability result, again regardless of the alphabet size. Learning in the limit from positive data can then even be achieved by an iterative learner, which updates its hypothesis based only on the previous hypothesis and the most recently seen word, ignoring all previously collected data (§ 5).

Preliminaries

Equal-Length Patterns and Their Languages

Given a set WW, we denote the set of finite strings over WW by W∗W^{*} and its subset of non-empty finite strings by W+W^{+}. If w∈W∗w \in W^{*} is any string over WW, then we denote by ∣w∣\lvert w\rvert the length of ww. We can then write w=w[1]w[2]⋯w[∣w∣]w = w[1]w[2]\cdots w[\lvert w\rvert] for w[1],w[2],…,w[∣w∣]∈Ww[1],w[2],\ldots,w[\lvert w\rvert] \in W, where w[i]w[i] denotes the symbol at the iith position in ww. Moreover, for any i,j∈{1,…,∣w∣}i,j \in\{1,\ldots,\lvert w\rvert\}, the term w[i:j]w[i:j] refers to the substring w[i]w[i+1]⋯w[j]w[i]w[i+1]\cdots w[j] of ww if i≤ji \leq j, and to the empty string if i>ji > j. Likewise, w[i:j]=εw[i:j] = \varepsilon whenever j=0j = 0.

Throughout this document, we assume that Σ\Sigma is a finite alphabet of cardinality at least 2, and X={x1,x2,x3,…}X = \{x_{1},x_{2},x_{3},\ldots\} is a countably infinite set of variables, disjoint from Σ\Sigma. A pattern is a finite non-empty string over Σ∪X\Sigma\cup X, with the property that variable xix_i may occur in pp only if all variables xjx_j, for 1≤j<i1 \le j < i also occur in pp. If pp is a pattern containing all and only the variables x1,…,xix_1, \ldots, x_i for some i≥1i \ge1, and variable xjx_j occurs exactly njn_j (≥1\ge1) times in pp, then an equal-length substitution for pp is a mapping defined by

xj↦(wj,1,wj,2,…,wj,nj) for 1≤j≤i,x_j \mapsto(w_{j,1}, w_{j,2}, \ldots, w_{j,n_j}) \text{ for } 1 \le j \le i,

where wj,1,wj,2,…,wj,nj∈Σ∗w_{j,1}, w_{j,2}, \ldots, w_{j,n_j} \in\Sigma^* and

∣wj,1∣=∣wj,2∣=⋯=∣wj,nj∣ for 1≤j≤i.|w_{j,1}| = |w_{j,2}| = \cdots= |w_{j,n_j}| \text{ for } 1 \le j \le i.

This substitution generates from pp the string that is obtained if the kkth occurrence of the variable xjx_j in pp (counted from the left) is replaced by wj,kw_{j,k}, for each j∈{1,…,i}j \in\{1, \ldots, i\} and each k∈{1,…,nj}k \in\{1, \ldots, n_j\}. The term equal-length refers to the fact that such a substitution replaces all occurrences of the same variable with strings of the same length. This stands in contrast with the original definition of pattern languages, where multiple occurrences of the same variable have to be substituted by the same string [1, 2]. If pp has no variables, i.e., p∈Σ+p \in\Sigma^+, then the only word that can be generated from pp is the word pp itself.

For example, consider the pattern p=x1aax1x2bp = x_1 a a x_1 x_2 b and the equal-length substitution defined by x1↦(ab,aa)x_1 \mapsto(ab, aa) and x2↦(b)x_2 \mapsto(b). This substitution generates the string ab a a aa b bab\,a\,a\,aa\,b\,b from pp. The (erasing) equal-length relational language of the pattern pp (over Σ\Sigma) is the set of all strings that are generated from pp by substitutions.

Earlier work also considered non-erasing equal-length relational pattern languages, which are defined in the same way, but using only substitutions for which the words wj,1,wj,2,…,wj,njw_{j,1}, w_{j,2}, \ldots, w_{j,n_j} belong to Σ+\Sigma^+, i.e., are non-empty [8]. Aside from equal-length relational pattern languages, other relations between the strings replacing multiple occurrences of the same variables have been considered in the literature, including reversal, abelian equivalence, et cetera [7, 8, 10]. From now on, we consider exclusively the equal-length relation and focus on (erasing) equal-length relational pattern languages.

Any pattern pp has a unique decomposition of the form

p=π0c1π1c2⋯cmπm,ck∈Σ, πj∈X∗.p = \pi_0 c_1 \pi_1 c_2 \cdots c_m \pi_m,\qquad c_k \in\Sigma,\ \pi_j \in X^*.

The non-empty πj\pi_j are called the variable blocks of pp. We call s(p)=c1⋯cms(p) = c_1 \cdots c_m the terminal word of pp and π0,…,πm\pi_0, \ldots, \pi_m its gaps. For instance, p=x1aax1x2bp = x_1 a a x_1 x_2 b has the gaps π0=x1\pi_0 = x_1, π1=ε\pi_1 = \varepsilon, π2=x1x2\pi_2 = x_1 x_2 and π3=ε\pi_3 = \varepsilon. Its variable blocks are x1x_1 and x1x2x_1 x_2.

For a variable xx in pp we define its gap vector γ(x)∈Nm+1\gamma(x) \in\mathbb{N}^{m+1} by letting γ(x)j\gamma(x)_j be the number of occurrences of xx in the gap πj\pi_j. For a vector v∈Nm+1v \in\mathbb{N}^{m+1} we write ∣v∣=v0+⋯+vm|v| = v_0 + \cdots+ v_m for its size, and for a set P⊆Nm+1P \subseteq\mathbb{N}^{m+1} we write ⟨P⟩\langle P\rangle for the submonoid of Nm+1\mathbb{N}^{m+1} generated by PP. For a submonoid ⟨P⟩⊆Nm+1\langle P\rangle\subseteq\mathbb{N}^{m+1} let mg⁡(⟨P⟩)\operatorname{mg}(\langle P\rangle) be the set of minimal generators of ⟨P⟩\langle P\rangle, i.e., the set of non-zero elements of ⟨P⟩\langle P\rangle that are not the sum of two non-zero elements of ⟨P⟩\langle P\rangle; here mg⁡({0}):=∅\operatorname{mg}(\{0\}) := \varnothing. The set mg⁡(⟨P⟩)\operatorname{mg}(\langle P\rangle) generates ⟨P⟩\langle P\rangle and is always contained in ⟨P⟩\langle P\rangle. For a finite set AA of integers, we use mg⁡(A):=mg⁡(⟨A⟩)\operatorname{mg}(A) := \operatorname{mg}(\langle A\rangle).

Definition 1. Let s=c1⋯cms = c_{1} \cdots c_{m}. A split of a word ww (with respect to ss) is a factorization w=w0c1w1⋯cmwmw = w_{0}c_{1}w_{1} \cdots c_{m}w_{m} with wj∈Σ∗w_{j} \in\Sigma^{*}. Its vector is (∣w0∣,…,∣wm∣)(|w_{0}|, \ldots, |w_{m}|), and Ds(w)D_{s}(w) denotes the set of vectors of all splits of ww. The fillings of a vector v∈Nm+1v \in\mathbb{N}^{m+1} with respect to ss are the words in the set

Fs(v)={w0c1w1⋯cmwm∣wj∈Σ∗, ∣wj∣=vj}.F_{s}(v) = \{w_{0}c_{1}w_{1} \cdots c_{m}w_{m} \mid w_{j} \in\Sigma^{*},\ |w_{j}| = v_{j}\}.

For a set P⊆Nm+1P \subseteq\mathbb{N}^{m+1} we let

Ls(P)={w∈Σ∗∣Ds(w)∩⟨P⟩≠∅}=⋃v∈⟨P⟩Fs(v).L_{s}(P) = \{w \in\Sigma^{*} \mid D_{s}(w) \cap\langle P\rangle\ne\varnothing\} = \bigcup_{v \in\langle P\rangle} F_{s}(v).

The following observation, expressing the equal-length relational language of a pattern pp in terms of the fillings of its gap vectors, is immediate.

Observation 2 (Normal form). Let pp be a pattern with terminal word ss, and let PP be the set of gap vectors of its variables. Then

εLlen(p)=Ls(P).\varepsilon L_{\mathrm{len}}(p) = L_{s}(P).

Conversely, for every word ss and every finite set P⊆N∣s∣+1∖{0∣s∣+1}P \subseteq\mathbb{N}^{|s|+1} \setminus\{0^{|s|+1}\} there is a pattern pp with εLlen(p)=Ls(P)\varepsilon L_{\mathrm{len}}(p) = L_{s}(P).

Example 3. Let p=x1ax2x2x1bx2x3p = x_{1} a x_{2}x_{2} x_{1} b x_{2} x_{3}. Its terminal word is abab and the gap vectors are (1,1,0)(1, 1, 0), (0,2,1)(0, 2, 1) and (0,0,1)(0, 0, 1). The substitution x1↦(a,a)x_{1} \mapsto(a, a), x2↦(b,a,a)x_{2} \mapsto(b, a, a), x3↦(ε)x_{3} \mapsto(\varepsilon) generates aabaabaaabaaba; the terminals of pp give the split a⋅a⋅baa⋅b⋅aa \cdot a \cdot baa \cdot b \cdot a with vector (1,3,1)=(1,1,0)+(0,2,1)(1, 3, 1) = (1, 1, 0) + (0, 2, 1). The same word has five further splits, with vectors (0,1,4)(0, 1, 4), (1,0,4)(1, 0, 4), (0,4,1)(0, 4, 1), (3,1,1)(3, 1, 1) and (4,0,1)(4, 0, 1). A word does not reveal which split was used to generate it; this ambiguity turns out to be the source of difficulties for learning equal-length relational pattern languages from positive examples (for binary alphabets).

Learning in the Limit and Telltales

The focus of this paper is on learning equal-length relational pattern languages in Gold’s model of learning in the limit from positive data [3].

A text for LL is an infinite sequence t0,t1,…t_{0}, t_{1}, \ldots with {ti∣i∈N}=L\{t_{i} \mid i \in\mathbb{N}\} = L.

A learner is a mapping that takes as input any initial segment t0,t1,…,tnt_{0}, t_{1}, \ldots, t_{n} of any text of any target language. If defined, its output is a representation of some language L′L', which is to be understood as the learner hypothesizing the target language to be L′L'. In general, the goal of a learner is to eventually identify an unknown language LL in a known class L\mathcal{L} of languages, when gradually processing any text for LL.

Definition 4. Let L\mathcal{L} be a class of languages and L∈LL \in\mathcal{L}. Fix a numbering (Li)i∈N(L_{i})_{i \in\mathbb{N}} such that L⊆{Li∣i∈N}\mathcal{L} \subseteq\{L_{i} \mid i \in\mathbb{N}\}. A learner AA learns LL in the limit from positive data (with respect to (Li)i∈N(L_{i})_{i \in\mathbb{N}}) if, for any text t0,t1,t2,…t_{0}, t_{1}, t_{2}, \ldots for LL, the following two properties hold:

  • A(t0,…,tn)A(t_{0}, \ldots, t_{n}) is defined for every n∈Nn \in\mathbb{N}.

  • There exists some n0∈Nn_{0} \in\mathbb{N} such that LA(t0,…,tn0)=LL_{A(t_{0},\ldots,t_{n_{0}})} = L and A(t0,…,tn)=A(t0,…,tn0)A(t_{0},\ldots,t_{n}) = A(t_{0},\ldots,t_{n_{0}}) for every n≥n0n \ge n_{0}.

The class L\mathcal{L} is learnable in the limit from positive data if there is a numbering (Li)i∈N(L_i)_{i\in\mathbb{N}} and a learner that learns every L∈LL\in\mathcal{L} from positive data with respect to (Li)i∈N(L_i)_{i\in\mathbb{N}}.

Angluin’s characterization of learnability in the limit from positive data [11] concerns computable learners for indexed families (Li)i∈N(L_i)_{i\in\mathbb{N}}; these are families for which a recursive procedure exists that, given (i,w)∈N×Σ∗(i,w)\in\mathbb{N}\times\Sigma^*, decides whether w∈Liw\in L_i. Clearly, the class of all equal-length relational pattern languages is an indexed family, since its membership problem is uniformly decidable. The central notion in Angluin’s characterization is that of a telltale: A telltale of a language LL in a class L\mathcal{L} is a finite set T⊆LT\subseteq L such that no L′∈LL'\in\mathcal{L} satisfies T⊆L′⊊LT\subseteq L'\subsetneq L.

Angluin’s result states that an indexed family (Li)i∈N(L_i)_{i\in\mathbb{N}} of languages is learnable in the limit from positive data if and only if there is an effective procedure that, given an index ii, enumerates a telltale for LiL_i with respect to {Li∣i∈N}\{L_i\mid i\in\mathbb{N}\}. Note that Angluin’s characterization builds on the same idea as the locking sequences of Blum and Blum [12]. For our negative result we need only the necessity part of the characterization, and we do not require computable learners or the recursive enumerability of telltales, i.e., the following statement suffices for our purposes:

Theorem 5 [11, 12]. If some (computable or non-computable) learner learns an indexed family L\mathcal{L} of languages in the limit from positive data, then every L∈LL\in\mathcal{L} has a telltale in L\mathcal{L}.

In the context of this paper, we focus on learning equal-length relational pattern languages in the limit from positive data. Hypotheses output by the learner are (indices of) relational patterns in a fixed enumeration.

Non-Learnability over Binary Alphabets

In this section, let Σ={a,b}\Sigma=\{a,b\}. Reidenbach showed that the erasing pattern languages under equality relation are not learnable in the limit from positive data over small alphabets [5, 6], and Mousawi and Zilles [9] obtained the same result for the reversal relation over a binary alphabet. We now show that the equal-length relation behaves in the same way, even though its languages are determined by the lengths of the gaps alone.

We exhibit a language L∈εLlenL\in\varepsilon\mathcal{L}_{\mathrm{len}} and a chain of languages L0⊊L1⊊L2⊊⋯L_0\subsetneq L_1\subsetneq L_2\subsetneq\cdots in εLlen\varepsilon\mathcal{L}_{\mathrm{len}} whose union is LL. Every finite subset of LL is then contained in some Lt⊊LL_t\subsetneq L, so LL has no telltale. Therefore, by Theorem 5, no learner can identify all of these languages.

The terminal word for our target language LL is s=aabs=aab. Gap vectors therefore have four coordinates, counting the variables before the first aa, between the two aa’s, between the second aa and bb, and after bb. Let

X1=(1,0,1,0),X2=(0,0,2,0),X3=(0,0,0,1).X_1=(1,0,1,0),\qquad X_2=(0,0,2,0),\qquad X_3=(0,0,0,1).

The target is

L=εLlen(x1aax1x2x2bbx3)=Laab({X1,X2,X3}).L=\varepsilon\mathcal{L}_{\mathrm{len}}(x_1aa x_1x_2x_2bbx_3)=L_{aab}(\{X_1,X_2,X_3\}).

For t≥0t \ge0 we let

Lt=Laab({X3}∪{X1+jX2∣0≤j≤t}).L_t = L_{aab}\left(\{X_3\} \cup\{X_1 + jX_2 \mid0 \le j \le t\}\right).

Since X1+jX2=(1,0,2j+1,0)X_1 + jX_2 = (1,0,2j+1,0), a pattern for LtL_t has, for each j≤tj \le t, a variable occurring once before aaaa and 2j+12j+1 times between the second aa and bb, in addition to the variable y3y_3 at the end of the pattern. For example,

L0=εLlen(y1aay1by3),L1=εLlen(y1y2aay1y2y2y2by3).L_0 = \varepsilon L_{\mathrm{len}}(y_1aa y_1b y_3), \qquad L_1 = \varepsilon L_{\mathrm{len}}(y_1y_2aa y_1y_2y_2y_2b y_3).

The target pattern, as well as all patterns generating the languages LtL_t for t∈Nt \in\mathbb{N}, have three variable blocks each. The target has the variable x2≠x1x_2 \ne x_1 occurring only in the middle variable block; the languages LtL_t have every variable in the middle block also appear in the first variable block.

For the remainder of this section we use the following notation:

M=⟨X1,X2,X3⟩M = \langle X_1, X_2, X_3\rangle

and

Mt=⟨X3,X1+jX2∣0≤j≤t⟩.M_t = \langle X_3, X_1 + jX_2 \mid0 \le j \le t\rangle.

In particular, MM and MtM_t are submonoids of N4\mathbb{N}^4.

We first make a simple observation on the structure of the monoids representing our target language LL and the languages LtL_t in the chain.

Lemma 6. MM and MtM_t satisfy the following:

M={(α,0,y,δ)∣α,y,δ∈N, y≥α, y≡α(mod2)},M = \{(\alpha,0,y,\delta) \mid\alpha,y,\delta\in\mathbb{N},\ y \ge\alpha,\ y \equiv\alpha\pmod{2}\},
Mt={(α,0,y,δ)∣α,y,δ∈N, α≤y≤(2t+1)α, y≡α(mod2)}.M_t = \{(\alpha,0,y,\delta) \mid\alpha,y,\delta\in\mathbb{N},\ \alpha\le y \le(2t+1)\alpha,\ y \equiv\alpha\pmod{2}\}.

In particular, every vector of MM and of MtM_t has second coordinate 00, and every vector of MtM_t with first coordinate 00 also has third coordinate 00.

Proof. Any element of MM is of the form αX1+βX2+δX3=(α,0,α+2β,δ)\alpha X_1 + \beta X_2 + \delta X_3 = (\alpha,0,\alpha+2\beta,\delta) with α,β,δ∈N\alpha,\beta,\delta\in\mathbb{N}. Its third coordinate y=α+2βy = \alpha+2\beta satisfies y≥αy \ge\alpha and y≡α(mod2)y \equiv\alpha\pmod{2}. Conversely, a vector (α,0,y,δ)(\alpha,0,y,\delta) with y≥αy \ge\alpha and y≡α(mod2)y \equiv\alpha\pmod{2} belongs to MM, as witnessed by β=(y−α)/2\beta= (y-\alpha)/2.

Any element of MtM_t is of the form δX3\delta X_3 plus a sum of α\alpha vectors X1+jiX2=(1,0,2ji+1,0)X_1+j_iX_2 = (1,0,2j_i+1,0) with 0≤ji≤t0 \le j_i \le t. Its first coordinate is α\alpha, and its third coordinate y=∑i=1α(2ji+1)y = \sum_{i=1}^{\alpha}(2j_i+1) is a sum of α\alpha odd numbers between 11 and 2t+12t+1. Hence α≤y≤(2t+1)α\alpha\le y \le(2t+1)\alpha and y≡α(mod2)y \equiv\alpha\pmod{2}. Conversely, let yy satisfy α≤y≤(2t+1)α\alpha\le y \le(2t+1)\alpha and y≡α(mod2)y \equiv\alpha\pmod{2} for α∈N\alpha\in\mathbb{N}. Clearly, then (α,0,y,δ)∈Mt(\alpha,0,y,\delta) \in M_t for all δ∈N\delta\in\mathbb{N}. □\square

It is straightforward to obtain the following chain.

Lemma 7. L0⊆L1⊆L2⊆⋯⊆LL_0 \subseteq L_1 \subseteq L_2 \subseteq\cdots\subseteq L.

Proof. Every generator of MtM_t is a generator of Mt+1M_{t+1}, and X1+jX2∈MX_1+jX_2 \in M. Hence M0⊆M1⊆⋯⊆MM_0 \subseteq M_1 \subseteq\cdots\subseteq M, from which the claim follows immediately. □\square

Next, we show that every word in LL is contained in some language LtL_t, t∈Nt \in\mathbb{N}, so that, together with Lemma 7, we obtain that the union of all languages LtL_t in the chain equals LL.

Lemma 8. Let w∈Lw \in L have a split with vector (α,0,α+2β,δ)∈M(\alpha, 0, \alpha+ 2\beta, \delta) \in M. Then w∈Lβw \in L_\beta. Consequently, ⋃t∈NLt=L\bigcup_{t \in\mathbb{N}} L_t = L.

Proof. Let e=(α,0,α+2β,δ)e = (\alpha, 0, \alpha+ 2\beta, \delta). We find a split of ww whose vector lies in MβM_\beta, distinguishing three cases.

Case α≥1\alpha\ge1. Then

e=(α−1)X1+(X1+βX2)+δX3,e = (\alpha- 1)X_1 + (X_1 + \beta X_2) + \delta X_3,

since (α−1)(1,0,1,0)+(1,0,1+2β,0)+(0,0,0,δ)=(α,0,α+2β,δ)(\alpha- 1)(1, 0, 1, 0) + (1, 0, 1 + 2\beta, 0) + (0, 0, 0, \delta) = (\alpha, 0, \alpha+ 2\beta, \delta). All three summands belong to MβM_\beta, so the given split already works.

Case α=0\alpha= 0 and β=0\beta= 0. Then e=δX3∈M0⊆Mβe = \delta X_3 \in M_0 \subseteq M_\beta.

Case α=0\alpha= 0 and β≥1\beta\ge1. The given split has the form w=aaubvw = aaubv with ∣u∣=2β≥2|u| = 2\beta\ge2 and ∣v∣=δ|v| = \delta. It uses the variable x2x_2 only in the middle variable block, corresponding to a vector (0,0,2β,δ)(0, 0, 2\beta, \delta) which is not in MβM_\beta, so we split ww differently, depending on the first letter of uu.

  • If uu begins with bb, then ww begins with aabaab. We use these three letters as the terminals. The resulting split has vector (0,0,0,∣w∣−3)=(0,0,0,2β+δ)=(2β+δ)X3∈M0⊆Mβ(0, 0, 0, |w| - 3) = (0, 0, 0, 2\beta+ \delta) = (2\beta+ \delta)X_3 \in M_0 \subseteq M_\beta.

  • If uu begins with aa, say u=au′u = au', then w=aaau′bvw = aa au'bv. We use the first letter of ww as the content of the first gap, its second and third letters as the two terminals aa, and the same bb as before. The second gap is empty, the third gap is u′u' of length 2β−12\beta- 1, and the fourth gap is vv. The resulting split has vector

(1,0,2β−1,δ)=(X1+(β−1)X2)+δX3∈Mβ−1.(1, 0, 2\beta- 1, \delta) = (X_1 + (\beta- 1)X_2) + \delta X_3 \in M_{\beta- 1}.

In every case, w∈Lβw \in L_\beta, using Lβ−1⊆LβL_{\beta- 1} \subseteq L_\beta in the last case. Since every word of LL has a split with vector in MM, every word of LL belongs to some LtL_t, and together with Lemma 7 we obtain ⋃tLt=L\bigcup_t L_t = L.

Example 9. The word aabaabb=aa⋅baab⋅baabaabb = aa \cdot baab \cdot b has the split vector (0,0,4,0)=2X2(0, 0, 4, 0) = 2X_2 in MM. Since baabbaab begins with bb, we may use its first occurrence of aabaab as the terminals, which gives the vector (0,0,0,4)=4X3∈M0(0, 0, 0, 4) = 4X_3 \in M_0; so this word belongs to L0L_0. The word aaababb=aa⋅abab⋅baaababb = aa \cdot abab \cdot b also has the split vector 2X22X_2. Since abababab begins with aa, we shift the terminals aaaa one position to the right, obtaining a⋅aa⋅bab⋅ba \cdot aa \cdot bab \cdot b with vector (1,0,3,0)=X1+X2∈M1(1, 0, 3, 0) = X_1 + X_2 \in M_1; so this word belongs to L1L_1. (Lemma 10 below will show that this word does not belong to L0L_0.)

Finally, we demonstrate that the chain is strict.

Lemma 10. For every t≥0t \ge0, the word

wt=aaab(ab)t+1bof length 2t+7w_t = aaab(ab)^{t+1}b \qquad\text{of length } 2t + 7

belongs to Lt+1∖LtL_{t+1} \setminus L_t. Consequently, Lt⊊Lt+1L_t \subsetneq L_{t+1} and Lt⊊LL_t \subsetneq L.

Proof. We number the positions of wtw_t from 0. The letter aa occurs at the positions 0, 1, 2 and at the even positions 4, 6, …\ldots, 2t+42t+4; the letter bb occurs at position 3, at the odd positions 5, 7, …\ldots, 2t+52t+5, and at position 2t+62t+6. For instance, w0=aaababbw_0=aaababb.

By Lemma 6, a split whose vector lies in Mt+1M_{t+1} or in MtM_t uses two adjacent occurrences of aa as the terminals a,aa,a. After position 3 in wtw_t, the letters aa and bb alternate, so the only adjacent pairs of aa’s are at the position pairs (0,1)(0,1) and (1,2)(1,2). Let rr be the position used for the terminal bb. A split using the pair (q,q+1)(q,q+1) and rr has the vector (q,0,r−q−2,2t+6−r)(q,0,r-q-2,2t+6-r). Table 1 lists all possibilities.

pair of aa’sposition rr of bbvectormembership
(0,1)(0,1)any r≥3r \ge3(0,0,r−2,⋅)(0,0,r-2,\cdot)not in MtM_t: first coordinate 0, third coordinate at least 1
(1,2)(1,2)r=3r=3(1,0,0,⋅)(1,0,0,\cdot)neither in MM nor in MtM_t: third coordinate smaller than the first
(1,2)(1,2)rr odd, 5≤r≤2t+55 \le r \le2t+5(1,0,r−3,⋅)(1,0,r-3,\cdot)neither in MM nor in MtM_t: wrong parity
(1,2)(1,2)r=2t+6r=2t+6(1,0,2t+3,0)(1,0,2t+3,0)in Mt+1M_{t+1}, as X1+(t+1)X2X_1+(t+1)X_2; not in MtM_t, as 2t+3>2t+12t+3>2t+1

Table 1. Possible combinations for positioning terminal symbols in wtw_t, and resulting membership of the split vector in Mt+1M_{t+1} and MtM_t.

The last row shows wt∈Lw_t \in L, and no row yields a vector of MtM_t, so wt∉Ltw_t \notin L_t. By Lemma 8, applied to the split of the last row with β=t+1\beta=t+1, we have wt∈Lt+1w_t \in L_{t+1}. Hence Lt≠Lt+1L_t \ne L_{t+1}, and with Lemma 7 the chain is strict.

For example, for t=0t=0 we obtain the following: w0=aaababbw_0=aaababb has its adjacent aa’s at position pairs (0,1)(0,1) and (1,2)(1,2) and its bb’s at positions 3, 5, 6. The pair (0,1)(0,1) gives the vectors (0,0,1,3)(0,0,1,3), (0,0,3,1)(0,0,3,1) and (0,0,4,0)(0,0,4,0), none of which lies in M0M_0. The pair (1,2)(1,2) gives (1,0,0,3)(1,0,0,3), (1,0,2,1)(1,0,2,1) and (1,0,3,0)(1,0,3,0); the first two are not even in MM, and the third is X1+X2∈M1∖M0X_1+X_2 \in M_1 \setminus M_0.

We finally put everything together to obtain our main result.

Theorem 11. Let Σ={a,b}\Sigma=\{a,b\}. Then the language L=εLlen(x1aax1x2x2bx3)L=\varepsilon L_{\mathrm{len}}(x_1aa x_1x_2x_2b x_3) has no telltale in εLlen\varepsilon L_{\mathrm{len}}. In particular, the class εLlen\varepsilon L_{\mathrm{len}} is not learnable in the limit from positive data, not even by a non-computable learner.

Proof. Let T⊆LT \subseteq L be finite. By Lemma 8, every word of TT belongs to some LtL_t; let tt be the largest index needed. By Lemma 7, T⊆LtT \subseteq L_t, and by Lemma 10, Lt⊊LL_t \subsetneq L. Since Lt∈εLlenL_t \in\varepsilon L_{\mathrm{len}}, the set TT is not a telltale of LL.

The binary alphabet is used at exactly one place, in the last case of the proof of Lemma 8: the first letter of uu is either bb, or aa, in which case the pair of terminals aaaa can be shifted one position to the right. Over a ternary alphabet {a,b,c}\{a,b,c\}, a word aac′u′bvaac'u'bv admits neither alternative.

The shift needs two equal adjacent terminals, forming an empty gap, followed by a gap between two different terminals. The large class of patterns studied in [9], for which telltales exist over binary alphabets, has no such configuration. This raises the following question. Given Σ={a,b}\Sigma= \{a,b\}, is the subclass of ELlen\mathcal{E}\mathcal{L}_{\mathrm{len}} consisting of the languages whose terminal word does not contain aaaa or bbbb as a factor learnable in the limit from positive data? We leave this question open.

Observe that the language LL from Theorem 11, as well as all the languages LtL_t in the chain in Lemma 7, are generated by patterns with exactly three variable blocks. We therefore obtain the following corollary.

Corollary 12. Let ∣Σ∣=2|\Sigma| = 2. Then the subclass of ELlen\mathcal{E}\mathcal{L}_{\mathrm{len}} consisting of languages generated by patterns with exactly three variable blocks is not learnable in the limit from positive data.

This immediately raises the question whether patterns with up to two variable blocks are learnable, for binary alphabets. The next section answers this question affirmatively.

Learning of Patterns with at Most Two Variable Blocks

Let Elen2\mathcal{E}_{\mathrm{len}}^{2} be the class of the languages ELlen(p)\mathcal{E}\mathcal{L}_{\mathrm{len}}(p) of patterns of the form

p=ω0x⃗1ω1x⃗2ω2(1)p = \omega_0\vec{x}_1\omega_1\vec{x}_2\omega_2 \tag*{(1)}

with ω0,ω1,ω2∈Σ∗\omega_0,\omega_1,\omega_2 \in\Sigma^*, x⃗1,x⃗2∈X∗\vec{x}_1,\vec{x}_2 \in X^*, and p≠εp \ne\varepsilon, i.e., patterns with at most two variable blocks. We require ω1≠ε\omega_1 \ne\varepsilon when both x⃗1≠ε\vec{x}_1 \ne\varepsilon and x⃗2≠ε\vec{x}_2 \ne\varepsilon. Moreover, when pp has exactly one variable block, we take x⃗2=ω2=ε\vec{x}_2 = \omega_2 = \varepsilon. This section establishes the following result, which stands in contrast with Corollary 12.

Theorem 13. Let ∣Σ∣≥2|\Sigma| \ge2. Then Elen2\mathcal{E}_{\mathrm{len}}^{2} is learnable in the limit from positive data.

The remainder of this section is dedicated to proving Theorem 13.

Following Observation 2, we identify the erasing equal-length relational language of a pattern pp of the form (1) with the monoid M=⟨P⟩M = \langle P\rangle generated by the set PP of gap vectors of the variables in pp. In particular,

ELlen(p)={ω0uω1vω2∣u,v∈Σ∗, (∣u∣,∣v∣)∈M}.(2)\mathcal{E}\mathcal{L}_{\mathrm{len}}(p) = \{\omega_0 u \omega_1 v \omega_2 \mid u,v \in\Sigma^*,\ (|u|,|v|) \in M\}. \tag*{(2)}

Note that, by contrast with the previous section, within this section, MM is a submonoid of N2\mathbb{N}^2.

We begin with two straightforward lemmas.

Lemma 14. Let ω1∈Σ+\omega_1 \in\Sigma^+ and let σ1,σ2∈Σ\sigma_1,\sigma_2 \in\Sigma such that σ1≠ω1[1]\sigma_1 \ne\omega_1[1] and σ2≠ω1[∣ω1∣]\sigma_2 \ne\omega_1[|\omega_1|]. For all k1,k2∈Nk_1,k_2 \in\mathbb{N}, the word w=σ1k1ω1σ2k2w = \sigma_1^{k_1}\omega_1\sigma_2^{k_2} contains exactly one occurrence of the substring ω1\omega_1, i.e., k1+1k_1 + 1 is the only integer such that w[k1+1:k1+∣ω1∣]=ω1w[k_1 + 1:k_1 + |\omega_1|] = \omega_1.

Proof. Let dd be a positive integer such that w[d:d+∣ω1∣−1]=ω1w[d:d + |\omega_1| - 1] = \omega_1. Since σ1≠ω1[1]\sigma_1 \ne\omega_1[1], we have d≥k1+1d \ge k_1 + 1. Since ω1\omega_1 does not end with σ2\sigma_2, we also have d≤k1+1d \le k_1 + 1.

Lemma 15. Let pp be as in (1), let MM be as in (2). If ω1≠ε\omega_1 \ne\varepsilon, choose letters σ1≠ω1[1]\sigma_1 \ne\omega_1[1] and σ2≠ω1[∣ω1∣]\sigma_2 \ne\omega_1[|\omega_1|]; otherwise choose σ1,σ2∈Σ\sigma_1,\sigma_2 \in\Sigma arbitrarily. Then ω0σ1k1ω1σ2k2ω2∈ELlen(p)\omega_0\sigma_1^{k_1}\omega_1\sigma_2^{k_2}\omega_2 \in\mathcal{E}\mathcal{L}_{\mathrm{len}}(p) if and only if (k1,k2)∈M(k_1,k_2) \in M.

Proof. The “if” direction is immediate from the definition of equal-length relational pattern languages. The “only if” direction follows likewise with the help of Lemma 14, since every word in εLlen(p)\varepsilon L_{\mathrm{len}}(p) is of the form ω0uω1vω2\omega_0u\omega_1v\omega_2 for (∣u∣,∣v∣)∈M(|u|,|v|)\in M. Lemma 14 forces ∣u∣=k1|u|=k_1, so that ∣v∣=k2|v|=k_2, implying (k1,k2)∈M(k_1,k_2)\in M.

The next lemma shows that there are constraints on the placement of variable blocks in any pattern p′p' whose language is contained in that of a pattern pp of form (1) and which generates the terminal word ω0ω1ω2\omega_0\omega_1\omega_2 of pp.

Lemma 16. Let p=ω0x⃗1ω1x⃗2ω2p=\omega_0\vec{x}_1\omega_1\vec{x}_2\omega_2 be as in (1), and let L′∈εLlen2L'\in\varepsilon\mathcal{L}^{2}_{\mathrm{len}} satisfy ω0ω1ω2∈L′⊆εLlen(p)\omega_0\omega_1\omega_2\in L'\subseteq\varepsilon L_{\mathrm{len}}(p). Let p′p' be a pattern with at most two variable blocks that generates L′L'. Then p′=ω0′x⃗1′ω1′x⃗2′ω2′p'=\omega'_0\vec{x}'_1\omega'_1\vec{x}'_2\omega'_2 where ω0′,ω1′,ω2′∈Σ∗\omega'_0,\omega'_1,\omega'_2\in\Sigma^*, x⃗1′,x⃗2′∈X∗\vec{x}'_1,\vec{x}'_2\in X^*, and ω0′ω1′ω2′=ω0ω1ω2\omega'_0\omega'_1\omega'_2=\omega_0\omega_1\omega_2. Moreover, the following two statements hold.

  1. If x⃗1′≠ε\vec{x}'_1\ne\varepsilon, then ∣ω0∣≤∣ω0′∣≤∣ω0ω1∣|\omega_0|\le|\omega'_0|\le|\omega_0\omega_1|.

  2. If x⃗2′≠ε\vec{x}'_2\ne\varepsilon, then ∣ω2∣≤∣ω2′∣≤∣ω1ω2∣|\omega_2|\le|\omega'_2|\le|\omega_1\omega_2|.

In particular, p′p' has the prefix ω0\omega_0 and the suffix ω2\omega_2.

Proof. Since L′⊆εLlen(p)L'\subseteq\varepsilon L_{\mathrm{len}}(p), every word of L′L' has length at least ∣ω0ω1ω2∣|\omega_0\omega_1\omega_2|; as ω0ω1ω2∈L′\omega_0\omega_1\omega_2\in L', the word ω0ω1ω2\omega_0\omega_1\omega_2 is the shortest word in L′L', and thus the terminal word of p′p', by Observation 2. It remains to show statements 1 and 2. We prove only statement 1; statement 2 follows by a completely symmetric argument.

Suppose x⃗1′≠ε\vec{x}'_1\ne\varepsilon, but ∣ω0∣>∣ω0′∣|\omega_0|>|\omega'_0| or ∣ω0′∣>∣ω0ω1∣|\omega'_0|>|\omega_0\omega_1|.

If ∣ω0∣>∣ω0′∣|\omega_0|>|\omega'_0| (so that, in particular, ω0≠ε\omega_0\ne\varepsilon), then let σ∈Σ\sigma\in\Sigma be a letter distinct from the last letter in ω0\omega_0. Now consider a substitution for p′p' that replaces every occurrence of every variable in x⃗1′\vec{x}'_1 with σ∣ω0∣\sigma^{|\omega_0|} and erases all other variables. This substitution generates a word in εLlen(p′)(=L′)\varepsilon L_{\mathrm{len}}(p') (=L') that does not begin with ω0\omega_0. Since every word in εLlen(p)\varepsilon L_{\mathrm{len}}(p) begins with ω0\omega_0, this yields a contradiction to L′⊆εLlen(p)L'\subseteq\varepsilon L_{\mathrm{len}}(p).

If ∣ω0′∣>∣ω0ω1∣|\omega'_0|>|\omega_0\omega_1|, then ∣ω1′ω2′∣<∣ω2∣|\omega'_1\omega'_2|<|\omega_2|, and we obtain a contradiction by considering a substitution for p′p' that replaces every variable in p′p' with τ∣ω2∣\tau^{|\omega_2|}, where τ\tau is a letter distinct from the first letter in ω2\omega_2. Such a substitution generates a word that does not end with ω2\omega_2, unlike all words in εLlen(p)\varepsilon L_{\mathrm{len}}(p).

Lemma 17. Let ∣Σ∣>2|\Sigma|>2, let p=ω0x⃗1ω1x⃗2ω2p=\omega_0\vec{x}_1\omega_1\vec{x}_2\omega_2 be as in (1), and let MM be as in (2). If ω1≠ε\omega_1\ne\varepsilon, choose letters σ1≠ω1[1]\sigma_1\ne\omega_1[1] and σ2≠ω1[∣ω1∣]\sigma_2\ne\omega_1[|\omega_1|]; otherwise choose σ1,σ2∈Σ\sigma_1,\sigma_2\in\Sigma arbitrarily. Then

T:={ω0ω1ω2}∪{ω0σ1k1ω1σ2k2ω2∣(k1,k2)∈mg⁡(M)}T:=\{\omega_0\omega_1\omega_2\}\cup\{\omega_0\sigma_1^{k_1}\omega_1\sigma_2^{k_2}\omega_2\mid(k_1,k_2)\in\operatorname{mg}(M)\}

is a telltale of εLlen(p)\varepsilon L_{\mathrm{len}}(p) with respect to εLlen2\varepsilon\mathcal{L}^{2}_{\mathrm{len}}.

Proof. Note that the letters σ1\sigma_1 and σ2\sigma_2 satisfy the assumption of Lemma 14. Thus, T⊆εLlen(p)T\subseteq\varepsilon L_{\mathrm{len}}(p) follows from Lemma 15.

Let L′∈εLlen2L'\in\varepsilon\mathcal{L}^{2}_{\mathrm{len}} with T⊆L′⊆Llen(p)T\subseteq L'\subseteq L_{\mathrm{len}}(p). We will show L′=εLlen(p)L'=\varepsilon L_{\mathrm{len}}(p). The latter is immediate if x⃗1=x⃗2=ε\vec{x}_1=\vec{x}_2=\varepsilon, since then T=L′=εLlen(p)={ω0ω1ω2}T=L'=\varepsilon L_{\mathrm{len}}(p)=\{\omega_0\omega_1\omega_2\}. So suppose pp has at least one non-empty variable block, so that εLlen(p)\varepsilon L_{\mathrm{len}}(p) is infinite and ∣T∣>1|T|>1.

Let p′=ω0′x⃗1′ω1′x⃗2′ω2′p'=\omega'_0\vec{x}'_1\omega'_1\vec{x}'_2\omega'_2 be a pattern with at most two variable blocks such that L′=εLlen(p′)L'=\varepsilon L_{\mathrm{len}}(p'). By Lemma 16, we know ω0′ω1′ω2′=ω0ω1ω2\omega'_0\omega'_1\omega'_2=\omega_0\omega_1\omega_2, and p′p' has the prefix

ω0\omega_0 and the suffix ω2\omega_2. Moreover, since T⊆εLlen⁡(p′)T \subseteq\varepsilon L_{\operatorname{len}(p')}, the pattern p′p' has at least one (non-empty) variable block.

We prove two crucial claims.

Claim 1: If x⃗1≠ε\vec{x}_1 \ne\varepsilon, then p′p' starts with ω0x\omega_0 x for some x∈Xx \in X. Since x⃗1≠ε\vec{x}_1 \ne\varepsilon, some (k1,k2)∈mg⁡(M)(k_1,k_2) \in\operatorname{mg}(M) satisfies k1>0k_1 > 0. Therefore, the word ω0σ1k1ω1σ2k2ω2∈T⊆L′\omega_0\sigma_1^{k_1}\omega_1\sigma_2^{k_2}\omega_2 \in T \subseteq L' has the letter σ1\sigma_1 immediately after ω0\omega_0. If the leftmost non-empty variable block of p′p' began at a position d>∣ω0∣+1d > |\omega_0|+1, every word of L′L' would begin with (ω0ω1ω2)[1:d−1](\omega_0\omega_1\omega_2)[1:d-1], whose letter immediately after ω0\omega_0 is ω1[1]≠σ1\omega_1[1] \ne\sigma_1. Therefore, the leftmost non-empty variable block of p′p' begins at a position d≤∣ω0∣+1d \le|\omega_0|+1. By Lemma 16, p′p' has the prefix ω0\omega_0, so that d=∣ω0∣+1d=|\omega_0|+1. This proves Claim 1.

Claim 2: If x⃗2≠ε\vec{x}_2 \ne\varepsilon, then p′p' ends with yω2y\omega_2 for some y∈Xy \in X. The proof of this claim is symmetric to the proof of Claim 1.

Let us distinguish two cases.

Case 1: pp has two variable blocks. Since pp and p′p' have the same terminal word, with Claim 1 and Claim 2 we obtain that p′p' has two variable blocks, starts with ω0x\omega_0x and ends with yω2y\omega_2, where x,y∈Xx,y \in X. This yields p′=ω0x⃗1′ω1x⃗2′ω2p'=\omega_0\vec{x}'_1\omega_1\vec{x}'_2\omega_2 where x⃗1′,x⃗2′\vec{x}'_1,\vec{x}'_2 are non-empty variable blocks. Let M′M' be the monoid generated by the set of gap vectors of p′p'. Since εLlen⁡(p′)\varepsilon L_{\operatorname{len}(p')} contains every word of the form ω0σ1k1ω1σ2k2ω2\omega_0\sigma_1^{k_1}\omega_1\sigma_2^{k_2}\omega_2 where (k1,k2)∈mg⁡(M)(k_1,k_2) \in\operatorname{mg}(M), we obtain mg⁡(M)⊆M′\operatorname{mg}(M) \subseteq M', and thus M⊆M′M \subseteq M'. This implies εLlen⁡(p)⊆εLlen⁡(p′)\varepsilon L_{\operatorname{len}(p)} \subseteq\varepsilon L_{\operatorname{len}(p')}, i.e., εLlen⁡(p′)=εLlen⁡(p)\varepsilon L_{\operatorname{len}(p')}=\varepsilon L_{\operatorname{len}(p)}.

Case 2: pp has exactly one variable block. By our normalization, x⃗1≠ε=x⃗2\vec{x}_1 \ne\varepsilon=\vec{x}_2. Then p=ω0x⃗1ω1ω2p=\omega_0\vec{x}_1\omega_1\omega_2. By Claim 1, p′p' starts with ω0x⃗1′\omega_0\vec{x}'_1. Specifically, p′=ω0x⃗1′μ1x⃗2′μ2p'=\omega_0\vec{x}'_1\mu_1\vec{x}'_2\mu_2, where μ1μ2=ω1ω2\mu_1\mu_2=\omega_1\omega_2. If p′p' has two variable blocks, i.e., x⃗2′≠ε\vec{x}'_2 \ne\varepsilon and μ1≠ε\mu_1 \ne\varepsilon, then p′p' can generate strings not ending in ω1ω2\omega_1\omega_2, contradicting εLlen⁡(p′)⊆εLlen⁡(p)\varepsilon L_{\operatorname{len}(p')} \subseteq\varepsilon L_{\operatorname{len}(p)}. So p′p' has only one variable block, and p′=ω0x⃗1′ω1ω2p'=\omega_0\vec{x}'_1\omega_1\omega_2. Let M′M' be the monoid generated by the set of gap vectors of p′p'. As in Case 1, we obtain mg⁡(M)⊆M′\operatorname{mg}(M) \subseteq M', and thus M⊆M′M \subseteq M', which finally yields εLlen⁡(p′)=εLlen⁡(p)\varepsilon L_{\operatorname{len}(p')}=\varepsilon L_{\operatorname{len}(p)}. □\square

We are now ready to prove Theorem 13.

Proof. (of Theorem 13.) Immediate from Lemma 17 and Angluin’s characterization, which states that an indexed family (Li)i∈N(L_i)_{i\in\mathbb{N}} of languages is learnable in the limit from positive data if and only if there is an effective procedure that, given an index ii, enumerates a telltale for LiL_i with respect to {Li∣i∈N}\{L_i \mid i\in\mathbb{N}\} [11]. Here note that the telltales in Lemma 17 can obviously be enumerated effectively, since the set of minimal generators of the underlying monoid MM is a finite subset of the corresponding set of gap vectors. □\square

It is worth noting that the telltales of Lemma 17 are of size linear in the length of the underlying patterns, both in terms of the number of words in the telltales, and in terms of the length of these words.

Iterative Learning of Patterns with at Most One Variable Block

An iterative learner computes each hypothesis from its previous hypothesis and the current example only, ignoring the examples seen in previous steps [13]. Lange and Wiehagen [4] showed that Angluin’s pattern languages can be learned iteratively in the limit from positive data. We now show that the equal-length pattern languages with at most one variable block can be learned iteratively as well, without any memory beyond the hypothesis, and that this holds even over a binary alphabet.

Definition 18 ([13]). A learner AA is iterative if, for any input (t0,t1,…,tn)(t_0,t_1,\ldots,t_n) with n>0n > 0, the output A(t0,t1,…,tn)A(t_0,t_1,\ldots,t_n) depends only on tnt_n and A(t0,t1,…,tn−1)A(t_0,t_1,\ldots,t_{n-1}).

Let Elen1\mathcal{E}^{1}_{\mathrm{len}} be the class of the languages εLlen(p)\varepsilon L_{\mathrm{len}}(p) of patterns of the form p=ωx⃗ω‾p = \omega\vec{x}\overline{\omega} with ω,ω‾∈Σ∗\omega,\overline{\omega} \in\Sigma^{*}, x⃗∈X∗\vec{x} \in X^{*}, and p≠εp \ne\varepsilon, i.e., patterns with at most one variable block. If the variables in pp occur with multiplicities g1,…,gkg_1,\ldots,g_k and M=⟨g1,…,gk⟩⊆NM = \langle g_1,\ldots,g_k\rangle\subseteq\mathbb{N} is the numerical monoid they generate, Observation 2 gives

εLlen(p)={ωuω‾∣u∈Σ∗, ∣u∣∈M}=:ωΣMω‾.(3)\varepsilon L_{\mathrm{len}}(p) = \{\omega u \overline{\omega} \mid u \in\Sigma^{*},\ |u| \in M\} =: \omega\Sigma^{M} \overline{\omega}. \tag*{(3)}

Every finite set of positive integers occurs as the set of variable multiplicities of such a pattern. Note that, within this section, MM is always a submonoid of N\mathbb{N}.

Given an unknown target pattern pp of this form, a learner has to identify three items: the prefix ω\omega, the suffix ω‾\overline{\omega}, and the monoid MM. The prefix and the suffix are the longest common prefix and suffix of all examples, and these can be updated one example at a time. Once they are correct, the length of every example minus ∣ωω‾∣|\omega\overline{\omega}| is an element of MM, and the learner collects these elements, keeping only the minimal generators. All of this information can be stored in the hypothesis itself, which can then be updated as needed, so that the learner is iterative.

Notation.

For words u,wu,w let lcp⁡(u,w)\operatorname{lcp}(u,w) and lcs⁡(u,w)\operatorname{lcs}(u,w) be their longest common prefix and suffix, and for a set DD of words let lcp⁡(D)\operatorname{lcp}(D) and lcs⁡(D)\operatorname{lcs}(D) be the longest common prefix and suffix of all words in DD. Clearly,

(L=ωΣMω‾ with M≠{0}) implies (lcp⁡(L)=ω and lcs⁡(L)=ω‾).(4)(L = \omega\Sigma^{M}\overline{\omega}\text{ with }M \ne\{0\}) \text{ implies } (\operatorname{lcp}(L) = \omega\text{ and }\operatorname{lcs}(L) = \overline{\omega}). \tag*{(4)}

The learner Ait\mathrm{A}_{\mathrm{it}}.

In step 0, on the first example t0t_0, the learner Ait\mathrm{A}_{\mathrm{it}} outputs the pattern p0:=t0p_0 := t_0. In step n≥1n \ge1, the learner has access to input datum tnt_n and its previous hypothesis, which is a pattern pn−1p_{n-1}.

  1. If pn−1=tnp_{n-1} = t_n, the learner outputs pn:=pn−1=tnp_n := p_{n-1} = t_n. (Note that the learner will output a hypothesis w∈Σ∗w \in\Sigma^{*} if and only if all examples seen so far equal ww.)

  1. If pn−1∈Σ∗p_{n-1} \in\Sigma^{*}, but pn−1≠tnp_{n-1} \ne t_n, then let r:=∣tn∣−∣lcp⁡(pn−1,tn)∣−∣lcs⁡(pn−1,tn)∣r := |t_n| - |\operatorname{lcp}(p_{n-1},t_n)| - |\operatorname{lcs}(p_{n-1},t_n)|. The learner resets the (currently empty) variable block:

  • If r>0r > 0, then the learner outputs pn:=lcp⁡(pn−1,tn)x1rlcs⁡(pn−1,tn)p_n := \operatorname{lcp}(p_{n-1},t_n)x_1^r\operatorname{lcs}(p_{n-1},t_n); this entails the conjecture that M=⟨r⟩M = \langle r\rangle.

  • If r≤0r \le0, then the learner outputs pn:=lcp⁡(pn−1,tn)x1x2lcs⁡(pn−1,tn)p_n := \operatorname{lcp}(p_{n-1},t_n)x_1x_2\operatorname{lcs}(p_{n-1},t_n).

(Note that, in case r=1r = 1, the hypothesis pn:=lcp⁡(pn−1,tn)x1lcs⁡(pn−1,tn)p_n := \operatorname{lcp}(p_{n-1},t_n)x_1\operatorname{lcs}(p_{n-1},t_n) is equivalent to a hypothesis of the form lcp⁡(pn−1,tn)x1x2lcs⁡(pn−1,tn)\operatorname{lcp}(p_{n-1},t_n)x_1x_2\operatorname{lcs}(p_{n-1},t_n) that may be output in some situation where r≤0r \le0, but the learner uses two different representations of the same language to be able to distinguish these two cases in step n+1n + 1. This is the only form in which the learner uses two representations of the same language.)

  1. If pn−1=vx⃗vˉp_{n-1} = v\vec{x}\bar{v} for v,vˉ∈Σ∗v,\bar{v} \in\Sigma^* and x⃗∈X+\vec{x} \in X^+, then let v′:=lcp⁡(v,tn)v' := \operatorname{lcp}(v,t_n), vˉ′:=lcs⁡(vˉ,tn)\bar{v}' := \operatorname{lcs}(\bar{v},t_n), and r:=∣tn∣−∣v′∣−∣vˉ′∣r := |t_n| - |v'| - |\bar{v}'|.

  • If (v′,vˉ′)=(v,vˉ)(v',\bar{v}') = (v,\bar{v}), and x⃗=x1x2\vec{x} = x_1x_2, then the learner outputs (i) pn:=v′x1rvˉ′p_n := v'x_1^r\bar{v}', if r>0r > 0, which entails the conjecture that M=⟨r⟩M = \langle r\rangle, and outputs (ii) pn:=v′x1x2vˉ′p_n := v'x_1x_2\bar{v}', if r≤0r \le0.

  • If (v′,vˉ′)=(v,vˉ)(v',\bar{v}') = (v,\bar{v}), x⃗≠x1x2\vec{x} \ne x_1x_2, and x⃗=x1g1⋯xkgk\vec{x} = x_1^{g_1}\cdots x_k^{g_k} where k>0k > 0 and gi>0g_i > 0 for i∈{1,…,k}i \in\{1,\ldots,k\}, then (i) if r≤0r \le0, the learner outputs pn:=pn−1p_n := p_{n-1}; (ii) if r>0r > 0, the learner outputs pn:=v′x1g1′x2g2′⋯xlgl′vˉ′p_n := v'x_1^{g'_1}x_2^{g'_2}\cdots x_l^{g'_l}\bar{v}', where {g1′,g2′,…,gl′}=mg⁡({g1,…,gk,r})\{g'_1,g'_2,\ldots,g'_l\} = \operatorname{mg}(\{g_1,\ldots,g_k,r\}) and g1′<g2′<⋯<gl′g'_1 < g'_2 < \cdots< g'_l. This entails the conjecture that M=⟨g1,…,gk,r⟩M = \langle g_1,\ldots,g_k,r\rangle.

  • If (v′,vˉ′)≠(v,vˉ)(v',\bar{v}') \ne(v,\bar{v}), then the learner resets the variable block:

    • If r>0r > 0, then the learner outputs pn:=v′x1rvˉ′p_n := v'x_1^r\bar{v}'; this entails the conjecture that M=⟨r⟩M = \langle r\rangle.

    • If r≤0r \le0, then the learner outputs pn:=v′x1x2vˉ′p_n := v'x_1x_2\bar{v}'.

By definition, AitA_{\mathrm{it}} is an iterative learner. It should be noted that hypotheses of the form vx1x2vˉvx_1x_2\bar{v} are the only ones carrying information beyond the language of the hypothesis; they mark transient states at which the learner knows that at least one variable must occur in the target pattern, but nothing is known about the multiplicities of variables as of yet. Hypotheses of this form are never used in the limit; i.e., the learner’s output on a valid text for a language in Elen1\mathcal{E}_{\mathrm{len}}^1 will not converge to such a hypothesis (see the proof of Theorem 20 for details).

Example 19. Let L=abΣ⟨2,3⟩bL = ab\Sigma^{\langle2,3\rangle}b over Σ={a,b}\Sigma= \{a,b\}, and consider a text beginning with abaab, abbbbb, abaaab, ababb.

  • After abaab the learner AitA_{\mathrm{it}} outputs abaab.

  • After abbbbb: lcp⁡(abaab,abbbbb)=ab\operatorname{lcp}(\text{abaab},\text{abbbbb}) = ab, lcs⁡(abaab,abbbbb)=b\operatorname{lcs}(\text{abaab},\text{abbbbb}) = b, and r=6−2−1=3r = 6 - 2 - 1 = 3. The learner outputs abx13babx_1^3b.

  • After abaaab: the prefix and suffix do not change (v=v′=abv = v' = ab, vˉ=vˉ′=b\bar{v} = \bar{v}' = b) and r=3r = 3, so the output stays abx13babx_1^3b.

  • After ababb: the prefix and suffix do not change (v=v′=abv = v' = ab, vˉ=vˉ′=b\bar{v} = \bar{v}' = b) and r=2r = 2. Since mg⁡({2,3})={2,3}\operatorname{mg}(\{2,3\}) = \{2,3\}, the learner AitA_{\mathrm{it}} outputs abx12x23babx_1^2x_2^3b, which generates LL.

Theorem 20. Let ∣Σ∣≥2|\Sigma| \ge2. Then AitA_{\mathrm{it}} learns Elen1\mathcal{E}_{\mathrm{len}}^1 in the limit from positive data. In particular, Elen1\mathcal{E}_{\mathrm{len}}^1 is learnable in the limit from positive data by an iterative learner.

Proof. Let p=ωx⃗ωˉp = \omega\vec{x}\bar{\omega} be the target pattern, and let s:=ωωˉs := \omega\bar{\omega}. Let Dn={t0,t1,…,tn}D_n = \{t_0, t_1, \ldots, t_n\} be the set of examples collected up until step nn.

Invariant. By induction on nn, the following facts are immediate from the definition of Ait\mathit{Ait}:

  1. If Ait\mathit{Ait}’s hypothesis at the end of step nn is w∈Σ∗w \in\Sigma^*, then Dn={w}D_n = \{w\}.

  2. If Ait\mathit{Ait}’s hypothesis at the end of step nn is vx1x2vˉv x_1 x_2 \bar{v}, then v=lcp⁡(Dn)v = \operatorname{lcp}(D_n), vˉ=lcs⁡(Dn)\bar{v} = \operatorname{lcs}(D_n) and, if n0n_0 is the last time step at which Ait\mathit{Ait} reset the variable block, then ∣tj∣−∣v∣−∣vˉ∣≤0|t_j|-|v|-|\bar{v}| \le0 for n0≤j≤nn_0 \le j \le n.

  3. If Ait\mathit{Ait}’s hypothesis at the end of step nn is vx1g1⋯xkgkvˉv x_1^{g_1}\cdots x_k^{g_k}\bar{v}, then v=lcp⁡(Dn)v = \operatorname{lcp}(D_n), vˉ=lcs⁡(Dn)\bar{v} = \operatorname{lcs}(D_n) and, if n0n_0 is the last time step at which Ait\mathit{Ait} reset the variable block, then ⟨g1,…,gk⟩\langle g_1,\ldots,g_k\rangle is generated by the strictly positive values ∣tj∣−∣v∣−∣vˉ∣|t_j|-|v|-|\bar{v}| for n0≤j≤nn_0 \le j \le n.

Observe that the learner Ait\mathit{Ait} resets the variable block only a finite number of times. This is true because, after the first reset the learner never outputs a word in Σ∗\Sigma^*, and every further reset strictly shortens vv or vˉ\bar{v}, both of which have length at most ∣t0∣|t_0|.

Let the target be L=ωΣMωˉL = \omega\Sigma^M\bar{\omega} and recall s=ωωˉs = \omega\bar{\omega}. If M={0}M = \{0\}, then L={s}L = \{s\}, every example equals ss, and the learner outputs ss forever.

Let M≠{0}M \ne\{0\}. Then LL is infinite, so the learner must reset the variable block at least once. Since Ait\mathit{Ait} resets the variable block only a finite number of times, there is some time step n0n_0 at which the last reset has occurred. From then on, vv and vˉ\bar{v} do not change. By the invariant, we have v=lcp⁡(Dn)=lcp⁡(Dn0)=ωv = \operatorname{lcp}(D_n) = \operatorname{lcp}(D_{n_0}) = \omega and vˉ=lcs⁡(Dn)=lcs⁡(Dn0)=ωˉ\bar{v} = \operatorname{lcs}(D_n) = \operatorname{lcs}(D_{n_0}) = \bar{\omega} for all n≥n0n \ge n_0. (Note that the text eventually contains two words whose lcp is exactly ω\omega, which exist by (4) since M≠{0}M \ne\{0\}. Likewise, the text eventually contains two words whose lcs is exactly ωˉ\bar{\omega}.) Consequently, ∣tj∣−∣v∣−∣vˉ∣=∣tj∣−∣s∣∈M|t_j|-|v|-|\bar{v}| = |t_j|-|s| \in M for every example tjt_j. Hence, from step n0n_0 onward, the learner outputs a pattern of the form ωx⃗′ωˉ\omega\vec{x}'\bar{\omega} such that either x⃗′=x1x2\vec{x}' = x_1x_2 or εLlen(ωx⃗′ωˉ)⊆εLlen(p)\varepsilon_{L_{\mathrm{len}}(\omega\vec{x}'\bar{\omega})} \subseteq\varepsilon_{L_{\mathrm{len}}(p)}.

We now show the key claim: for every m∈M∖{0}m \in M \setminus\{0\}, some word of LL of length ∣s∣+m|s|+m appears in the text at a step j≥n0j \ge n_0. Since every word of LL appears in the text, it suffices to find a word of LL of length ∣s∣+m|s|+m that is not among the examples before step n0n_0.

  • If the restart at n0n_0 was the first one, all earlier examples equal a single word ww, while LL contains ∣Σ∣m≥2|\Sigma|^m \ge2 words of length ∣s∣+m|s|+m.

  • Otherwise, the restart at n0n_0 shortened vv or vˉ\bar{v}. Before step n0n_0, the words vv and vˉ\bar{v} were the longest common prefix and suffix of some words of LL, so they extended ω\omega and ωˉ\bar{\omega}, respectively, and at least one of them was a strict extension—say vv; the case of vˉ\bar{v} is symmetric. Let σ\sigma be the letter of vv following ω\omega. All examples before step n0n_0 begin with ωσ\omega\sigma, but the word ωσˉωˉ∈L\omega\bar{\sigma}\bar{\omega} \in L with σˉ≠σ\bar{\sigma} \ne\sigma, σˉ∈Σ\bar{\sigma} \in\Sigma, and ∣u′∣=m−1|u'| = m-1 does not.

Let g1,…,gkg_1,\ldots,g_k be the multiplicities of the variables in the target pattern, where we assume without loss of generality that {g1,…,gk}=mg⁡({g1,…,gk})\{g_1,\ldots,g_k\} = \operatorname{mg}(\{g_1,\ldots,g_k\}). Note that ⟨g1,…,gk⟩=M\langle g_1,\ldots,g_k\rangle= M. Let g1(n),…,gk(n)(n)g_1^{(n)},\ldots,g_{k^{(n)}}^{(n)} be the multiplicities of the variables in the pattern output by Ait\mathit{Ait} in step nn. By the claim and the invariant, there is n1≥n0n_1 \ge n_0 such that ⟨g1(n),…,gk(n)(n)⟩\langle g_1^{(n)},\ldots,g_{k^{(n)}}^{(n)}\rangle contains g1,…,gkg_1,\ldots,g_k for all n≥n1n \ge n_1, and therefore ⟨g1(n),…,gk(n)(n)⟩=M\langle g_1^{(n)},\ldots,g_{k^{(n)}}^{(n)}\rangle= M. Since mg⁡\operatorname{mg} depends only on the generated monoid, {g1(n),…,gk(n)(n)}=mg⁡(M)\{g_1^{(n)},\ldots,g_{k^{(n)}}^{(n)}\} = \operatorname{mg}(M) for n≥n1n \ge n_1. So the learner outputs a fixed pattern that generates LL from time step n1n_1 onward.

Conclusions

This paper resolved an open question on the learnability of erasing equal-length relational pattern languages in the limit. In particular, it was shown that, over a binary alphabet, ELlen\mathcal{E}_{\mathrm{Llen}} is not learnable from positive data: the language of the relational pattern p:=x1aax1x2x2bx3p := x_1 a a x_1 x_2 x_2 b x_3 is the union of a strictly increasing chain of languages of the class and thus has no telltale (Theorem 11). Since pp as well as all the underlying patterns in this chain have exactly three variable blocks, our non-learnability result already holds for the subclass of languages generated by patterns with exactly three variable blocks.

This result was contrasted with two positive learnability results for structurally much simpler subclasses:

  • The subclass of languages generated by patterns with at most two variable blocks is learnable in the limit from positive data, for every alphabet with at least two letters (Theorem 13).

  • The subclass of languages generated by patterns with at most one variable block is learnable in the limit from positive data by an iterative learner, for every alphabet with at least two letters (Theorem 20).

Given that (i) for alphabets of size at least three, the whole class of erasing equal-length relational pattern languages is learnable in the limit from positive data [9], and (ii) a wide variety of erasing equal-length relational pattern languages are known for which telltales exist even in case of binary alphabets [9], a natural next step is to characterize those patterns whose equal-length languages over binary alphabets have telltales.

Disclosure

Generative AI tools (specifically Anthropic’s Claude Opus 5.5) were used to help with working out details of some of our technical proofs, as well as with the proofreading. The authors assume full responsibility for the entire content and presentation of the paper.

Acknowledgements

S. Zilles was supported through a Canada CIFAR AI Chair at the Alberta Machine Intelligence Institute (Amii), through an NSERC Canada Research Chair, through the New Frontiers in Research Fund under grant no. NFRFE-2023-00109 and through the NSERC Discovery Grants program under application no. RGPIN-2026-05856.

References

  1. [1]Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21, 46–62 (1980)
  2. [2]Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: Proc. RIMS Symposia on Software Science and Engineering, pp. 115–127 (1982)
  3. [3]Gold, E.M.: Language identification in the limit. Inform. Control 10, 447–474 (1967)DOI
  4. [4]Lange, S., Wiehagen, R.: Polynomial-time inference of arbitrary pattern languages. New Generation Computing 8(4), 361–370 (1991)DOI
  5. [5]Reidenbach, D.: A non-learnable class of e-pattern languages. Theoretical Computer Science 350(1), 91–102 (2006)DOI
  6. [6]Reidenbach, D.: Discontinuities in pattern inference. Theor. Comput. Sci. 397, 166–193 (2008)DOI
  7. [7]Geilke, M., Zilles, S.: Learning relational patterns. In: ALT, pp. 84–98 (2011)DOI
  8. [8]Holte, R.C., Mousawi, S.M., Zilles, S.: Distinguishing relational pattern languages with a small number of short strings. In: ALT, pp. 498–514 (2022)
  9. [9]Mousawi, S.M., Zilles, S.: Positive characteristic sets for relational pattern languages. ArXiv abs/2511.12039 (2025)arxiv.org/abs/2511.12039
  10. [10]Jansen, K., Nowotka, D., Pirotton, L., Wambsganz, C., Wiedenhöft, M.: An analysis of decision problems for relational pattern languages under various constraints. ArXiv abs/2512.07476 (2025)arxiv.org/abs/2512.07476
  11. [11]Angluin, D.: Inductive inference of formal languages from positive data. Inform. Control 45, 117–135 (1980)
  12. [12]Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Information and Control 28(2), 125–155 (1975)DOI
  13. [13]Wiehagen, R.: Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. Elektronische Informationsverarbeitung und Kybernetik 12(1/2), 93–99 (1976)

Paper details

vlnc:W_32sbzrd8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents