Bidual Horn functions and extensions

Partially defined Boolean functions (pdBf) (T,F), where T,F subset of or eq ual to {0,1}(n) are disjoint sets of true and false vectors, generalize tot al Boolean functions by allowing that the function values on some input vec tors are unknown. The main issue with pdBfs is the extension problem, which is deciding, given a pdBf, whether it is interpolated by a function f from a given class of total Boolean functions, and computing a formula for f. I n this paper, we consider extensions of bidual Horn functions, which are th e Boolean functions f such that both f and its dual function f(d) are Horn. They are intuitively appealing for considering extensions because they giv e a symmetric role to positive and negative information (i.e., true and fal se vectors) of a pdBf, which is not possible with arbitrary Horn functions. Bidual Horn functions turn out to constitute an intermediate class between positive and Horn functions which retains several benign properties of pos itive functions. Besides the extension problem, we study recognition of bid ual Horn functions from Boolean formulas and properties of normal form expr essions. We show that finding a bidual Horn extension and checking bidualit y of a Horn DNF is feasible in polynomial time, and that the latter is intr actable from arbitrary formulas. We also give characterizations of shortest DNF expressions of a bidual Horn function f and show how to compute such a n expression from a Horn DNF for f in polynomial time; for arbitrary Horn f unctions, this is NP-hard. Furthermore, we show that a polynomial total alg orithm for dualizing a bidual Horn function exists if and only if there is such an algorithm for dualizing a positive function. (C) 1999 Elsevier Scie nce B.V. All rights reserved.