arrow
返回

Determining inference semantics for disjunctive logic programs

delete2019-12-01
delete4
delete
OA
AI
Y
Yidong Shen *
T
Thomas Eiter
DOI:10.1016/j.artint.2019.103165delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
In a seminal paper, Gelfond and Lifschitz [34] introduced simple disjunctive logic programs, where in rule heads the disjunction operator vertical bar is used to express incomplete information, and defined the answer set semantics (called GL-semantics for short) based on a program transformation (called GL-reduct) and the minimal model requirement. Our observations reveal that the requirement of the GL-semantics, i.e., an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong a condition and exclude some answer sets that would be reasonably acceptable. To address this, we present an alternative, more permissive answer set semantics, called the determining inference (DI) semantics. Specifically, we introduce a head selection function to formalize the operator vertical bar and define answer sets as follows: (i) Given an interpretation I and a selection function sel, we transform a disjunctive program Pi into a normal program Pi(I)(sel), called a disjunctive program reduct; (ii) given a base answer set semantics chi for normal programs, we define I to be a candidate answer set of Pi w.r.t. chi if I is an answer set of Pi(I)(sel) under chi; and (iii) we define I to be an answer set of Pi w.r.t. chi if I is a minimal candidate answer set. The DI-semantics is general and applicable to extend any answer set semantics chi for normal programs to disjunctive programs. By replacing chi with the GL(nlp)-semantics defined by Gelfond and Lifschitz [33], we induce a DI-semantics for simple disjunctive programs, and by replacing chi with the well justified semantics defined by Shen et al. [65], we further induce a DI-semantics for general disjunctive programs. We also establish a novel characterization of the GL-semantics in terms of a disjunctive program reduct, which reveals the essential difference of the DI-semantics from the GL-semantics and leads us to giving a satisfactory solution to the open problem presented by Hitzler and Seda [36] about characterizing split normal derivatives of a simple disjunctive program Pi such that answer sets of the normal derivatives are answer sets of Pi under the GL-semantics. Finally we give computational complexity results; in particular we show that in the propositional case deciding whether a simple disjunctive program Pi has some DI-answer set is NP-complete. This is in contrast to the GL-semantics and equivalent formulations such as the FLP-semantics [24], where deciding whether Pi has some answer set is Sigma(p)(2)-complete, while brave and cautious reasoning are Sigma(p)(2)- and Pi(p)(2)-complete, respectively, for both GL- and DI-answer sets. For general disjunctive programs with compound formulas as building blocks, the complexity of brave and cautious reasoning increases under DI-semantics by one level of the polynomial hierarchy, which thus offers higher problem solving capacity. (C) 2019 The Authors. Published by Elsevier B.V.
Keyword:
Answer set programming
Knowledge representation and reasoning
Nonmonotonic reasoning
Disjunctive logic programs
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

Artificial Intelligence Review 封面图
Artificial Intelligence Review
IF:
13.9
论文数:
6.2K
被引数:
3.0W

机构

中
中国科学院
学者数:
2.9W
论文数: 8.1K
被引数: 39.2W
引用论文

引用论文

Vaporization of Beryllium Oxide and Its Reaction with Tungsten
err1959-03-01
err0
PREAI
errWilliam A. Chupka; Joseph Berkowitz; Clayton F. Giese
err分享
err收藏
Investigation of ancient and new Japanese papers
err1996-07-01
err0
PREAI
errHans G. Wiedemann; John R. Günter; Hans R. Oswald
err分享
err收藏
Combining answer set programming with description logics for the semantic Web
err2008-08-01
err182
errOAAI
errEiter, Thomas; Ianni, Giovambattista; Lukasiewicz, Thomas; Schindlauer, Roman; Tompits, Hans
err分享
err收藏
Semi-equilibrium models for paracoherent answer set programs
err2016-05-01
err22
errOAAI
errAmendola, Giovanni; Eiter, Thomas; Fink, Michael; Leone, Nicola; Moura, Joao
err分享
err收藏
err分享
err收藏
FLP answer set semantics without circular justifications for general logic programs
err2014-08-01
err25
errOAAI
errShen, Yi-Dong; Wang, Kewen; Eiter, Thomas; Fink, Michael; Redl, Christoph; Krennwallner, Thomas; Deng, Jun
err分享
err收藏
Sputtered electrochromic V2O5 films
err1989-12-01
err0
PREAI
errD. Wruck; S. Ramamurthi; M. Rubin
err分享
err收藏
Gummy smile - causes and modern treatment methods
err2023-02-21
err0
errOAAI
errMonika Blicharz; Agnieszka Blicharz; Diana Bartosik-Zielińska; Tomasz Swatko; Magdalena Bartosik
err分享
err收藏
学者 查看更多内容