TY  - JOUR
A1  - Gerbser, Martin
A1  - Lee, Joohyung
A1  - Lierler, Yuliya
T1  - Elementary sets for logic programs
Y1  - 2006
SN  - 978-1-57735-281-5
ER  - 
TY  - JOUR
A1  - Gebser, Martin
A1  - Lee, Joohyung
A1  - Lierler, Yuliya
T1  - Head-elementary-set-free logic programs
Y1  - 2007
SN  - 978-3-540- 72199-4
ER  - 
TY  - JOUR
A1  - Gebser, Martin
A1  - Lee, Joohyung
A1  - Lierler, Yuliya
T1  - On elementary loops of logic programs
JF  - Theory and practice of logic programming
N2  - Using the notion of an elementary loop, Gebser and Schaub (2005. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'05), 53-65) refined the theorem on loop formulas attributable to Lin and Zhao (2004) by considering loop formulas of elementary loops only. In this paper, we reformulate the definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we also show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs attributable to Ben-Eliyahu and Dechter (1994. Annals of Mathematics and Artificial Intelligence 12, 53-87). Like an Ha: program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.
KW  - stable model semantics
KW  - loop formulas
KW  - unfounded sets
Y1  - 2011
U6  - https://doi.org/10.1017/S1471068411000019
SN  - 1471-0684
VL  - 11
IS  - 2
SP  - 953
EP  - 988
PB  - Cambridge Univ. Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Cabalar, Pedro
A1  - Fandinno, Jorge
A1  - Lierler, Yuliya
T1  - Modular Answer Set Programming as a formal specification language
JF  - Theory and practice of logic programming
N2  - In this paper, we study the problem of formal verification for Answer Set Programming (ASP), namely, obtaining aformal proofshowing that the answer sets of a given (non-ground) logic programPcorrectly correspond to the solutions to the problem encoded byP, regardless of the problem instance. To this aim, we use a formal specification language based on ASP modules, so that each module can be proved to capture some informal aspect of the problem in an isolated way. This specification language relies on a novel definition of (possibly nested, first order)program modulesthat may incorporate local hidden atoms at different levels. Then,verifyingthe logic programPamounts to prove some kind of equivalence betweenPand its modular specification.
KW  - Answer Set Programming
KW  - formal specification
KW  - formal verification
KW  - modular logic programs
Y1  - 2020
U6  - https://doi.org/10.1017/S1471068420000265
SN  - 1471-0684
SN  - 1475-3081
VL  - 20
IS  - 5
SP  - 767
EP  - 782
PB  - Cambridge University Press
CY  - New York
ER  - 
TY  - GEN
A1  - Gebser, Martin
A1  - Lee, Joohyung
A1  - Lierler, Yuliya
T1  - On elementary loops of logic programs
T2  - Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
N2  - Using the notion of an elementary loop, Gebser and Schaub (2005. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’05 ), 53–65) refined the theorem on loop formulas attributable to Lin and Zhao (2004) by considering loop formulas of elementary loops only. In this paper, we reformulate the definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we also show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs attributable to Ben-Eliyahu and Dechter (1994. Annals of Mathematics and Artificial Intelligence 12, 53–87). Like an HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.
T3  - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 566 
KW  - stable model semantics
KW  - loop formulas
KW  - unfounded sets
Y1  - 2019
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-413091
SN  - 1866-8372
IS  - 566
ER  -