This project is aimed at the development of algorithms, theory, and applications for the identification, including the enumeration of all minimal representatives, of implicitly given monotone systems. Monotone systems are a frequent target of knowledge discovery as they represent important information hidden in large data bases and complex networks. Problems involving the determination of monotone systems arise naturally in a multitude of areas, including data mining (finding all maximal frequent, minimal infrequent sets), text mining (finding the best linear query in vector space models), machine learning (finding the best rules or patterns), hypergraph dualization (generating all minimal transversals), reliability theory (generating all minimal working and/or maximal failing states), integer programming (generating all minimal feasible solutions), stochastic programming (constructing deterministic equivalents to certain stochastic models), etc. Both the determination, and efficient and complete representation of such systems are the subject of this project.
We study the problem of identifying implicitly given monotone systems, and building on several recent results we aim at developing a coherent theory of such identification problems. A major part of our research effort focuses on identifying tractable classes, developing efficient algorithms for those, and implementing and testing the resulting new methods. In particular we study monotone systems definable via systems of threshold, regular or submodular functions, since these classes seem to be the most important building blocks of tractable classes.