Dagstuhl Seminar 14201
Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications
( May 11 – May 16, 2014 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/14201
Organizers
- Kira V. Adaricheva (Yeshiva University - New York, US)
- Giuseppe F. Italiano (University of Rome "Tor Vergata", IT)
- Hans Kleine Büning (Universität Paderborn, DE)
- György Turan (University of Illinois - Chicago, US)
Contact
- Annette Beyer (for administrative matters)
Schedule
Horn formulas in propositional logic, directed hypergraphs, lattices, closure systems, closure operators, formal concepts, implicational systems and functional dependencies in relational databases are closely related frameworks. They have been studied in mathematics (algebra, combinatorics, logic), computer science (database theory) and artificial intelligence (logic programming, knowledge representation, data mining, formal concept analysis) for a long time.
The study of these frameworks is of fundamental importance for applications involving discrete modeling, reasoning and data analysis. Much of the research has been going on in parallel. Basic problems such as optimization, dynamic and probabilistic aspects, and knowledge acquisition issues are studied from different, but related angles. It is important to get a comprehensive understanding of the results and techniques, and to identify major research challenges.
Optimization problems include finding a minimal equivalent Horn formula, finding a minimal basis for a closure system, finding a minimal cover for functional dependencies, and finding optimal hyperpaths for a directed hypergraph. A comprehensive understanding would involve the different objective functions, subclasses, algorithmic and complexity theoretic aspects.
Dynamic problems are motivated in part by constantly changing knowledge bases, modeled by Horn formulas or directed hypergraphs. For Horn formulas such problems include maintaining consistency using versions of belief revision adapted to the Horn case. Compared to dynamic graph algorithms, dynamic algorithms and data structures for directed hypergraphs are still in their infancy, and there are many challenging problems such as trading off the bounds for queries, updates and space. The need for handling large and changing data sets for knowledge bases in industrial and real-world scenarios also motivates the study of streaming algorithms and other models for handling big data in these contexts. Probabilistic modeling of the evolution of knowledge bases or databases leads to questions about the evolution of random directed hypergraphs, and are also related to the study of phase transition for satisfiability problems.
The analysis of large data sets of attribute values is an important application area of closures and lattices, involving formal concept analysis, and using notions such as frequent and closed item sets, and various associated lattices. General algorithmic questions such as the computation of different representations of the information extracted, and the computation of one representation given another representation have been studied from different angles, and, again, it would be useful to have a comprehensive picture. The data analysis approaches developed for classic data mining problems have the potential to be useful for such major current and near-future enterprises as the Semantic Web, and cross-fertilization along these directions would be important.
The principal objective of this Dagstuhl Seminar is to bring together a critical mass of researchers and to provide a platform for personal contacts and scientific interchange between the different disciplines in an atmosphere that will stimulate collaboration and lead to new partnerships.
The Dagstuhl Seminar 14201 on "Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications" was motivated by the growing recognition in the respective research communities that theoretical research and applications of the areas would benefit from increasing the interaction between these fields of research.
These areas deal with very closely related concepts, but have traditionally been studied within logic, algebra, combinatorics, database theory and artificial intelligence using different techniques and often exploring similar questions with somewhat different emphasis corresponding to the particular area. One of the basic results, the existence of GD-basis, was discovered independently and has different proofs in several areas, such as database theory, the theory of implicational systems and computational learning theory.
The principal objective of the seminar was, as formulated in the seminar announcement, to "bring together a critical mass of researchers and to provide a platform for personal contacts and scientific interchange between the different disciplines in an atmosphere that will stimulate collaboration and lead to new partnerships". In particular, it was hoped that the invitation of a large number of young researchers who would then become familiar with the related research in all the topics discussed, will contribute to the fruitful study of these areas as a more unified discipline in the next generation. Another, related, objective was to help crystallize the main research directions and to disseminate challenging open problems across the different research areas.
Organization of the Seminar and Activities
The seminar brought together 40 participants working in various areas of mathematics and computer science, mostly in algebra, logic, date base theory, artificial intelligence and data mining. In order to establish the common ground for the discussion and use of terminology, the organizers planned five tutorial talks that were scheduled in the first two days of the seminar. There were the following:
- Endre Boros, in Horn Boolean functions
- Leonid Libkin, in Data Bases
- Marcel Wild, in Closure Systems
- Karell Bertet, in Implicational systems and Concept Analysis
- Georgio Ausiello, in Directed Hypergraphs
It is worth mentioning that two of the tutorial presenters, Endre Boros and Georgio Ausiello, are editors-in-chief of two leading journals that often publish papers associated with the topic of the seminar: Applied Discrete Mathematics and Theoretical Computer Science, respectively. Most other talks of the seminar were related to one or more of these big themes, and they were loosely grouped into sections of presentations in order to stimulate the discussion during regular sessions of the seminar, as well as the break time and follow-up informal meetings.
The following grouping gives an approximation to the various topics reflected in the presentations:
- Closures: Duquenne, Wild, Rudolph, Khardon
- Implicational systems: Wild, Adaricheva, Bertet
- Databases: Petit, Libkin
- Directed hypergraphs: Berczi, Nanni, Turßan, Ausiello
- Concept Analysis: Obiedkov, Napoli, Kuznetsov
- Horn formulas: Arias, Kucera, Stasi, Cepek
- Applications : Arias, Balcazar, Nation, Bertet
- Knowledge representation: Khardon, Marquis, Sloan
- Constraints: Tamaki
- Probability: Istrate, Balcazar
- Satisfiability: Kleine Büning, Kullmann, Wild
There was a relatively large group of participants attending the seminar without giving a presentation, many of them formed an active audience that initiated discussions and informal meetings. There were several young participants, who associated themselves with one or two presenters, some of them were co-authors in presented results. In some presentations, the participants touched the rare topics which remarkably found active response from the audience. For example, U. Nanni mentioned application of hypergraphs in the modeling of E-Learning. This seems to open a new connection to the theory Knowledge Spaces that were not previously considered by the organizers as the direction of common interests with the current seminar. S. Tamaki presented the overview of recent developments in constraint satisfiability, the topic of the separate Dagstuhl seminar in 2012, which is also familiar to a number of participants of the current seminar. This gave a nice connection to the earlier collective effort of researchers approaching a common research problem with different tools. On Wednesday most participants took part in the countryside walk, the venue of informal exchange of news and views. It was followed by a dinner and a session on open problems. 17 open problems were presented by the participants, some of them referring to the topics of presentations, several young participants introducing new topics. On Thursday night many informal groups were gathering in the after-dinner discussions. During the work of the whole seminar participants took advantage of open access to the comprehensive library, in particular, checking the collection of books authored by participants of the seminar.
Concluding Remarks
We believe that the seminar was very successful in bringing together a critical mass of researchers from different communities and in providing a platform for personal contacts and scientific interchange between the participants. Due to its highly interdisciplinary nature, in order to stimulate collaborations and to foster possible interactions between different research communities, the organizers decided to schedule talks and discussions not only grouped according to topics but also so as to provide a vivid mix of different research questions and results. In particular, the first two days started with introductory talks (tutorials and surveys) delivered by leading experts, while the rest of the seminar included talks presenting current research and applications as well as problem sessions aimed at identifying core research problems coming from the different fields. Besides presentations, the program offered room for open discussions and informal working groups. As a major outcome, a special issue of the journal Theoretical Computer Science, co-edited by the organizers, will be devoted to the themes of the seminar. We hope this could serve as a reference material for future interdisciplinary research in the field. Schloss Dagstuhl and its staff provided a very convenient and stimulating environment. The seminar participants appreciated the cordial atmosphere which improved mutual understanding and inspiration. The organizers of this seminar wish to thank all those who helped to make the seminar a fruitful research experience.
Creative Commons BY 3.0 Unported license
Kira V. Adaricheva, Giuseppe F. Italiano, Hans Kleine Büning, and György Turan
- Kira V. Adaricheva (Yeshiva University - New York, US) [dblp]
- Marta Arias (UPC - Barcelona, ES) [dblp]
- Giorgio Ausiello (Sapienza University of Rome, IT) [dblp]
- Jose Luis Balcazar (UPC - Barcelona, ES) [dblp]
- Laurent Beaudou (University Blaise Pascal - Aubiere, FR) [dblp]
- Kristof Berczi (Eötvös Lorand University - Budapest, HU) [dblp]
- Karell Bertet (University of La Rochelle, FR) [dblp]
- Endre Boros (Rutgers University - Piscataway, US) [dblp]
- Ondrej Cepek (Charles University - Prague, CZ) [dblp]
- Vincent Duquenne (UPMC - Paris, FR) [dblp]
- Thomas Eiter (TU Wien, AT) [dblp]
- Donatella Firmani (University of Rome "Tor Vergata", IT) [dblp]
- John Franco (University of Cincinnati, US) [dblp]
- Loukas Georgiadis (University of Ioannina, GR) [dblp]
- Amélie Gheerbrant (University of Paris VII, FR) [dblp]
- Gabriel Istrate (West University of Timisoara, RO) [dblp]
- Giuseppe F. Italiano (University of Rome "Tor Vergata", IT) [dblp]
- Roni Khardon (Tufts University - Medford, US) [dblp]
- Hans Kleine Büning (Universität Paderborn, DE) [dblp]
- Petr Kucera (Charles University - Prague, CZ) [dblp]
- Oliver Kullmann (Swansea University, GB) [dblp]
- Sergei O. Kuznetsov (NRU Higher School of Economics - Moscow, RU) [dblp]
- Luigi Laura (Sapienza University of Rome, IT) [dblp]
- Leonid Libkin (University of Edinburgh, GB) [dblp]
- Kazuhisa Makino (University of Tokyo, JP) [dblp]
- Pierre Marquis (CNRS - Lens, FR) [dblp]
- Umberto Nanni (Sapienza University of Rome, IT) [dblp]
- Amedeo Napoli (LORIA & INRIA Nancy, FR) [dblp]
- James B. Nation (University of Hawaii at Manoa, US) [dblp]
- Lhouari Nourine (University Blaise Pascal - Aubiere, FR) [dblp]
- Sergei Obiedkov (NRU Higher School of Economics - Moscow, RU) [dblp]
- Jean-Marc Petit (INSA - Lyon, FR) [dblp]
- Sebastian Rudolph (TU Dresden, DE) [dblp]
- Petr Savicky (Academy of Science - Prague, CZ) [dblp]
- Robert H. Sloan (University of Illinois - Chicago, US) [dblp]
- Ewald Speckenmeyer (Universität Köln, DE) [dblp]
- Despina Stasi (Illinois Inst. of Technology, US) [dblp]
- Suguru Tamaki (Kyoto University, JP) [dblp]
- György Turan (University of Illinois - Chicago, US) [dblp]
- Marcel Wild (Stellenbosch University - Matieland, ZA) [dblp]
Classification
- artificial intelligence / robotics
- data structures / algorithms / complexity
- verification / logic
Keywords
- Horn formulas
- hypergraphs
- closures
- lattices
- dependencies
- formal concepts
