Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T03:31:28.949Z Has data issue: false hasContentIssue false

The rise and fall of semantic rule updates based on SE-models*

Published online by Cambridge University Press:  07 August 2013

MARTIN SLOTA
Affiliation:
CENTRIA and Departamento de Informática, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal e-mail: jleite@fct.unl.pt
JOÃO LEITE
Affiliation:
CENTRIA and Departamento de Informática, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal e-mail: jleite@fct.unl.pt
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

More recently, AGM revision has been successfully applied to a significantly more expressive semantic characterisation of logic programs based on SE-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.

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 SE-models.

Information

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2013