CS Paper Radar

A Denotational Semantics for Synchronized Regular Expressions (extended version)

Lukas Grätz

cs.FL ·submitted 2026-08-18 16:53 UTC · v1
published

Abstract

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.

Comment
Extended submitted manuscript to be presented and published at ICTAC 2026, November 9-15, Bariloche, see https://ictac2026.github.io/

Closest papers

Nearest neighbours by meaning across the whole index.

Subregular Expressions and Their Expressive Power

cs.FL ·2026-08-25 ·Martin Kutrib, Matthias Wendlandt
publishedsurvey similarity 0.66
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

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.

0.39

Semantic Prefix Oracles for LLM Decoding: Contracts and Differential Validation

cs.PL cs.AIcs.CL ·2026-09-28 ·Paul Kronlund-Drouault
similarity 0.62
Abstract

Constrained decoding can enforce regular or context-free output formats, but many program-generation failures are semantic: scope, typing, and declaration effects depend on context. We present semantic grammar specifications, a declarative formalism that attaches such constraints to a context-free surface and executes them during Earley descent. Our implementation enforces \emph{safe pruning}: it rejects only prefixes whose semantic contradictions cannot be repaired by any continuation. A separate, grammar-dependent, \emph{dead-end freedom} property guarantees the existence of a realizable witness for each remaining branch. We give simple sufficient conditions based on surface productivity, type coverage, and left-to-right constraint flow. Our finite-lambda, core ML, and C-like fragments satisfy them, while the STLC instance used in our experiments does not: plain STLC can violate type coverage, and we show how restricting its type universe recovers it. A tokenizer-lifting lemma carries character-level witnesses to token sequences under an explicit vocabulary-coverage hypothesis. We validate the implementation differentially against production compilers (\texttt{ocamlc}, \texttt{cc}). Across every prefix of 65 compiler-valid programs we observe zero false prunes. The semantic oracle localizes 25/30 invalid programs mid-stream, against 0/30 for a syntax-only oracle, and agrees on 42/42 recursion probes. A twelve-model generation study, including a matched semantic-versus-syntactic ablation for nine models, finds nonnegative observed semantic-minus-syntactic point estimates for every model-language pair, with maxima of $+15.2$ points on STLC task correctness and $+14.3$ points on ML validity.

0.32

Completeness and incompleteness of basic matching logic

cs.LO ·2026-08-13 ·Xiaohong Chen, Grigore Rosu
theory similarity 0.62
Abstract

Basic matching logic is matching logic without definedness. Symbols are interpreted as set-valued operations, element variables denote singletons and are bound by $\exists$, and no connective uniformly internalizes totality. For basic matching logic without fixpoints over an arbitrary one-sorted finitary signature, we prove \emph{global completeness} ($Γ\vDash\varphi$ iff $Γ\vdash\varphi$, for arbitrary, possibly infinite $Γ$) and, as a corollary, conservativity of the definedness extension. The proof localizes $Γ$ to a theory $Δ_Γ$ and reduces semantic consequence and derivability to the same local relation: $Γ\vDash\varphi$ iff $Δ_Γ\vDash_\text{loc}\varphi$ iff $Γ\vdash\varphi$. A double-cover construction establishes the semantic equivalence. Least fixpoints destroy effective axiomatizability. Over a signature with one unary and two binary symbols and no constants, validity is not recursively enumerable; hence no sound calculus with a recursively enumerable proof relation is even weakly complete, already for the empty theory and without definedness. The positive result is also sharp in the number of sorts. Global completeness fails with three sorts for a satisfiable $Γ$. Thus the completeness conjecture holds for one sort and fails in general. The negative results arise from sort flow, fixpoint effectivity, and, for hybrid logic, an obstruction to every well-founded calculus whose leaves are hypotheses or valid patterns and whose rules respect localization. This yields a matching-logic-independent dichotomy: the language with state variables bound by $\exists$ and $\forall$ over modalities of arbitrary arity is globally complete without nominals, while no calculus in that well-founded class is globally complete once nominals are added.

0.04

Undecidability of Adjacent Equality for Insertion, Shuffle, and Crossover Language Operations

cs.FL ·2026-08-27 ·Charles E. Hughes
similarity 0.60
Abstract

We study a family of language operations based on insertion, shuffle, and crossover and investigate the undecidability of adjacent equality together with finite convergence and associated spectrum questions. Insertion and shuffle operations on formal languages arise in formal language theory, models of concurrency, and biologically inspired computation. This paper studies a different question from the usual closure problem, specifically whether an increasing sequence of languages generated by repeated insertion, or by increasing the permitted degree of bounded shuffle, reaches an instance of adjacent equality after finitely many stages. We show that several such adjacent equality questions are undecidable. In particular, reaching such an adjacent equality event is undecidable for each of the following: iterated insertion of a regular language into a context-free language; bounded shuffle of a regular language with a context-free language as the bound increases; and the corresponding self-insertion and self-bounded-shuffle hierarchies for context-free languages. The new reductions proceed directly from the undecidability of context-free-language universality, using separator-delimited block constructions and, for self-operations, an absorbing regular language of guard violations. Earlier trace-based proofs relied on mortality and uniform halting. More generally, we investigate finite-stage equality and stabilization (persistent equality) in hierarchies generated by insertion and bounded shuffle. In addition to giving substantially simpler proofs of earlier undecidability results, we obtain general criteria for one-step equality, develop new reductions for self-insertion, and identify several open problems, including structural questions concerning insertion depth and degree whose resolution determines whether adjacent equality necessarily implies permanent stabilization.

0.51

Model Checking HyperRecHML is Decidable

cs.LO cs.FL ·2026-10-15 ·Elli Anastasiadi, Kim Guldstrand Larsen, Martin Zimmermann
similarity 0.59
Abstract

Temporal hyperlogics combine explicit quantification over traces with temporal requirements evaluated over the quantified traces. HyperRecHML is a temporal hyperlogic which allows for arbitrary mixing of trace quantification and the use of fixed points for expressing temporal requirements, which makes it very expressive in comparison to other first-order hyperlogics. HyperRecHML has already been successfully applied in runtime verification, but the decidability of its model checking problem remains open. We answer this question positively by providing two main contributions. Firstly, a normalization procedure that allows to reduce arbitrary HyperRecHML formulas to a normal form with restricted nesting of trace quantification and fixed points. Secondly, we provide an automata-based model checking algorithm for formulas of this normal form. The complexity of our algorithm is comparable to similar ones for other hyperlogics, despite the extra expressive power.

0.16

Separating Parsing Expression Grammars using Cell-Probe Lower Bounds

cs.PL cs.CCcs.FL ·2026-08-30 ·Jungyeom Kim, Jihyeok Park
theory similarity 0.58
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

Mechanising Denotational Semantics in Agda

cs.PL ·2026-10-10 ·Peter D. Mosses, Jesper Cockx, Bernhard Reus
published similarity 0.58
Abstract · 23 pages, excl. references. To be published in Proceedings of MFPS 2026

Mechanisation of a mathematical definition (also referred to as formalisation) has many benefits. Here, we focus on mechanising denotational semantic definitions of programming languages by embedding them in the Agda language. The Agda type-checker detects and reports any issues with the wellformedness and type correctness of the embedded definitions. To minimise the effort required, and to facilitate correlation of the original definition with its Agda embedding, mechanisation should not involve significant reformulation or extension. Here, we show how to embed conventional Scott-Strachey denotational definitions in Agda with almost no changes to $λ$-notation or domain equations. Agda notation for definitions of types and functions corresponds closely to the conventional meta-notation of denotational semantics. We have developed a collection of Agda modules with postulated types for commonly used domain constructors and their associated operations. We illustrate our approach with mechanisations of three denotational definitions: a model of the untyped $λ$-calculus, Plotkin's denotational semantics of PCF, and a semantics of a sublanguage of Scheme. In previous work, similar mechanisations in Agda have revealed several unsuspected wellformedness issues in published denotational definitions. Some of the postulated properties of our definitions are inconsistent with a classical set-theoretic interpretation of Agda. We conjecture that they would be consistent with an interpretation of Agda in a higher-order intuititionistic logic, such as that used by Simpson in his work on synthetic domain theory. After recalling previous work on mechanising domain theory, we consider the possibility of mechanising synthetic domain theory in Agda.

0.30

Normalization by Evaluation with Substitutions as Operations

cs.PL math.LO ·2026-10-15 ·Jason Z. S. Hu
similarity 0.58
Abstract

In previous works on normalization by evaluation (NbE) with an untyped domain model, explicit substitutions are a major decision choice, which, in retrospect, is taken to simplify subsequent semantic proofs. This choice hence is taken for a purely technical reason. In addition, there is no obvious lemma to test the completeness of the definition or the laws for explicit substitutions. In this technical report, we investigate NbE in a typical setting, i.e. defining substitutions as operations. We show that this setting brings simplifications in proving syntactic properties and soundness of NbE, though complications are introduced in the completeness proof of NbE.

0.15