On disguised double horn functions and extensions

As a natural restriction of disguised Horn functions (i.e., Boolean functions which become Horn after a renaming (change of polarity) of some of the variables), we consider the class C DH R of disguised double Horn functions, i.e., the functions which and whose complement are both disguised Horn. We investigate the syntactical properties of this class and relationship to other classes of Boolean functions. Moreover, we address the extension problem of partially defined Boolean functions (pdBfs) in C DH R, where a pdBf is a function defined on a subset (rather than the full set) of Boolean vectors. We show that the class C DH R coincides with the class C 1–DL of 1-decision lists, and with the intersections of several well-known classes of Boolean functions. Furthermore, polynomial time algorithms for the recognition of a function in C DH R from Horn formulas and other classes of formulas are provided, while the problem is intractable in general. We also present an algorithm for the extension problem which, properly implemented, runs in linear time.