



Hydras: Horn formulas and directed hypergraphs
- April 11, 2014
- 11 a.m.
- LeConte 312
Abstract
Horn formulas are an important fragment of propositional logic, with various applications including knowledge representation and reasoning. We define and study the hydra number of a graph, a graph property that arises from a combinatorial reformulation of a restricted version of the NP-hard problem of Horn formula minimization. This talk is based on joint work with Robert H. Sloan and Gyorgy Turan.