A characterization of answer sets for logic programs

• Published in: Science China. Information sciences 2007-02, Vol.50 (1), p.46-62
• Main Authors: Zhang, MingYi, Zhang, Ying, Lin, FangZhen
• Format: Article
• Language: English
• Subjects: Algorithms; Computation; Logic programming; Logic programs; Semantics; Tightness; 计算机; 逻辑程序
• ISSN: 1009-2757; 1674-733X; 1862-2836; 1869-1919
• DOI: 10.1007/s11432-007-0001-1

Checking if a program has an answer set, and if so, compute its answer sets are just some of the important problems In answer set logic progremming. Solving these problems using Gelfond and Llfschltz＇s original definition of answer sets Is not an easy task. Alternative charaoterlzatlons of answer sets for nested logic programs by Erdem and Llfschltz, Lee and Llfschltz, and You at el. are based on the completion semantics and various notions of tlghtnese. However, the notion of tightness Is a local notion In the sense that for different answer sets there are, In general, different level mappings capturing their tlghtnese. This makes It hard to be used In the deelgn of algorithms for computing answer sets. This paper proposes a charecterization of answer sets based on sets of generetlng rules. From this charaoterlzation new algorithms are derived for computing answer sets and for performing some other reasoning teaks. As an application of the charecterlzatlon a sufficient and necessary condition for the equivalence between answer set sementics and completion semantics has been proven, and a basic theorem Is shown on computing answer sets for nested logic programs baaed on an extended notion of loop formulas. These results on tlghtnese and loop formulas are more general than that in You and Lin＇a work.