Reasoning on Data Words over Numeric Domains
Abstract
We introduce parametric semilinear data logic (pSDL) for reasoning about data words with numeric data. The logic allows parameters, and Presburger guards on the data and on the Parikh image of equivalence classes (i.e. data counting), allowing us to capture data languages like: (1) each data value occurs at most once in the word and is an even number, (2) the subset of the positions containing data values divisible by 4 has the same number of a’s and b’s, (3) the data value with the highest frequency in the word is divisible by 3, and (4) each data value occurs at most once, and the set of data values forms an interval. We provide decidability and complexity results for the problem of membership and satisfiability checking over these models. In contrast to two-variable logic of data words and data automata (which also permit a form of data counting but no arithmetics over numeric domains and have incomparable inexpressivity), pSDL has elementary complexity of satisfiability checking. We show interesting potential applications of our models in databases and verification.
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.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective cites Decision Procedures for Sequence Theories
- Reachability in Vector Addition Systems is Ackermann-complete cites The Reachability Problem for Petri Nets is Not Primitive Recursive
- The Reachability Problem for Petri Nets is Not Primitive Recursive cites Reachability in Vector Addition Systems is Ackermann-complete
Cited by top-tier papers3
- Decision Procedures for Sequence TheoriesArtur Jez, Anthony W. Lin, Oliver Markgraf, Philipp RümmerCAV 2023 · 8 citations
- The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspectivePascal Bergsträßer, Chris Köcher, Anthony Widjaja Lin, Georg ZetzscheNeurIPS 2024 · 7 citations
- Star Complexity of Parikh Images of Languages over Infinite AlphabetsYoav DanieliLICS 2026
Builds on2
Related papers
- Parikh's Theorem Made SymbolicMatthew Hague, Artur Jez, Anthony W. LinPOPL 2024 · 3 citations
- Complexity and Expressive Power of Disjunction and Negation in Limit DatalogMark Kaminski, Bernardo Cuenca Grau, Egor V. Kostylev, Ian HorrocksAAAI 2020 · 5 citations
- Slice closures of indexed languages and word equations with counting constraintsLaura Ciobanu, Georg ZetzscheLICS 2024 · 2 citations
- Logics for Sizes with Union or IntersectionCaleb Kisby, Saúl A. Blanco, Alex Kruckman, Lawrence S. MossAAAI 2020 · 2 citations
- Initial Limit Datalog: a New Extensible Class of Decidable Constrained Horn ClausesToby Cathcart Burn, Luke Ong, Steven J. Ramsay, Dominik WagnerLICS 2021 · 2 citations
