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

Research output: Contribution to journalArticle

23 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)869-907
JournalTheory and Practice of Logic Programming
Volume14
Issue number6
DOIs
Publication statusPublished - Nov 2014

Fingerprint

Semantics
Syntactics
Knowledge representation
Computational complexity

Keywords

  • answer-set programs
  • Belief update
  • literal inertia
  • rule update
  • SE-models
  • support

Cite this

@article{6a64765beff2435f9aefb241785497fa,
title = "The rise and fall of semantic rule updates based on SE-models",
abstract = "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{\'o}n, G{\"a}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.",
keywords = "answer-set programs , Belief update , literal inertia , rule update, SE-models , support",
author = "Martin Slota and Leite, {Jo{\~a}o Alexandre Carvalho Pinheiro}",
note = "SCOPUSID:84905464205 WOS:000346848400003",
year = "2014",
month = "11",
doi = "10.1017/S1471068413000100",
language = "English",
volume = "14",
pages = "869--907",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge Univ Press",
number = "6",

}

The rise and fall of semantic rule updates based on SE-models. / Slota, Martin; Leite, João Alexandre Carvalho Pinheiro.

In: Theory and Practice of Logic Programming, Vol. 14, No. 6, 11.2014, p. 869-907.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Slota, Martin

AU - Leite, João Alexandre Carvalho Pinheiro

N1 - SCOPUSID:84905464205 WOS:000346848400003

PY - 2014/11

Y1 - 2014/11

N2 - 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.

AB - 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.

KW - answer-set programs

KW - Belief update

KW - literal inertia

KW - rule update

KW - SE-models

KW - support

U2 - 10.1017/S1471068413000100

DO - 10.1017/S1471068413000100

M3 - Article

VL - 14

SP - 869

EP - 907

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 6

ER -