CLA 2011 Proceedings of the Eighth International Conference on Concept Lattices and Their Applications CLA Conference Series http://cla.inf.upol.cz INRIA Nancy – Grand Est and LORIA, France The Eighth International Conference on Concept Lattices and Their Applications CLA 2011 Nancy, France October 17–20, 2011 Edited by Amedeo Napoli Vilem Vychodil CLA 2011, October 17–20, 2011, Nancy, France. Copyright c 2011 by paper authors. Copying permitted only for private and academic purposes. This volume is published and copyrighted by its editors. Technical Editors: Jan Outrata, jan.outrata@upol.cz Vilem Vychodil, vychodil@acm.org Page count: xii+419 Impression: 100 Edition: 1st First published: 2011 Printed version published by INRIA Nancy – Grand Est and LORIA, France ISBN 978–2–905267–78–8 Organization CLA 2011 was organized by the INRIA Nancy – Grand Est and LORIA Steering Committee Radim Belohlavek Palacky University, Olomouc, Czech Republic Sadok Ben Yahia Faculté des Sciences de Tunis, Tunisia Jean Diatta Université de la Réunion, France Peter Eklund University of Wollongong, Australia Sergei O. Kuznetsov State University HSE, Moscow, Russia Michel Liquière LIRMM, Montpellier, France Engelbert Mephu Nguifo LIMOS, Clermont-Ferrand, France Program Chairs Amedeo Napoli INRIA NGE/LORIA, Nancy, France Vilem Vychodil Palacky University, Olomouc, Czech Republic Program Committee Jaume Baixeries Polytechnical University of Catalonia Jose Balcazar University of Cantabria and UPC Barcelona, Spain Radim Belohlavek Palacky University, Olomouc, Czech Republic Karell Bertet University of La Rochelle, France François Brucker University of Marseille, France Claudio Carpineto Fondazione Ugo Bordoni, Roma, Italy Jean Diatta Université de la Réunion, France Felix Distel TU Dresden, Germany Florent Domenach University of Nicosia, Cyprus Mireille Ducassé IRISA Rennes, France Alain Gély University of Metz, France Cynthia Vera Glodeanu TU Dresden, Germany Marianne Huchard LIRMM, Montpellier, France Vassilis G. Kaburlasos TEI, Kavala, Greece Stanislav Krajci University of P.J. Safarik, Kosice, Slovakia Sergei O. Kuznetsov State University HSE, Moscow, Russia Léonard Kwuida Zurich University of Applied Sciences, Switzerland Mondher Maddouri URPAH, University of Gafsa, Tunisie Rokia Missaoui UQO, Gatineau, Canada Lhouari Nourine LIMOS, University of Clermont Ferrand, France Sergei Obiedkov State University HSE, Moscow, Russia Manuel Ojeda-Aciego University of Malaga, Spain Jan Outrata Palacky University, Olomouc, Czech Republic Pascal Poncelet LIRMM, Montpellier, France Uta Priss Napier University, Edinburgh, United Kingdom Olivier Raynaud LIMOS, University of Clermont Ferrand, France Camille Roth EHESS, Paris, France Stefan Schmidt TU Dresden, Germany Baris Sertkaya SAP Research Center, Dresden, Germany Henry Soldano Université of Paris 13, France Gerd Stumme University of Kassel, Germany Petko Valtchev Université du Québec à Montréal, Canada Additional Reviewers Mikhail Babin State University HSE, Moscow, Russia Daniel Borchmann TU Dresden, Germany Peggy Cellier IRISA Rennes, France Sebastien Ferre IRISA Rennes, France Nathalie Girard University of La Rochelle, France Alice Hermann IRISA Rennes, France Mehdi Kaytoue INRIA NGE/LORIA, Nancy, France Petr Krajca Palacky University, Olomouc, Czech Republic Christian Meschke TU Dresden, Germany Petr Osicka Palacky University, Olomouc, Czech Republic Violaine Prince LIRMM, Montpellier, France Chedy Raissy INRIA NGE/LORIA, Nancy, France Yoan Renaud LIRIS, Lyon, France Heiko Reppe TU Dresden, Germany Lucie Urbanova Palacky University, Olomouc, Czech Republic Jean Villerd ENSAIA, Nancy, France Organization Committee Mehdi Kaytoue (chair) INRIA NGE/LORIA, Nancy, France Elias Egho INRIA NGE/LORIA, Nancy, France Felipe Melo INRIA NGE/LORIA, Nancy, France Amedeo Napoli INRIA NGE/LORIA, Nancy, France Chedy Raı̈ssi INRIA NGE/LORIA, Nancy, France Jean Villerd ENSAIA, Nancy, France Table of Contents Preface Invited Contributions Mathematical Morphology, Lattices, and Formal Concept Analysis . . . . . . 1 Isabelle Bloch Random concept lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Richard Emilion Galois and his Connections—A retrospective on the 200th birthday of Evariste Galois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Marcel Erné Canonical extensions, Duality theory, and Formal Concept Analysis . . . . . 7 Mai Gehrke Galois connections and residuation: origins and developments II . . . . . . . . . 9 Bruno Leclerc Galois connections and residuation: origins and developments I . . . . . . . . . 11 Bernard Monjardet Metrics, Betweeness Relations, and Entropies on Lattices and Applications 13 Dan Simovici Long Papers Vertical decomposition of a lattice using clique separators . . . . . . . . . . . . . . 15 Anne Berry, Romain Pogorelcnik and Alain Sigayret Building up Shared Knowledge with Logical Information Systems . . . . . . . 31 Mireille Ducasse, Sebastien Ferre and Peggy Cellier Comparing performance of algorithms for generating the Duquenne- Guigues basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Konstantin Bazhanov and Sergei Obiedkov Filtering Machine Translation Results with Automatically Constructed Concept Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Yılmaz Kılıçaslan and Edip Serdar Güner Concept lattices in fuzzy relation equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Juan Carlos Dı́az and Jesús Medina-Moreno Adaptation knowledge discovery for cooking using closed itemset extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Emmanuelle Gaillard, Jean Lieber and Emmanuel Nauer Fast Computation of Proper Premises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Uwe Ryssel, Felix Distel and Daniel Borchmann Block relations in fuzzy setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Jan Konecny and Michal Krupka A closure algorithm using a recursive decomposition of the set of Moore co-families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Pierre Colomb, Alexis Irlande, Olivier Raynaud and Yoan Renaud Iterative Software Design of Computer Games through FCA . . . . . . . . . . . . 143 David Llansó, Marco Antonio Gómez-Martı́n, Pedro Pablo Gomez-Martin and Pedro Antonio González-Calero Fuzzy-valued Triadic Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Cynthia Vera Glodeanu Mining bicluster of similar values with triadic concept analysis . . . . . . . . . . 175 Mehdi Kaytoue, Sergei Kuznetsov, Juraj Macko, Wagner Meira and Amedeo Napoli Fast Mining of Iceberg Lattices: A Modular Approach Using Generators . 191 Laszlo Szathmary, Petko Valtchev, Amedeo Napoli, Robert Godin, Alix Boc and Vladimir Makarenkov Boolean factors as a means of clustering of interestingness measures of association rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Radim Belohlavek, Dhouha Grissa, Sylvie Guillaume, Engelbert Mephu Nguifo and Jan Outrata Combining Formal Concept Analysis and Translation to Assign Frames and Thematic Grids to French Verbs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Ingrid Falk and Claire Gardent Generation algorithm of a concept lattice with limited access to objects . . 239 Christophe Demko and Karell Bertet Homogeneity and Stability in Conceptual Analysis . . . . . . . . . . . . . . . . . . . . 251 Paula Brito and Géraldine Polaillon A lattice-based query system for assessing the quality of hydro-ecosystems 265 Agnés Braud, Cristina Nica, Corinne Grac and Florence Le Ber The word problem in semiconcept algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 Philippe Balbiani Looking for analogical proportions in a formal concept analysis setting . . . 295 Laurent Miclet, Henri Prade and David Guennec Random extents and random closure systems . . . . . . . . . . . . . . . . . . . . . . . . . 309 Bernhard Ganter Extracting Decision Trees From Interval Pattern Concept Lattices . . . . . . 319 Zainab Assaghir, Mehdi Kaytoue, Wagner Meira and Jean Villerd A New Formal Context for Symmetric Dependencies . . . . . . . . . . . . . . . . . . 333 Jaume Baixeries Cheating to achieve Formal Concept Analysis over a large formal context 349 Vı́ctor Codocedo, Carla Taramasco and Hernán Astudillo A FCA-based analysis of sequential care trajectories . . . . . . . . . . . . . . . . . . . 363 Elias Egho, Nicolas Jay, Chedy Raissi and Amedeo Napoli Querying Relational Concept Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 Zeina Azmeh, Mohamed Hacéne-Rouane, Marianne Huchard, Amedeo Napoli and Petko Valtchev Links between modular decomposition of concept lattice and bimodular decomposition of a context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 Alain Gély Short Papers Abduction in Description Logics using Formal Concept Analysis and Mathematical Morphology: application to image interpretation . . . . . . . . . 405 Jamal Atif, Céline Hudelot and Isabelle Bloch A local discretization of continuous data for lattices: Technical aspects . . . 409 Nathalie Girard, Karell Bertet and Muriel Visani Formal Concept Analysis on Graphics Hardware . . . . . . . . . . . . . . . . . . . . . . 413 W. B. Langdon, Shin Yoo, and Mark Harman Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 Preface The Eighth International Conference “Concept Lattices and Applications (CLA 2011)” is held in Nancy, France from October 17th until October 20th 2011. CLA 2011 is aimed at providing to everyone interested in Formal Concept Analysis and more generally in Concept Lattices or Galois Lattices, students, professors, researchers and engineers, a global and an advanced view of some of the last research trends and applications in this field. As the diversity of the selected pa- pers shows, there is a wide range of theoretical and practical research directions, around data and knowledge processing, e.g. data mining, knowledge discovery, knowledge representation, reasoning, pattern recognition, together with logic, algebra and lattice theory. This volume includes the selected papers and the abstracts of the 7 invited talks. This year there were initially 47 submissions from which 27 papers were accepted as full papers and 3 papers as posters. We would like to thank here the authors for their work, often of very good quality, the members of the program committee and the external reviewers who did a great job as this can be seen in their reviews. This is one witnesses of the growing quality and importance of CLA, highlightening its leading position in the field. Next, this year is a little bit special while the bicentennial of the birth of Evariste Galois (1811–1832) is celebrated, particularly in France. Evariste Galois has something to do with Concept Lattices as they are based on a so-called “Galois connection”. Among the invited speakers, some of them will discuss of these fundamental aspects of Concept Lattices. Moreover, this is also the occasion of thanking the seven invited speakers who, at least we hope that, will meet the wishes of the attendees. We would like to thank firstly our first sponsors, namely the CNRS GDR I3 and Institut National Polytechnique de Lorraine (INPL). Then we would like to thank the steering committee of CLA for giving us the occasion of leading this edition of CLA, the conference participants for their participation and support, and people in charge of the organization, especially Anne-Lise Charbonnier, Nicolas Alcaraz and Mehdi Kaytoue, whose help was very precious in many occasions. Finally, we also do not forget that the conference was managed (quite easily) with the Easychair system, paper submission, selection, and reviewing, and that Jan Outrata has offered his files for preparing the proceedings. October 2011 Amedeo Napoli Vilem Vychodil Program Chairs of CLA 2011