Decidable Fragments of First-Order Language Under Stable Model Semantics and Circumscription

Heng Zhang, Mingsheng YingAAAI 2010 · DOI

Abstract

This paper maps the boundaries of decidability for two major non-monotonic reasoning frameworks: Stable Model Semantics and Circumscription. The authors reveal a significant divergence: while circumscription's decidability often mirrors classical first-order logic, stable model semantics is more restrictive, turning several classically decidable fragments into undecidable ones. This work provides a comprehensive classification of prefix-vocabulary classes under these semantics.

Introduction

In classical First-Order Logic (FOL), the general problem of formula satisfiability is undecidable. However, logicians have identified specific "fragments"—subsets of the language defined by their quantifier patterns (e.g., $\exists^*\forall^*$) and vocabulary—that are decidable. Modern AI relies heavily on non-monotonic reasoning, where adding information can invalidate previous conclusions. Two primary frameworks in this domain are Stable Model Semantics (the foundation of Answer Set Programming) and Circumscription (a method of minimalizing predicates). This paper addresses the critical question: where does the "cliff" of undecidability lie for these semantics?

Methods and Fragment Classification

The authors analyze standard prefix-vocabulary classes, categories of formulas defined by their quantifier prefix and the arity of predicates and functions used. To establish the boundaries of decidability, the research employs two primary techniques:

  1. Undecidability Proofs: The authors use a reduction from the "Domino Problem" (a known-undecidable tiling problem) to show that specific logic fragments can encode undecidable behavior.
  2. Decidability Proofs: Syntax translations, such as Lin’s transformation, are utilized to convert formulas under stable model semantics into equivalent formulas in classical logic fragments already known to be decidable.
Table of specific prefix-vocabulary classes and their formal notations.

Key Insights: The Divergence of Semantics

The core contribution of the paper is the discovery of how stable model semantics and circumscription diverge from classical logic.

  • Circumscription's Classical Alignment: A major finding is that for nearly all fragments considered, decidability under circumscription coincides with classical FOL. This is counterintuitive because circumscription is a second-order logic construction, which typically entails higher computational complexity.
  • The Cost of Stability: Stable model semantics is significantly "harder" than circumscription. The authors identified fragments, such as the Bernays-Schönfinkel class ($\exists^*\forall^*$), that are decidable under circumscription but undecidable under stable models.
  • Robustness of the Rabin Class: The "Rabin Class," involving unary predicates, equality, and one unary function, remains decidable under both semantics, marking it as a robust tool for automated reasoning.
Comparison of decidability boundaries across Classical FOL, Circumscription, and Stable Model Semantics. Dark grey indicates decidable, white indicates undecidable, and light grey indicates unidentified classes.

Key Results

The paper provides a definitive classification of which fragments are decidable:

  • Maximally Decidable Classes: The authors identified six classes that are "maximally decidable" for circumscription, meaning any expansion leads to undecidability.
  • Stable Model Limits: The existential class without functions is fully decidable, while the inclusion of functions makes it only semi-decidable.
  • New Undecidability Proofs: Several fragments, such as $[\forall^2, (0,0,1), (0,1)]$, were proven undecidable under both semantics, narrowing the search space for efficient solvers.

Limitations and Future Work

The study focuses on standard prefix classes and does not address the Guarded Fragment, which is widely used in description logics and web ontology languages. Additionally, while the paper identifies if a fragment is decidable, it does not focus on the exact computational complexity (e.g., NP-complete vs. EXPTIME). The authors suggest that "stabilization" likely increases complexity even within decidable fragments. Future research will aim to resolve the status of "unidentified" classes in the classification map.

Summary updated

BibTeX
@inproceedings{zhang2010decidable,
  author = {Heng Zhang and Mingsheng Ying},
  title = {{Decidable Fragments of First-Order Language Under Stable Model Semantics and Circumscription}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7590},
}
Figure