# Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (I)

## IJCAI-93 Contents Vol 1

Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence

August 28 - September 3,1993

AUTOMATED REASONING

Abduction I

A Tractable Class of Abduction Problems

Kave Eshghi ..3

An Abductive Framework for General Logic Programs and other Nonmonotonic Systems

Gerhard Brewka and Kurt Konolige ..9

**Abduction II**

Olivier Raiman, Johan de Kleer,

and Vijay Saraswat..18

Focusing Construction and Selection of Abductive Hypotheses

David B. Leake ..24

Deductive Planning and Theory Approximation

A New Logical Framework for Deductive Planning

Werner Stephan and Susanne Biundo ..32

Semantical and Computational Aspects of Horn Approximations

Marco Cadoli ..39

**Theorem Proving I**

A new algorithm for incremental prime implicate generation

Teow-Hin Ngair..46

Automatic Generation of Some Results in Finite Algebra

Masayuki Fujita, John Slaney

and Frank Bennett..52

**Theorem Proving II**

Extending the Resolution Method with Sorts

Christoph Weidenbaeh ..60

Proving theorems in a multi-source environment

Laurence Cholvy..66

**Theorem Proving III**

Ricardo Caferra and Stephane Demri..74

First-Order Modal Logic Theorem Proving and Functional Simulation

Andreas Nonnengart ..80

**Theorem Proving IV**

Automatic Case Analysis in Proof by Induction

Adel Bouhoula and Michael Rusinowitch ..88

Combining Induction Axioms by Machine

Christoph Walther ..95

**Theorem Proving V**

Bottom-up Abduction by Model Generation

Katsumi Inoue, Yoshihiko Ohta, Ryuzo Hasegawa and Makoto Nakashima..102

SCOTT: A Model-Guided Theorem Prover

John Slaney ..109

**Theorem Proving VI**

David A. Basin and Toby Walsh ..116

On the Polynomial Transparency of Resolution

Reinhold Letz..123

**Theorem Proving VII**

A Note on Backward Dual Resolution and Its Application to Proving Completeness of Rule-Based Systems

Antoni Ligeza..132

Exploiting Irrelevance Reasoning to Guide Problem Solving

Alon Y. Levy and Yehoshua Sagiv..138

**Time and Action I**

Automated Trend Detection with Alternate Temporal Hypotheses

Ira J. Haimowitz and Isaac S. Kohane..146

Exploiting Domain Structure to Achieve Efficient Temporal Reasoning

Mike Williamson and Steve Hanks ..152

**Time and Action II**

Explanation in the Situation Calculus

Murray Shanahan ..160

Situation Recognition: Representation and Algorithms Christophe Dousson, Paul Gaborit and Malik Ghallab..166

**COGNITIVE MODELING**

**Cognitive Modeling I**

ANTLIMA - A Listener Model with Mental Images

Jorg RJ. Schirra and Eva Stopp..175

Perception and Experience in Problem Solving

Edmund Furse and Rod Nicolson..181

**Cognitive Modeling II**

AI Models as a Variety of Psychological Explanation

Kieron O'Hara and Nigel Shadbolt..188

Using the Affective Reasoner to Support Social Simulations

Clark Elliott..194

**Cognitive Modeling III**

A Computational Model of Tractable Reasoningï¿½ taking inspiration from cognition

Lokendra Shastri..202

Dynamic Memories: Analysis of an Integrated Comprehension and Episodic Memory Retrieval Model

Trent E. Lange and Charles M. Wharton..208

**CONSTRAINT SATISFACTION PROBLEMS**

**Complexity**

Bidirectional Best-First Search with Bounded Error: Summary of Results

Andreas L. Koll and Hermann Kaindl..217

When functional and bijective constraints make a CSP polynomial

Philippe David ..224

**Consistency**

Consistency Techniques for Numeric CSPs

Olivier Lhomme..232

Why AC-3 is Almost Always Better than AC-4 for Establishing Arc Consistency in CSPs

Richard J. Wallace ..239

**Constraint Satisfaction Strategies I**

Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA

Alexander Reinefeld ..248

Using Inferred Disjunctive Constraints To Decompose Constraint Satisfaction Problems

Eugene C. Freuder and Paul D. Hubhe..254

**Constraint Satisfaction Strategies II**

Domain filtering can degrade intelligent backtracking search

Patrick Prosser..262

Optimistic Parallel Discrete Relaxation

Kinson Ho, Paul N. Hilfinger and Hans W. Guesgen..268

**Overdetermination and Interchangeability**

Diagnosing and solving over-determined constraint satisfaction problems

R.R. Bakker, F. Dikker, F. Tempelman and P.M. Wognum ..276

Exploiting Interchangeabilities in Constraint Satisfaction Problems

Alois Haselbock..282

**Satisfiability**

Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems

Bart Selman and Henry Kautz..290

Satisfiability of Boolean formulas over linear constraints

Henri Be ringer and Bruno de Backer...296

**DISTRIBUTED AI**

**Agent Learning**

Agents, Habitats, and Routine Behavior

Richard AIterman and Roland Zito-Wolf..305

Learning to Coordinate Actions in Multi-Agent Systems

Gerhard Weiss ..311

**Analysis of Multi-Agent Systems I**

A Model-Theoretic Approach to the Verification of Situated Reasoning Systems

Anand S. Rao and Michael P. Georgeff..318

Liveness and Fairness Properties in Multi-Agent Systems

Hans-Dieter Burkhard..325

**Analysis of Multi-Agent Systems II**

Enhancing Performance of Cooperating Agents in Real-Time Diagnostic Systems

U.M. Schwuttke and AG. Quan ..332

Provably bounded optimal agents

Stuart J. Russell, Devika Subramanian and Ronald Parr ..338

**Multi-Agent Collaboration I**

A Collaboration Mechanism on Positive Interactions in Multi-agent Environments

Kei Matsubayashi and Mario Tokoro..346

A Scheme for Agent Collaboration in Open Multiagent Environments

Ei-lchi Osawa ..352

**Multi-Agent Collaboration II**

An Approach to Analyzing the Need for Meta-Level Communication

Keith Decker and Victor Lesser..360

Collaborative Plans for Group Activities

Barbara Grosz and Sarit Kraus..367

**Multi-Agent Epistemology I**

All They Know: A Study in Multi-Agent Autoepistemic Reasoning

Gerhard Lakemeyer..376

Epistemic Extension of Propositional Preference Logics

Jacques Wainer..382

**Multi-Agent Epistemology II**

A Representationalist Theory of Intention

Kurt Konolige and Martha E. Pollack..390

Elements of a Utilitarian Theory of Knowledge and Action

Piotr J. Gmytrasiewicz and Edmund H. Durfee . . 396

**Multi-Agent Logic Programming**

Ozï¿½A Programming Language for Multi-Agent Systems

Martin Henz, Gert Smolka and Jorg Wurtz..404

Wï¿½A Logic System Based on the Shared Common Knowledge Views

Xianchang Wang, Huowang Chen, Quingping Zhao, and Wei Li ..410

**Multi-Agent Negotiation I**

A Domain Theory for Task Oriented Negotiation

Gilad Zlotkin and Jeffrey S. Rosenschein ..416

Multi-Agent Planning as a Dynamic Search for Social Consensus

Eithan Ephrati and Jeffrey S. Rosenschein ..423

**Multi-Agent Negotiation II**

Are Many Reactive Agents Better Than a Few Deliberative Ones?

Kevin Knight..432

Understanding the Role of Negotiation in Distributed Search Among Heterogeneous Agents

Susan E. Lander and Victor R. Lesser..438

**INTELLIGENT TUTORING SYSTEMS**

**Intelligent Tutoring Systems I**

Classification Networks: A Knowledge Representation Scheme for Curriculum Prescription

Kwok-Keung Yum and Thomas J. Richards..447

Constraint Based Automatic Construction and Manipulation of Geometric Figures

Richard Allen, Jeanne Idt and Laurent Trilling .. 453

**Intelligent Tutoring Systems II**

PHIï¿½A Logic-Based Tool for Intelligent Help Systems

M. Bauer, S. Biundo, D. Dengler, J. Koehler and G. Paul ..460

Nonmonotonic Model Inferenceï¿½A Formalization of Student Modeling

Mitsuru Ikeda, Yasuyuki Kono and Riichiro Mizoguchi..467

**KNOWLEDGE BASE TECHNOLOGY**

**Knowledge Base Technology I**

Expert System Validation through Knowledge Base Refinement

Pedro Meseguer..477

Test Case Generation using KBS Strategy

Laurence Vignollet and Ruddy Lelouche ..483

**Knowledge Base Technology II**

Off-line Reasoning for On-line Efficiency

Yoram Moses and Moshe Tennenholtz ..490

TREE: the Heuristic Driven Join Strategy of a RETE-Like Matcher

Jacques Bouaud..496

**Knowledge Base Technology III**

Brian R. Gaines..504

Specification and Generation of Custom-Tailored Knowledge-Acquisition Tools

Henrik Eriksson..510

**KNOWLEDGE REPRESENTATION**

**Belief Revision I**

Revision Sequences and Nested Conditionals

Craig Boutilier..519

The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions

Thomas Eiter and Georg Gottlob..526

**Belief Revision II**

Connections Between the ATMS and AGM Belief Revision

Simon Dixon and Norman Foo..534

Syntactic Characterizations of Belief Change Operators

Alvaro del Val..540

**Contexts**

Non-omniscient belief as context-based reasoning

Fausto Giunchiglia, Luciano Serafini, Enrico Giunchiglia and Marcello Frixione..548

John McCarthy..555

**Default Logics I**

Statistical Foundations for Default Reasoning

Fahiem Bacchus, Adam J. Grove, Joseph Y. Halpern and Daphne Koller..563

The Power of Beliefs or Translating Default Logic Into Standard Autoepistemic Logic

Georg Gottlob..570

**Default Logics II**

On the Semantics of Supernormal Defaults

Stefan Brass..578

Preference-based semantics for nonmonotonic logics

Frans Voorbraak..584

**Evidential Reasoning**

Generalization of the Dempster-Shafer Theory

J.W. Guan and DA. Bell..592

Quantifying Beliefs by Belief Functions: an Axiomatic Justification

Philippe Smets..598

**Reasoning Under Uncertainty **

David Poole..606

On the Hardness of Approximate Reasoning Dan Roth..613

Reasoning Under Uncertainty II

Didier Dubois and Henri Prade..620

Second Order Measures for Uncertainty Processing

Zdenek Zdrdhal..626

**Reasoning with Inconsistent or Disjunctive Information**

Curb Your Theory! A circumscriptive approach for inclusive interpretation of disjunctive information

Thomas Eiter, Georg Gottlob

and Yuri Gurevich..634

Inconsistency management and prioritized syntax-based entailment

Salem Benferhat, Claudette Cayrol, Didier Dubois, Jerome Lang and Henri Prade..640

**Temporal Reasoning**

Efficient Temporal Reasoning through Timegraphs

Alfonso Gerevini and Lenhart Schubert..648

Path Consistency in a Network of Non-convex Intervals

Robert A. Morris, William D. Shoaff and Lina Khatib..655

**Terminological Logic I**

A Terminological Logic with Defaults: A Definition and an Application

Lin Padgham and Tingting Zhang ..662

How to Prefer More Specific Defaults in Terminological Default Logic

Franz Baader and Bernhard Hollunder..669

T**erminological Logic II**

Default Inheritance Reasoning in Hybrid KL-ONE-style Logics

Umberto Straceia..676

More Notes on 'A Clash of intuitions'

R. Al-Asady and A. Narayanan..682

**Terminological Logic 111**

A Multi-Dimensional Terminological Knowledge Representation Language

Hans Jurgen Ohlbach ..690

Using Classification as a Programming Language

Chris Mellish and Ehud Reiter..696

**Terminological Logic IV**

Decidable Reasoning in Terminological Knowledge Representation Systems

Martin Buchheit, Francesco M. Donini

and Andrea Schaerf..704

The Equivalence of Model-Theoretic and Structural Subsumption in Description Logics

Robert Dionne, Eric Mays and Frank J. Oles .. .710

**Theory of Action I**

Reasoning About Persistence: A Theory of Actions

Yan Zhang and Norman Y. Foo..718

Soundness and Completeness Theorems for Three Formalizations of Action

G. Neelakantan Kartha ..724

**Theory of Action II**

Deriving Properties of Belief Update from Theories of Action (II)

Alvaro del Val and Yoav Shoham ..732

The range of applicability of nonmonotonic logics for the inertia problem

Erik Sandewall..738

INVITED SPEAKERS

AI Adventures Worth Writing Home About

Miroslav Benda, Boeing Commercial Aircraft.. 747

Social Knowledge and Social Action: Heterogeneity in Practice

Les Gasser, University of Southern California .. 751

Artificial Thought and Emergent Mind

Ivan M. Havel, Center for Theoretical Study..758

Vision Based Robot Behavior: Tools and Testbeds for Real-World AI Research

Hirochika Inoue, University of Tokyo ..767

Susan J. Lederman, Queens University ..774

Toward Flexible Intelligence: MITI's New Program of Real World Computing

Nohuyuki Otsu, Electrotechnical Laboratory..786

Consenting Agents: Negotiation Mechanisms for Multi-Agent Systems

Jeffrey Rosenschein, Hebrew University..792

Conceptual Design and Artificial Intelligence

Devika Subramanian, Cornell University..800

Johan van Benthem, University of Amsterdam .. .810

**AWARDS**

Computers and Thought Award Challenges of Massive Parallelism

Hiroaki Kitano, NEC Corporation andCarnegie Mellon University ..813

INDEX ..835

DISCLAIMER: Please note that IJCAI Organization is the sole copyright owner of all materials published in the Proceedings of its conferences. All rights are reserved. No part of any IJCAI conference Proceedings may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher, which is also the IJCAI Organization. Contact information for obtaining written permission can be found here.