IJCAI _1989-VOLUME 1

Proceedings of the Eleventh International Joint Conference

Volume 1

August 20-25 1989

sponsored by International Joint Conferences on Artificial Intelligence, Inc. (IJCAII)

cosponsored and hosted by American Association for Artificial Intelligence (AAAI)

In cooperation with A consortium of Michigan companieson

Artificial Intelligence

CONTENTS

FOUNDATIONS

Symbols and Subsymbols for Representing Knowledge: A Catalogue Raisonne

Marcello Frixione, Giuseppe Spinelli and Salvatore Gaglio................ 3

A Symbol Is Not a Symbol

NilsDahlback.............................................................. 8

Execution Architectures and Compilation

Stuart J. Russell........................................................... 15

TOOLS

Parallel Iterative A* Search: An Admissible Distributed Heuristic Search Algorithm

Shie-rei Huang and Larry 5. Davis.............................. 23

Correct Parallel Status Assignment for the Reason Maintenance System

Rosanne M. Fulcomer and William E. Ball................. 30

Single-Agent Parallel Window Search: A Summary of Results

Curt Powley and Richard E. Korf................................ 36

Searching Game Trees in Parallel Using SSS

Subir Bhattacharya and A. Bagchi............................... 42

Platypus: A Constraint-Based Reasoning System

William 5. Havens and Paul Stephen Rehfuss............. 48

Domain Dependence in Parallel Constraint Satisfaction

Paul R. Cooper and Michael J. Swain......................... 54

A Universal Programming Language

Hans Werner Guesgen................................................60

Explaining Prolog Based Expert Systems Using a Layered Meta-lnterpreter

Leon Sterling and L. Omit Yalcinalp............................66

Simulation of Hybrid Circuits in Constraint Logic Programming

Thomas Graf, Pascal Van Hentenryck,Claudia Pradclles and Laurent Zimmer........ 72

A Framework for Network Modeling in Prolog

Zdravko I. Markov...................................................... 78

An Evaluation of DRete on CUPID for OPS5 Matching

Michael A. Kelly and Rudolph E. Seviora................... 84

The Search Ahead Conflict Resolution for Parallel Firing of Production Systems

Ching-Chi Hsu and Feng-Hsu Wang........................... 91

A Technique for Customizing Object-Oriented Knowledge Representation Systems, With An Application to Network Problem Management

Lisiane Goffaux and Robert Mathonet........................ 97

Contexts: Dynamic Identification of Common Parameters in Distributed Analysis of Complex Devices

San jaya Addanki, Roberto Cremonini and J. Scott Penberthy............ 104

A Knowledge-Based Software Information System

Premkumar Devanbu, Peter G. Selfridge, Bruce W. Ballard and Ronald J. Brachman............ 110

Chart Parsing of Flowgraphs

Rudi Lutz.................................................................. 116

Call-Graph Caching: Transforming Programs into Networks

MarkPerlin.............................................................. 122

A New Metaphor for the Graphical Explanation of Forward-Chaining Rule Execution

John Domingue and Marc Eisenstadt....................... 129

Reconstructive Explanation: Explanation as Complex Problem Solving

Michael R. Wick and William B. Thompson............ 135

Adaptation-Based Explanation: Extending Script/Frame Theory to Handle Novel Input

Alex Kass.................................................................. 141

PARALLEL AND DISTRIBUTED PROCESSING

A Vectorization Technique for Prolog without Explosion

Yasusi Kanada and Masahiro Sugaya....................... 157

Unrestricted And-Parallel Execution of Logic Programs with Dependency Directed Backtracking

Nikos Drakos........................................................... 157

A Sequential View of AND-Parallelism Through Partial AND-Processes

Bernd Schend........................................................... 163

Unsupervised Learning by Backward Inhibition

Tomas Hrycej.......................................................... 170

On Multi-Layered Connectionist Models: Adding Layers vs. Increasing Width

Chung-jen Ho........................................................... 176

Generation, Local Receptive Fields and Global Convergence Improve Perceptual Learning in Connectionist Networks

Vasant Honavar and Leonard Uhr............................ 180

Beyond PDP: The Frequency Modulation Neural Network Architecture

Hideto Tomabcchi and Hiroaki Kitano..................... 186

Integrating Knowledge-Based System and Neural Network Techniques for Robotic Skill Acquisition

David A. Handelman, Stephen H. Lane and Jack J. Gelfand.................. 193

Experiences Implementing a Parallel ATMS on a Shared-Memory Multiprocessor

Edward Rothberg and Anoop Gupta........................ 799

Neural Computing on a One Dimensional SIMD Array

Stephen S. Wilson.................................................... 206

The ELINT Application on Poligon: The Architecture and Performance of a Concurrent Blackboard System

James Rice................................................................212

REAL-TIME AND HIGH PERFORMANCE

The Implementation of Expert, Knowledge-Based Systems

John Debenham....................................................... 221

Knowledge Base Compilation

F. D. Highland and C. T. Iwaskiw............................. 227

Rapid Retrieval Algorithms for Case-Based Reasoning

 Richard H. Stottler, Andrea L. Henke and James A. King............. 233

Minimizing Response Times in Real Time Planning and Search

Shashi Shekhar and Soumitra Dutta......................... 238

Intelligent Monitoring and Control

Barbara Hayes-Roth, Richard Washington, Rattikorn Hewett, Micheal Hewett and Adam  Seivcr................. 243

Input Data Management in Real-Time Al Systems

Richard Washington and Barbara Hayes-Roth......... 250

Real-Time Al Systems: A Definition and An Architecture

Rajendra Dodhiawala, N. S. Sridharan, Peter Raulefs and Cynthia Pickering............... 256

SEARCH

Node Aggregation for Distributed Inference in Bayesian Networks

Kuo-Chu Chang and Robert Fung............................ 265

Experimental Evaluation of Preprocessing Techniques in Constraint Satisfaction Problems

Rina Dechter and Itay Meiri..................................... 271

Partial Constraint Satisfaction

Eugene C. Freuder.................................................... 278

An Algebraic Approach to Constraint Satisfaction Problems

Igor Rivin and Ramin Zabih......................................284

A Comparison of ATMS and CSP Techniques

Johan de Klecr......................................................... 290

Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory

Anup K. Sen and A. Bagchi...................................... 297

Towards Finding Optimal Solutions with Non-Admissible Heuristics: A New Technique

Henry W. Davis, Anna Bramanti-Gregor and Xiaofeng Chen......................303

Constrained Heuristic Search

Mark S. Fox, Norman Sadeh and Can Baykan...........309

Multi-Dimensional Heuristic Searching

Peter C. Nelson and Lawrence J. Henschen.............. 316

The Reason for the Benefits of Minimax Search

Anton Scheucher and Hermann Kaindl.................... 322

Generalized Game Trees

Richard E. Korf.........................................................328

On Optimal Game-Tree Search using Rational Meta-Reasoning

Stuart Russell and Eric Wefald.................................. 334

Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving

Charles Elkan........................................................... 341

AUTOMATED DEDUCTION

Preprocessing Search Spaces for Branch and Bound Search

Qiang Yang and Dana 5. Nau....................................349

And-Or Graphs Applied to RUE Resolution

 Vincent J. Digricoli, James J. Lu and V. 5. Subrahmanian................... 354

A Rational Reconstruction and Extension of Recursion Analysis

Alan Bundy, Frank van Harmelen, Jane Hesketh, Alan Smaill and Andrew Stevens............ 359

Recognizing Unnecessary Inference

Dan Benanav........................................................... 366

Abstract Theorem Proving

Fausto Giunchiglia and Toby Walsh..........................372

Structuring Computer Generated Proofs

Christoph Lingenfelder............................................. 378

A Computational Structure for the Propositional Calculus

M. J. Shensa............................................................. 384

Program Derivation Using Analogy

Mehdi T. Harandi and San jay Bhansali.................... 389

Logic Programming with General Clauses and Defaults Based on Model Elimination

Marco A. Casanova, Ramiro Guerreiro and

Andrea Silva............................................................. 395

Reducing the Derivation of Redundant Clauses in Reasoning Systems

Rolf Socher-Ambrosius............................................. 401

Explanation Based Program Transformation

Maurice Bruynooghe, Luc De Raedt and Danny De Schreye.....................407

The Specialization and Transformation of Constructive Existence Proofs

Peter Madden...........................................................413

On Wu's Method for Proving Constructive Geometric Theorems

Dongming Wang..................................................... 419

On the Decidability of Formulae Involving Continuous and Closed Functions

Domenico Cantone and Eugenio G. Omodeo.......... 425

An Approximate Solver for Symbolic Equations

Elisha Sacks............................................................. 431

Lock, Linear Lambda-Paramodulation in Operator Fuzzy Logic

LiuXuHua................................................................435

Modal Theorem Proving: An Equational Viewpoint

Yves Auffray and Patrice Enjalbert............................441

Extending Reflective Architectures

Timothy M. Lownie.................................................. 446

Maximum Entropy in Nilsson's Probabilistic Logic

Thomas B. Kane....................................................... 452

How to Represent Opaque Sentences in First Order Logic

BijanArbab.............................................................. 458

A Theorem Prover for Prioritized Circumscription

Andrew B. Baker and Matthew L. Ginsberg.............. 463

Circumscribing Equality

Peter K. Rathmann and Marianne Winslett............... 468

INTELLIGENT TUTORING SYSTEMS

A Computational Framework for Granularity and its Application to Educational Diagnosis

Jim Greer and Gordon McCalia................................ 477

The Generation of 'Critical Problems' by Abstract Interpretations of Student Models

RickEvertsz............................................................. 483

Generating Causal Explanation from a Cardiovascular Simulation

Sarah A. Douglas and Zheng-Yang Liu ....................489

COGNITIVE MODELS

Focus of Control Through Goal Relationships

Victor R. Lesser, Daniel D. Corkill, Robert C. Whitehair and Joseph A. Hernandez.................. 497

Opportunistic Memory

Kristian J. Hammond.................................................504

An Adaptive Model of Decision-Making in Planning

Gregg Collins, Lawrence Birnbaum and Bruce Krulwich................. 511

Argumentation: Planning Other Agents' Plans

Katia P. Sycara......................................................... 517

Combining Case-Based and Rule-Based Reasoning: A Heuristic Approach

Edwina L. Rissland and David B. Skalak................... 524

Generating Facts From Opinions with Information Source Models

Martin Thost.............................................................531

Defining Salience in Case-Based Arguments

Kevin D. Ashley........................................................537

Simulating Student Programmers

James C. Spohrer and Elliot Soloway........................ 543

The Correction Machine: Formulating Explanations for User Misconceptions

AlexQuilici..............................................................550

Learning to Diagnose by Doing

Jayant Kalagnanam and Eswaran Subrahmanian.......556

Focusing Attention for Observational Learning: The Importance of Context

Joel Martin............................................................... 562

Neural-Net Implementation of Complex Symbol-Processing in a Mental Model Approach to Syllogistic Reasoning

John A. Barnden...................................................... 568

A Probabilistic Approach to Marker Propagation

Dekai Wu................................................................ 574

MACHINE LEARNING

Automated Synthesis of Constrained Generators

Wesley Braudaway and Chris Tong.......................... 583

Using and Refining Simplifications: Explanation-Based Learning of Plans in Intractable Domains

Steve A. Chien.........................................................590

Towards a General Framework for Composing Disjunctive and Iterative Macro-operators

Peter Shell and Jaime Carbonell............................... 596

Selective Learning of Macro-operators with Perfect Causality

Seiji Yamada and Saburo Tsuji................................. 603

Learning Subgoal Sequences for Planning

David Ruby and Dennis Kibler................................. 609

A Study of Empirical Learning for an Involved Problem

LarryRendell........................................................... 675

A Problem Space Approach to Expert System Specification

Gregg R. Yost and Allen Newell.............................. 621

On the Road to Automatic Knowledge Engineering

JituPatel................................................................... 628

Comparing the Conceptual Systems of Experts

Brian R. Gaines and Mildred L. G. Shaw................... 633

Learning DNF by Decision Trees

Giulia Pagallo........................................................... 639

Constructive Induction On Decision Trees

Christopher J. Mathcus and Larry A. Rendell............ 645

Principled Constructive Induction

Pankaj Mehra, Larry A. Rendell and Benjamin W.          651

Wah......................................................................... 657

Improving Efficiency by Learning Intermediate Concepts

James Wogulis and Pat Langley................................ 657

Coping With Uncertainty in Map Learning

Kenneth Basye, Thomas Dean and Jeffrey Scott

Vitter........................................................................ 663

Learning Novel Domains Through Curiosity and Conjecture

Paul D. Scott and Shaul Markovitch..........................669

Rule Creation and Rule Learning Through Environmental Exploration

Wci-Min Shcn and Herbert A. Simon....................... 675

Abstraction in Problem Solving and Learning

Amy Unruh and Paul 5. Rosenbloom....................... 681

Acquiring Recursive Concepts with Explanation-Based Learning

Jude W. Shavlik........................................................ 688

Lazy Explanation-Based Learning: A Solution to the Intractable Theory Problem

Prasad Tadcpalli....................................................... 694

Discovering Admissible Heuristics by Abstracting and Optimizing: A Transformational Approach

Jack Mostow and Armand E. Prieditis....................... 701

Induction in an Abstraction Space: A Form of Constructive Induction

George Drastal, Gabor Czako and Stan Raatz.......... 708

Detecting and Correcting Errors of Omission After Explanation-Based Learning

Michael J. Pazzani.................................................... 713

An Integrated Characterization and Discrimination Scheme to Improve Learning Efficiency in Large Data Sets

Roberto Gemello and Franco Mana..........................719

The Effect of Rule Use on the Utility of Explanation-Based Learning

Raymond Mooney.................................................... 725

Eliminating Expensive Chunks by Restricting Expressiveness

Milind Tambe and Paul Rosenbloom....................... 731

Utilization Filtering: A Method for Reducing the Inherent Harmfulncss of Deductively Learned Knowledge

Shaul Markovitch and Paul D. Scott.........................738

Incorporating Redundant Learned Rules: A Preliminary Formal Analysis of EBL

Russell Greiner and Joseph Likuski.......................... 744

Representation and Hidden Bias II: Eliminating Defining Length Bias in Genetic Search via Shuffle Crossover

Richard A. Caruana, Larry J. Eshelman and J. David Schaffer............................... 750

Alternatives for Classifier System Credit Assignment

Gunar E. Licpins, Michael R. HilIiard, Mark Palmer and Gita Rangarajan............................ 756

Training Feedforward Neural Networks Using Genetic Algorithms

David J. Montana and Lawrence Davis.................... 762

Hierarchical Genetic Algorithms Operating on Populations of Computer Programs

John R. Koza............................................................ 768

An Experimental Comparison of Symbolic and Connectionist Learning Algorithms

Raymond Mooney, Jude Shavlik, Geoffrey Towel I and Alan Gove............................................. 775

An Empirical Comparison of Pattern Recognition, Neural Nets, and Machine Learning Classification Methods

Sholom M. Weiss and loannis Kapouleas................. 781

An Empirical Comparison of ID3 and Back-propagation

Douglas H. Fisher and Kathleen B. McKusick........... 788

Noise-Tolerant Instance-Based Learning Algorithms

David W. Aha and Dennis Kibler............................. 794

Generating Better Decision Trees

Steven W. Norton.................................................... 800

Building Robust Learning Systems by Combining Induction and Optimization

David Tcheng, Bruce Lambert, Stephen C-Y Lu and Larry Rendell.................... 806

Concept Learning and the Problem of Small Disjuncts

Robert C. Holte, Liane E. Acker and Bruce W.Porter................................ 813

Chemical Analogies: Two Kinds of Explanation

Paul Thagard, Dawn M. Cohen and Keith J. Holyoak....................819

Noise-Tolerant Conceptual Clustering

Douglas H. Fisher.................................................... 825

Concept Formation by Incremental Conceptual Clustering

Mirsad Hadzikadic and David Y. Y. Yun.................. 831

A Critique of the Valiant Model

Wray Buntine.......................................................... 837

The Minimum Description Length Principle and Its Application to Online Learning of Handprinted Characters

Qiong Gao and Ming Li.......................................... 843

Towards Friendly Concept-Learners

Luc De Raedt and Maurice Bruynooghe.................. 849