CS Paper Radar

Semi-Linearity and Generalized Stratified Semi-Linearity beyond Context-Free Languages

Tomoyuki Yamakami

cs.FL cs.CC ·submitted 2026-10-14 04:21 UTC · v1
theory

Abstract

Parikh's famous theorem relates to the semi-linearity of context-free languages. We seek for expanding the scope of the semi-linear property from context-free languages to languages beyond them. Of those languages, this work focuses on the languages that are particularly recognized by one-way nondeterministic depth-k storage automata under a natural restriction of frozen blank sensitivity. Those languages (which are called $k$-storable languages) have been already proven to satisfy a natural generalization of the well-known pumping lemmas for regular and context-free languages. The semi-linearity of k-storable languages generalizes Parikh's theorem on the semi-linearity of context-free languages. As for bounded languages, Ginsburg and Spanier's well-known theorem characterizes context-free languages in terms of stratified semi-linearity. This notion is further generalized and is used to characterize the k-storable languages as well. Such a generalization is interesting in its own right. This helps us take an abstract treatment of k-storable languages without relying on "machines". Our results strengthen the belief that those languages are "natural" generalizations of context-free languages.

Comment
(10pt, 6 figures, 21 pages) This is a preliminary report

Closest papers

Nearest neighbours by meaning across the whole index.

Full AFLs Closed under Nested Iterated $k$-Variate Substitution and Depth-k Storage Automata

cs.FL cs.CC ·2026-10-14 ·Tomoyuki Yamakami
similarity 0.66
Abstract · (10pt, A4, 3 figures, 13 pages) This is a preliminary report

Greibach and Ginsburg (1969) studied abstract families of languages or AFLs. A full AFL is a class of languages closed under the following operations: homomorphism, inverse homomorphism, intersection with regular languages, union, concatenation, and Kleene star. Greibach (1970) used a restricted substitution, called nested iterated substitution, to introduce the notion of super AFLs, which are full AFLs that are further closed under nested iterated substitution. The smallest super AFL was shown to be the class of all context-free languages. From this fact, we focus on Greibach's limited, univariable application of nested iterated substitution and further generalize it into k-variate. This introduces the notion of nested iterated $k$-variate substitution whose definition does not rely on "machines". Recently, a "two-tape" version of Hibbard's (1967) rewriting systems, which were later reformulated by Pighizzini and Pisoni (2014) as k-limited automata with "single" input/work tapes, has been studied under the name of depth-k storage automata. This work unearths a few characteristics of the languages recognized by those automata under a restriction known as frozen blank sensitivity in terms of full AFLs and nested iterated k-variate substitution. This will promote a further abstract treatment of those languages.

0.28

Witness Languages for Pumping Lemmata

cs.FL ·2026-10-11 ·Pamela Fleischmann, Annika Huch, Christian Rauch
similarity 0.63
Abstract

In 2022 Dassow and Jecker started investigations on the operational complexity of the pumping constant w.r.t.~two pumping lemmata. Since then, the research on pumping lemmata emerged to several variants for regular as well as context-free languages. Within this work, we further investigate the \emph{witnesses} of regular languages (firstly introduced by Rauch) w.r.t.~different pumping lemmata: For a language $L$ and a minimal pumping constant $K$, a \emph{witness} of a language is a word that cannot be \emph{pumped} by $K$ w.r.t.~the given pumping lemma. Here, the pumping constant is minimal if for all smaller numbers, the pumping lemma condition is not satisfied. Alongside combinatorial investigations on (unary) witness languages, we introduce and study the measure of scattered factor distance, which is related to minimal pumping constants. We present bounds on minimal pumping constants by the scattered factor distance and show that deciding, given two regular languages, whether one of them is equal to the witness language of the second is \coNP-complete.

0.30

Algebraic Decomposition Theory for Transformer Length Generalization

cs.FL cs.AI ·2026-08-13 ·Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs +3 more
similarity 0.62
Abstract · 54 pages, 12 figures

Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit length generalization. It is not even known which regular languages transformers length-generalize on -- and this is a foundational class of languages. Our contributions are to establish the first complete characterization of which regular languages transformers length-generalize on and provide a decision algorithm running in polynomial time in the size of the language's syntactic monoid. These results rely on an effective characterization of the regular languages in C-RASP, a recently-established formalism that expresses which languages transformers length-generalize on. This characterization is challenging because classical tools like Krohn-Rhodes decomposition theory for finite semigroups are insufficient for C-RASP. Firstly, the basic building blocks of Krohn-Rhodes theory -- flip-flop and simple groups -- are not expressible in C-RASP. Secondly, the basic building block of C-RASP (unbounded counting) is not expressible by the finite semigroups of Krohn-Rhodes theory. Thus, length generalization on regular languages is controlled by an algebraic property that is invisible to classical finite decomposition theory. We generalize classical decomposition theory from finite semigroups to the infinite additive group on the integers, allowing us to characterize C-RASP in terms of iterated wreath products of the integers and derive a provable polynomial-time decision algorithm for regular language membership. Experiments across a broad test suite of regular languages confirm that our theory captures transformers' length-generalization behavior more accurately than existing classifications.

0.43

Languages and Recognition in a Category with Factorisation

cs.FL cs.LO ·2026-09-03 ·Harsh Beohar, Mike Cruchten, Georg Struth
similarity 0.62
Abstract · 23 pages, 3 figures

Language recognition by homomorphisms is a central construction of algebraic language theory. Initially studied for monoids and semigroups, it has subsequently been expanded to other algebraic structures. Our new categorical account is based on fibrations, which have already seen other applications in automata theory. Languages and surjective homomorphisms give indeed rise to two fibrations, and the notion of language recognition is stable under reindexing. We develop this framework in a category with a factorisation system and address two main technical questions in the fibrational setting. First, we provide sufficient conditions under which languages have syntactic quotients (which is a generalisation of syntactic congruences) and we show how such quotients can be described in some concrete cases using a result by Slomiński. Second, we introduce sufficient conditions under which (regular) languages are closed under certain J-limits and J-colimits.

0.24

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown automaton, we first consider, for each string in its language, the minimum number of turns made in accepting computations (weak measure). We prove that it is decidable whether a pushdown automaton accepts a bounded language in a constant number of turns and whether it accepts a bounded language in k turns, for any given k>=0. This is in contrast to the general case, in which these problems are known to be undecidable, with the exception of acceptance in 0 turns, which is decidable. Furthermore, we prove that when the number of turns sufficient to accept a bounded language is not limited by any constants, it linearly grows with respect to the input length. Also this is in contrast with the general case where, for each nonnegative k, there exists a language for which the number of turns necessary and sufficient is of the order of log^(k), the k times composition of the logarithm with itself. We also prove that, when the costs of all accepting computations are taken into account (accept measure), a linear lower bound for the number of turns, if not limited by any constants, holds even removing the restriction to bounded languages.

0.43

Independent Languages and Witnesses of Dependence (Non-satisfaction)

cs.FL ·2026-08-25 ·Stavros Konstantinidis
published similarity 0.60
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

Pumping Constants for Infinite Alphabets

cs.FL ·2026-10-05 ·Yoav Danieli
publishedtheoryhot direction similarity 0.60
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

Solution to Bucher's density problem for context-free languages

cs.FL ·2026-09-08 ·Rastko Maslic, Jeffrey Shallit
similarity 0.58
Abstract

In 1980 Bucher asked whether, given context-free languages $L\subseteq U$ with $U\setminus L$ infinite, there must be a context-free language $K$ between them for which both $K\setminus L$ and $U\setminus K$ are infinite. We give a negative answer. We first construct an infinite language $D$ with context-free complement such that, for every regular language $R$, either $D\cap R$ or $D\setminus R$ is finite. The words of $D$ encode computations of factorials; repetition of letters ensures that each finite automaton either accepts all but finitely many words of $D$ or rejects all but finitely many words of $D$, while a one-counter automaton recognizes errors in the encodings. We then construct $L$ and $U$ from the complement of $D$. A grammar argument shows that any context-free intermediate language $K$ would divide $D$ in the same way as some regular language. This proves the required impossibility. Both $L$ and $U$ can be taken over a binary alphabet.

0.30