KR'94 - Program and Registration Information
Fourth International Conference on
Principles of Knowledge Representation and Reasoning
Gustav Stresemann Institut
Bonn, Germany
May 24-27, 1994
With support from the Gesellschaft fuer Informatik, the Austrian Society for
Artificial Intelligence, the Canadian Society for Computational Studies of In-
telligence, and the European Coordinating Committee on Artificial Intelli-
gence; in cooperation with the American Association for Artificial Intelli-
gence and the International Joint Conferences on Artificial Intelligence, Inc.
ABOUT KR'94
KR'94, the first in its series to be held in Europe, provides a more intimate
setting than that of general AI conferences for researchers studying explicit
representations of knowledge manipulated by inference algorithms, which pro-
vide an important foundation for much work in Artificial Intelligence from na-
tural language to expert systems.
The conference emphasizes both the theoretical principles of knowledge
representation and reasoning and the relationships between these principles
and their embodiments in working systems. Presented papers, invited talks,
panels, and audience discussion will address the following important ques-
tions:
(1) What issues arise in representing and using knowledge about real problems,
and how can they be addressed?
(2) What are the theoretical principles in knowledge representation and rea-
soning?
(3) How can these principles be embodied in implemented knowledge representa-
tion systems, and what practical tradeoffs arise?
(4) How do these approaches to problems relate to corresponding approaches in
other parts of AI (natural language, robotics, etc.) or in other fields
(psychology, philosophy, logic, economics, cognitive science, computer
science, management, engineering, etc.)
LOCATION
The KR'94 Conference will be held at the Gustav Stresemann Institut (GSI) in
Bonn, Germany. The GSI is located just south of the downtown area within easy
reach of the main train station. Major airports are Cologne/Bonn (with regular
bus service to downtown Bonn), Duesseldorf (1 hour by train) and Frankfurt (2
hours by train). Registered participants will receive detailed information
about the GSI and how to get there.
CORRESPONDENCE
KR'94 information:
E-mail: ····@cs.uni-bonn.de
Regular KR'94
Mail: Institute of Computer Science III
University of Bonn
Roemerstr. 164
D-53117 Bonn
Germany
Phone: +49-228-550-281
Fax: +49-228-550-382
Automatic E-mail: If you send a message to ·········@cs.uni-bonn.de, a reply
containing a copy of this announcement will be sent to the address in the
sender field (without being read by a person).
ORGANIZERS
Conference Chair:
Erik Sandewall, Department of Computer and Information Science,
Linkoeping University, Sweden
Program Chairs:
Jon Doyle, Laboratory for Computer Science, MIT, USA
Piero Torasso, Dipartimento di Informatica, Universita' di Torino, Italy
Local Arrangements Chair:
Gerhard Lakemeyer, Institute of Computer Science III, University of Bonn,
Germany
Publicity Chair:
Werner Horn, Austrian Research Institute for Artificial Intelligence,
Austria
PROGRAM COMMITTEE
Giuseppe Attardi (U. Pisa, Italy),
Franz Baader (DFKI, Germany),
Fahiem Bacchus (U. Waterloo, Canada),
Philippe Besnard (IRISA, France),
Piero Bonissone (GE, USA),
Craig Boutilier (UBC, Canada),
Ron Brachman (AT&T, USA)
Maurice Bruynooghe (KUL, Belgium),
Anthony Cohn (U. Leeds, UK),
Ernest Davis (NYU, USA),
Rina Dechter (UC Irvine, USA),
Johan de Kleer (Xerox, USA),
Oskar Dressler (Siemens, Germany),
Jennifer Elgot-Drapkin (Arizona State U., USA),
Richard Fikes (Stanford U., USA),
Alan Frisch (U. York, UK),
Hector Geffner (Simon Bolivar U., Venezuela),
Georg Gottlob (TU Wien, Austria),
Pat Hayes (U. Illinois, USA),
Hirofumi Katsuno (NTT, Japan),
Henry Kautz (AT&T, USA),
Sarit Kraus (Bar-Ilan U., Israel),
Maurizio Lenzerini (U. Rome, Italy),
Vladimir Lifschitz (U. Texas, USA),
David Makinson (Unesco, France),
Joao Martins (IST, Portugal)
David McAllester (MIT, USA),
John-Jules Meyer (U. Amsterdam, Netherlands),
Katharina Morik (U. Dortmund, Germany),
Johanna Moore (U. Pittsburgh, USA),
Hideyuki Nakashima (ETL, Japan),
Bernhard Nebel (U Ulm, Germany),
Hans Juergen Ohlbach (Max Planck Institut, Germany),
Lin Padgham (Linkoeping U., Sweden),
Peter Patel-Schneider (AT&T, USA),
Ramesh Patil (USC/ISI, USA),
Raymond Perrault (SRI, USA),
David Poole (UBC, Canada),
Henri Prade (IRIT, France),
Anand Rao (AAII, Australia),
Jeff Rosenschein (Hebrew U., Israel),
Stuart Russell (UC Berkeley, USA),
Len Schubert (U. Rochester, USA)
Marek Sergot (Imperial College, UK),
Lokendra Shastri (ICSI, USA),
Yoav Shoham (Stanford U., USA),
Lynn Stein (MIT, USA),
Devika Subramanian (Cornell U., USA),
William Swartout (USC/ISI, USA),
Austin Tate (AIAI, Edinburgh, UK),
Peter van Beek (U. Alberta, Canada),
Michael Wellman (U. Michigan, USA)
INVITED TALKS
Beyond Ignorance-Based Systems,
W. A. Woods --- Sun Microsystems Laboratories, Inc., USA
The field of artificial intelligence has a long tradition of exploiting the
potential of limited domains. While this is beneficial as a way to get start-
ed and has utility for applications of limited scope, these approaches will
not scale to systems with more open-ended domains of knowledge. Many
"knowledge-based" systems actually derive their success as much from ignorance
as from the knowledge that they contain. That is, they succeed because they
don't know any better. Too great a reliance on a closed-world assumption and
default reasoning in a limited domain can result in a system that is fundamen-
tally limited and cannot be extended beyond its initial domain.
If the field of knowledge-based systems is to move beyond this stage, we need
to develop knowledge representation and reasoning technology that is more
robust in the face of domain extensions. Nonmonotonic reasoning becomes a lia-
bility if the fundamental abilities of a system can be destroyed by the addi-
tion of knowledge from a new domain. This talk will discuss some of the chal-
lenges that we must meet to develop systems that can handle diverse ranges of
knowledge.
Non Standard Theories of Uncertainty in Knowledge Representation and Reasoning
Didier Dubois --- IRIT-CNRS Universite' Paul Sabatier, Toulouse, France
The last 15 years have witnessed a noticeable but scattered research effort
towards a rational theory of plausible reasoning. While Bayesian nets have
recently blossomed in this area, the role of logic and symbolic representa-
tions continue to be prominent. Besides, the monopoly of probability theory
as a tool for modelling uncertainty has been challenged by alternative ap-
proaches such as belief functions and possibility theory. Current efforts
search for a knowledge representation framework that combines the merits of
classical logic and Bayesian probability. The aim of this talk is to try and
provide a perspective view of uncertainty theories in plausible reasoning.
The lecture will touch on the following issues:
- The use of ordering relations in uncertainty modelling and its link to
non-monotonic reasoning.
- The problem of compositionality, and the difference between partial truth
(as in fuzzy logic) and uncertainty.
- Why Bayesian probabilities might be questioned in reasoning tasks that
are not decision-driven.
- The importance of representing generic, exception-tolerant, knowledge as
distinct from uncertain evidence in plausible reasoning tasks.
- The analysis of three forms of belief change: updating, revision, and
focusing and their role in defeasible inference systems.
Knowledge Representation Issues in Integrated Planning and Learning Systems
Jaime Carbonell --- Carnegie Mellon University, USA
Advances in Machine Learning and in non-linear planning systems in Artificial
Intelligence have proceeded somewhat independently of Knowledge Representation
issues. In essence, both fields borrow from KR the very essentials (e.g.
typed FOL, or simple inheritance methods), and then proceed to address other
important issues. However, the increasing sophistication of integrated archi-
tectures such as SOAR. PRODIGY and THEO at CMU (that combine problem solving,
planning and learning) place new demands on their KR infrastructures. These
demands include reasoning about strategic knowledge as well as factual
knowledge, supporting representational shifts in domain knowledge, and meta-
reasoning about the system's own reasoning and learning processes. The
presentation will focus on the PRODIGY architecture and its needs and implica-
tions for KR, especially when these may be in divergence with the primary ac-
tive topics in modern KR research.
PROGRAM
Monday, May 23: Registration and informal get-together, 5:00-10:00 p.m.
____________________________________________________________
Tuesday, May 24:
Plenary Session: Invited Talk
9:00 Beyond Ignorance-Based Systems
William A. Woods (Sun Microsystems Laboratories, Inc., USA)
10:10 Break
Track A: Description Logics I
10:30 A Framework for Part-of Hierarchies in Terminological Logics
Lin Padgham and Patrick Lambrix (Linkoeping U., Sweden)
11:05 A Computational Account for a Description Logic of Time and Action
Alessandro Artale and Enrico Franconi (IRST, Italy)
11:40 Probabilistic Reasoning in Terminological Logics
Manfred Jaeger (Max Plank Institut, Germany)
12:15 Lunch
Track B: Logics of Knowledge and Belief
10:30 Knowledge, Certainty, Belief, and Conditionalisation
Philippe Lamarre and Yoav Shoham (Stanford, USA)
11:05 Belief Ascription, Its Existence and Uniqueness
Ronen I. Brafman (Stanford, USA) and Moshe Tennenholtz
(Technion, Israel)
11:40 Strong Circumscription in Epistemic Logic
Wiebe van der Hoek (Utrecht U., Netherlands), Jan Jaspars and
Elias Thijsse (Tilburg U., Netherlands)
12:15 Lunch
Track A: Description Logics II
1:45 Foundations of a Unified Theory for Class-Based Representation
Formalisms
Diego Calvanese, Maurizio Lenzerini, Daniele Nardi (U. Roma, Italy)
2:20 Making the Difference: A Subtraction Operation for Description Logics
Gunnar Teege (TU Munich, Germany)
2:55 Terminological Cycles and the Propositional Mu-Calculus
Klaus Schild (DFKI, Germany)
3:30 Break
Track B: Planning
1:45 Refinement Search as a Unifying Framework for Analyzing Planning
Algorithms
Subararao Kambhampati (Arizona State U., USA)
2:20 The Complexity of Approximately Optimal Planning
Bart Selman (AT&T, USA)
2:55 Representing Uncertainty in Simple Planners
Robert P. Goldman and Mark S. Boddy (Honeywell, USA)
3:30 Break
Track A: Reasoning I
4:00 Enhancing the Power of a Decidable First-Order Reasoner
Gerhard Lakemeyer and Susanne Meyer (U. Bonn, Germany)
4:35 A Decision Method for Nonmomotonic Reasoning Based on
Autoepistemic Reasoning
Ilkka Niemela (Helsinki U. of Technology, Finland)
5:10 Proofs in Context
Giuseppe Attardi (ICSI, USA) and Maria Simi (U. Pisa, Italy)
5:45 End of session
Track B: Logics of Preference and Utility
4:00 Toward a Logic for Qualitative Decision Theory
Craig Boutilier (U. British Columbia, Canada)
4:35 Specification and Evaluation of Preferences for Planning Under
Uncertainty
Sek-Wah Tan and Judea Pearl (UCLA, USA)
5:10 Risk-Sensitive Planning with Decision Graphs
Sven Koenig and Reid Simmons (CMU, USA)
5:45 End of session
____________________________________________________________
Wednesday, May 25:
Track A: Multiagent Reasoning
9:00 Mutual Belief Revision
Ron van der Meyden (NTT, Japan)
9:35 On Multiagent Autoepistemic Logic - an Extrospective View
Yuejun Jiang (Imperial College, UK)
10:10 Break
Track B: Temporal Reasoning
9:00 An Efficient Method for Managing Disjunctions in Qualitative
Temporal Reasoning
Alfonso Gerevini (IRST, Italy) and Lenhart Schubert (U. Rochester, USA)
9:35 Complexity Results for First-Order Theories of Temporal Constraints
Manolis Koubarakis (Nat. Tech. U. of Athens, Greece)
10:10 Break
Track A: Reasoning about the Physical World
10:30 Reasoning in Logic about Continuous Systems
Benjamin J. Kuipers and Benjamin Shults (U. Texas, USA)
11:05 How Far Can We 'C'? Defining a 'Doughnut' using Connection Alone
N. M. Gotts (U. Leeds, UK)
11:40 Spatial Reasoning with Propositional Logics
Brandon Bennett (U. Leeds, UK)
12:15 Lunch
Track B: Nonmonotonic Reasoning I
10:30 On the Relation Between Default and Modal Consequence Relations
Alexander Bochman (Bar-Ilan U., Israel)
11:05 Preferential Entailments for Circumscriptions
Yves Moinard (IRISA, France)
11:40 Conditional Objects as Nonmonotonic Consequence Relations
Didier Dubois and Henri Prade (U. Paul Sabatier, France)
12:15 Lunch
Track A: Panel
1:45 Exploiting Natural Language for KR&R
Lenhart Schubert (U. Rochester, USA), moderator
4:00 Break
Track B: Complexity of Reasoning
1:45 On the Complexity of Conditional Logics
Nir Friedman (Stanford, USA) and Joseph Y. Halpern (IBM, USA)
2:20 Reasoning with Minimal Models: Efficient Algorithms and Applications
Rachel Ben-Eliyahu (Technion, Israel) and Luigi Palopoli (U.
Calabria, Italy)
2:55 Default Logic as a Query Language
Marco Cadoli (U. Roma, Italy), Thomas Eiter and Georg Gottlob
(TU Wien, Austria)
3:30 Break
5:00 Social event: Banquet Cruise on the Rhine
____________________________________________________________
Thursday, May 26:
Plenary Session: Invited Talk
9:00 Non-Standard Theories of Uncertainty in KR&R
Didier Dubois (U. Paul Sabatier, France)
10:10 Break
Track A: Tractable Reasoning
10:30 Tractable Closed World Reasoning With Updates
Oren Etzioni, Keith Golden, Daniel Weld (U. Washington, USA)
11:05 Tractable Databases: How to Make Propositional Unit Resolution
Complete Through Compilation
Alvaro del Val (Stanford, USA)
11:40 Constraint Tightness Versus Global Consistency
Peter van Beek (U. Alberta, Canada) and Rina Dechter (UC Irvine, USA)
12:15 Lunch
Track B: Theory of Action
10:30 Modalities Over Actions
L. Thorne McCarty (Rutgers U., USA)
11:05 Actions with Indirect Effects
G. Neelakantan Kartha and Vladimir Lifschitz (U. Texas, USA)
11:40 How to Progress a Database (and Why) I. Logical Foundations
Fangzhen Lin and Raymond Reiter (U. Toronto, Canada)
12:15 Lunch
Track A: Description Logics III
1:45 An Application of Terminological Logics to Case-Based Reasoning
Jana Koehler (DFKI, Germany)
2:20 Action Representation and Natural Language Instructions
Barbara Di Eugenio (CMU, USA)
2:55 Experimental Results on Learning in a Description Logic
William W. Cohen (AT&T, USA)
3:30 Break
Track B: Belief Revision
1:45 A Knowledge-Based Framework for Belief Change, Part II: Revision
and Update
Nir Friedman (Stanford, USA) and Joseph Y. Halpern (IBM, USA)
2:20 Transmutations of Knowledge Systems
M.A. Williams (U. Newcastle, Australia)
2:55 REVISE: Extended Logic Programmming System for Revising Knowledge Bases
Carlos Viegas Damasio and Luis Moniz Pereira (U. Nova de Lisboa,
Portugal) and Wolfgang Nejdl (RWTH Aachen, Germany)
3:30 Break
Track A: Knowledge Sharing and Ontology
4:00 An Ontology for Engineering Mathematics
Thomas R. Gruber (Stanford, USA)
4:35 An Ontology of Meta-Level Categories
Nicola Guarino and Massimiliano Carrara (LADSEB, Italy) and
Pierdaniele Giaretta (U. Padova, Italy)
5:10 The Role of Reversible Grammars in Translating Between
Representation Languages
Jeffrey Van Baalen (U. Wyoming, USA) and Richard E. Fikes
(Stanford, USA)
5:45 End of session
Track B: Nonmonotonic Reasoning II
4:00 A General Approach to Specificity in Default Reasoning
James P. Delgrande (Simon Fraser U., Canada) and Torsten H.
Schaub (IRISA, France)
4:35 Defeasible Reasoning with Structured Information
Anthony Hunter (Imperial College, UK)
5:10 On Positive Occurrences of Negation as Failure
Katsumi Inoue (Toyohashi U., Japan) and Chiaki Sakama (ASTEM
Kyoto, Japan)
5:45 End of session
Plenary Session: Panel
8:00 Theory vs Systems vs ...: KR&R Research Methodologies
Lin Padgham (Linkoeping U., Sweden), moderator
____________________________________________________________
Friday, May 27:
Plenary Session: Invited Talk
9:00 Knowledge Representation Issues in Integrated Planning and
Learning Systems
Jaime Carbonell (CMU, USA)
10:10 Break
Track A: Reasoning II
10:30 Generating Tests Using Abduction
Sheila McIlraith (U. Toronto, Canada)
11:05 Means-End Plan Recognition--Towards a Theory of Reactive Recognition
Anand S. Rao (AAII, Australia)
11:40 An Integrated Implementation of Simulative, Uncertain and
Metaphorical Reasoning about Mental States
J. A. Barnden, S. Helmreich, E. Iverson, and G. C. Stein
(New Mexico State U., USA)
12:15 Lunch & End of conference
Track B: Search and Deduction
10:30 GSAT and Dynamic Backtracking
Matthew L. Ginsberg (U. Oregon, USA)
11:05 Easy to be Hard: Difficult Problems for Greedy Algorithms
Kurt Konolige (SRI, USA)
11:40 Directional Resolution: the Davis-Putnam Procedure, Revisited
Rina Dechter and Irina Rish (UC Irvine, USA)
12:15 Lunch & End of conference
PROCEEDINGS
As in previous years, Morgan Kaufmann will be the distributor of the proceed-
ings.
REGISTRATION
Due to space limitations and the success of earlier KR conferences, early
registration is strongly recommended.
FEE SCHEDULE (all fees are in German marks)
Early: Registration and payment received by April 15, 1994
Regular DM 600
Student DM 330
Banquet DM 80 (optional)
Late: Registration or payment received after April 15, 1994
Regular DM 700
Student DM 400
Banquet DM 80 (optional)
The registration fee entitles participants to
+ attend all Invited Lectures, Technical Sessions, and Panels
+ receive all conference documentation including the conference proceedings
+ attend the reception on Monday
+ lunch and dinner during the time of the conference
+ morning and afternoon refreshments
HOUSING
We reserved rooms at the Gustav Stresemann Institut at the following rates
(per night and per person, breakfast included):
single room DM 95
double room DM 75
Rooms will be allocated at a first-come first-served basis. We reserve the
right to change a reservation from double to single room if demand exceeds
supply.
To book a room, please fill in the room reservation section on the registra-
tion form and return it to the conference office. Please note that rooms can-
not be occupied before 5 p.m. on Monday, May 23. However, it is possible to
stay at the GSI over the weekend following the conference (Friday-Sunday).
Rooms need to be prepaid at the time of registration except for extra nights
following the conference.
SOCIAL EVENTS
On Monday evening, 5:00-10:00 p.m., a buffet style dinner will be offered to
set the stage for an informal get-together.
The banquet on Wednesday evening will be a knight's meal at the castle of
Linz. The participants will be taken to Linz by boat. The boat will sail
along the beautiful Rhine valley and also pass by the historically interesting
bridge of Remagen. This was the very last bridge destroyed by the Germans at
the end of World War II.
AIRLINE DISCOUNT FARES (U.S.)
Special discount fares on Delta Airlines have been arranged for KR'94 atten-
dees traveling from the U.S. to Germany. To take advantage of these fares,
you must call Young's Travel/American Express at 1-800-682-0141 between 8 a.m.
and 6 p.m. E.S.T. and identify yourself as a KR'94 attendee. In addition to
the lowest available airfares quoted at the time of ticketing, they offer a 5%
reduction on fares booked on B and Y class. (Some restrictions apply.)
CANCELLATION AND REFUNDS
A written notification of cancellation must be sent to the conference office.
If received before May 2 all fees, except for a cancellation charge of DM 50,
will be refunded. We regret that no refunds can be made for cancellations re-
ceived after May 2.
INSURANCE
The Local Arrangements Committee can accept no liability for personal inju-
ries, or for loss or damage to property belonging to conference participants,
either during or as a result of the conference. Please check the validity of
your personal insurance.
SUPPORT FOR PARTICIPANTS FROM
EAST EUROPEAN COUNTRIES AND COUNTRIES
OF THE FORMER USSR
We have applied for funds to partially subsidize conference participants from
East European countries including countries of the former USSR. Participants
of KR'94 from these countries who wish to apply for such subsidy should send
an e-mail message IMMEDIATELY to ············@cs.uni-bonn.de to obtain further
instructions. If you do not have e-mail access, you should send a fax or write
to
KR'94
Subsidy Program
Institute of Computer Science III
University of Bonn
Roemerstr. 164
D-53117 Bonn
Germany
Fax: +49 228 550 382
Please note that there is no guarantee that any funding will be available.
HOW TO REGISTER
1. Fill in the registration form
2. Payment
Your payment must be for the total amount in German marks.
In Germany: Payment may be made by
- money transfer (see bank account information below)
- cheque, payable to "KR Inc., c/o Gerhard Lakemeyer"
Outside Germany: Payment may be made by
- SWIFT money transfer (see bank account information below),
free of charges to the beneficiary
- Bank Draft or International Money Order,
free of charges to the beneficiary,
payable to "KR Inc., c/o Gerhard Lakemeyer"
Outside Germany, personal and company cheques are not accepted. We regret
that it is not possible to accept Euro Cheques or Credit Cards.
Please, make sure that your own name is clearly legible in order to ensure
that your payment will be correctly registered.
Bank Account Information:
Bank: Volksbank Bonn
Beneficiary: "KR Inc., c/o Gerhard Lakemeyer"
Account No: 1602522012
Bank code: 380 601 86
SWIFT code: DGWGDEDW31860
3. Return the registration form and cheque, draft or money order (if
applicable) to:
Christine Harms
c/o GMD
KR'94
Schloss Birlinghoven
D-53757 Sankt Augustin
Germany
4. In order to receive the early registration discount rate, your registration
and payment must be received by April 15, 1994. Confirmations may not be
mailed for registrations received after April 15.
5. Spaces will be allocated on a first-come first-served basis to the maximum
that the facility can accommodate. Therefore, participants are strongly ad-
vised to register as soon as possible.
6. On-site registration is possible at the late registration fee. In that
case, the only acceptable form of payment is cash.
REGISTRATION FORM
Print out the form below on paper, fill it in and return it with your cheque,
draft or money order (if applicable) to the address below. Electronic mail
registrations are *not* allowed.
Christine Harms
c/o GMD
KR'94
Schloss Birlinghoven
D-53757 Sankt Augustin
Germany
Name _________________________________________________________________
Title ________________________________________________________________
Organization/Affiliation _____________________________________________
______________________________________________________________________
Mailing Address ______________________________________________________
______________________________________________________________________
______________________________________________________________________
Zip/Postal Code _____________________ Country _______________________
Telephone ___________________________________________________________
Fax __________________________________________________________________
Internet E-mail address _____________________________________________
Are you presenting a paper at the conference? Yes ___ No ___
Check here if you have a disability that requires special needs. _______
Please explain _________________________________________________________
________________________________________________________________________
The GSI offers both vegetarian and non-vegetarian meals. Please indicate
any other dietary restrictions (honored to the best of our ability):
________________________________________________________________________
REGISTRATION/BANQUET:
Early Registration Late Registration
Conference fee DM ______________ DM _____________
Student fee DM ______________ DM _____________
Banquet fee
___ Persons x 80 = DM ______________ DM _____________
ACCOMMODATION:
single: ___ nights x 95 DM ______________
double: ___ nights x 75 DM ______________
Please prepay only for nights during the conference (Monday night -
Thursday night). Extra nights should be paid directly to GSI at the
time of the conference.
Please indicate:
Arrival (date, time): ___________________________________________________
Departure (date, time): _________________________________________________
Roommate (for double rooms): ____________________________________________
TOTAL: (Registration + Banquet + Accommodation)
DM ________________
Please indicate your form of payment below:
__ Cheque, draft, or money order (must be included with the registration)
__ Money transfer
Date: ___________________________________________________________________
Signature: ______________________________________________________________
Note: Registrations received by April 15, 1994 will receive the early regis-
tration discount rate. Confirmations may not be mailed for registrations re-
ceived after April 15.