CS Paper Radar

Subregular Expressions and Their Expressive Power

Martin Kutrib, Matthias Wendlandt

cs.FL ·submitted 2026-08-25 08:46 UTC · v1
publishedsurvey

Abstract

We provide a survey of several families of subregular expressions obtained by modifying the classical operator set consisting of union, concatenation, and Kleene star. More specifically, we consider expression systems based on sets of two or three operations chosen from union, intersection, complementation, concatenation, and Kleene star. The resulting language families range from finite languages to the full class of regular languages. We collect and organize known results on the expressive power and structural properties of these families. We compare the resulting language classes over unary and arbitrary alphabets and summarize known inclusion, equality, and incomparability results. The aim of this survey is to provide a unified view of the language families induced by restricted operator sets and to highlight open relations and possible directions for further research.

Comment
In Proceedings AFL 2026, arXiv:2608.23071
Journal ref
EPTCS 451, 2026, pp. 17-32
DOI
10.4204/EPTCS.451.2

Closest papers

Nearest neighbours by meaning across the whole index.

A Denotational Semantics for Synchronized Regular Expressions (extended version)

cs.FL ·2026-08-18 ·Lukas Grätz
published similarity 0.66
Abstract · Extended submitted manuscript to be presented and published at ICTAC 2026, November 9-15, Bariloche, see https://ictac2026.github.io/

Pure and full synchronized regular expressions (pure sregex and full sregex ) extend regular expressions by adding labels to the operators (Kleene star and alternation). Operators within the same scope are synchronized if they have the same label. We show that a regular expression with backreferences (known from practical regex engines) can be translated into a full sregex. Previous work did not consider synchronized alternations or nested star synchronization. Within the same scope, stars with the same label match the same number of iterations, alternations with the same label match the same choice. The scope may depend on the current iteration of an outer star. Pure sregexes restrict synchronization to the local scope, while full sregexes also allow synchronization across iterations. In contrast to operational semantics in previous work on backreferences, we present a denotational semantics, where concretizations act similarly to valuations in logic. As with backreferences, we show that matching a word is NP-complete. Pure and full synchronized languages are considered and we show that they are closed under concatenation, union and star. By a pumping lemma, they are not closed under intersection. Relationships to other language models are discussed.

0.29

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

Separating Parsing Expression Grammars using Cell-Probe Lower Bounds

cs.PL cs.CCcs.FL ·2026-08-30 ·Jungyeom Kim, Jihyeok Park
theory similarity 0.59
Abstract

We resolve three open problems concerning parsing expression grammars (PEGs). We construct a single language $C$ satisfying $C\in\mathsf{LIN}\cap\mathsf{PEG}$ and $C^R\in\mathsf{LIN}\setminus\mathsf{PEG}$. This proves that some linear context-free language is not a PEG language and that PEG languages are not closed under reversal, confirming a conjecture of Loff, Moreira, and Reis. Factoring the same witness resolves the concatenation-closure problem of Rubtsov and Chudinov negatively, in the strong form $\mathsf{PEG}\cdot\mathsf{REG}\not\subseteq\mathsf{PEG}$ despite $\mathsf{REG}\cdot\mathsf{PEG}\subseteq\mathsf{PEG}$. It also refutes closure under Kleene star, homomorphisms, and substitutions. Our main technique converts scaffolding automata (SCAs), which characterize reversals of PEG languages, into dynamic data structures in the cell-probe model. For any suitably local serialization of a problem with preprocessing, updates, and a final Boolean query, an SCA recognizer yields an exact deterministic cell-probe data structure whose operation costs are proportional to the corresponding encoding lengths. Cell-probe lower bounds can therefore prove SCA non-membership and, by reversal, PEG non-membership. We apply this transfer to Multiphase Inner Product using one-symbol update blocks and a query suffix of length $O(\log n)$, while keeping both the language and its reversal linear context-free. Ko's cell-probe lower bound then yields the witness above. The arguments are additionally formalized in Lean 4.

0.24

A new method for proving confluence on abstract reduction systems --- Confluence of non-E-overlapping weakly-shallow TRSs ---

cs.LO ·2026-10-07 ·Masahiko Sakai, Mizuhito Ogawa, Michio Oyamaguchi
similarity 0.58
Abstract · 68 pages, 17 figures

This paper proposes a new method for proving the confluence of an abstract reduction system (ARS) by clarifying the sufficient conditions, called compatibility and edge commutativity, for expanding a given finite sub-ARS into a confluent one by adding rewrite edges. This method can be regarded as an extension of our earlier work, which showed that a weakly non-overlapping, shallow, and non-collapsing term rewriting system (TRS) is confluent. Furthermore, we apply our method to demonstrate that a non-$E$-overlapping and weakly shallow TRS is confluent. Here, a term is weakly shallow if each defined function symbol occurs either at the root or in the ground subterms, and a TRS is weakly shallow if both sides of all its rewrite rules are weakly shallow. This drops the non-collapsing condition assumed in our previous work on weakly shallow TRSs. Moreover, since a weakly shallow TRS is non-$E$-overlapping whenever it is non-$ω$-overlapping, and the latter property is decidable, we also obtain a decidable sufficient condition for confluence: non-$ω$-overlapping and weakly shallow TRSs are confluent.

0.34

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.57
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

Languages and Recognition in a Category with Factorisation

cs.FL cs.LO ·2026-09-03 ·Harsh Beohar, Mike Cruchten, Georg Struth
similarity 0.57
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

Typechecking without Minimum Types: Finite Bases and Backward Checking for $F_{<:}^{\top}$

cs.PL ·2026-10-14 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.55
Abstract · 44 pages, 8 figures, 2 tables. Includes appendices

System $F_{<:}^{\top}$ has decidable subtyping but lacks minimum types. We prove that typechecking is decidable for arbitrary explicitly annotated terms with unrestricted subsumption. The difficulty is that type abstraction uses a variable's declared bound to type its body, while quantified subtyping forgets that bound. We construct finite covers that preserve all required subtype comparisons across this change of context. These covers yield a compositional finite typing basis and a decision procedure. We then derive a backward checker that propagates acceptable targets without constructing the complete typing basis. Rectangularity of typing families gives a uniform elimination domain while retaining every result type, even when the canonical type is not least. Finite inverse families transport targets through type substitution. The same inverse specification recovers bound forgetting and yields finite type-avoidance families. Both typechecking procedures are total Rocq functions proved equivalent to the original typing judgment. For a separate symbolic word-RAM realization, we prove a quartic worst-case work bound. We measure family representation sizes and comparison storage in independent OCaml prototypes on synthetic checking judgments.

0.25

Freely Generated Categorical Structures and Automatic Differentiation, PhD Thesis (Introduction and Conclusion)

cs.PL cs.LOmath.CT ·2026-09-30 ·Fernando Lucatelli Nunes
similarity 0.55
Abstract · PhD thesis, Utrecht University, 2026. Introduction, conclusion, and English and Dutch summaries only; the six research papers constituting C…

This version contains the introduction and conclusion of my PhD thesis, "Freely Generated Categorical Structures and Automatic Differentiation", together with its English and Dutch summaries. The full thesis consists of an introductory chapter, six joint research papers, and a concluding chapter, developed during my PhD studies at Utrecht University under the supervision of Gabriele Keller and Matthijs Vákár. The research papers are available separately and are not reproduced here. The introduction presents the scope of the thesis, explains the contributions of the six papers and their connections, and introduces the categorical foundations of our approach. The guiding idea is that programming languages, viewed as freely generated categorical structures, provide a principled setting for constructing structure-preserving program transformations and proving their correctness. Automatic differentiation supplies the central application: we study forward- and reverse-mode differentiation for expressive typed languages, including higher-order functions, recursive types, iteration and partiality. The semantic requirements of these transformations also motivate independent mathematical results on free distributive and extensive categories, cartesian closedness, and Grothendieck constructions. The conclusion brings these contributions together, discusses their limitations, and outlines further directions. Throughout, the thesis develops a dialogue between theory and practice: categorical semantics guides the construction of reliable and practically useful program transformations, while the demands of computation lead to new categorical structures and results.

0.22