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: kr94@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 kr94-info@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 Subbarao 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 kr94-subsidy@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.