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

IJCAI-99 Contents Vol 1

AUTOMATED REASONING

THEOREM PROVING

Lemma Generation for Model Elimination by Combining Top-Down and Bottom-Up Inference

Marc Fuchs.. 4

Cooperation of Heterogeneous Provers

Jorg Denzinger and Dirk Fuchs.. 10

UPML: A framework for knowledge system reuse

Dieter Fensel, V Richard Benjamins, Enrico Motta, and Bob Wielinga.. 16

NONMONOTONIC REASONING 1

Complexity results for propositional closed world reasoning and circumscription from tractable knowledge bases

Sylvie Coste-Marquis and Pierre Marquis..24

Credulous Nonmonotonic Inference

Alexander Bochman.. 30

Preferred Arguments are Harder to Compute than Stable Extensions

Yannis Dimopoulos, Bernhard Nebel and Francesca Toni.. 36

NONMONOTONIC REASONING 2

Abducing Priorities to Derive Intended Conclusions

Katsumi Inoue and Chiaki Sakama.. 44

Maximum Entropy and Variable Strength Defaults

Rachel A. Bourne and Simon Parsons.. 50

On the Relationship between Probabilistic Logic and Tl-CMS

P Hansen, B. Jaumard, and A. D. Parreira.. 56

NONMONOTONIC REASONING 3: MODEL CHECKING METHODS

On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases

Robert Baumgartner and Georg Gottlob.. 64

Stable Model Checking Made Easy

Christoph Koch and Nicola Leone.. 70

Model checking for nonmonotonic logics: algorithms and complexity

Riccardo Rosati.. 76

DESCRIPTION LOGICS 1

Reasoning in Expressive Description Logics with Fixpoints based on Automata on Infinite Trees

Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini.. ..84

Reasoning with Concrete Domains

Carsten Lutz..90

Computing Least Common Subsumers in Description Logics with Existential Restrictions

Franz Baader, Ralf Kuster and Ralf Molitor..96

DESCRIPTION LOGICS 2

Multi-dimensional description logics

Frank Wolter and Michael Zakharyaschev..104

On the Relation of Resolution and Tableaux Proof Systems for Description Logics

Ullrich Hustadt and Renate A Schmidt..110

SEMANTICS AND MODELS

Preferential Semantics for Causal Systems

Pavlos Peppas, Maurice Pagnucco, Mikhail Prokopenko, Norman Y. Foo, and Abhaya Nayak..118

Query Evaluation and Progression in AOL Knowledge Bases

Gerhard Lakemeyer and Hector J. Levesque..124

Axiomatic Foundations for Qualitative/Ordinal Decisions with Partial Preferences

Adriana Zapico..132

REAS0NIN6 ABOUT ACTION 1

The Ramification Problem in the Event Calculus

Murray Shanahan..140

Logic-Based Subsumption Architecture

Eyal Amir and Pedrito Maynard-Reid II..147

Automata Theory for Reasoning about Actions

Eugenia Ternovskaia..153

REASONING ABOUT ACTION 2

Projection using Regression and Sensors

Giuseppe De Giacomo and Hector J. Levesque..160

Expressive Reasoning about Action in Nondeterministic Polynomial Time

Thomas Drakengren and Marcus Bjaeland..166

A Logic of Intention

Xiaoping Chen and Guiquan Liu..172

BELIEF REVISION

Considerations on a Similarity-Based Approach to Belief Change

James P Delgrande..180

Postulates for Conditional belief revision

gabricle Kern-Isberrier.. 186

An Inconsistency Tolerant Model for Belief Representation and Belief Revision

Samir Chopra and Rohit Parikh.. 192

RESOURCE-BOUNDED REASONING

Programming Resource-Bounded Deliberative Agents

Michael Fisher and Chiara Ghidini.. 200

Exploiting a Common Property Resource under a Fairness Constraint: a Case Study

Michel Lemaitre, GerardVerfaillie, and Nicolas Bataille.. 206

Maximization of the Average Quality of Anytime Contract Algorithms over a Time Interval

Arnaud Delhay Max Dauchet, Patrick Taillibert, and Philippe Vanheeghe.. 212

CASE-BASED REASONING

CASE-BASED REASONING 1

Demand-Drivcn Discovery of Adaptation Knowledge

David McSherry.. 222

Dynamic Refinement of Feature Weights Using Quantitative Introspective Learning

Zhong Zhang and Qiang Yang.. 228

Remembering to Add: Competence-preserving Case-Addition Policies for Case- Base Maintenance

Jun Zhu and Qiang Yang.. 234

CASE-BASED REASONING 2

PEBM: A Probabilistic Exemplar Based Model

Andre's E M. Rodriguez and Sunil Vadera..242

Toward a Probabilistic Formalization of Case-Based Inference

Eyke Hullermeier.. 248

A Lattice Machine Approach to Automated Casebase Design: Marrying Lazy and Eager Learning

Hui Wang, Werner Dubitzky, Ivo Duntsch, and David Bell.. 254

CHALLENGE PAPERS

CHALLENGE PAPERS 1

Adaptive Web Sites: Conceptual Cluster Mining

Mike Perkowitz and Ortn Etzioni.. 264

An assessment of submissions made to the Predictive Toxicology Evaluation Challenge

A. Srinivasan, R. D. King and D. W. Bristol.. 270

Two Fielded Teams and Two Experts: A RoboCup Challenge Response from the Trenches

Milind Tambe, Gal A. Kaminka, Stacy Marsella, Ion Muslea, and Taylor Raines.. 276

Compiling Knowledge into Decomposable Negation Normal Form

Adnan Darwiche ..284

Using Walk-SAT and RelAT for Cryptographic Key Search

Fabio Massacci.., 290

SAT-Encodings, Search Space Structure, and Local Search Performance

HolgerH. Hoos.. 296

CHALLENGE PAPERS 3: PROPOSITIONAL REASONING AND SEARCH / PLANNING

On the Use of Integer Programming Models in AI Planning

Thomas Vossen, Michael Ball, Amnon Lotem, and Dana Nau.. 304

The LPSAT Engine & its Application to Resource Planning

Steven A, Wolfinan and Daniel S. Weld..310

CHALLENGE PAPERS 4:

BRIDGING PLAN SYNTHESIS PARADIGMS

Unifying SAT-based and Graph-based Planning

Henry Kautz and Bart Selman..318

Temporal Planning with Mutual Exclusion Reasoning

David E. Smith and Daniel S. Weld..326

COGNITIVE MODELING

COGNITIVE MODELING 1

An anthropocentric tool for decision making support

Elisabeth Le Saux, Philippe Lenca, Philippe Picouet, and Jean-Pierre Barthilemy..338

Autonomous Concept Formation

Edwin D. de Jong..344

Reasoning About Actions in Narrative Understanding

Srinivas Narayanan .. 350

COGNITIVE MODELING 2

Using a Cognitive Architecture to Plan Dialogs for the Adaptive Explanation of Proofs

Armin Fiedler..358

Investigating the Emergence of Speech Sounds

Bart de Boer..364

Computer-Aided Tracing of Children's Physics Learning: a Teacher Oriented View

Filippo Neri..370

COGNITIVE MODELING 3: SPATIAL REASONING

Diagrammatic Proofs

Norman Y. Foo, Maurice Pagnucco, and Abhaya C. Nayak.. ..378

Modeling the Basic Meanings of Path Relations

Christian Kray and Anselm Blocker..384

CONSTRAINT SATISFACTION

CONSTRAINT SATISFACTION 1

A Comparison of Structural CSP Decomposition Methods

Georg Gottlob, Nicola Leone, and Francesco Scarcello..394

Solving Strategies for Highly Symmetric CSPs

Pedro Meseguerand Came Tonus.. 400

Extending consistent domains of numeric CSP

Helene Collavizza, Francois Delobel and Michel Rueher.. 406

CONSTRAINT SATISFACTION 2

The Difference All-Difference Makes

Kostas Stergiou and Toby Walsh.. 414

The Symmetric Alldiff Constraint

Jean-Charles Regin.. 420

Branch and Bound with Mini-Bucket Heuristics

Kalev Kask and Rina Dechter.. 426

CONSTRAINT SATISFACTION 3

Improving search using indexing: a study with temporal CSPs

Nikos Mamoulis and Dimitris Papadias.. 436

A new tractable subclass of the rectangle algebra

P Balhiani, J.-F Condotta, and L. Farinas del Cerro.. 442

Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis

Jochen Renz.. 448

CONSTRAINT SATISFACTION 4

Path Consistency on Triangulated Constraint Graphs

Christian Bliek and Djamila Sam-Haroud.. 456

A New Method to Index and Query Sets

Jorg Hoffmann and Jana Koehler.. 462

Constraint Propagation and Value Acquisition: why we should do it Interactively

E. Lamma, P Mello, M. Milano, R Cucchiara, M. Gavanelli, and M. Piccardi.. 468

DISTRIBUTED AI

MULTI-AGENT SYSTEMS 1

Sequential Optimality and Coordination in Multiagent Systems

Craig Boutilier..478

A Protocol-Based Semantics for an Agent Communication Language

Jeremy Pitt and Abe Mamdani..486

Towards Flexible Multi-Agent Decision-Making Under Tune Pressure

Sanguk Noh and Piotr J. Gmytrasiewicz.. ..492

MULTI-AGENT SYSTEMS 2

Risk Control in Multi-agent Coordination by Negotiation with a Trusted Third Party

Shih-Hung Wu and Von-Wun Soo..500

Shopbots and Pricebots

Amy R. Greenwald and Jeffrey O. Kephart..506

Be Patient and Tolerate Imprecision: How Autonomous Agents can Coordinate Effectively

Sudhir K. Rustogi and Munindar P. Singh.. 512

ECONOMIC MODELS 1

Efficiency and Equilibrium in Task Allocation Economies with Hierarchical Dependencies

William E. Walsh and Michael P Wellman..520

Sequential Auctions for the Allocation of Resources with Complementarities

Craig Boutilier, Moists Goldszmidt, and Bikash Sahata..527

Algorithms for Optimizing Leveled Commitment Contracts

Tuomas Sandholm, Sandeep Sikka, and Samphel Norden..535

ECONOMIC MODELS 2: AUCTIONS

An Algorithm for Optimal Winner Determination in Combinatorial Auctions

Tuomas Sandholm..542

Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches

Yuzo Fujishima, Kevin Leyton-Brown, and Yoav Shoham..548

Speeding Up Ascending-Bid Auctions

Yuzo Fujishima, David McAdams, and Yoav Shoham..554

COMPUTER GAME PLAYING

SAME PLAYING 1

Temporal Coherence and Prediction Decay in TDLeaming

Don E Bed and Martin C Smith.. 564

Domain-Dependent Single-Agent Search Enhancements

Andreas Junghanns and Jonathan Schaeffer.. 570

GAME PLAYING 2

Decomposition Search: A Combinatorial Games Approach to Game Tree Search, with Applications to Solving Go Endgames

Martin Midler.. 578

GIB: Steps Toward an Expert-Level Bridge-Playing Program

Matthew L Ginsberg.. 584

KNOWLEDGE-BASED APPLICATIONS

APPLICATIONS 1

An Effective Ship Berthing Algorithm

Andrew Lim.. 594

A Distributed Case-Based Reasoning Application for Engineering Sales Support

Ian Watson and Dan Gardingen.. 600

Knowledge Modeling and Reusability in ExClaim

Liviu Badea.. 606

APPLICATIONS 2

Verifying Integrity Constraints on Web Sites

Mary Ferndndez, Daniela Florescu, Alon Levy, and Dan Suciu.. 614

Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems

Christophe Dousson and Thang Vu Duong.. 620

Integrating Problem-Solving Methods into Cyc

James Stuart Aitken and Dimitrios Sklavakis.. 627

APPLICATIONS 3

Visual Planning: A Practical Approach to Automated Presentation Design

Michelle X Zhou.. 634

A Case Based Approach to the Generation of Musical Expression

Taizan Suzuki, Takenobu Tokunaga, and Hozumi Tarutka.. 642

Using Focus Rules in Requirements Elicitation Dialogues

Renaud Lecoeuche, Dave Robertson, and Catherine Barry.. 649

Author Index.. .. 655

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.