Sequential Evaluation of Boolean Functions

This paper presents methods for iterative evaluation of Boolean expressions suitable, e. g., in sequential search and matching when the input variables appear in sequence. The sum-of-product form is assumed and the clue is to partially compute the values of all products partially for each new variab...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1979-12, Vol.C-28 (12), p.879-887
Main Authors: Plavsic, Danielsson
Format: Article
Language:English
Subjects:
Boolean decision
data base search
evaluation of Boolean expressions
fast evaluation
hierarchical Boolean functions
multilevel Boolean functions
partial evaluation
sequential evaluation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents methods for iterative evaluation of Boolean expressions suitable, e. g., in sequential search and matching when the input variables appear in sequence. The sum-of-product form is assumed and the clue is to partially compute the values of all products partially for each new variable being defined. It is shown that the additive use of an expression for the complementary function can result in a faster evaluation. The method proves to be extendable to multilevel expressions.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.1979.1675278