Lune

POPL2025Top-tier venue

The Decision Problem for Regular First Order Theories

Umang Mathur, David Mestel, Mahesh Viswanathan

Abstract

The Entscheidungsproblem , or the classical decision problem, asks whether a given formula of first-order logic is satisfiable. In this work, we consider an extension of this problem to regular first-order theories , i.e., (infinite) regular sets of formulae. Building on the elegant classification of syntactic classes as decidable or undecidable for the classical decision problem, we show that some classes (specifically, the EPR and Gurevich classes), which are decidable in the classical setting, become undecidable for regular theories. On the other hand, for each of these classes, we identify a subclass that remains decidable in our setting, leaving a complete classification as a challenge for future work. Finally, we observe that our problem generalises prior work on automata-theoretic verification of uninterpreted programs and propose a semantic class of existential formulae for which the problem is decidable.

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.

1 top-tier paper has 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

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. EUFⁿ: A Decidable Extension to the Theory of Equality with Uninterpreted FunctionsYide Du, Zhenbang Chen, Weijiang Hong, Wei DongOOPSLA 2026

Builds on11

  1. Testing Database Engines via Pivoted Query SynthesisManuel Rigger, Zhendong SuOSDI 2020 · 150 citations
  2. Validating SMT solvers via semantic fusionDominik Winterer, Chengyu Zhang, Zhendong SuPLDI 2020 · 80 citations
  3. First-order quantified separatorsJason R. Koenig, Oded Padon, Neil Immerman, Alex AikenPLDI 2020 · 31 citations
  4. Exact and approximate methods for proving unrealizability of syntax-guided synthesis problemsQinheping Hu, John Cyphert, Loris D'Antoni, Thomas W. RepsPLDI 2020 · 22 citations
  5. Reductions for safety proofsAzadeh Farzan, Anthony VandikasPOPL 2020 · 21 citations

Related papers

  1. Decidable Synthesis of Programs with Uninterpreted FunctionsPaul Krogmeier, Umang Mathur, Adithya Murali, P. Madhusudan et al.CAV 2020 · 8 citations
  2. Witnessability of Undecidable ProblemsShuo Ding, Qirun ZhangPOPL 2023
  3. Transformer Encoder Satisfiability: Complexity and Impact on Formal ReasoningMarco Sälzer, Eric Alsmann, Martin LangeICLR 2025
  4. Revisiting Membership Problems in Subclasses of Rational RelationsPascal Bergsträßer, Moses GanardiLICS 2023 · 2 citations
  5. Automata for MSO over Infinite Trees with Quantification over Borel Sets of BranchesMikolaj Bojanczyk, Antonio Casares, Sven Manthe, Pawel ParysLICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines