Premium
On boolean decision trees with faulty nodes
Author(s) -
Kenyon Claire,
King Valerie
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050306
Subject(s) - boolean function , context (archaeology) , decision tree , computer science , combinatorics , binary decision diagram , probability of error , discrete mathematics , tree (set theory) , boolean data type , mathematics , theoretical computer science , algorithm , artificial intelligence , paleontology , biology
Abstract We consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are faulty with a fixed probability. We show that if f can be represented in k ‐DNF form and in j ‐CNF form, then O ( n log(min( k, j )/ q )) queries suffice to compute f with error probability less than q , where n is the number of input bits. © 1994 John Wiley & Sons, Inc.