On updates of epistemic states: belief chance under incomplete information [Elektronische Ressource] / Juan Carlos Acosta Guadarrama

Sujets

• Informatik

Informations

• Publié par: technische_universitat_clausthal
• Publié le: 01 janvier 2010
• Nombre de lectures: 20
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

On Updates of Epistemic States
Belief Change under Incomplete Information
Doctoral Thesis
(Dissertation)
to be awarded the degree of
Doctor rerum naturalium (Dr.rer.nat.)
submitted by
M.Sc. Juan Carlos Acosta Guadarrama
from Toluca, Mexican United States
approved by
the Faculty of Mathematics/Computer Science and Mechanical Engineering,
Clausthal University of Technology,
Date of oral examination
18.12.2009Chairperson of the Board of Examiners: Prof. Dr. G. Zachmann
Chief Reviewer: Prof. Dr. J. Dix
Reviewers: PD. Dr. habil. W. Jamroga
Prof. Dr. S. HartmannAbstract
In this dissertation I present some aspects of belief-change theory and rep-
resentation of knowledge as one of the main theoretical basis to formulate
semantics for updates of logic programs. Firstly, there is an introduction to
relevant principles and postulates, like the classical belief-revision formula-
tion and a following proposal to make a difference between belief revision
and updates. Next, there is a survey of some few proposals to update logic
programs that are the main motivation for this thesis. Finally, I present
a progressive approach that overrides the problems pointed out in other
alternatives, and that meets most of the principles here introduced.
In particular, revising and updating knowledge bases is an important prob-
lem in knowledge representation and reasoning. It has led to various propos-
als for updating logic programs, specifically with respect to the well known
answer-sets semantics. However, most of these approaches are based on the
causal rejection principle, which leads to counter-intuitive behaviour. The
proposed approach in this thesis is a semantics for abduction known as gen-
eralised answer sets, which allows one to choose potential models, without
changing the semantics of the original given update programs. With gen-
eralised answer sets one can actually formulate semantics for updates that
consist in choosing between generalised models that satisfy an intended set
of properties and overcome certain problems from other approaches. Weak
Irrelevance of Syntax and Strong Consistency are two of the main properties
an update semantics should manifest, which are a keystone to overcome the
mentioned problems.
Finally, as an important component of logic programming and as a useful
tool in the classroom, this work also provides the research community with
online solver prototypes that help close the gap between theory and practice.
These automatic testbeds make the semantics more accessible, and open
up a path with a solid component for further more-complex prototypes of
knowledge management.COPYRIGHT
THEAUTHORRESERVESOTHERPUBLICATIONRIGHTS,ANDNEI-
THER THE THESIS NOR EXTENSIVE EXTRACTS FROM IT MAY
BE PRINTED OR OTHERWISE REPRODUCED WITHOUT THE AU-
THOR’S WRITTEN PERMISSION.
THE AUTHOR ATTESTS THAT PERMISSION HAS BEEN OBTAINED
FOR THE USE OF ANY COPYRIGHTED MATERIAL APPEARING IN
THIS THESIS (OTHER THAN BRIEF EXCERPTS REQUIRING ONLY
PROPER ACKNOWLEDGEMENT IN SCHOLARLY WRITING) AND
THAT ALL SUCH USE IS CLEARLY ACKNOWLEDGED.
c Copyright 2008, Juan Carlos Acosta GuadarramaAcknowledgements
I would like to acknowledge the National Council of Science and Technology
of Mexico for a doctoral grant, which has funded a large part of this project.
Software Tools
AThetypesettingofthisdocumenthasbeenaccomplishedwithhelpof LT X2e,E
BibT X, and ACM’s bibliography style, all running on TeXShop on MacE
TMOS systems. Most of the implementations are running on Apache Mac
TMOS or Linux servers.
Reviewers
ThisworkhasalsobeenaccompaniedbyclosereviewsfromPD.Dr.W.Jam-
roga, as well as some other anonymous reviewers from workshops and con-
ferences. Prof. M. Osorio also played a key role in publishing one of the
papers.
Juan Carlos Acosta Guadarrama
TU-Clausthal, 2009J.C.A.Guadarrama
ivContents
Preface xi
1 Introduction 1
1.1 Knowledge and Belief Representation . . . . . . . . . . . . . . . . . . . . 2
1.2 A Question of Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Logic in Artificial Intelligence . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Knowledge Incompleteness . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Theory Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Representing Knowledge with Logic Programs . . . . . . . . . . . . . . . 6
1.4 Updating Theories with Logic Programming . . . . . . . . . . . . . . . . 7
1.4.1 Semantics for Updates . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.3 A Principle-based Approach to Represent Knowledge and Beliefs 11
1.5 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Foundations 15
2.1 Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Intuitionistic Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Multi-Valued Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.3 Nelson’s Logic andN -logic . . . . . . . . . . . . . . . . . . . . . 182
2.2 Change and Belief Representation . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Belief Revision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Belief Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Conclusion for Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Preliminaries 27
3.1 Logic Programming and Answer Sets . . . . . . . . . . . . . . . . . . . . 27
3.2 Stable Models and Answer Sets . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Equivalence in Logic Programming . . . . . . . . . . . . . . . . . . . . . 30
3.4 Weak Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5 Ordered Disjunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5.1 ODLP-reduct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
vContents J.C.A.Guadarrama
3.5.2 ODLP-semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5.3 ODLP and Weak Constraints . . . . . . . . . . . . . . . . . . . . 37
3.5.4 ODLP-solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6 Abductive Programming and GAS . . . . . . . . . . . . . . . . . . . . . 38
3.7 Complexity Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.7.1 The Polynomial Hierarchy . . . . . . . . . . . . . . . . . . . . . . 40
3.7.2 The Exponential-time Hierarchy . . . . . . . . . . . . . . . . . . 41
4 A Road Map for Update Semantics 43
4.1 Eiter and Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 DyLP and Other Dialects . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Sakama & Inoue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.1 Extended Abduction Framework . . . . . . . . . . . . . . . . . . 54
4.3.2 -operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55SI
4.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 Zhang’s line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4.1 General View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4.2 Prioritised Logic Programs . . . . . . . . . . . . . . . . . . . . . 67
4.4.3 Eliminating Contradictions . . . . . . . . . . . . . . . . . . . . . 71
4.4.4 Solving Conflicts . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.5 Logic Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.6 Conclusions for Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5 Observations and Examples 85
5.1 Vacuous Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2 Updates at the Object Level . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.3 Conflicting Information . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.4 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.5 Conclusions for Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6 Relaxing Knowledge-bases 95
6.1 Model Choice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.2 Structural Properties for Updates in ASP . . . . . . . . . . . . . . . . . 98
6.3 Computing Updates with ODLP . . . . . . . . . . . . . . . . . . . . . . . 101
6.3.1 ODLP-reduct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3.2 ODLP-semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3.3 ODLP and Weak Constraints . . . . . . . . . . . . . . . . . . . . 103
6.3.4 ODLP-solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.3.5 Translating into ODLP . . . . . . . . . . . . . . . . . . . . . . . . 104
6.3.6 Updating with ODLP . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.4 Conclusions for Chapter 6 . . . . . . . . . . . . . . . . . . . . . . . . . . 107
viTU-Clausthal Contents
7 Update Sequences 109
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2
-Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.3
-Properties . . . . . . . .