IJCAI 93 VOL 1

Proceedings of the

Thirteenth International Joint Conference

on Artificial Intelligence

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

Critical Reasoning

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

Cooperation between Direct Method and Translation Method in Non Classical Logics: Some Results in Prepositional S5

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

Difference Unification

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

A Class Library Implementation of a Principled Open Architecture Knowledge Representation Server with Plug-in Data Types

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

Notes on Formalizing Context

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

Average-case analysis of a search algorithm for estimating prior and posterior probabilities in Bayesian networks with extreme probabilities

David Poole...............................606

On the Hardness of Approximate Reasoning Dan Roth.................................613

Reasoning Under Uncertainty II

Belief revision and updates in numerical formalisms� An overview, with new results for the possibilistic framework

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

Terminological 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

The Intelligent Hand: An Experimental Approach to Human Object Recognition and Implications for Robotic Design

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

The Logic of Cognitive Action

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