CS Paper Radar

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

S. Mahmoud Mousawi, Sandra Zilles

cs.LO cs.FLcs.LG ·submitted 2026-10-29 01:41 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Encoding Trees: A Method for Producing a Variable-Length Prefix Code From Sets of Arbitrary Size

cs.IT ·2026-10-21 ·Bryony H. Laporte, Karen Rudie
theory similarity 0.64
Abstract · 31 pages, 18 figures, submitted to IEEE Transactions on Information Theory

In this work we formalize a new class of binary trees called encoding trees. We extend this structure in two ways, through labelling to create the class of labelled encoding trees, and pruning to create the class of pruned encoding trees. We discuss how these two extensions can be combined to create the the class of pruned labelled encoding trees. Using the supplementary results that we prove about these classes of trees, we construct a code that uses pruned labelled encoding trees to convert a string of symbols from a sequence of non-empty sets to a binary string. We prove that this code is a variable-length prefix code that can process any valid string of symbols from the given sequence of non-empty sets. Furthermore, we construct a code from the class of pruned labelled encoding trees that goes in the opposite direction, from binary strings to a string of symbols from a sequence of non-empty sets of arbitrary symbols. We prove that this code is also a variable-length prefix code that can process any binary string of any length, provided that the sequence of non-empty sets is sufficiently long. We provide an equation that establishes the minimum sequence length to encode any binary string of a given length, based on that length.

0.21

An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints

cs.FL cs.CC ·2026-10-05 ·Klaus Jansen, Dirk Nowotka, Lis Pirotton, Corinna Wambsganz, Max Wiedenhöft
publishedunusual similarity 0.64
Abstract · In Proceedings AFL 2026, arXiv:2608.23071. A full version of this paper, containing all proofs, can be found at arXiv:2512.07476

Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only terminals. In their original definition, patterns only allow for multiple distinct occurrences of some variables to be related by the equality relation, represented by using the same variable multiple times. In an extended notion, called relational patterns and relational pattern languages, variables may be related by arbitrary other relations, achieved by using regular patterns and relating individual variables independently from the patterns structure separately. We extend the ongoing investigation of the main decision problems for patterns (namely, the equivalence problem, the inclusion problem, and the membership problem) to relational pattern languages under a wide range of relevant individual relations, providing a comprehensive foundation in all three research directions.

0.62

Independent Languages and Witnesses of Dependence (Non-satisfaction)

cs.FL ·2026-08-25 ·Stavros Konstantinidis
published similarity 0.58
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the independent language property defined by the language equation φ(X)=\emptyset, where the expression φ involves the language variable X, constant languages, and standard regular operations including transductions, but not complementation. This property consists of all languages L satisfying φ(L)=\emptyset. Depending on the choice of the operations in φ, the equation defines a broad class of codes, including combinations of standard variable-length codes and error-detecting codes. We show that any φ-independence is a Jürgensen independence, we define what a witness of non-satisfaction of φ(X)=\emptyset is, for a language L, and we show how to compute a witness of non-satisfaction when L is regular. We also discuss the complexity of the problem, showing that the decision version of the problem is PSPACE-complete.

0.48

Non-Terminal Complexity of Simple Semi-Conditional Grammars

cs.FL math.LO ·2026-09-12 ·Henning Fernau, Sanjay Jain, Linus Richter, Frank Stephan, Dan Turetsky
theory similarity 0.57
Abstract · 26 pages

We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of alphabet size at least 3 which cannot be generated by any one-non-terminal SSCG. Finally, we prove that membership testing for SSCGs of two non-terminals is already NP-hard.

0.16

Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

cs.IT ·2026-09-29 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.56
Abstract · 52 pages

We construct systematic $q$-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length $n\ge2$, our first construction has length $n+3$ over an alphabet of size $q=2^s<2^{32}n^7$ for some integer $s$, with polynomial-time encoding and decoding. A cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size $O(n^4)$, leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size $q<(n+2)^4$. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for $n\ge2$.

0.12

Testing and Learning Symbolic Finite State Machines

cs.FL cs.SE ·2026-09-22 ·Wen-ling Huang, Jan Peleska
theory similarity 0.55
Abstract

Symbolic finite state machines (SFSMs) describe input/output behaviour using guards and output assignments with possibly infinite data domains. We study deterministic and completely specified SFSMs whose guards and output assignments depend only on the current input. We define finite representative input sets that contain witnesses for relevant guard overlaps and separating witnesses for output assignments that differ on those overlaps. Our main theorem shows that language equivalence of the finite instantiations implies language equivalence over the full input domain. This result transfers complete testing methods for deterministic finite state machines (DFSMs) to SFSMs, provided finite sets of admissible guards and output assignments and an upper bound on the number of distinguishable reachable states are known. Under these assumptions, a DFSM learner with complete testing can learn a finite instantiation, which is then lifted to an equivalent SFSM. We establish a bound on the size of representative input sets and give an SMT construction whose correctness and termination hold under stated solver assumptions.

0.18

A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners

cs.CL stat.MLcs.LGq-bio.NC ·2026-10-20 ·Rakesh Sengupta
theoryunusual similarity 0.55
Abstract

Gold's theorem shows that no learner can identify an arbitrary language in a superfinite class from positive presentations alone. We prove a positive result of a different shape. Fix an innate \emph{recursive contrast operator} $R$ mapping any string to a finite set of structurally bounded perturbations of it, and a discriminative scorer of bounded capacity trained by InfoNCE-style contrastive estimation \citep{vandenoord2018,macollins2018} on self-generated perturbations. Under a faithfulness condition relating operator, scorer, and target, the trained scorer achieves \emph{PAC conditional identification} from positive data alone: with high probability it ranks all but an $\varepsilon$-fraction of positives above every out-of-language perturbation in their own orbit, with sample complexity polynomial in the capacity, the orbit size, the score bound, and $1/\varepsilon$. The negatives are constructed by the learner, not supplied by an oracle, and no global normalizing constant over strings is ever computed. The misranking bound follows from the geometry of the contrastive loss---per-example loss floors plus a definite loss increment under misranking---yielding an $\varepsilon^{-2}$ rate, together with an explicit approximation gap that quantifies the cost of in-language (``colliding'') perturbations and vanishes for orbit-pure operators. The ranking guarantee lifts to a global membership classifier under a margin condition, and the same operator composed with the learned scorer is a normalization-free Metropolis--Hastings generator. We instantiate the hypotheses for substitutable context-free languages \citep{clarkeyraud2007} and the subregular classes \citep{heinz2010,hayashikamigaito2025}, and state an open conjecture locating the construction in the mildly context-sensitive hierarchy.

0.24

Pumping Constants for Infinite Alphabets

cs.FL ·2026-10-05 ·Yoav Danieli
publishedtheoryhot direction similarity 0.55
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

It is well known that the pumping lemma for regular languages over finite alphabets does not extend to infinite alphabets. Instead, the generalized version of the pumping lemma for infinite alphabets states that the pumped patterns need not be identical, but only equivalent up to a finite-order permutation of the alphabet. This generalized variant of the pumping lemma involves two parameters: the length of the pumped pattern and an upper bound on the order of the permutation. We improve the known permutation-order bounds from factorial to tight bounds governed by Landau's function. We also show that, if the pumping length is sufficiently large, then permutations of order at most two always suffice. Our main structural result concerns the one-register case: every one-register automaton satisfies the classical pumping lemma, with no alphabet permutation. We prove a quadratic upper bound on the pumping length and give a matching quadratic lower bound up to constant factors. The same classical pumping phenomenon is shown for hierarchical register automata. Finally, we prove that, in general, deciding whether a quasi-regular language is pumpable for given constants is undecidable, while the minimal classical pumping length is computable for non-guessing one-register automata.

0.68