IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC