Show simple item record

AuthorAsuncion, Vernon
AuthorZhang, Yan
AuthorZhang, Heng
Available date2016-05-16T10:57:31Z
Publication Date2014
Publication Name14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014
ResourceScopus
CitationAsuncion, V., Zhang, Y., Zhang, H. "Logic programs with ordered disjunction: First-order semantics and expressiveness" (2014) 14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014, pp. 2-11.
ISBN978-157735657-8
URIhttp://www.aaai.org/ocs/index.php/KR/KR14/paper/view/7844
URIhttp://hdl.handle.net/10576/4539
AbstractLogic programs with ordered disjunction (LPODs) (Brewka 2002) generalize normal logic programs by combining alternative and ranked options in the heads of rules. It has been showed that LPODs are useful in a number of areas including game theory, policy languages, planning and argumentations. In this paper, we extend propositional LPODs to the first-order case, where a classical second-order formula is defined to capture the stable model semantics of the underlying first-order LPODs. We then develop a progression semantics that is equivalent to the stable model semantics but naturally represents the reasoning procedure of LPODs. We show that on finite structures, every LPOD can be translated to a firstorder sentence, which provides a basis for computing stable models of LPODs. We further study the complexity and expressiveness of LPODs and prove that almost positive LPODs precisely capture first-order normal logic programs, which indicates that ordered disjunction itself and constraints are sufficient to represent negation as failure.
SponsorNPRP grant (NPRP 09-079-1-013) from the Qatar National Research Fund (QNRF).
Languageen
PublisherAAAI Publications
SubjectArtificial intelligence
Logic programming
Answer set programming
TitleLogic programs with ordered disjunction: First-order semantics and expressiveness
TypeConference Paper
Paginationpp 2-11
dc.accessType Open Access


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record