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

S. Mahmoud Mousawi; Sandra Zilles

cs.LOOct 29, 2026

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

Authors: S. Mahmoud Mousawi, Sandra Zilles

Organizations: Department of Computer Science, University of Regina, Canada. · Alberta Machine Intelligence Institute.

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.

Figures & tables

pair of $a$ ’s	position $r$ of $b$	vector	membership
$(0,1)$	any $r\geq 3$	$(0,0,r-2,\cdot)$	not in $M_{t}$ : first coordinate $0$ , third coordinate at least $1$
$(1,2)$	$r=3$	$(1,0,0,\cdot)$	neither in $M$ nor in $M_{t}$ : third coordinate smaller than the first
$(1,2)$	$r$ odd, $5\leq r\leq 2t+5$	$(1,0,r-3,\cdot)$	neither in $M$ nor in $M_{t}$ : wrong parity
$(1,2)$	$r=2t+6$	$(1,0,2t+3,0)$	in $M_{t+1}$ , as $X_{1}+(t+1)X_{2}$ ; not in $M_{t}$ , as $2t+3>2t+1$

Table 1: Possible combinations for positioning terminal symbols in

w_{t}

, and resulting membership of the split vector in

M_{t+1}

and

M_{t}

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
May 28, 2026Wei Luo
School of Information Technology, Deakin University
On Language Generation in the Limit with Bounded Memory
May 28, 2026Jon Kleinberg, Anay Mehrotra, Amin Saberi +1Statistical Learning Theory Text Generation
Cornell University · Stanford University · Google Research
Causally Evaluating the Learnability of Formal Language Tasks
Jun 8, 2026Vésteinn Snæbjarnarson, Anej Svete, Josef Valvoda +3Language Modeling Causal Interventions in Language Models
1ETH Zürich · University of Copenhagen · *Now at Google

May 28, 2026J/K move · Enter open · S save

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

Wei Luo

School of Information Technology, Deakin University

Open paper AskPDF arXiv

Pattern languages are a classical model in formal language theory and algorithmic learning theory. This note formulates the problem of computing the inclusion depth of a pattern language: the length of the longest strict inclusion chain from the universal pattern language to the language generated by a given pattern. Inclusion depth captures the mind-change complexity of pattern identification from positive data. The central open question is whether the inclusion depth ID_Sigma(p) is computable for every pattern p over every finite alphabet Sigma with at least two symbols, and whether it is computable in polynomial time. A simple conjectured formula, ID_Sigma(p) = 2|p| - #var(p) - 1, would imply a linear-time algorithm. The problem connects pattern language inclusion, combinatorics on words, language identification in the limit, and mind-change-bounded learning.

Abstract

Explore similar work

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

On Language Generation in the Limit with Bounded Memory

Causally Evaluating the Learnability of Formal Language Tasks