https://www.dagstuhl.de/14201

### May 11 – 16 , 2014, Dagstuhl Seminar 14201

# Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications

## 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)

## For support, please contact

## Documents

Dagstuhl Report, Volume 4, Issue 5

Aims & Scope

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Schedule [pdf]

## Summary

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.

**Summary text license**

Creative Commons BY 3.0 Unported license

Kira V. Adaricheva, Giuseppe F. Italiano, Hans Kleine Büning, and György Turan

## Classification

- Artificial Intelligence / Robotics
- Data Structures / Algorithms / Complexity
- Verification / Logic

## Keywords

- Horn formulas
- Hypergraphs
- Closures
- Lattices
- Dependencies
- Formal concepts