Lecture Notes in Artificial Intelligence 2479 SubseriesofLectureNotesinComputerScience EditedbyJ.G.CarbonellandJ.Siekmann Lecture Notes in Computer Science EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Tokyo Matthias Jarke Jana Koehler Gerhard Lakemeyer (Eds.) KI 2002: Advances in Artificial Intelligence 25thAnnual German Conference onAI, KI 2002 Aachen, Germany, September 16-20, 2002 Proceedings 1 3 SeriesEditors JaimeG.Carbonell,CarnegieMellonUniversity,Pittsburgh,PA,USA Jo¨rgSiekmann,UniversityofSaarland,Saarbru¨cken,Germany VolumeEditors MatthiasJarke GerhardLakemeyer RWTHAachen,InformatikV Ahornstraße55,52056Aachen,Germany E-mail:{jarke,lakemeyer}@cs.rwth-aachen.de JanaKoehler IBMResearchLaboratory,ComputerScienceResearch Säumerstraße4,8803Rüschlikon,Switzerland E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Advancesinartificialintelligence:proceedings/KI2002,25thAnnualGerman ConferenceonAI,KI2002,Aachen,Germany,September16-20,2002. MatthiasJarke...(ed.).-Berlin;Heidelberg;NewYork;Barcelona; HongKong;London;Milan;Paris;Tokyo:Springer,2002 (Lecturenotesincomputerscience;2479:Lecturenotesinartificial intelligence) ISBN3-540-44185-9 CRSubjectClassification(1998):I.2 ISSN0302-9743 ISBN3-540-44185-9Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagBerlinHeidelbergNewYork, amemberofBertelsmannSpringerScience+BusinessMediaGmbH http://www.springer.de ©Springer-VerlagBerlinHeidelberg2002 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyPTP-Berlin,StefanSossnae.K. Printedonacid-freepaper SPIN:10871403 06/3142 543210 Preface This year marks the 25th anniversary of the Annual German Conference on Artificial Intelligence. When starting in 1975 as the German Workshop on AI (GWAI) in Bonn, the meetings were primarily intended as a forum for the Ger- manAIcommunityandthus,overtheyears,alsoreflectedthedevelopmentofAI researchinGermany.Rightfromthebeginning,thegoalofthemeetingshasbeen tobringtogetherAIresearchersworkinginacademiaandindustrytosharetheir research results and interests in the field of artificial intelligence. In 1993, the nameofthemeetingchangedtoitscurrentformAnnual German Conference on Artificial Intelligence, or KI for short. Since KI-94 in Saarbru¨cken presentations have been in English and the proceedings have been published in the Springer LNAISeries.Withthatthemeetinghasbecomeatrulyinternationalevent,and still is in 2002. Thisvolumecontainstheproceedingsofthe25thAnnualGermanConference on Artificial Intelligence.Forthetechnicalprogramwehad58submissionsfrom 17countriesandfromallcontinentsexceptAustralia.Outofthesecontributions slightly less than 30% (20 papers in total) were selected for presentation at the conference and for inclusion in the proceedings. Thecontributionsinthisvolumereflecttherichnessanddiversityofartificial intelligence research. They cover important areas such as multi-agent systems, machine learning, natural language processing, constraint reasoning, knowledge representation, planning, and temporal reasoning. The paper “On the problem of computing small representations of least common subsumers” by Franz Baader and Anni-Yasmin Turhan (Dresden Uni- versity of Technology) stood out for its exceptional quality and the program committee selected it for the Springer Best Paper Award. Congratulations to the authors for their excellent contribution. Inadditiontothetechnicalpapers,thisvolumecontainstheabstractsofthe three invited presentations of the conference: – Elisabeth Andr´e (University of Augsburg): From Simulated Dialogues to In- teractive Performances with Virtual Actors. – MichaelWooldridge(UniversityofLiverpool):Time, Knowledge, and Coop- eration: Alternating-Time Temporal Epistemic Logic and Its Applications. – Dieter Fensel (Vrije Universiteit Amsterdam): Semantic Web Enabled Web Services. VI Preface Lastly, the volume features summaries of the three DFG Priority Programs onagenttechnology,alsopresentedattheconference.These,togetherwiththeir respective speakers, are: – Thomas Malsch (Hamburg-Harburg University of Technology): Socionics – Stefan Kirn (Ilmenau University of Technology): Intelligent Agents and Re- alistic Commercial Application Scenarios – Thomas Christaller (Fraunhofer AIS): Cooperating Teams of Mobile Robots in Dynamic Environments A large number of people were involved in making this conference a success. Asforthetechnicalprogram,wethankallthoseauthorswhosubmittedpapersto the conference and provided the basis from which we could select a high-quality technical program. The members of the program committee and the additional reviewers helped us in this process by providing timely, qualified reviews and participating in the discussion during the paper selection process. Many thanks to all of you! We are very grateful to Gerhard Weiss, who served as the Workshop Chair, and Andreas Becks, who served as the Local Arrangements Chair. The Orga- nizing Committee Members took care of the many important details that are needed to make a conference work and that require so much effort and time. Besides Andreas Becks we thank Frank Dylla, Alexander Ferrein, Gu¨nter Gans, and Irene Wicke. Gu¨nter Gans deserves a special mention for wrestling with the ConfMan system and for formatting this volume. We hope you will enjoy its contents! July 2002 Matthias Jarke, Jana Koehler, and Gerhard Lakemeyer. KI 2002 Conference Organization General Chair Matthias Jarke RWTH Aachen, Germany Program Co-chair Program Co-chair Jana Koehler Gerhard Lakemeyer IBM Zurich Research Laboratory, RWTH Aachen, Switzerland Germany Workshop Chair Organizing Chair Gerhard Weiss Andreas Becks TU Munich, Fraunhofer FIT, Germany Sankt Augustin, Germany Program Committee Elisabeth Andr´e Germany Gerhard Lakemeyer Germany Armin Biere Switzerland Thomas Malsch Germany Susanne Biundo Germany Martin Mueller Canada Ronen Brafman Israel Daniele Nardi Italy Gerhard Brewka Germany Bernhard Nebel Germany Thomas Christaller Germany Wolfgang Nejdl Germany Sven Dickinson Canada Hermann Ney Germany Dieter Fox USA Juergen Sauer Germany Gerhard Friedrich Austria Ute Schmid Germany Ulrich Furbach Germany Dale Schuurmans Canada Holger Hoos Canada Kilian Stoffel Switzerland Ian Horrocks UK Michael Thielscher Germany Stefan Kirn Germany Wolfgang Wahlster Germany Jana Koehler Switzerland Gerhard Weiss Germany Rudolf Kruse Germany Stefan Wrobel Germany Organizing Committee Andreas Becks Fraunhofer FIT, Alexander Ferrein RWTH Aachen Sankt Augustin Gu¨nter Gans RWTH Aachen Frank Dylla RWTH Aachen Irene Wicke RWTH Aachen VIII KI 2002 Conference Organization Additional Referees Steffen Albrecht Axel Großmann Matthias Nickles Cyrille Artho Jesse Hoey Kai Paetow Volker Baier Tamas Horvath Frank Pasemann Peter Baumgartner Geoff Hulten Fuchun Peng Christian Borgelt Luca Iocchi Jochen Renz Ali Ghodsi Boushehri Dietmar Jannach Jussi Rintanen Felix Brandt Jo¨rg Kindermann Danny Roobaert Ralph Breithaupt Alexander Kleiner Michael Rovatsos Michael Brenner Aljoscha Klose Andrew Rowley Diego Calvanese Cody Kwok Marco Schmitt Ingo Dahn Edda Leopold Viktor Schuppan Georg Dorffner David Lowe Klaus Stein Christian Do¨ring Maren Lu¨bcke Frieder Stolzenburg Peter Geibel Thomas Lukasiewicz Heiko Timm Lilia Georgieva Silvia Miksch Thilo Weigel Erich Gra¨del Bernd Mu¨ller KI 2002 Workshops Workshop Chair Gerhard Weiss TU Munich, Germany Foundations of Multiagent Resolving Conflicts between Systems: The Economic Theory Self-interested Agents Perspective (RCSIA 2002) Stefan Kirn Germany Ingo J. Timm Germany Andreas Will Germany Torsten Eymann Germany Modeling Artificial Societies and Workshop on Agent Standards in Hybrid Organizations Theory and Practice (MASHO 2002) (ASTAP 2002) Gabriela Lindemann Germany Michael Berger Germany Catholijn M. Jonker The Netherlands Stefan Kirn Germany Pietro Panzarasa U.K. Jens Nimis Germany Ingo J. Timm Germany Ubbo Visser Germany Workshop on Applications of Workshop on Description Logics (ADL 2002) Cognitive Agents Gu¨nther Go¨rz Germany Michael Thielscher Germany Volker Haarslev Germany Carsten Lutz Germany Ralf Mo¨ller Germany Table of Contents Natural Language LIGHT – A Constraint Language and Compiler System for Typed-Unification Grammars ....................................... 3 Liviu Ciortuz Phrase-Based Statistical Machine Translation.......................... 18 Richard Zens, Franz Josef Och, Hermann Ney Compiling Dynamic Agent Conversations ............................. 33 Pierre Bonzon Machine Learning – Combined Approaches Dynamic Pricing of Information Products Based on Reinforcement Learning: A Yield-Management Approach............................. 51 Michael Schwind, Oliver Wendt Incremental Fuzzy Decision Trees .................................... 67 Marina Guetova, Steffen H¨olldobler, Hans-Peter St¨orr Learning from Multiple Bayesian Networks for the Revision and Refinement of Expert Systems ....................................... 82 Michael Borth Knowledge Representation, Semantic Web, AI Planning On the Problem of Computing Small Representations of Least Common Subsumers ........................................................ 99 Franz Baader, Anni-Yasmin Turhan Approximate Information Filtering on the Semantic Web................ 114 Heiner Stuckenschmidt ParleE: An Adaptive Plan Based Event Appraisal Model of Emotions .... 129 The Duy Bui, Dirk Heylen, Mannes Poel, Anton Nijholt Integrating Function Application in State-Based Planning............... 144 Ute Schmid, Marina Mu¨ller, Fritz Wysotzki Machine Learning – Neural Networks Fast Winner-Takes-All Networks for the Maximum Clique Problem....... 163 Brijnesh J. Jain, Fritz Wysotzki