Lune

POPL2024Top-tier venue

Parikh's Theorem Made Symbolic

Matthew Hague, Artur Jez, Anthony W. Lin

Abstract

Parikh’s Theorem is a fundamental result in automata theory with numerous applications in computer science. These include software verification (e.g. infinite-state verification, string constraints, and theory of arrays), verification of cryptographic protocols (e.g. using Horn clauses modulo equational theories) and database querying (e.g. evaluating path-queries in graph databases), among others. Parikh’s Theorem states that the letter-counting abstraction of a language recognized by finite automata or context-free grammars is definable in Linear Integer Arithmetic (a.k.a. Presburger Arithmetic). In fact, there is a linear-time algorithm computing existential Presburger formulas capturing such abstractions, which enables an efficient analysis via SMT-solvers. Unfortunately, real-world applications typically require large alphabets (e.g. Unicode, containing a million of characters) — which are well-known to be not amenable to explicit treatment of the alphabets — or even worse infinite alphabets. Symbolic automata have proven in the last decade to be an effective algorithmic framework for handling large finite or even infinite alphabets. A symbolic automaton employs an effective boolean algebra, which offers a symbolic representation of character sets (i.e. in terms of predicates) and often lends itself to an exponentially more succinct representation of a language. Instead of letter-counting, Parikh’s Theorem for symbolic automata amounts to counting the number of times different predicates are satisfied by an input sequence. Unfortunately, naively applying Parikh’s Theorem from classical automata theory to symbolic automata yields existential Presburger formulas of exponential size. In this paper, we provide a new construction for Parikh’s Theorem for symbolic automata and grammars, which avoids this exponential blowup: our algorithm computes an existential formula in polynomial-time over (quantifier-free) Presburger and the base theory. In fact, our algorithm extends to the model of parametric symbolic grammars, which are one of the most expressive models of languages over infinite alphabets. We have implemented our algorithm and show it can be used to solve string constraints that are difficult to solve by existing solvers.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Decision Procedures for Sequence Theories cites Solving string constraints with Regex-dependent functions through transducers with priorities and variables
  • Regex Decision Procedures in Extended RE# cites Decision Procedures for Sequence Theories
  • Regex Decision Procedures in Extended RE# cites Solving string constraints with Regex-dependent functions through transducers with priorities and variables
  • Regex Decision Procedures in Extended RE# cites Symbolic Boolean derivatives for efficiently solving extended regular expression constraints
  • Regex Decision Procedures in Extended RE# cites Word Equations in Synergy with Regular Constraints
  • Regex Decision Procedures in Extended RE# cites Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics
  • Word Equations in Synergy with Regular Constraints cites Solving string constraints with Regex-dependent functions through transducers with priorities and variables
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Regex Decision Procedures in Extended RE#Ian Erik Varatalu, Margus Veanes, Ekaterina Zhuchko, Juhan P. ErnitsCAV 2025 · 3 citations
  2. Star Complexity of Parikh Images of Languages over Infinite AlphabetsYoav DanieliLICS 2026

Builds on6

  1. Solving string constraints with Regex-dependent functions through transducers with priorities and variablesTaolue Chen, Alejandro Flores-Lamas, Matthew Hague, Zhilei Han et al.POPL 2022 · 39 citations
  2. Symbolic Boolean derivatives for efficiently solving extended regular expression constraintsCaleb Stanford, Margus Veanes, Nikolaj S. BjørnerPLDI 2021 · 38 citations
  3. Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking SemanticsDan Moseley, Mario Nishio, Jose Perez Rodriguez, Olli Saarikivi et al.PLDI 2023 · 21 citations
  4. Word Equations in Synergy with Regular ConstraintsFrantisek Blahoudek, Yu-Fang Chen, David Chocholatý, Vojtech Havlena et al.FM 2023 · 16 citations
  5. Decision Procedures for Sequence TheoriesArtur Jez, Anthony W. Lin, Oliver Markgraf, Philipp RümmerCAV 2023 · 8 citations

Related papers

  1. A Constraint Solving Approach to Parikh Images of Regular LanguagesAmanda Stjerna, Philipp RümmerOOPSLA 2024 · 2 citations
  2. Context-Free-Language Reachability for Almost-Commuting Transition SystemsNikhil Pimpalkhare, Zachary Kincaid, Thomas RepsPOPL 2026
  3. How Big is the Automaton? Certified Lower Bounds on the Size of Presburger DFAsNicolas Amat, Pierre Ganty, Alessio MansuttiASE 2025 · 1 citation
  4. Reasoning on Data Words over Numeric DomainsDiego Figueira, Anthony Widjaja LinLICS 2022 · 3 citations
  5. A Uniform Framework for Handling Position Constraints in String SolvingYu-Fang Chen, Vojtech Havlena, Michal Hecko, Lukás Holík et al.PLDI 2025
Dusk over the sea between two cliffs drawn in fine vertical lines