Variations on extending partially defined Boolean functions with missing bits

Endre Boros, Toshihide Ibaraki, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


In this paper we consider four possible definitions for extending a partially defined Boolean function in which the input contains some missing bits. We show somewhat surprisingly that, for many general and frequently used families of function classes, three of these notions of an extension are mathematically equivalent, though such an equivalence does not hold universally, as demonstrated by several examples.

Original languageEnglish (US)
Pages (from-to)53-70
Number of pages18
JournalInformation and Computation
Issue number1
StatePublished - Jan 10 2003

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


  • Boolean functions
  • Extensions
  • Logical analysis of data
  • Missing bits
  • Partially defined Boolean functions


Dive into the research topics of 'Variations on extending partially defined Boolean functions with missing bits'. Together they form a unique fingerprint.

Cite this