Structures of Renamable Horn and q-Horn Formulae

Richard Sun

Abstract:
In this talk, we will revisit the problem of
recognizing renamable Horn and q-Horn formulae,
my first research topic on Boolean functions
supervised by Dr. Hammer. Using a graph associated
with any disjunctive normal form, we identify the
structures of renamable Horn and q-Horn formulae,
in terms of paths and cycles of the graph, which
can be used to recognize renamable Horn or q-Horn
formulae in linear time.