Optimal sequential arrangement of evaluation trees for boolean functions

Y. Perl, Y. Breitbart

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Let F be a disjunction of boolean functions of pairwise disjoint variables. Suppose an evaluation tree is given for each such function. We consider the problem of finding an optimal sequential order of scanning the trees for evaluation of F. A necessary and sufficient condition is given. A more general arrangement-a tree-structured arrangement of the trees is considered. It is shown to give no improvement.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalInformation sciences
Volume11
Issue number1
DOIs
StatePublished - 1976
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Optimal sequential arrangement of evaluation trees for boolean functions'. Together they form a unique fingerprint.

Cite this