11.05.14 - 16.05.14, Seminar 14201

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

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Motivation

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 arti cial 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 di fferent, 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 fi nding optimal hyperpaths for a directed hypergraph. A comprehensive understanding would involve the di erent 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 satisfi ability 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 di fferent representations of the information extracted, and the computation of one representation given another representation have been studied from diff erent 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 scienti c interchange between the diff erent disciplines in an atmosphere that will stimulate collaboration and lead to new partnerships.