99-30: Fully Consistent Extensions of Partially Defined Boolean Functions with Missing Bits

DIMACS TR: 99-30

Fully Consistent Extensions of Partially Defined Boolean Functions with Missing Bits

Authors: Endre Boros, Toshihide Ibaraki and Kazuhisa Makino

ABSTRACT
In this paper we consider four different definitions for an extension of a partially defined Boolean function in which the input contains some missing bits. We show that, for many general and reasonable families of function classes, three of these extensions are mathematically equivalent. However we also demonstrate that such an equivalence does not hold for all classes.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-30.ps.gz

DIMACS Home Page