CS Paper Radar

Separating Parsing Expression Grammars using Cell-Probe Lower Bounds

Jungyeom Kim, Jihyeok Park

cs.PL cs.CCcs.FL ·submitted 2026-08-30 06:27 UTC · v1
theory

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.

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

Subregular Expressions and Their Expressive Power

cs.FL ·2026-08-25 ·Martin Kutrib, Matthias Wendlandt
publishedsurvey similarity 0.59
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

A Denotational Semantics for Synchronized Regular Expressions (extended version)

cs.FL ·2026-08-18 ·Lukas Grätz
published similarity 0.58
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

The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence

cs.FL cs.CLcs.LO ·2026-11-01 ·Sherzod Turaev
similarity 0.58
Abstract · 13 pages, 1 figure, 1 table

A rule written for people fixes its atomic conditions and connectives but leaves open how the connectives are bracketed, and each bracketing is a different logical reading that an autoformalizer must resolve or expose. We study the scope grammar, a deliberately ambiguous context-free grammar whose derivation trees are the readings of a connective skeleton and whose quotient by logical equivalence is what matters downstream. A skeleton with $k$ binary connectives has $C_k$ derivation trees, the $k$-th Catalan number, but far fewer logically distinct readings. For the positive, repetition-free fragment we make the gap exact: through the uniqueness of the read-once normal form we characterize the realizable normal forms by lowest common ancestors and count them with a two-label recurrence over the operator word, verified against exhaustive enumeration up to eleven atoms. The count is invariant under reversal and $\wedge/\vee$ duality; a skeleton is ambiguous if and only if it uses both $\wedge$ and $\vee$, a one-pass test; and the number of classes is at least $2^{\lfloor n/3\rfloor}$. Up to fifteen atoms the alternating pattern is the worst case; its count has a cubic generating function, is the 3-Schröder sequence (OEIS A137842), and grows with base $\varphi^{5/2}\approx3.330$, below the Catalan base 4. We reduce maximality to an inequality on increments, verified to sixteen atoms, and explain why local exchange arguments cannot prove it. We also treat negation, exceptions, and background axioms, where normal-form uniqueness still decides equivalence but counting is open.

0.28

A generalized transition framework for identifying reduction domains in non-binary constituency parsing

cs.CL ·2026-11-09 ·Jungyeul Park, Zihao Huang, Eunkyul Leah Jo
theory similarity 0.58
Abstract

Direct non-binary constituency parsing must identify an ordered sequence of children at each phrase-level reduction. We extend our earlier delimiter-guided bottom-up construction to a common calculus for top-down, in-order, and bottom-up parsing. At reduction, the rightmost delimiter marks the left boundary, the nonterminal marker supplies the mother label, and the completed items in the delimited segment determine the children and arity. We use a stack invariant to prove soundness and completeness and derive the exact length of the static oracle's action sequence. A projection-and-lifting theorem shows that each delimiter-guided system and its canonical counterpart generate the same set of trees under both the structural and grammar-licensed transition relations. In controlled experiments on PTB and CTB, the delimiter-guided parsers achieve similar labeled accuracy to their canonical counterparts across all traversal orders. For bottom-up parsing, delimiter guidance reduces the number of action classes and increases the number of supervised decisions per tree.

0.18

Semantic Prefix Oracles for LLM Decoding: Contracts and Differential Validation

cs.PL cs.AIcs.CL ·2026-09-28 ·Paul Kronlund-Drouault
similarity 0.58
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

Construction of a DFA for Computing Grundy Numbers in the Successful Derivation Games on Right-Linear Grammars

cs.FL cs.GT ·2026-09-01 ·Yoshiaki Takata, Yusuke Inoue, Hiroyuki Seki
theory similarity 0.56
Abstract

Inoue et al. have introduced the successful derivation game (SDG) on context-free grammars (CFGs), which is a generalization of classic heap-based games including subtraction games and Keyles, and shown that the least upper bound of the Grundy numbers in the SDG on a given CFG G is undecidable in general even when we restrict G to be a linear CFG. This paper shows that for the SDG on a right-linear grammar (RLG), we can construct a DFA for computing the Grundy number of a given position. In other words, for the SDG on an RLG, the set of positions with a given Grundy number c is regular. As a corollary, the least upper bound of the Grundy numbers in the SDG on a given RLG is decidable. We also investigate the complexity of computing the least upper bound of the Grundy numbers in the SDG on a given RLG, and it is shown to be PSPACE-complete.

0.18

Breaking the Space Barrier and its Application to Language Model Inference

cs.AI cs.CC ·2026-10-06 ·Arip Asadulaev
theory similarity 0.56
Abstract

Language models are more and more often asked for structured output: JSON that follows a schema, or a tool call with typed arguments. A small machine, an automaton, enforces the format by forbidding the tokens that would break it. We observe that this machine has a rare property: from any of its states, each token leads along exactly one path. Graphs in which only a few paths join any two points are a classical object of complexity theory, and our theoretical result settles an open question about them: one can decide whether such a graph connects two points while verifying that it really has few paths, with very little memory. Precisely, the problem lies in the classes ReachUL, LOGDCFL, C=L and SC2, and needs only O(log2 n/ log log n) space, below the classical O(log2 n) of Savitch's theorem. The constructions behind the proofs become an inference engine: text the format forces is written without running the model, the mask is recomputed on the GPU without any table, recursive formats use a small stack, every output stays valid under a token limit, and independent fields are decoded in parallel and verified. On one 16 GB Apple M2 Pro with Qwen3.5-2B and 4B, against MLX with llguidance, the standard setup for this hardware, schema-constrained extraction finishes 1.2- 1.3x sooner with the same answers, a grammar costs 3 MB instead of up to 1.5 GB, one server holds sixteen grammars where tables run out of memory, and sixteen tool-calling agents finish 2.5x sooner.

0.31