Head-elementary-set-free logic programs

Martin Gebser; Joohyung Lee; Yuliya Lierler

doi:10.1007/978-3-540-72200-7_14

Head-elementary-set-free logic programs

Martin Gebser, Joohyung Lee, Yuliya Lierler

Computer Science and Engineering

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

9 Scopus citations

Abstract

The recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its elementary sets. Based on the notion of an elementary set, we propose the notion of head-elementary-set-free (HEF) programs, a more general class of disjunctive programs than head-cycle-free (HCF) programs proposed by Ben-Eliyahu and Dechter, that can still be turned into nondisjunctive programs in polynomial time and space by "shifting" the head atoms into the body. We show several properties of HEF programs that generalize earlier results on HCF programs. Given an HEF program, we provide an algorithm for finding an elementary set whose loop formula is not satisfied, which has a potential for improving stable model computation by answer set solvers.

Original language	English (US)
Title of host publication	Logic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings
Publisher	Springer Verlag
Pages	149-161
Number of pages	13
ISBN (Print)	9783540721994
DOIs	https://doi.org/10.1007/978-3-540-72200-7_14
State	Published - 2007
Event	9th International Conference on Logic Programming and Nonmonotomic Reasoning, LPNMR 2007 - Tempe, AZ, United States Duration: May 15 2007 → May 17 2007

Publication series

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

Other

Other	9th International Conference on Logic Programming and Nonmonotomic Reasoning, LPNMR 2007
Country/Territory	United States
City	Tempe, AZ
Period	5/15/07 → 5/17/07

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-72200-7_14

Cite this

Gebser, M., Lee, J., & Lierler, Y. (2007). Head-elementary-set-free logic programs. In Logic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings (pp. 149-161). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4483 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-540-72200-7_14

Head-elementary-set-free logic programs. / Gebser, Martin; Lee, Joohyung; Lierler, Yuliya.
Logic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings. Springer Verlag, 2007. p. 149-161 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4483 LNAI).

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

Gebser, M, Lee, J & Lierler, Y 2007, Head-elementary-set-free logic programs. in Logic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4483 LNAI, Springer Verlag, pp. 149-161, 9th International Conference on Logic Programming and Nonmonotomic Reasoning, LPNMR 2007, Tempe, AZ, United States, 5/15/07. https://doi.org/10.1007/978-3-540-72200-7_14

Gebser M, Lee J, Lierler Y. Head-elementary-set-free logic programs. In Logic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings. Springer Verlag. 2007. p. 149-161. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-72200-7_14

@inproceedings{d0dd5be14cfc4977837c851ecc8e9684,

title = "Head-elementary-set-free logic programs",

abstract = "The recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its elementary sets. Based on the notion of an elementary set, we propose the notion of head-elementary-set-free (HEF) programs, a more general class of disjunctive programs than head-cycle-free (HCF) programs proposed by Ben-Eliyahu and Dechter, that can still be turned into nondisjunctive programs in polynomial time and space by {"}shifting{"} the head atoms into the body. We show several properties of HEF programs that generalize earlier results on HCF programs. Given an HEF program, we provide an algorithm for finding an elementary set whose loop formula is not satisfied, which has a potential for improving stable model computation by answer set solvers.",

author = "Martin Gebser and Joohyung Lee and Yuliya Lierler",

note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 9th International Conference on Logic Programming and Nonmonotomic Reasoning, LPNMR 2007 ; Conference date: 15-05-2007 Through 17-05-2007",

year = "2007",

doi = "10.1007/978-3-540-72200-7_14",

language = "English (US)",

isbn = "9783540721994",

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

publisher = "Springer Verlag",

pages = "149--161",

booktitle = "Logic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings",

}

TY - GEN

T1 - Head-elementary-set-free logic programs

AU - Gebser, Martin

AU - Lee, Joohyung

AU - Lierler, Yuliya

PY - 2007

Y1 - 2007

N2 - The recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its elementary sets. Based on the notion of an elementary set, we propose the notion of head-elementary-set-free (HEF) programs, a more general class of disjunctive programs than head-cycle-free (HCF) programs proposed by Ben-Eliyahu and Dechter, that can still be turned into nondisjunctive programs in polynomial time and space by "shifting" the head atoms into the body. We show several properties of HEF programs that generalize earlier results on HCF programs. Given an HEF program, we provide an algorithm for finding an elementary set whose loop formula is not satisfied, which has a potential for improving stable model computation by answer set solvers.

AB - The recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its elementary sets. Based on the notion of an elementary set, we propose the notion of head-elementary-set-free (HEF) programs, a more general class of disjunctive programs than head-cycle-free (HCF) programs proposed by Ben-Eliyahu and Dechter, that can still be turned into nondisjunctive programs in polynomial time and space by "shifting" the head atoms into the body. We show several properties of HEF programs that generalize earlier results on HCF programs. Given an HEF program, we provide an algorithm for finding an elementary set whose loop formula is not satisfied, which has a potential for improving stable model computation by answer set solvers.

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

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

U2 - 10.1007/978-3-540-72200-7_14

DO - 10.1007/978-3-540-72200-7_14

M3 - Conference contribution

AN - SCOPUS:38049067614

SN - 9783540721994

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

SP - 149

EP - 161

BT - Logic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings

PB - Springer Verlag

T2 - 9th International Conference on Logic Programming and Nonmonotomic Reasoning, LPNMR 2007

Y2 - 15 May 2007 through 17 May 2007

ER -

Head-elementary-set-free logic programs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this