Decidability of Querying First-Order Theories via Countermodels of Finite Width

Thomas FellerThomas Feller, Tim LyonTim Lyon, Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja, Sebastian RudolphSebastian Rudolph

Thomas Feller, Tim Lyon, Piotr Ostropolski-Nalewaja, Sebastian Rudolph
Decidability of Querying First-Order Theories via Countermodels of Finite Width
Logical Methods in Computer Science, 21(2):7:1-7:35, April 2025

Details
Bibtex

KurzfassungAbstract
We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying), based on the existence of countermodels that are structurally simple, gauged by certain types of width measures (with treewidth and cliquewidth as popular examples). As an important special case of our framework, we identify logics exhibiting width-finite finitely universal model sets, warranting decidable entailment for a wide range of homomorphism-closed queries, subsuming a diverse set of practically relevant query languages. As a particularly powerful width measure, we propose to employ Blumensath's partitionwidth, which subsumes various other commonly considered width measures and exhibits highly favorable computational and structural properties. Focusing on the formalism of existential rules as a popular showcase, we explain how finite partitionwidth sets of rules subsume other known abstract decidable classes but - leveraging existing notions of stratification - also cover a wide range of new rulesets. We expose natural limitations for fitting the class of finite unification sets into our picture and suggest several options for remedy.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@article{FLOR2025,
  author  = {Thomas Feller and Tim Lyon and Piotr Ostropolski-Nalewaja and
             Sebastian Rudolph},
  title   = {Decidability of Querying First-Order Theories via Countermodels of
             Finite Width},
  journal = {Logical Methods in Computer Science},
  volume  = {21},
  number  = {2},
  year    = {2025},
  month   = {April},
  pages   = {7:1-7:35},
  doi     = {10.46298/lmcs-21(2:7)2025}
}