Boolean analysis of incomplete examples

Endre Boros, Toshihide Ibaraki, Kazuhisa Makino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsRolf Karlsson, Andrzej Lingas
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540614222, 9783540614227
StatePublished - 1996
Event5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 - Reykjavik, Iceland
Duration: Jul 3 1996Jul 5 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Scandinavian Workshop on Algorithm Theory, SWAT 1996

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Boolean analysis of incomplete examples'. Together they form a unique fingerprint.

Cite this