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

Mirosław Truszczyński

doi:10.1007/978-3-642-02846-5_18

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

Mirosław Truszczyński

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 language	English
Title of host publication	Logic Programming - 25th International Conference, ICLP 2009, Proceedings
Pages	175-189
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-02846-5_18
State	Published - 2009
Event	25th International Conference on Logic Programming, ICLP 2009 - Pasadena, CA, United States Duration: Jul 14 2009 → Jul 17 2009

Publication series

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

Conference

Conference	25th International Conference on Logic Programming, ICLP 2009
Country/Territory	United States
City	Pasadena, CA
Period	7/14/09 → 7/17/09

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.

Funding

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.

Funders	Funder number
National Science Foundation Arctic Social Science Program	IIS-0913459

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-02846-5_18

Cite this

Truszczyński, M. (2009). Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. In Logic Programming - 25th International Conference, ICLP 2009, Proceedings (pp. 175-189). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5649 LNCS). https://doi.org/10.1007/978-3-642-02846-5_18

@inproceedings{bc171b120ff744008b055258f28cdbbc,

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

abstract = "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.",

keywords = "Answer-set programming, Logic here-and-there, Stable models",

author = "Miros{\l}aw Truszczy{\'n}ski",

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.; 25th International Conference on Logic Programming, ICLP 2009 ; Conference date: 14-07-2009 Through 17-07-2009",

year = "2009",

doi = "10.1007/978-3-642-02846-5_18",

language = "English",

isbn = "3642028454",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "175--189",

booktitle = "Logic Programming - 25th International Conference, ICLP 2009, Proceedings",

}

Truszczyński, M 2009, Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. in Logic Programming - 25th International Conference, ICLP 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5649 LNCS, pp. 175-189, 25th International Conference on Logic Programming, ICLP 2009, Pasadena, CA, United States, 7/14/09. https://doi.org/10.1007/978-3-642-02846-5_18

Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. / Truszczyński, Mirosław.
Logic Programming - 25th International Conference, ICLP 2009, Proceedings. 2009. p. 175-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5649 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Truszczyński, Mirosław

N1 - 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.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Answer-set programming

KW - Logic here-and-there

KW - Stable models

UR - http://www.scopus.com/inward/record.url?scp=69949116454&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=69949116454&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02846-5_18

DO - 10.1007/978-3-642-02846-5_18

M3 - Conference contribution

AN - SCOPUS:69949116454

SN - 3642028454

SN - 9783642028458

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 175

EP - 189

BT - Logic Programming - 25th International Conference, ICLP 2009, Proceedings

T2 - 25th International Conference on Logic Programming, ICLP 2009

Y2 - 14 July 2009 through 17 July 2009

ER -

Truszczyński M. Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. In Logic Programming - 25th International Conference, ICLP 2009, Proceedings. 2009. p. 175-189. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-02846-5_18

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

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this