Lecture Notes in Computer Science 5956 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Sebastian Link Henri Prade (Eds.) Foundations of Information and Knowledge Systems 6th International Symposium, FoIKS 2010 Sofia, Bulgaria, February 15-19, 2010 Proceedings 1 3 VolumeEditors SebastianLink SchoolofInformationManagement TheVictoriaUniversityofWellington Wellington,NewZealand E-mail:[email protected] HenriPrade InstitutdeRechercheenInformatiquedeToulouse CNRS UniversityofToulouseIII Toulouse,France E-mail:[email protected] LibraryofCongressControlNumber:2010920282 CRSubjectClassification(1998):G.2,F.4.1,I.2.3,I.2.4,D.3 LNCSSublibrary:SL3–InformationSystemsandApplication,incl.Internet/Web andHCI ISSN 0302-9743 ISBN-10 3-642-11828-3SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-11828-9SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2010 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12990597 06/3180 543210 Preface Thisvolumecontainsthearticlespresentedatthe 6thInternationalSymposium onFoundationsofInformationandKnowledgeSystems(FoIKS2010)whichwas held in Sofia, Bulgaria during February 15–19,2010. The FoIKS symposia provide a biennial forum for presenting and discussing theoreticalandappliedresearchoninformationandknowledgesystems.Thegoal is to bring together researchers with an interest in this subject, share research experiences, promote collaboration and identify new issues and directions for future research. FoIKS 2010 solicited original contributions dealing with any foundational aspects of information and knowledge systems. This included submissions that apply ideas, theories or methods from specific disciplines to information and knowledgesystems.Examplesofsuchdisciplinesarediscretemathematics,logic and algebra, model theory, information theory, complexity theory, algorithmics and computation, statistics, and optimization. Previous FoIKS symposia were held in Pisa (Italy) in 2008, Budapest (Hungary) in 2006, Vienna (Austria) in 2004, Schloss Salzau near Kiel (Germany)in2002,andBurg/SpreewaldnearBerlin(Germany)in2000.FoIKS took up the tradition of the conference series Mathematical Fundamentals of Database Systems (MFDBS), which initiated East–West collaboration in the field of database theory. Former MFDBS conferences were held in Rostock (Germany) in 1991, Visegrad (Hungary) in 1989, and Dresden (Germany) in 1987. The FoIKS symposia are a forum for intense discussions. Speakers are given sufficient time to present their ideas and results within the larger context of their research.Furthermore,participants are askedin advance to prepare a first response to a contribution of another author. Suggested topics for FoIKS 2010 included, but were not limited to: – Database design: formal models, dependencies and independencies – Dynamics of information: models of transactions, concurrency control, updates, consistency preservation, belief revision – Informationfusion:heterogeneity,views,schemadominance,multiplesource information merging, reasoning under inconsistency – Integrity and constraint management: verification, validation, consistent query answering, information cleaning – Intelligent agents: multi-agent systems, autonomous agents, foundations of software agents, cooperative agents, formal models of interactions, logical models of emotions – Knowledgediscoveryandinformationretrieval:machinelearning,datamin- ing, formal concept analysis and association rules, text mining, information extraction VI Preface – Knowledge representation, reasoning and planning: non-monotonic formalisms,probabilisticandnon-probabilisticmodelsofuncertainty,graph- ical models and independence, similarity-based reasoning, preference mod- eling and handling, argumentation systems – LogicsindatabasesandAI:classicalandnon-classicallogics,logicprogram- ming, description logic, spatial and temporal logics, probability logic, fuzzy logic – Mathematicalfoundations:discretestructuresandalgorithms,graphs,gram- mars,automata,abstractmachines,finite modeltheory,informationtheory, coding theory, complexity theory, randomness – Securityininformationandknowledgesystems:identitytheft,privacy,trust, intrusion detection, access control, inference control, secure Web services, secure Semantic Web, risk management – Semi-structured data and XML: data modeling, data processing, data com- pression, data exchange – Social computing: collective intelligence and self-organizing knowledge, col- laborative filtering, computational social choice, Boolean games, coalition formation, reputation systems – TheSemanticWebandknowledgemanagement:languages,ontologies,agents, adaption, intelligent algorithms – The WWW: models of Web databases, Web dynamics, Web services, Web transactions and negotiations The call for papers resulted in the submission of 50 full articles. A rigorous refereeing process saw each submitted article referred by at least three inter- national experts. The 13 articles judged best by the Program Committee were accepted for long presentation. In addition, six articles were accepted for short presentation. This volume contains versions of these articles that have been re- visedbytheirauthorsaccordingto thecommentsprovidedinthe reviews.After theconference,authorsofafewselectedarticleswereaskedtoprepareextended versions of their articles for publication in a special issue of the journal Annals of Mathematics and Artificial Intelligence. We wouldliketo thankallauthorswho submittedarticlesandallconference participants for the fruitful discussions. We are grateful to Philippe Balbiani, Jan Paredaens, and Dimiter Vakarelov, who presented invited talks at the con- ference. We would also like to thank the members of the Program Committee andexternalrefereesfortheirtimelyexpertiseincarefullyreviewingthesubmis- sions. A special thank-you goes to Markus Kirchberg for his outstanding work asFoIKSPublicityChair.Finally,wewishtoexpressourappreciationtoStefan DodunekovandhisteamforbeingourhostsandforthewonderfuldaysinSofia. February 2010 Sebastian Link Henri Prade Conference Organization Program Committee Chairs Sebastian Link Victoria University of Wellington, New Zealand Henri Prade Universit´e de Toulouse, France Program Committee Leila Amgoud University of Toulouse, France Lyublena Antova Cornell University, USA Marcelo Arenas PontificiaUniversidadCato´licadeChile,Chile Salem Benferhat University of Lens, France Jonathan Ben-Naim University of Toulouse, France Leopoldo Bertossi Carleton University, Canada Philippe Besnard University of Toulouse, France Joachim Biskup University of Dortmund, Germany Piero A. Bonatti University of Naples “Federico II”, Italy Gerhard Brewka University of Leipzig, Germany Balder ten Cate INRIA, France Jan Chomicki University at Buffalo, USA Samir Chopra City University of New York, USA Marina De Vos University of Bath, UK Michael I. Dekhtyar Tver State University, Russia James P. Delgrande Simon Fraser University, Canada Ju¨rgen Dix Clausthal University of Technology, Germany Stefan Dodunekov Bulgarian Academy of Sciences, Bulgaria Thomas Eiter Vienna University of Technology, Austria Ronald Fagin IBM Almaden Research Center, San Jose, USA Victor Felea “Al.I. Cuza” University of Iasi, Romania Flavio Ferrarotti University of Santiago de Chile and Yahoo! Research Latin America, Chile Floris Geerts The University of Edinburgh, UK Lluis Godo Artificial Intelligence Research Institute (IIIA - CSIC), Spain Edward Hermann Haeusler Pontif´ıcia Universidade Cat´olica, Brazil Joe Halpern Cornell University, USA Sven Hartmann Clausthal University of Technology, Germany Stephen J. Hegner Ume˚a University, Sweden VIII Conference Organization Andreas Herzig University of Toulouse, France Eyke Hu¨llermeier University of Marburg, Germany Anthony Hunter University College London, UK Yasunori Ishihara Osaka University, Japan Ulrich Junker ILOG, France Gyula O.H. Katona Alfr´ed R´enyi Institute, Hungarian Academy of Sciences, Hungary Gabriele Kern-Isberner University of Dortmund, Germany Hans-Joachim Klein University of Kiel, Germany Henning Koehler The University of Queensland, Australia Phokion G. Kolaitis Universityof California,Santa Cruz andIBM Almaden Research Center, USA S´ebastien Konieczny University of Lens, France Gerhard Lakemeyer RWTH Aachen University, Germany J´erˆome Lang University of Paris 9, France Mark Levene Birkbeck University of London, UK Thomas Lukasiewicz University of Oxford, UK Sebastian Maneth NICTA and University of New South Wales, Australia Pierre Marquis University of Artois, France Carlo Meghini Institute of Information Science and Technologies, Italy Leora Morgenstern New York University, USA Wilfred S.H. Ng Hong Kong University of Science and Technology, Hong Kong Juliana Peneva New BulgarianUniversity, Bulgaria Patrice Perny University of Paris 6, France Attila Sali Alfr´edR´enyiInstitute,HungarianAcademyof Sciences, Hungary Vladimir Sazonov University of Liverpool, UK Francesco Scarcello Universita’ degli Studi della Calabria, Italy Torsten Schaub University of Potsdam, Germany Klaus-Dieter Schewe Information Science Research Centre, New Zealand Karl Schlechta Universit´e de Provence, France Dietmar Seipel University of Wu¨rzburg, Germany Guillermo R. Simari Universidad Nacional del Sur, Argentina Margarita Spiridonova Bulgarian Academy of Sciences, Bulgaria Nicolas Spyratos University of Paris-South, France Letizia Tanca Politecnico di Milano, Italy Bernhard Thalheim University of Kiel, Germany Miroslaw Truszczynski University of Kentucky, USA Jos´e Mar´ıa Turull-Torres Massey University Wellington, New Zealand Conference Organization IX Jan Van den Bussche Universiteit Hasselt, Belgium Wiebe van der Hoek University of Liverpool, UK Dirk Van Gucht Indiana University, USA Victor Vianu University of California San Diego, USA Millist Vincent University of South Australia, Australia Irina B. Virbitskaite Russian Academy of Sciences, Russia Evgenii E. Vityaev Russian Academy of Sciences, Russia Peter Vojtas Charles University, Czech Republic Jef Wijsen University of Mons-Hainaut, Belgium Mary-Anne Williams University of Technology, Sydney, Australia Masatoshi Yoshikawa Kyoto University, Japan External Referees Loredana Afanasiev UniversiteitvanAmsterdam,TheNetherlands Foto Afrati National Technical University of Athens, Greece Diego Arroyuelo Yahoo! Research Latin America, Chile Pablo Barcelo University of Chile, Chile Nils Bulling Clausthal University of Technology, Germany Michael Fink Vienna University of Technology, Austria Olivier Gauwin INRIA, France Rita Hartel University of Paderborn, Germany Thomas Krennwallner Vienna University of Technology, Austria Aurelien Lemay University of Lille, France J¨org Pu¨hrer Vienna University of Technology, Austria Luigi Sauro University of Naples “Federico II”, Italy Qing Wang University of Otago, New Zealand Marco Zaffalon DalleMolleInstituteforArtificialIntelligence, Switzerland Local Arrangements Chair Stefan Dodunekov Bulgarian Academy of Sciences, Bulgaria Publicity Chair Markus Kirchberg Institute for Infocomm Research, A*STAR, Singapore Table of Contents Invited Talks Tools and Techniques in Qualitative Reasoning about Space........... 1 Philippe Balbiani A Simple but Formal Semantics for XML Manipulation Languages ..... 3 Jan Paredaens and Jan Hidders Algorithmic Definability and Completeness in Modal Logic (Extended Abstract) ............................................. 6 Dimiter Vakarelov Regular Articles A Probabilistic Temporal Logic That Can Model Reasoning about Evidence........................................................ 9 Dragan Doder, Zoran Markovi´c, Zoran Ognjanovi´c, Aleksandar Perovi´c, and Miodrag Raˇskovi´c An Algorithm for Generating Nash Stable Coalition Structures in Hedonic Games.................................................. 25 Helena Kein¨anen Conjunctive Queries with Constraints: Homomorphism, Containment and Rewriting ................................................... 40 Ali Kiani and Nematollaah Shiri Enhancing Dung’s Preferred Semantics ............................. 58 Zhihu Zhang and Zuoquan Lin On the Distance of Databases ..................................... 76 Gyula O.H. Katona, Anita Keszler, and Attila Sali On the Existence of Armstrong Data Trees for XML Functional Dependencies.................................................... 94 Sven Hartmann, Henning K¨ohler, and Thu Trinh Polymorphism in Datalog and Inheritance in a Metamodel ............ 114 Paolo Atzeni, Giorgio Gianforme, and Daniele Toti Possibilistic Semantics for Logic Programs with Ordered Disjunction ... 133 Roberto Confalonieri, Juan Carlos Nieves, Mauricio Osorio, and Javier Va´zquez-Salceda