The rise and fall of semantic rule updates based on SE-models*. Issue 6 (November 2014)

• Record Type: Journal Article
• Authors: SLOTA, MARTIN; LEITE, JOÃO
• Is Part Of: Theory and practice of logic programming. Volume 14:Issue 6(2014)
• Page Start: 869
• Page End: 907
• Publication Date: 2014-11
• Subjects: Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068413000100
• Languages: English
• ISSNs: 1471-0684

Abstract

<abstract abstract-type="normal"> <title>Abstract</title> <p>Logic programs under the stable model semantics, or answer-set programs, provide an expressive rule-based knowledge representation framework, featuring a formal, declarative and well-understood semantics. However, handling the evolution of rule bases is still a largely open problem. The Alchourrón, Gärdenfors and Makinson (AGM) framework for belief change was shown to give inappropriate results when directly applied to logic programs under a non-monotonic semantics such as the stable models. The approaches to address this issue, developed so far, proposed update semantics based on manipulating the syntactic structure of programs and rules.</p> <p>More recently, AGM revision has been successfully applied to a significantly more expressive semantic characterisation of logic programs based on <monospace>SE</monospace>-models. This is an important step, as it changes the focus from the evolution of a syntactic representation of a rule base to the evolution of its semantic content.</p> <p>In this paper, we borrow results from the area of belief update to tackle the problem of updating (instead of revising) answer-set programs. We prove a representation theorem which makes it possible to constructively define any operator satisfying a set of postulates derived from Katsuno and Mendelzon's postulates for belief update. We define a specific operator based on this theorem, examine its computational complexity and compare the behaviour of this operator with syntactic rule update semantics from the literature. Perhaps surprisingly, we uncover a serious drawback of all rule update operators based on Katsuno and Mendelzon's approach to update and on <monospace>SE</monospace>-models.</p> </abstract>