IJCAI _1985-VOLUME 1

Proceedings of the Ninth International

Joint Conference on Artificial Intelligence

IJCAI-85

VOLUME -1

CONTENTS

Al and Education 1

The Geometry Tutor

John R. Anderson, C. Franklin Boyle, and Gregg Yost      1

Dynamic Student Modelling in an Intelligent Tutor for LISP Programming

Brian J. Reiser, John R. Anderson, and Robert G. Farrell           8

 Heuristic and Formal Methods in Automatic Program Debugging

William R. Murray         15

Grammars as User Models  

Ethel Schuster          20

An Expert System for Understanding Expressions from Electric Circuit Analysis

Rostam Joobbani and Sarosh N. Talukdar             23

Computer Assisted Reasoning with MIZAR

Andrzej Trybulec and Howard Blair         26

Al ARCHITECTURES

Al Architectures 1

The Intelligent Channel: A Scheme for Result Sharing in Logic Programs

Simon Kasif and Jack Minker              29

The Architecture of the FAIM-1 Symbolic Multiprocessing System

A. L Davis and S. V. Robison                 32

A Variable Supply Model for Distributing Deductions

Vineet Singh and Michael R. Genesereth             39

 A Modular Tool Kit for Knowledge Management

Gilles M. E. Lafue and Reid G. Smith   46

Al Architectures 2

Parallelism in Al Programs

Dennis F. Kibler and John Conery         53

Recognition Algorithms for the Connection Machine

Anita M. Flynn and John G. Harris          57

 NON-VON's Applicability to Three Al Task Areas

David Elliot Shaw Yes         61

An SIMD Machine Can Be Used for Al

Ruven Brooks and Rosalyn Lum             73

AUTOMATED REASONING

Automated Reasoning 1

Counterfactuals

Matthew L Ginsberg             80

Reasoned Assumptions and Pareto Optimality

Jon Doyle Deals              87

Deals Among Rational Agents

Jeffrey S. Rosenschein and Michael R. Genesereth             91

Automated Reasoning 2

A Functional Approach to Non-Monotonic Logic

Erik Sandewall                     100

Does Probability Have a Place in Non-monotonic Reasoning?

Matthew L Ginsberg                 107

Combination and Propagation of Uncertainty with Belief Functions—A Reexamination

Didier Dubois and Henri Prade             111

Results on Translating Defaults to Circumscription

Tomasz Imielinski             114

 Computing Circumscription

Vladimir Lifschitz                 121

Automated Reasoning 3

The Limits of Qualitative Simulation

Benjamin Kuipers                 128

 Qualitative Mathematical Reasoning

Elisha Sacks                 137

Combining Discrete and Continuous Process Models

Daniel S. Weld             140

On the Comparison of Theories: Preferring the Most Specific Explanation

David L Poole                 144

Using Model Theory to Specify Al Programs

Alan M. Frisch                 148

Automated Reasoning 4

EGS: A Transformational Approach to Automatic Example Generation

Myung W. Kim              155

Applying Adaptive Algorithms to Epistatic Domains

Lawrence Davis             162

Automating Program Speedup by Deciding What to Cache

Jack Mostow and Donald Cohen                 165

 Evaluating Queries in Deductive Databases by Generating

Eliezer L Lozinskii                     173

Automated Reasoning 5

Modal Propositional Semantics for Reason Maintenance Systems

Allen L Brown, Jr                  178

A Process Theory of Non-monotonic Inference

James W. Goodwin             185

An Approach to Dependency Directed Backtracking Using Domain Specific Knowledge

Vasant Dhar............................... 188

Taxonomic Reasoning

Josh D. Tenenberg...........................191

Paraifelism in Inheritance Hierarchies with Exceptions

Garrison W. Cottrell........................ 194

AUTOMATIC PROGRAMMING

Automatic Programming 1

Automated Enhancement of Knowledge Representations

Robert Balzer............................. 203

Synthesis by Completion

Nachum Dershowitz........................ 208

Reasoning by Cases and the Formation of Conditional Programs

Douglas R. Smith.......................... 215

A Heuristic Approach to Program Inversion

David Eppstein............................ 219

The Origin of the Binary-Search Paradigm

Zohar Manna and Richard Waldinger......... 222

Automatic Programming 2

Symbolic Execution in Algorithm Design

David Steier and Elaine Kant................ 225

Automatic Programming for Streams

David Barstow............................. 232

COGNITIVE MODELLING

Cognitive Modelling 1

Symbols Among the Neurons: Details of a Connectionist Inference Architecture

David S. Touretzky and Geoffrey E. Hinton..... 238

Virtual Lateral Inhibition in Parallel Activation Models of Associative Memory

James A. Reggia........................... 244

The Teachable Letter Recognizer

James Geller.............................. 249

Shape Recognition and Illusory Conjunctions

Geoffrey E. Hinton and Kevin J. Lang......... 252

Computational Neurolinguistics—What Is It All About?

Helen M. Gigley............................ 260

Cognitive Modelling 2

Input-Expectation Discrepancy Reduction: A Ubiquitous Mechanism

Derek Partridge............................ 267

What's in a Mental Model? On Conceptual Models in Reasoning with Spatial Descriptions

Goran Hagert.............................. 274

Daydreaming in Humans and Computers

Erik T. Mueller and Michael G. Dyer........... 278

A Short Note on Opportunistic Planning and Memory in Arguments

Lawrence Birnbaum........................ 281

A Process Model of Cased-Based Reasoning in Problem Solving

Janet L Kolodner, Robert L Simpson, Jr., and Katia Sycara-Cyranski.......... 284

Learning to Understand Contractual Situations

Seth R. Goldman, Michael G. Dyer, and Margot Flowers............ 291

Arguments of Persuasion in Labour Mediation

Katia Sycara-Cyranski...................... 294

EXPERT SYSTEMS

Expert Systems 1

Empirical and Model-based Reasoning in Expert Systems

P. A. Koton................................ 297

Control Issues in Classificatory Diagnosis

Jon Sticklen, B. Chandrasekaran, and John R. Josephson.................. 300

On Using Causal Knowledge to Recognize Vital Signals: Knowledge-based Interpretation of Arrhythmias

Tetsutaro Shibahara........................ 307

Expert Systems 2

Judgmental Reasoning for Expert Systems

TimNiblett................................ 315

Uncertainty Management in a Distributed Knowledge Based System

Naseem A. Khan and Ramesh Jain........... 318

Parallel Formulation of Evidential-Reasoning Theories

Terence R. Thompson....................... 321

Predictor: An Alternative Approach to Uncertain Inference in Expert Systems

Allan P. White............................. 328

The Characteristic Error Approach to Conflict Resolution

Richard D. Ferrante......................... 331

Expert Systems 3

An Architecture for Knowledge Based Deduction

Arthur J. Nevins........................... 335

Transactional Blackboards

J. Robert Ensor and John D. Gabbe........... 340

Representing Procedural Knowledge in Expert Systems: An Application to Process Control

Massimo Gallanti, Giovanni Guida, Luca Spampinato, and Alberto Stefanini...... 345

COMODEL: A Language for the Representation of Technical Knowledge

Werner Dilger and Jorge Kippe............... 353

Controlling Production Firing: The FCL Language

Leonard Friedman......................... 359

Expert Systems 4

SEEK2: A Generalized Approach to Automatic Knowledge Base Refinement

Allen Ginsberg, Sholom Weiss, and Peter Politakis......................... 367

Checking an Expert Systems Knowledge Base for Consistency and Completeness

T. A. Nguyen, W. A. Perkins, T. J. Laffey, and D. Pecora.................... 375

Neat Explanation of Proof Trees

Agneta Eriksson and Anna-Lena Johansson ... 379

Explainable (and Maintainable) Expert Systems

Robert Neches, William R. Swartout, and Johanna Moore................. 382

A Case Study in Structured Knowledge Acquisition

Paul de Greet and Joost Breuker............. 390

Expert Systems 5

Headache and Facial Pain

Mlchio Kimura, Yasushi Matsumura, Takashi Matsunaga, Ryuji Hata, and Hiroshi Matsumura............. 393

Model Expert System MES

Guan Jiwen, Xu Ylng, Chang Minche, and Zhao Jizhl..................... 397

Knowledge Representation In an Expert Storm Forecasting System

Rene'e Elio and Johannes de Haan........... 400

Parsing Circuit Topology In a Deductive System

Takushl Tanaka............................ 407

An Expert Advisor for Photolithography

Terry Cllne, Wendy Fong, and Steven Rosenberg...................... 411

A Fault Detection and Isolation Method Applied to Liquid Oxygen Loading for the Space Shuttle

Ethan A. Scarl, John R. Jamieson, and Carl I. Delaune......................... 414

Expert Systems 6

Syllogistic Reasoning as a Basis for Combination of Evidence in Expert Systems

L A. Zadeh................................ 417

Flexible Data Fusion (and Fission)

Alexander Yeh............................. 420

Fault Diagnosis Through Responsibility

Robert Milne.............................. 423

Control and Integration of Diverse Knowledge in a Diagnostic Expert System

Pamela K. Fink............................ 426

KNOWLEDGE REPRESENTATION

Knowledge Representation 1

Granularity

Jerry R. Hobbs............................ 432

Naive Kinematics: One Aspect of Shape

Yoav Shoham.............................. 436

A Representation for Complex Physical Domains

Sanjaya Addanki and Ernest Davis........... 443

ONYX: An Architecture for Planning in Uncertain Environments

Curtis Langlotz, Lawrence Fagan, Samson Tu, John Williams, and Branlmlr Sikic............ 447

Understanding Behavior Using Consolidation

Tom Bylander and B. Chandrasekaran......... 450

Knowledge Representation 2

A Decidable First-Order Logic for Knowledge Representation

Peter F. Patel-Schnelder..................... 455

Two Results on Default Logic

Witold Lukaszewlcz........................ 459

On the Descriptional Complexity of Production Systems

Peter Trum................................ 462

Evidential Reasoning in Semantic Networks: A Formal Theory

Lokendra Shastrl and Jerome A. Feldman..... 465

An Endorsement-based Plan Recognition Program

Michael Sullivan and Paul R. Cohen.......... 475

A Guide to the Modal Logics of Knowledge and Belief: Preliminary Draft

Joseph Y. Halpern and Yoram O. Moses....... 480

Belief, Awareness, and Limited Reasoning: Preliminary Report

Ronald Fagin and Joseph Y. Halpern.......... 491

A Computational Theory of Belief Introspection

Kurt Konollge............................. 502

A Model-Theoretic Analysis of Monotonic Knowledge

Moshe Y. Vardi............................. 509

Using Situation Descriptions and Russell Ian Attitudes for Representing Beliefs and Wants

Alfred Kobsa.............................. 513

Knowledge Representation 4

A Procedural Logic

Michael P. Georgeff, Amy L Lansky,and Pierre Besslere........................ 516

Event Calculus

Gary C. Borchardt.......................... 524

A Common-Sense Theory of Time

James F. Allen and Patrick J. Hayes.......... 528

An Essential Hybrid Reasoning System: Knowledge and Symbol Level Accounts of KRYPTON

Ronald J. Brachman, Victoria Pigman Gilbert, and Hector J. Levesque......................... 532

The Layered Architecture of a System for Reasoning about Programs

Charles Rich.............................. 540

The Restricted Language Architecture of a Hybrid Representation System

Marc Vilain................................ 547

LEARNING AND ACQUISITION

Learning and Acquisition 1

Proportionality Graphs, Units Analysis, and Domain Constraints: Improving the Power and Efficiency of the Scientific Discovery Process

Brian Falkenhalner......................... 552

A Comparison of Analytic and Experimental Goal Regression for Machine Learning

Bruce W. Porter and Dennis F. Kibler.......... 555

Learning Disjunction of Conjunctions

LG. Valiant............................... 560

Learning Hidden Causes from Empirical Data

Judea Pearl............................... 567

Learning and Acquisition 2

LEAP: A Learning Apprentice for VLSI Design

Tom M. Mitchell, Sridhar Mahadevan, and Louis I. Steinberg........... 573

MORE: An Intelligent Knowledge Acquisition Tool

Gary Kahn, Steve Nowlan, and John McDermott............... 581

The Utility of Expert Knowledge

Jonathan Schaeffer and T A. Marsland....... 585

Dynamic System Control Using Rule Learning and Genetic Algorithms

David E. Goldberg.......................... 588

Multi-Objective Learning via Genetic Algorithms

J. David Schaffer and John J. Grefenstette..... 593

Learning and Acquisition 3

Sefectively Generalizing Plans for Problem-Solving

Steve Minton.............................. 596

Learning Planning Heuristics through Observation

Charles Dolan and Michael Dyer............. 600

Heuristics for Inductive Learning

Steven Salzberg........................... 603

Discovering the Wave Theory of Sound: Inductive Inference in the Context of Problem Solving

Paul Thagard and Keith Holyoak............. 610

Validating Concepts from Automated Acquisition Systems

Albrecht Heeffer........................... 613

Verification-based Learning: A Generalized Strategy for Inferring Problem-Reduction Methods

Sridhar Mahadevan......................... 616

Learning and Acquisition 4

Learning Procedures from Examples and by Doing

David M. Neves............................ 624

Generating Rules from Examples

Bijan Arbab and Donald Michie.............. 631

Learning Concept Descriptions from Examples with Errors

Jukab Segen.............................. 634

Knowledge Acquisition for Constructive Systems

Sandra Marcus, John McDermott, and Tianran Wang............ 637

Learning by Discovering Macros in Puzzle Solving

Glenn A. Iba............. 640

Learning and Acquisition 5

Generalizing Logic Circuit Designs by Analyzing Proofs of Correctness

Thomas Ellman............................ 643

Automatically Inferring Database Schemas

Sitaram Lanka............................. 647

Substantial Constructive Induction Using Layered Information Compression: Tractable Feature Formation in Search

Larry Rendell.............................. 650

Learning Intermediate Concepts in Constructing a Hierarchical Knowledge Base

Li-Min Fu and Bruce G. Buchanan............ 659

Learning about Momentum Conservation

Jude W. Shavlik............................ 667

Training and Tracking in Robotics

Oliver G. Selfridge, Richard S. Sutton, and Andrew G. Barto............... 670

Learning and Acquisition 6

Representation and Use of Explicit Justifications for Knowledge Base Refinements

Reid G. Smith, Howard A. Winston, Tom M. Mitchell, and Bruce G. Buchanan............ 673

Learning Schemata for Natural Language Processing

Raymond Mooney and Gerald DeJong........ 681

Towards a Model of Conceptual Knowledge Acquisition Through Directed Experimentation

Shankar Rajamoney, Gerald DeJong, and Boi Faltings..................... 688

Approaches to Conceptual Clustering

Douglas Fisher and Pat Langley.............. 691

A Prototypical Approach to Machine Learning

R. I. Phelps and R B. Musgrove...............698