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 and must eventually settle on a correct description for . 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 with respect to a family of languages is a finite subset of that is not contained in any language with . The uniform enumerability of a system of telltales is a necessary and sufficient condition for the learnability of a family 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 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 whose erasing equal-length relational language over a binary alphabet does not have a telltale with respect to . Consequently, for alphabets of only two letters, the class 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 by the sequence of terminals in the underlying pattern and by a finitely generated monoid of gap vectors.1 Roughly speaking, a word belongs to if it can be cut around the terminals of 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 , and has to identify . 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 such that does not possess a telltale with respect to the class .
The pattern , as well as all the patterns that witness the fact that 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 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 , we denote the set of finite strings over by and its subset of non-empty finite strings by . If is any string over , then we denote by the length of . We can then write for , where denotes the symbol at the th position in . Moreover, for any , the term refers to the substring of if , and to the empty string if . Likewise, whenever .
Throughout this document, we assume that is a finite alphabet of cardinality at least 2, and is a countably infinite set of variables, disjoint from . A pattern is a finite non-empty string over , with the property that variable may occur in only if all variables , for also occur in . If is a pattern containing all and only the variables for some , and variable occurs exactly () times in , then an equal-length substitution for is a mapping defined by
where and
This substitution generates from the string that is obtained if the th occurrence of the variable in (counted from the left) is replaced by , for each and each . 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 has no variables, i.e., , then the only word that can be generated from is the word itself.
For example, consider the pattern and the equal-length substitution defined by and . This substitution generates the string from . The (erasing) equal-length relational language of the pattern (over ) is the set of all strings that are generated from 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 belong to , 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 has a unique decomposition of the form
The non-empty are called the variable blocks of . We call the terminal word of and its gaps. For instance, has the gaps , , and . Its variable blocks are and .
For a variable in we define its gap vector by letting be the number of occurrences of in the gap . For a vector we write for its size, and for a set we write for the submonoid of generated by . For a submonoid let be the set of minimal generators of , i.e., the set of non-zero elements of that are not the sum of two non-zero elements of ; here . The set generates and is always contained in . For a finite set of integers, we use .
Definition 1. Let . A split of a word (with respect to ) is a factorization with . Its vector is , and denotes the set of vectors of all splits of . The fillings of a vector with respect to are the words in the set
For a set we let
The following observation, expressing the equal-length relational language of a pattern in terms of the fillings of its gap vectors, is immediate.
Observation 2 (Normal form). Let be a pattern with terminal word , and let be the set of gap vectors of its variables. Then
Conversely, for every word and every finite set there is a pattern with .
Example 3. Let . Its terminal word is and the gap vectors are , and . The substitution , , generates ; the terminals of give the split with vector . The same word has five further splits, with vectors , , , and . 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 is an infinite sequence with .
A learner is a mapping that takes as input any initial segment of any text of any target language. If defined, its output is a representation of some language , which is to be understood as the learner hypothesizing the target language to be . In general, the goal of a learner is to eventually identify an unknown language in a known class of languages, when gradually processing any text for .
Definition 4. Let be a class of languages and . Fix a numbering such that . A learner learns in the limit from positive data (with respect to ) if, for any text for , the following two properties hold:
is defined for every .
There exists some such that and for every .
The class is learnable in the limit from positive data if there is a numbering and a learner that learns every from positive data with respect to .
Angluin’s characterization of learnability in the limit from positive data [11] concerns computable learners for indexed families ; these are families for which a recursive procedure exists that, given , decides whether . 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 in a class is a finite set such that no satisfies .
Angluin’s result states that an indexed family of languages is learnable in the limit from positive data if and only if there is an effective procedure that, given an index , enumerates a telltale for with respect to . 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 of languages in the limit from positive data, then every has a telltale in .
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 . 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 and a chain of languages in whose union is . Every finite subset of is then contained in some , so has no telltale. Therefore, by Theorem 5, no learner can identify all of these languages.
The terminal word for our target language is . Gap vectors therefore have four coordinates, counting the variables before the first , between the two ’s, between the second and , and after . Let
The target is
For we let
Since , a pattern for has, for each , a variable occurring once before and times between the second and , in addition to the variable at the end of the pattern. For example,
The target pattern, as well as all patterns generating the languages for , have three variable blocks each. The target has the variable occurring only in the middle variable block; the languages 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:
and
In particular, and are submonoids of .
We first make a simple observation on the structure of the monoids representing our target language and the languages in the chain.
Lemma 6. and satisfy the following:
In particular, every vector of and of has second coordinate , and every vector of with first coordinate also has third coordinate .
Proof. Any element of is of the form with . Its third coordinate satisfies and . Conversely, a vector with and belongs to , as witnessed by .
Any element of is of the form plus a sum of vectors with . Its first coordinate is , and its third coordinate is a sum of odd numbers between and . Hence and . Conversely, let satisfy and for . Clearly, then for all .
It is straightforward to obtain the following chain.
Lemma 7. .
Proof. Every generator of is a generator of , and . Hence , from which the claim follows immediately.
Next, we show that every word in is contained in some language , , so that, together with Lemma 7, we obtain that the union of all languages in the chain equals .
Lemma 8. Let have a split with vector . Then . Consequently, .
Proof. Let . We find a split of whose vector lies in , distinguishing three cases.
Case . Then
since . All three summands belong to , so the given split already works.
Case and . Then .
Case and . The given split has the form with and . It uses the variable only in the middle variable block, corresponding to a vector which is not in , so we split differently, depending on the first letter of .
If begins with , then begins with . We use these three letters as the terminals. The resulting split has vector .
If begins with , say , then . We use the first letter of as the content of the first gap, its second and third letters as the two terminals , and the same as before. The second gap is empty, the third gap is of length , and the fourth gap is . The resulting split has vector
In every case, , using in the last case. Since every word of has a split with vector in , every word of belongs to some , and together with Lemma 7 we obtain .
Example 9. The word has the split vector in . Since begins with , we may use its first occurrence of as the terminals, which gives the vector ; so this word belongs to . The word also has the split vector . Since begins with , we shift the terminals one position to the right, obtaining with vector ; so this word belongs to . (Lemma 10 below will show that this word does not belong to .)
Finally, we demonstrate that the chain is strict.
Lemma 10. For every , the word
belongs to . Consequently, and .
Proof. We number the positions of from 0. The letter occurs at the positions 0, 1, 2 and at the even positions 4, 6, , ; the letter occurs at position 3, at the odd positions 5, 7, , , and at position . For instance, .
By Lemma 6, a split whose vector lies in or in uses two adjacent occurrences of as the terminals . After position 3 in , the letters and alternate, so the only adjacent pairs of ’s are at the position pairs and . Let be the position used for the terminal . A split using the pair and has the vector . Table 1 lists all possibilities.
| pair of ’s | position of | vector | membership |
| any | not in : first coordinate 0, third coordinate at least 1 | ||
| neither in nor in : third coordinate smaller than the first | |||
| odd, | neither in nor in : wrong parity | ||
| in , as ; not in , as |
Table 1. Possible combinations for positioning terminal symbols in , and resulting membership of the split vector in and .
The last row shows , and no row yields a vector of , so . By Lemma 8, applied to the split of the last row with , we have . Hence , and with Lemma 7 the chain is strict.
For example, for we obtain the following: has its adjacent ’s at position pairs and and its ’s at positions 3, 5, 6. The pair gives the vectors , and , none of which lies in . The pair gives , and ; the first two are not even in , and the third is .
We finally put everything together to obtain our main result.
Theorem 11. Let . Then the language has no telltale in . In particular, the class is not learnable in the limit from positive data, not even by a non-computable learner.
Proof. Let be finite. By Lemma 8, every word of belongs to some ; let be the largest index needed. By Lemma 7, , and by Lemma 10, . Since , the set is not a telltale of .
The binary alphabet is used at exactly one place, in the last case of the proof of Lemma 8: the first letter of is either , or , in which case the pair of terminals can be shifted one position to the right. Over a ternary alphabet , a word 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 , is the subclass of consisting of the languages whose terminal word does not contain or as a factor learnable in the limit from positive data? We leave this question open.
Observe that the language from Theorem 11, as well as all the languages in the chain in Lemma 7, are generated by patterns with exactly three variable blocks. We therefore obtain the following corollary.
Corollary 12. Let . Then the subclass of 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 be the class of the languages of patterns of the form
with , , and , i.e., patterns with at most two variable blocks. We require when both and . Moreover, when has exactly one variable block, we take . This section establishes the following result, which stands in contrast with Corollary 12.
Theorem 13. Let . Then 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 of the form (1) with the monoid generated by the set of gap vectors of the variables in . In particular,
Note that, by contrast with the previous section, within this section, is a submonoid of .
We begin with two straightforward lemmas.
Lemma 14. Let and let such that and . For all , the word contains exactly one occurrence of the substring , i.e., is the only integer such that .
Proof. Let be a positive integer such that . Since , we have . Since does not end with , we also have .
Lemma 15. Let be as in (1), let be as in (2). If , choose letters and ; otherwise choose arbitrarily. Then if and only if .
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 is of the form for . Lemma 14 forces , so that , implying .
The next lemma shows that there are constraints on the placement of variable blocks in any pattern whose language is contained in that of a pattern of form (1) and which generates the terminal word of .
Lemma 16. Let be as in (1), and let satisfy . Let be a pattern with at most two variable blocks that generates . Then where , , and . Moreover, the following two statements hold.
If , then .
If , then .
In particular, has the prefix and the suffix .
Proof. Since , every word of has length at least ; as , the word is the shortest word in , and thus the terminal word of , 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 , but or .
If (so that, in particular, ), then let be a letter distinct from the last letter in . Now consider a substitution for that replaces every occurrence of every variable in with and erases all other variables. This substitution generates a word in that does not begin with . Since every word in begins with , this yields a contradiction to .
If , then , and we obtain a contradiction by considering a substitution for that replaces every variable in with , where is a letter distinct from the first letter in . Such a substitution generates a word that does not end with , unlike all words in .
Lemma 17. Let , let be as in (1), and let be as in (2). If , choose letters and ; otherwise choose arbitrarily. Then
is a telltale of with respect to .
Proof. Note that the letters and satisfy the assumption of Lemma 14. Thus, follows from Lemma 15.
Let with . We will show . The latter is immediate if , since then . So suppose has at least one non-empty variable block, so that is infinite and .
Let be a pattern with at most two variable blocks such that . By Lemma 16, we know , and has the prefix
and the suffix . Moreover, since , the pattern has at least one (non-empty) variable block.
We prove two crucial claims.
Claim 1: If , then starts with for some . Since , some satisfies . Therefore, the word has the letter immediately after . If the leftmost non-empty variable block of began at a position , every word of would begin with , whose letter immediately after is . Therefore, the leftmost non-empty variable block of begins at a position . By Lemma 16, has the prefix , so that . This proves Claim 1.
Claim 2: If , then ends with for some . The proof of this claim is symmetric to the proof of Claim 1.
Let us distinguish two cases.
Case 1: has two variable blocks. Since and have the same terminal word, with Claim 1 and Claim 2 we obtain that has two variable blocks, starts with and ends with , where . This yields where are non-empty variable blocks. Let be the monoid generated by the set of gap vectors of . Since contains every word of the form where , we obtain , and thus . This implies , i.e., .
Case 2: has exactly one variable block. By our normalization, . Then . By Claim 1, starts with . Specifically, , where . If has two variable blocks, i.e., and , then can generate strings not ending in , contradicting . So has only one variable block, and . Let be the monoid generated by the set of gap vectors of . As in Case 1, we obtain , and thus , which finally yields .
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 of languages is learnable in the limit from positive data if and only if there is an effective procedure that, given an index , enumerates a telltale for with respect to [11]. Here note that the telltales in Lemma 17 can obviously be enumerated effectively, since the set of minimal generators of the underlying monoid is a finite subset of the corresponding set of gap vectors.
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 is iterative if, for any input with , the output depends only on and .
Let be the class of the languages of patterns of the form with , , and , i.e., patterns with at most one variable block. If the variables in occur with multiplicities and is the numerical monoid they generate, Observation 2 gives
Every finite set of positive integers occurs as the set of variable multiplicities of such a pattern. Note that, within this section, is always a submonoid of .
Given an unknown target pattern of this form, a learner has to identify three items: the prefix , the suffix , and the monoid . 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 is an element of , 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 let and be their longest common prefix and suffix, and for a set of words let and be the longest common prefix and suffix of all words in . Clearly,
The learner .
In step 0, on the first example , the learner outputs the pattern . In step , the learner has access to input datum and its previous hypothesis, which is a pattern .
If , the learner outputs . (Note that the learner will output a hypothesis if and only if all examples seen so far equal .)
If , but , then let . The learner resets the (currently empty) variable block:
If , then the learner outputs ; this entails the conjecture that .
If , then the learner outputs .
(Note that, in case , the hypothesis is equivalent to a hypothesis of the form that may be output in some situation where , but the learner uses two different representations of the same language to be able to distinguish these two cases in step . This is the only form in which the learner uses two representations of the same language.)
If for and , then let , , and .
If , and , then the learner outputs (i) , if , which entails the conjecture that , and outputs (ii) , if .
If , , and where and for , then (i) if , the learner outputs ; (ii) if , the learner outputs , where and . This entails the conjecture that .
If , then the learner resets the variable block:
If , then the learner outputs ; this entails the conjecture that .
If , then the learner outputs .
By definition, is an iterative learner. It should be noted that hypotheses of the form 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 will not converge to such a hypothesis (see the proof of Theorem 20 for details).
Example 19. Let over , and consider a text beginning with abaab, abbbbb, abaaab, ababb.
After abaab the learner outputs abaab.
After abbbbb: , , and . The learner outputs .
After abaaab: the prefix and suffix do not change (, ) and , so the output stays .
After ababb: the prefix and suffix do not change (, ) and . Since , the learner outputs , which generates .
Theorem 20. Let . Then learns in the limit from positive data. In particular, is learnable in the limit from positive data by an iterative learner.
Proof. Let be the target pattern, and let . Let be the set of examples collected up until step .
Invariant. By induction on , the following facts are immediate from the definition of :
If ’s hypothesis at the end of step is , then .
If ’s hypothesis at the end of step is , then , and, if is the last time step at which reset the variable block, then for .
If ’s hypothesis at the end of step is , then , and, if is the last time step at which reset the variable block, then is generated by the strictly positive values for .
Observe that the learner 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 , and every further reset strictly shortens or , both of which have length at most .
Let the target be and recall . If , then , every example equals , and the learner outputs forever.
Let . Then is infinite, so the learner must reset the variable block at least once. Since resets the variable block only a finite number of times, there is some time step at which the last reset has occurred. From then on, and do not change. By the invariant, we have and for all . (Note that the text eventually contains two words whose lcp is exactly , which exist by (4) since . Likewise, the text eventually contains two words whose lcs is exactly .) Consequently, for every example . Hence, from step onward, the learner outputs a pattern of the form such that either or .
We now show the key claim: for every , some word of of length appears in the text at a step . Since every word of appears in the text, it suffices to find a word of of length that is not among the examples before step .
If the restart at was the first one, all earlier examples equal a single word , while contains words of length .
Otherwise, the restart at shortened or . Before step , the words and were the longest common prefix and suffix of some words of , so they extended and , respectively, and at least one of them was a strict extension—say ; the case of is symmetric. Let be the letter of following . All examples before step begin with , but the word with , , and does not.
Let be the multiplicities of the variables in the target pattern, where we assume without loss of generality that . Note that . Let be the multiplicities of the variables in the pattern output by in step . By the claim and the invariant, there is such that contains for all , and therefore . Since depends only on the generated monoid, for . So the learner outputs a fixed pattern that generates from time step 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, is not learnable from positive data: the language of the relational pattern is the union of a strictly increasing chain of languages of the class and thus has no telltale (Theorem 11). Since 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]Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21, 46–62 (1980)
- [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]Gold, E.M.: Language identification in the limit. Inform. Control 10, 447–474 (1967)DOI
- [4]Lange, S., Wiehagen, R.: Polynomial-time inference of arbitrary pattern languages. New Generation Computing 8(4), 361–370 (1991)DOI
- [5]Reidenbach, D.: A non-learnable class of e-pattern languages. Theoretical Computer Science 350(1), 91–102 (2006)DOI
- [6]Reidenbach, D.: Discontinuities in pattern inference. Theor. Comput. Sci. 397, 166–193 (2008)DOI
- [7]Geilke, M., Zilles, S.: Learning relational patterns. In: ALT, pp. 84–98 (2011)DOI
- [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]Mousawi, S.M., Zilles, S.: Positive characteristic sets for relational pattern languages. ArXiv abs/2511.12039 (2025)arxiv.org/abs/2511.12039
- [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]Angluin, D.: Inductive inference of formal languages from positive data. Inform. Control 45, 117–135 (1980)
- [12]Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Information and Control 28(2), 125–155 (1975)DOI
- [13]Wiehagen, R.: Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. Elektronische Informationsverarbeitung und Kybernetik 12(1/2), 93–99 (1976)