Horn formulas and directed hypergraphs

A Horn formula in propositional logic is a set of rules of the form a,b → c. This is a basic formalism for representing knowledge and for reasoning. Combinatorially, a rule can be thought of as a generalization of a directed edge in a directed graph, and so Horn formulas can be thought of as directed hypergraphs. In addition, Horn formulas are equivalent to other notions such as lattices and closure operators. We discuss some algorithmic and combinatorial problems in this area, such as the complexity of finding an approximately shortest formula equivalent to a given formula, and extremal problems for directed hypergraphs. Joint work with Amitava Bhattacharya, Bhaskar DasGupta, Marina Langlois, Dhruv Mubayi, Robert Sloan and Despina Stasi.

Event Topic

Discrete Applied Math Seminar