Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs

Miroslaw Truszczyński

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


Over the years, the stable-model semantics has gained a position of the correct (two-valued) interpretation of default negation in programs. However, for programs with aggregates (constraints), the stable-model semantics, in its broadly accepted generalization stemming from the work by Pearce, Ferraris and Lifschitz, has a competitor: the semantics proposed by Faber, Leone and Pfeifer, which seems to be essentially different. Our goal is to explain the relationship between the two semantics. Pearce, Ferraris and Lifschitz's extension of the stable-model semantics is best viewed in the setting of arbitrary propositional theories. We propose here an extension of the Faber-Leone-Pfeifer semantics, or FLP semantics, for short, to the full propositional language, which reveals both common threads and differences between the FLP and stable-model semantics. We use our characterizations of FLP-stable models to derive corresponding results on strong equivalence and on normal forms of theories under the FLP semantics. We apply a similar approach to define supported models for arbitrary propositional theories, and to study their properties.

Original languageEnglish
Pages (from-to)1285-1306
Number of pages22
JournalArtificial Intelligence
Issue number16-17
StatePublished - 2010

Bibliographical note

Funding Information:
The present text reflects many corrections and suggestions offered by the anonymous reviewers. The author gratefully acknowledges their effort. The work was partially supported by the NSF grant IIS-0913459.


  • Logic HT
  • Logic programming
  • Reducts
  • Stable models
  • Supported models

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs'. Together they form a unique fingerprint.

Cite this