Some classes of Boolean formulae with polynomial time satisfiability testing.

Abstract

In this paper we study several classes of Boolean formulae which generalize Horn formulae while preserving one of their main properties, namely the fact that satisfiability is decidable in polynomial time.