Principles of Knowledge Representation and Reasoning (eBook)

Proceedings of the Fourth International Conference (KR '94)

Jon Doyle, Erik Sandewall, Pietro Torasso (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
668 Seiten
Elsevier Science (Verlag)
978-1-4832-1452-8 (ISBN)

Infos

Principles of Knowledge Representation and Reasoning contains the proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR '94) held in Bonn, Germany, on May 24-27, 1994. The conference provided a forum for reviewing the theory and principles underlying knowledge representation and reasoning. Topics covered range from reasoning about mental states and spatial reasoning with propositional logics to default logic as a query language. Comprised of 60 chapters, this book begins with a description of a formal language for representing and reasoning about time and action before turning to proof in context and how it can replace the most common uses of reflection principles. The reader is then introduced to reasoning with minimal models; belief ascription and mental-level modeling; and a unified framework for class-based representation formalisms. A general approach to specificity in default reasoning is also described, together with an ontology for engineering mathematics and the use of abduction to generate tests. The book concludes by considering the use of natural language for knowledge representation and reasoning. This monograph will be of interest to both students and practitioners in the fields of artificial intelligence and computer science.

Inhalt

Front Cover 1
Principles of Knowledge Representation and Reasoning 4
Copyright Page 5
Table of Contents 6
Preface 10
Acknowledgments 11
Part I: Contributed Papers 14
Chapter 1. A Computational Account for a Description Logic of Time and Action 16
Abstract 16
1 INTRODUCTION 16
2 THE TEMPORAL LANGUAGE 17
3 ACTIONS AND PLANS 20
4 THE CALCULUS 22
5 CONCLUSIONS 26
Acknowledgments 26
References 26
Chapter 2. Proofs in context 28
Abstract 28
1 INTRODUCTION 28
2 DIFFICULTIES WITH PROOFS IN CONTEXT 29
3 A METHOD FOR PROOFS IN CONTEXT 31
4 A PROOF METHOD AND NOTATION 33
5 CONCLUSIONS 36
Acknowledgments 36
References 36
A APPENDIX 38
Chapter 3. An Integrated Implementation of Simulative, Uncertain and Metaphorical Reasoning about Mental States 40
Abstract 40
1 INTRODUCTION 40
2 METAPHORS OF MIND 40
3 SKETCH OF REASONING 42
4 REPRESENTATION SCHEME 44
5 REASONING BASICS 45
6 BELIEF REASONING 47
7 METAPHORICAL REASONING 49
8 CONCLUSION 50
Acknowledgements 51
References 51
Chapter 4. Reasoning with minimal models: Efficient algorithms and applications 52
Abstract 52
1 Introduction 52
2 The elimination algorithm for HCF theories 53
3 The elimination algorithm forfirst-order HCF theories 55
4 Applications of the elimination algorithm 57
5 Expressive power of stratified knowledgebases 60
6 Related work 61
7 Conclusion 61
Appendix 61
Acknowledgments 62
References 62
Chapter 5. Spatial Reasoning with Propositional Logics 64
Abstract 64
1 INTRODUCTION 64
2 TOPOLOGICAL INTERPRETATION OF PROPOSITIONAL LOGIC 65
3 DEFINING TOPOLOGICAL RELATIONS 66
4 REASONING WITH Co+ 68
5 MORE EXPRESSIVENESS WITH INTUITIONISTIC LOGIC 69
6 IMPLEMENTATION OF A20+ REASONING SYSTEM 71
7 EXTENDING THE REPRESENTATION 72
8 CONCLUSIONS 75
Acknowledgements 75
References 75
Chapter 6. On the Relation Between Default and Modal Consequence Relations 76
Abstract 76
1 INTRODUCTION 76
2 DEFAULT CONSEQUENCE RELATIONS 76
3 MODAL DEFAULT CONSEQUENCE RELATIONS 81
4 REDUCTIONS AND EMBEDDINGS 84
5 CONCLUSIONS 86
References 87
Chapter 7. Toward a Logic for Qualitative Decision Theory 88
Abstract 88
1 Introduction 88
2 Conditional Preferences 89
3 Default Knowledge 93
4 Ability and Incomplete Knowledge 94
5 Concluding Remarks 98
References 99
Acknowledgements 99
Chapter 8. Belief Ascription and Mental-level Modelling 100
Abstract 100
1 INTRODUCTION 100
2 THE FRAMEWORK 102
3 ASCRIBING BELIEF 104
4 CHOOSING AMONG BELIEF ASSIGNMENTS 105
5 ADDING TIME 106
6 BELIEF CHANGE 106
7 EXISTENCE - GOAL SEEKING AGENTS 108
8 DISCUSSION 109
Acknowledgement 110
References 111
Chapter 9. Default Logic as a Query Language 112
Abstract 112
1 INTRODUCTION 112
2 DEFINITION OF DQL 113
3 EXPRESSIVE POWER OF DQL 115
4 APPLICATIONS AND EXAMPLES 118
5 COMBINED COMPLEXITY OF DQL 119
6 CONCLUSIONS 120
APPENDIX 120
Acknowledgements 120
References 120
Chapter 10. A Unified Framework for Class-Based Representation Formalisms 122
Abstract 122
1 INTRODUCTION 122
2 A UNIFYING CLASS-BASED REPRESENTATION LANGUAGE 123
3 REASONING IN UNRESTRICTED MODELS 128
4 REASONING IN FINITE MODELS 130
5 CONCLUSIONS 132
Acknowledgements 132
References 132
Chapter 11. Learning the CLASSIC Description Logic: Theoretical and Experimental Results 134
Abstract 134
1 INTRODUCTION 134
2 BACKGROUND 134
3 C-CLASSIC IS PAC-LEARNABLE 138
4 EXPERIMENTAL RESULTS 140
5 LEARNING DISJUNCTIONS 142
6 CONCLUDING REMARKS 145
Acknowledgments 145
References 145
Chapter 12. Directional Resolution: The Davis-Putnam Procedure, Revisited 147
Abstract 147
1 Introduction 147
2 Definition and preliminaries 148
3 DP-elimination – Directional Resolution 148
4 Tractable classes 149
5 Bounded directional resolution 154
6 Experimental evaluation 154
7 Related work and conclusions 156
Acknowledgements 158
References 158
Chapter 13. A General Approach to Specificity in Default Reasoning 159
Abstract 159
1 Introduction 159
2 Background 160
3 The Approach: Intuitions 162
4 Minimal Conflicting Sets 164
5 Compiling Specificity into Default Theories 165
6 Alternative Translations 168
7 Discussion 169
Acknowledgements 170
References 170
Chapter 14. Action Representation for interpreting Purpose Clauses in Natural Language Instructions 171
Abstract 171
1 INTRODUCTION 171
2 INFERENCE PROCESSES 171
3 THE REPRESENTATION FORMALISM 173
4 INFERENCE IMPLEMENTATION 178
5 CONCLUSIONS 181
Acknowledgements 181
References 181
Chapter 15. Conditional Objects as Nonmonotonic Consequence Relations 183
Abstract 183
1 INTRODUCTION 183
2 CONDITIONAL OBJECTS: THE 3-VALUED SEMANTICS 184
3 CONNECTIVES FOR DEFAULT RULES 185
4 CONDITIONAL OBJECTS AND NONMONOTONIC CONSEQUENCE RELATIONS 186
5 CONSISTENCY AND REFUTATION 187
6 QUASI-CONJUNCTION AND META-RESOLUTION 187
7 TWO MODES OF BELIEF REVISION 188
8 CONCLUSION 188
Acknowledgements 188
ANNEX 188
References 189
Chapter 16. Tractable Closed World Reasoning with Updates 191
Abstract 191
1 INTRODUCTION AND MOTIVATION 191
2 LOCAL CLOSED WORLD INFORMATION 192
3 UPDATING CLOSED WORLD INFORMATION 194
4 EXPERIMENTAL RESULTS 197
5 RELATED WORK 197
6 FUTURE WORK 198
7 CONCLUSIONS 198
A ACTION SEMANTICS 198
B PROOFS 199
Acknowledgments 200
References 200
Chapter 17. A Knowledge-Based Framework for Belief Change, Part II: Revision and Update 203
Abstract 203
1 INTRODUCTION 203
2 THE FRAMEWORK 204
3 BELIEF CHANGE SYSTEMS 205
4 REVISION 206
5 UPDATE 208
6 SYNTHESIS 210
7 CONCLUSION 213
Acknowledgements 213
References 213
Chapter 18. On the Complexity of Conditional Logics 215
Abstract 215
1 INTRODUCTION 215
2 CONDITIONAL LOGIC 217
3 SMALL MODEL THEOREMS 217
4 COMPLEXITY RESULTS 221
5 AXIOMATIZATION 224
6 CONCLUSIONS 225
Acknowledgements 225
References 225
Chapter 19. An Efficient Method for Managing Disjunctions in Qualitative Temporal Reasoning 227
Abstract 227
1 INTRODUCTION 227
2 MANAGING DISJUNCTIONS THROUGH TIMEGRAPHS 228
3 EXPERIMENTAL RESULTS 235
4 CONCLUSIONS 237
Acknowledgements 237
References 237
Chapter 20. GSAT and Dynamic Backtracking 239
Abstract 239
1 INTRODUCTION 239
2 CONSTRAINTS AND NOGOODS 240
3 DYNAMIC BACKTRACKING 242
4 DYNAMIC BACKTRACKING AS LOCAL SEARCH 243
5 PARTIAL-ORDER DYNAMIC BACKTRACKING 243
6 ARBITRARY MOVEMENT 245
7 EXPERIMENTAL RESULTS 247
8 CONCLUSION AND FUTURE WORK 248
A PROOFS 248
References 249
Chapter 21. Representing Uncertainty in Simple Planners 251
Abstract 251
1 INTRODUCTION 251
2 PRELIMINARY DEFINITIONS 252
3 THE SIMPLE PLANNING PROBLEM 252
4 REGRESSION 252
5 ACTIONS WITH UNCERTAIN OUTCOMES 253
6 CNLP AND PLINTH 254
7 UNCERTAINTY AND SECONDARY PRECONDITIONS 255
8 CASSANDRA 256
9 INFORMATION-GATHERING ACTIONS 256
10 OTHER RELATED WORK 257
11 POSSIBLE EXTENSIONS 257
12 SUMMARY AND CONCLUSIONS 257
References 258
Chapter 22. How Far Can We 'C' ? Defining a 'Doughnut' Using Connection Alone 259
Abstract 259
1 INTRODUCTION 259
2 CLARKE'S LOGIC OF CONNECTION, AND RCC'S VERSION 261
3 DEFINING A DOUGHNUT MADE EASY 262
4 DEFINING A DOUGHNUT MADE LESS EASY 264
5 DEFINING A DOUGHNUT MADE HARDER STILL 267
6 Discussion: HOW FAR CAN C TAKE US? 268
Acknowledgements 269
References 270
Chapter 23. An Ontology for Engineering Mathematics 271
Abstract 271
1. INTRODUCTION 271
2. THE PURPOSE OF THE ONTOLOGY 271
3. OVERVIEW OF THE CONCEPTUALIZATION 273
4. RATIONALE FOR IMPORTANT DISTINCTIONS 277
5. DESIGN AND EVALUATION ISSUES 279
6. RELATED WORK 280
Acknowledgments 281
References 281
Chapter 24. An Ontology of Meta-Level Categories 283
Abstract 283
1 INTRODUCTION 283
2 REDS AND APPLES 285
3 THE FORMAL FRAMEWORK 285
4 A BASIC ONTOLOGY OF UNARY PREDICATE TYPES 287
5 ONTOLOGICAL ENGINEERING 290
6 CONCLUSIONS 291
Acknowledgements 292
References 292
Chapter 25. Defeasible reasoning with structured information 294
Abstract 294
1 INTRODUCTION 294
2 STRUCTURED INFORMATION 295
3 NAIVE INFERENCES 295
4 PREFERRED INFERENCES 296
5 INFLUENCE RELATIONS 296
6 STRONGFORWARD LOGICS 297
7 FRAMEWORK EXAMPLES 300
8 FRAMEWORK ISSUES 302
9 AGGREGATION PRINCIPLES 303
10 DISCUSSION 303
Acknowledgements 304
References 304
Chapter 26. On Positive Occurrences of Negation as Failure 306
Abstract 306
1 Introduction 306
2 Answer Sets of Programs with Positive Occurrences of not 307
3 Representing Abduction by GEDP 308
4 Complexity and Computation 310
5 Relation to Autoepistemic Logic 313
6 Discussion 315
7 Conclusion 316
Acknowledgements 316
References 316
Chapter 27. Probabilistic Reasoning in Terminological Logics 318
Abstract 318
1 INTRODUCTION 318
2 SYNTAX 319
3 SEMANTICS 320
4 COMPUTING PROBABILITIES 323
5 A PROBABILISTIC VERSION OF ACC 326
6 CONCLUDING REMARKS 328
References 329
Chapter 28. On Multiagent Autoepistemic Logic - an extrospective view 330
Abstract 330
1 Introduction 330
2 Autoepistemic Logic 332
3 A simple multiagent autoepistemic logic AEEpis 334
4 Conjecture 335
5 Another Multiagent Autoepistemic Logic 336
6 MAE = AEEpis 337
7 Subsumption of Morgenstern's formulation 339
8 Conclusion 340
Acknowledgements 341
References 341
Chapter 29. Refinement Search as a Unifying Framework for analyzing Planning Algorithms 342
Abstract 342
1 Introduction 342
2 Refinement search Preliminaries 343
3 Planning as Refinement Search 344
4 A generalized algorithm for Refinement Planning 346
5 Applications of the Unified Framework 350
6 Extending the framework 352
7 Conclusion 353
References 353
Chapter 30. Actions with Indirect Effects (Preliminary Report) 354
Abstract 354
1 Introduction 354
2 Syntax of ARo 355
3 Examples 356
4 Semantics of ARo 357
5 Two Theorems about Domain Descriptions 358
6 Relation to A 359
7 Translating from ARo into Circumscription 359
8 Conclusion 362
Acknowledgements 362
References 363
Chapter 31. An Application of Terminological Logics to Case-based Reasoning 364
Abstract 364
1 INTRODUCTION 364
2 THE SOLUTION 365
3 AN EXAMPLE 367
4 IMPLEMENTATION 373
5 RELATED WORK 374
6 CONCLUSION 374
Acknowledgements 374
References 374
Chapter 32. Risk-Sensitive Planning with Probabilistic Decision Graphs 376
Abstract 376
1 Introduction 376
2 The Planning Framework 377
3 The Problem 378
4 A Solution 380
5 Conclusion 385
Acknowledgements 385
References 385
Chapter 33. Easy to be Hard: Difficult Problems for Greedy Algorithms 387
Abstract 387
1 Introduction 387
2 Graph crosswords 388
3 The experiments 388
4 Analysis 389
5 Conclusion 391
References 391
Chapter 34. Complexity Results for First-Order Theories of Temporal Constraints 392
Abstract 392
1 INTRODUCTION 392
2 FIRST-ORDER THEORIES OF POINT CONSTRAINTS 393
3 NAIVE QUANTIFIER ELIMINATION ALGORITHMS 393
4 AN IMPROVED QUANTIFIER ELIMINATION ALGORITHM FOR diPC 394
5 AN IMPROVED QUANTIFIER ELIMINATION ALGORITHM FOR dePC 398
6 THEORIES OF POINT AND INTERVAL CONSTRAINTS 400
7 CONCLUSIONS 401
Acknowledgements 401
References 402
Chapter 35. Reasoning in Logic about Continuous Systems 404
Abstract 404
1 INTRODUCTION 404
2 BTL AND EBTL 405
3 QSIM AND THE IMPLEMENTATION OF THE LOGIC 407
4 THE MAIN THEOREM 412
5 APPLICATIONS OF EBTL AND QSIM 413
6 FUTURE DIRECTIONS 414
7 MISCELLANY 414
8 CONCLUSION 415
Acknowledgements 415
References 415
Chapter 36. Enhancing the Power of a Decidable First-Order Reasoner 416
Abstract 416
1 Introduction 416
2 The Logic BLqs 417
3 On Decidable Belief Implication in BLqs 421
4 Sorted Introspective Reasoning 424
5 Conclusion 426
Acknowledgements 426
References 426
Chapter 37. Knowledge, Certainty, Belief, and Conditionalisation (abbreviated version) 428
Abstract 428
1 Introduction 428
2 Belief, certainty, and knowledge: the language 430
3 Belief, certainty, and knowledge: a model theory 430
4 Belief, certainty, and knowledge: an axiomatic system 432
5 Related work 434
6 Conclusions 436
Acknowledgements 436
References 436
Chapter 38. How to Progress a Database (and Why) I. Logical Foundations 438
Abstract 438
1 INTRODUCTION 438
2 LOGICAL PRELIMINARIES 439
3 BASIC ACTION THEORIES 439
4 FORMAL FOUNDATIONS 441
5 PROGRESSION WITH RELATIVELY COMPLETE INITIAL DATABASES 445
6 PROGRESSION IN THE CONTEXT FREE CASE 446
7 SUMMARY 448
Acknowledgements 449
References 449
Chapter 39. Modalities Over Actions, I. Model Theory 450
Abstract 450
1 Introduction 450
2 Intuitions and Applications 451
3 Events and Actions 454
4 Deontic Modalities 457
5 Discussion 460
References 460
Chapter 40. Generating Tests using Abduction 462
Abstract 462
1 INTRODUCTION 462
2 PRELIMINARIES 463
3 TEST GENERATION AS ABDUCTION 465
4 PRACTICAL BENEFITS 467
5 SUMMARY 472
Acknowledgements 472
References 472
Chapter 41. Preferential entailments for circumscriptions 474
Abstract 474
1 Introduction 474
2 Preferential entailment 474
3 Circumscriptions 476
4 General properties 477
5 Some circumscriptions viewed as preferential entailment 479
6 Conclusion 484
Acknowledgements 484
References 484
Chapter 42. A Decision Method for Nonmonotonic Reasoning Based on Autoepistemic Reasoning 486
Abstract 486
1 INTRODUCTION 486
2 AUTOEPISTEMIC LOGIC 487
3 OTHER FORMS OF NONMONOTONIC REASONING 489
4 AUTOMATING NONMONOTONIC REASONING 489
5 CONCLUSIONS 496
References 497
Chapter 43. A Framework for Part-of Hierarchies in Terminological Logics 498
Abstract 498
1 INTRODUCTION 498
2 LANGUAGE 499
3 KEY RELATIONS 501
4 COMPOSITIONAL EXTENSIONS 502
5 DISCUSSION AND CONCLUSIONS 508
Acknowledgements 509
References 509
Chapter 44. Means-End Plan Recognition - Towards a Theory of Reactive Recognition 510
Abstract 510
1 INTRODUCTION 510
2 MEANS-END PLAN EXECUTION AND RECOGNITION 511
3 ALGORITHMS 512
4 DYNAMIC AGENT LOGIC 514
5 REACTIVE RECOGNITION 519
6 COMPARISON AND CONCLUSIONS 520
Acknowledgements 520
References 521
Chapter 45. Terminological Cycles and the Propositional µ-Calculus 522
Abstract 522
1 Introduction 522
2 The Terminological Logic ACC 524
3 Syntactically Monotone Fixpoint Terminologies 525
4 The Terminological Logic ACCµ 528
5 Expressive Power 530
6 Computational Complexity 531
7 Conclusion 532
Acknowledgements 533
References 533
Chapter 46. Near-Optimal Plans, Tractability, and Reactivity 534
Abstract 534
1 INTRODUCTION 534
2 DOMAIN-INDEPENDENT PLANNING 535
3 DOMAIN-DEPENDENT PLANNING 536
4 TRACTABILITY: REACTIVE PLANNING AND UNIVERSAL PLANS 538
5 CONCLUSIONS 540
Acknowledgments 541
References 541
Appendix 541
Chapter 47. Specification and Evaluation of Preferences under Uncertainty 543
Abstract 543
1 Introduction 543
2 Preference Specification 544
3 Evaluation of Preferences 547
4 Quantified Conditional Desires 548
5 Comparison with Related Work 550
6 Conclusion 550
Acknowledgements 552
References 552
Chapter 48. Making the Difference: A Subtraction Operation for Description Logics 553
Abstract 553
1 INTRODUCTION 553
2 THE DIFFERENCE OPERATION IN DESCRIPTION LOGICS 553
3 THE DIFFERENCE OPERATION IN SPECIFIC DESCRIPTION LOGICS 556
4 APPLICATIONS 561
5 CONCLUSION 562
Acknowledgments 562
References 563
Chapter 49. Tractable Databases: How to Make Propositional Unit Resolution Complete through Compilation 564
Abstract 564
1 INTRODUCTION 564
2 NO-MERGE RESOLUTION AND ITS RELATION TO UNIT RESOLUTION 565
3 COMPILATION 566
4 TIED CHAINS, MERGES, AND ORDERING STRATEGIES 570
5 A COMPLETE LTMS 572
6 EXPERIMENTAL RESULTS 573
7 DISCUSSION 573
Acknowledgements 574
References 574
Chapter 50. The Role of Reversible Grammars in Translating Between Representation Languages 575
Abstract 575
1 Introduction 575
2 Interlingua-Based Translations and Semantics 576
3 Definite Clause Translation Grammars 577
4 Reversible Definite Clause Translation Grammars 581
5 Showing that a Translator is Reversible 582
6 Ongoing Work 583
7 Summary 583
Acknowledgments 584
References 584
Chapter 51. Constraint Tightness versus Global Consistency 585
Abstract 585
1 Introduction 585
2 Background 586
3 Binary constraint networks 587
4 R-ary constraint networks 589
5 Conclusions 594
Acknowledgements 595
References 595
Chapter 52. Honesty in Partial Logic 596
Abstract 596
1 INTRODUCTION 596
2 THE LOGIC 598
3 HONESTY 601
4 CONCLUSION 606
Acknowledgements 607
References 607
Chapter 53. Mutual Belief Revision (Preliminary Report) 608
Abstract 608
1 INTRODUCTION 608
2 PRELIMINARIES 609
3 A Theory of Mutual Belief Revision 612
4 Scientists in Conference 614
5 Speech Act Semantics 616
6 Conclusion 618
Acknowledgements 618
References 619
Chapter 54. REVISE: An Extended Logic Programming System for Revising Knowledge Bases 620
Abstract 620
1 INTRODUCTION 620
2 REVIEW OF THE LOGIC PROGRAMMING BASIS 620
3 PREFERENCE LANGUAGE AND SEMANTICS 622
4 EXAMPLES OF APPLICATION 623
5 REVISION ALGORITHM 627
6 COMPARISONS AND CONCLUSIONS 630
Acknowledgements 631
References 631
Chapter 55. Transmutations of Knowledge Systems 632
Abstract 632
1 INTRODUCTION 632
2 THE AGM PARADIGM 633
3 ORDINAL CONDITIONAL FUNCTIONS 634
4 ORDINAL EPISTEMIC ENTRENCHMENT FUNCTIONS 637
5 TRANSLATIONS 639
6 RELATED WORK 640
7 DISCUSSION 640
Acknowledgements 641
References 641
Part II: InvitedTalks 644
Chapter 56. Knowledge Representation Issues in Integrated Planning and Learning Systems 646
Abstract 646
Chapter 57. Non-Standard Theories of Uncertainty in Knowledge Representation and Reasoning 647
INTRODUCTION 647
1 PLAUSIBLE EXCEPTION-TOLERANT INFERENCE 647
2 LIMITATIONS OF CLASSICAL LOGIC 648
3 LIMITATIONS OF BAYESIAN NETWORKS 648
4 LESSONS FROM BAYESIAN NETWORKS 650
5 GRADED REPRESENTATIONS OF INCOMPLETE KNOWLEDGE 651
6 POSSIBILISTIC LOGIC 654
7 PROPERTIES OF EXCEPTION-TOLERANT INFERENCE 655
8 POSSIBILISTIC ENCODING OF RATIONAL INFERENCE 656
CONCLUSION 657
References 657
Chapter 58. Beyond Ignorance-Based Systems 659
Abstract 659
Part III: Panels 660
Chapter 59. Systems vs. Theory vs....: KR& R Research Methodologies
Abstract 662
Chapter 60. Exploiting Natural Language for Knowledge Representation and Reasoning 663
Abstract 663
Contributions by Topic 666
Author Index 668

Produkt-Details

• Erscheint lt. Verlag: 5.6.2014
• Sprache: englisch
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik
• ISBN-10: 1-4832-1452-4 / 1483214524
• ISBN-13: 978-1-4832-1452-8 / 9781483214528