Russo Revision, Acceptability and Context

Theoretical and Algorithmic Aspects
1. Auflage 2010
ISBN: 978-3-642-14159-1
Verlag: Springer
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 386 Seiten

An important aspect in the formalisation of common-sense reasoning is the construction of a model of what an agent believes the world to be like to help in her reasoning process. This model is often incomplete or inaccurate, but new information can be used to refine it. The study of techniques that achieve this in a rational way is the task of the discipline of belief revision, with which this book is concerned. There are three key elements to the book's approach. Firstly, the methodology of logic by translation. A specific instance of this is the idea of revision by translation. Revision for a foreign logic is done via its translation into a well-known logic, usually classic logic. Secondly, the technique of meta-level/object-level movement, where we bring some operation defined at the meta-level of a logic into its object level. In this book, we bring the operation of deletion to the object level. Finally, through Labelled Deductive Systems, we use the context of the revision to finetune its operation and illustrate the idea through the presentation of various algorithms. The book is suitable for researchers and postgraduates in the areas of artificial intelligence, database theory, and logic.

Autoren/Hrsg.

Russo, Alessandra

Inhaltsverzeichnis

1;Preface;5
2;Contents;7
3;1 Background and Overview;11
3.1;1.1 Introductory Discussion;11
3.2;1.2 Focusing on `Acceptability' Rather than `Inconsistency';15
3.3;1.3 Overview of This Book;17
3.4;1.4 Notation Used in This Book;18
3.5;1.5 Basic Mathematical Notions;20
3.6;References;21
4;2 Introducing Revision Theory;23
4.1;2.1 AGM Belief Revision;23
4.2;2.2 Katsuno and Mendelzon's Characterisation;30
4.3;2.3 Counterfactual Statements and the Ramsey Test;31
4.4;2.4 Grove's Systems of Spheres;35
4.5;2.5 Epistemic Entrenchment;38
4.6;2.6 Discussion;40
4.7;2.7 Action Updates;40
4.8;2.8 Generalising the Concept of Revision;43
4.9;2.9 Iterating the Revision Operation;47
4.9.1;2.9.1 Darwiche and Pearl's Postulates for Iterated Revisions;47
4.9.2;2.9.2 Lehmann's Approach: Belief Revision, Revised;50
4.10;2.10 Compromise Revision;51
4.11;2.11 Controlled Revision;55
4.12;2.12 Revision by Translation;57
4.13;2.13 A General Setting for Algorithmic Revision ;59
4.14;2.14 Outline of This Book;62
4.15;References;62
5;3 Stepwise Revision Operations;65
5.1;3.1 Introduction;65
5.2;3.2 Quantitative Measurement of Change;65
5.2.1;3.2.1 Minimal Change and the Function d;66
5.3;3.3 Qualitative Measurements of Change;73
5.4;3.4 Representation Issues;75
5.5;3.5 Revision of Formulae;77
5.6;3.6 Properties of the Revision Operator r;80
5.7;3.7 Other Belief Change Operators;87
5.7.1;3.7.1 Belief Contraction;87
5.7.2;3.7.2 Consolidating Information on the Belief Base;92
5.8;3.8 Comparison with Other Belief Change Operators;95
5.9;3.9 Operators for Reasoning About the Effects of Actions;98
5.9.1;3.9.1 Updates of Sentences via Distance d;99
5.9.2;3.9.2 Properties of the Action Update Operator;103
5.9.3;3.9.3 Action Updates of Sentences via Distance diff;106
5.9.4;3.9.4 Ambiguous Action Updates;108
5.9.5;3.9.5 Taking Causality into Account;110
5.10;References;112
6;4 Iterating Revision;114
6.1;4.1 Introduction;114
6.2;4.2 Motivating Structure for Belief Revision;116
6.3;4.3 Iteration of the Revision Operation;117
6.4;4.4 Prioritised Databases;120
6.4.1;4.4.1 Properties of the Revisions of PDBs;124
6.4.2;4.4.2 Discussion about Iteration of Revision;128
6.5;4.5 Structured Databases;133
6.6;4.6 Applications and Examples;135
6.7;4.7 Related Work;137
6.7.1;4.7.1 Prioritised Base Revision;137
6.7.2;4.7.2 Ordered Theory Presentations;140
6.8;4.8 Using Additional Information for Action Updates;141
6.9;References;145
7;5 Structured Revision;147
7.1;5.1 Identifying Inconsistency;147
7.2;5.2 Reasoning with Partial Priorities;156
7.2.1;5.2.1 Degree of Confidence/Reliability of the Source;157
7.2.2;5.2.2 Linearisations;173
7.3;5.3 Clustering;174
7.4;5.4 Applications in Software Engineering;176
7.4.1;5.4.1 Requirements Specification;176
7.4.2;5.4.2 An Example with the Light Control System;177
7.5;References;183
8;6 Algorithmic Context Revision;185
8.1;6.1 Introduction;185
8.2;6.2 Abductive Revision;185
8.2.1;6.2.1 Introducing LDS for ;188
8.2.2;6.2.2 Goal-Directed Algorithm for ;191
8.2.3;6.2.3 Discussion on the Abduction Procedure;195
8.2.4;6.2.4 Abduction Algorithm for ;200
8.2.5;6.2.5 Abduction for Intuitionistic Logic;202
8.3;6.3 Compromise Revision ;205
8.3.1;6.3.1 Introducing Compromise Revision for ;205
8.3.2;6.3.2 Comparison with AGM Revision;218
8.4;6.4 Controlled Revision;222
8.4.1;6.4.1 Proof Theory;224
8.4.2;6.4.2 Policies for Inconsistency;225
8.4.3;6.4.3 Conclusions;229
8.5;References;230
9;7 Revision by Translation;231
9.1;7.1 Introduction;231
9.2;7.2 Belief Revision for Modal Logic;233
9.2.1;7.2.1 An Overview of Propositional Modal Logics;233
9.2.2;7.2.2 Hilbert Systems for Modal Logics;238
9.2.3;7.2.3 Translation of the Modal Logic K into Classical Logic;241
9.3;7.3 Revising in ukasiewicz' Finitely Many-Valued Logic n;243
9.3.1;7.3.1 ukasiewicz' Finitely Many-Valued Logic n;243
9.3.2;7.3.2 Translating ukasiewicz' Many-Valued Logic n into Classical Logic;249
9.3.3;7.3.3 Revision in ukasiewicz' Many-Valued Logic ( n);252
9.4;7.4 Revising in Algebraic Logics;254
9.4.1;7.4.1 Translating Algebraic Logic into Classical Logic;254
9.4.2;7.4.2 Revision in Algebraic Logics;256
9.5;7.5 Introducing Belnap's Four-Valued Logic;257
9.5.1;7.5.1 Belief Revision in Belnap's Four-Valued Logic;257
9.6;7.6 Belnap's Four-Valued Logic;259
9.6.1;7.6.1 Axiomatising Belnap's Four-Valued Logic;259
9.6.2;7.6.2 Entailment in Belnap's Four-Valued Logic;261
9.6.3;7.6.3 Generalising Belnap's Notion of Entailment to Infinite Theories;263
9.6.4;7.6.4 Translating Belnap's Logic into Classical Logic;267
9.6.5;7.6.5 Revising in Belnap's Four-Valued Logic;273
9.7;7.7 Conclusions and Discussions;276
9.8;References;277
10;8 Object-Level Deletion;279
10.1;8.1 Introduction;279
10.2;8.2 Object-Level Meta-Level Operations;279
10.3;8.3 The Need for Object-Level Deletion;282
10.4;8.4 Strategy of the Technique;287
10.5;8.5 Substructural Logics;289
10.5.1;8.5.1 Hilbert and Gentzen Formulations;290
10.5.2;8.5.2 Goal-Directed Proof Theory;296
10.5.3;8.5.3 Semantics;305
10.6;8.6 Introducing Anti-formulae in Concatenation and Linear Logic;312
10.6.1;8.6.1 Analysis;313
10.6.2;8.6.2 Introducing Anti-formulae into Logics with and e;318
10.6.3;8.6.3 Anti-formulae and Negation;323
10.7;8.7 The Notion of Failure in Resource Logics;329
10.8;8.8 Deletion in Resource-Unbounded Logics;333
10.9;8.9 Logical Deletion in LDS;335
10.10;8.10 Introducing N-Prolog with Negation as Failure;344
10.11;8.11 Exploring Deletion via Addition;352
10.12;8.12 A Formal System for Deletion via Addition;361
10.13;8.13 Concluding Remarks;363
10.14;References;366
11;9 Conclusions and Discussions;367
11.1;9.1 Concluding Remarks;367
11.2;9.2 Discussions;372
11.3;References;382
12;List of Symbols;384
13;Subject Index;386