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 -