Lune

LICS2022Top-tier venue

Reasoning on Data Words over Numeric Domains

Diego Figueira, Anthony Widjaja Lin

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.

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

  • 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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Decision Procedures for Sequence TheoriesArtur Jez, Anthony W. Lin, Oliver Markgraf, Philipp RümmerCAV 2023 · 8 citations
  2. 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
  3. Star Complexity of Parikh Images of Languages over Infinite AlphabetsYoav DanieliLICS 2026

Builds on2

  1. Reachability in Vector Addition Systems is Ackermann-completeWojciech Czerwinski, Lukasz OrlikowskiFOCS 2021 · 69 citations
  2. The Reachability Problem for Petri Nets is Not Primitive RecursiveJérôme LerouxFOCS 2021 · 62 citations

Related papers

  1. Parikh's Theorem Made SymbolicMatthew Hague, Artur Jez, Anthony W. LinPOPL 2024 · 3 citations
  2. Complexity and Expressive Power of Disjunction and Negation in Limit DatalogMark Kaminski, Bernardo Cuenca Grau, Egor V. Kostylev, Ian HorrocksAAAI 2020 · 5 citations
  3. Slice closures of indexed languages and word equations with counting constraintsLaura Ciobanu, Georg ZetzscheLICS 2024 · 2 citations
  4. Logics for Sizes with Union or IntersectionCaleb Kisby, Saúl A. Blanco, Alex Kruckman, Lawrence S. MossAAAI 2020 · 2 citations
  5. Initial Limit Datalog: a New Extensible Class of Decidable Constrained Horn ClausesToby Cathcart Burn, Luke Ong, Steven J. Ramsay, Dominik WagnerLICS 2021 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines