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

Abstract

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
Volume180
Issue number1
DOIs
StatePublished - Jan 10 2003

All Science Journal Classification (ASJC) codes

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

Keywords

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

Fingerprint

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

Cite this