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

Mirosław Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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 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 establish several properties of the FLP semantics. We apply a similar approach to define supported models for arbitrary propositional theories.

Original languageEnglish
Title of host publicationLogic Programming - 25th International Conference, ICLP 2009, Proceedings
Number of pages15
StatePublished - 2009
Event25th International Conference on Logic Programming, ICLP 2009 - Pasadena, CA, United States
Duration: Jul 14 2009Jul 17 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5649 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference25th International Conference on Logic Programming, ICLP 2009
Country/TerritoryUnited States
CityPasadena, CA

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.


  • Answer-set programming
  • Logic here-and-there
  • Stable models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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