TY - GEN

T1 - Boolean analysis of incomplete examples

AU - Boros, Endre

AU - Ibaraki, Toshihide

AU - Makino, Kazuhisa

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.

PY - 1996

Y1 - 1996

N2 - As a form of knowledge acquisition from data, we consider the problem of deciding whether there exists an extension of a partially defined Boolean function with missing data (T, F), where T (resp., F) is a set of positive (resp., negative) examples. Here, “*”denotes a missing bit in the data, and it is assumed that T ⊆ {0,1, *}n and F ⊆ {0,1, *}n hold. A Boolean function f: {0,1}n → {0,1} is an extension of (T,F) if it is true (resp., false) for the Boolean vectors corresponding to positive (resp., negative) examples; more precisely, we define three types of extensions called consistent, robust and most robust, depending upon how to deal with missing bits. We then provide polynomial time algorithms or prove their NP-hardness for the problems under various restrictions.

AB - As a form of knowledge acquisition from data, we consider the problem of deciding whether there exists an extension of a partially defined Boolean function with missing data (T, F), where T (resp., F) is a set of positive (resp., negative) examples. Here, “*”denotes a missing bit in the data, and it is assumed that T ⊆ {0,1, *}n and F ⊆ {0,1, *}n hold. A Boolean function f: {0,1}n → {0,1} is an extension of (T,F) if it is true (resp., false) for the Boolean vectors corresponding to positive (resp., negative) examples; more precisely, we define three types of extensions called consistent, robust and most robust, depending upon how to deal with missing bits. We then provide polynomial time algorithms or prove their NP-hardness for the problems under various restrictions.

UR - http://www.scopus.com/inward/record.url?scp=84862203355&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862203355&partnerID=8YFLogxK

U2 - 10.1007/3-540-61422-2_152

DO - 10.1007/3-540-61422-2_152

M3 - Conference contribution

AN - SCOPUS:84862203355

SN - 3540614222

SN - 9783540614227

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 440

EP - 451

BT - Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Karlsson, Rolf

A2 - Lingas, Andrzej

PB - Springer Verlag

T2 - 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996

Y2 - 3 July 1996 through 5 July 1996

ER -