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

Producción científica: Conference contribution › revisión exhaustiva

Resumen

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.

Idioma original	English
Título de la publicación alojada	Logic Programming - 25th International Conference, ICLP 2009, Proceedings
Páginas	175-189
Número de páginas	15
DOI	https://doi.org/10.1007/978-3-642-02846-5_18
Estado	Published - 2009
Evento	25th International Conference on Logic Programming, ICLP 2009 - Pasadena, CA, United States Duración: jul 14 2009 → jul 17 2009

Serie de la publicación

Nombre	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen	5649 LNCS
ISSN (versión impresa)	0302-9743
ISSN (versión digital)	1611-3349

Conference

Conference	25th International Conference on Logic Programming, ICLP 2009
País/Territorio	United States
Ciudad	Pasadena, CA
Período	7/14/09 → 7/17/09

Nota bibliográfica

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.

Financiación

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.

Financiadores	Número del financiador
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	IIS-0913459

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Acceder al documento

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

Otros archivos y enlaces

Citar esto

Truszczyński, M. (2009). Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. En 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. En 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).

Producción científica: Conference contribution › revisión exhaustiva

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 - https://www.scopus.com/pages/publications/69949116454

UR - https://www.scopus.com/pages/publications/69949116454#tab=citedBy

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

Resumen

Serie de la publicación

Conference

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto