Guided inference of nested monotone Boolean functions

Vetle I. Torvik, Evangelos Triantaphyllou

Research output: Contribution to journalArticle

Abstract

This paper addresses the problem of minimizing the average query complexity of inferring a pair of nested monotone Boolean functions defined on {0,1}n using a pair of oracles. Here, nested refers to the case when one of the functions is always greater than or equal to the other function. It is shown that the nested case is equivalent to inferring the single function case defined on {0,1}n+1 when access to the two oracles is unrestricted. Two common examples of restricted oracles, namely sequential oracles and a single three-valued oracle, are also analyzed. The most efficient known approach to minimizing the average query complexity in inferring a single monotone Boolean function is based on a query selection criterion. It is shown that the selection criterion approach is easily modified for use with restricted oracles. Several real world examples illustrate the necessity and sufficiency of the nested monotone Boolean function model. Extensive computational results indicate that the nestedness assumption reduces the average query complexity by a few percent. This is a dramatic improvement considering the fact that this complexity is exponential in n.

Original languageEnglish (US)
Pages (from-to)171-200
Number of pages30
JournalInformation Sciences
Volume151
Issue numberSUPPL
DOIs
StatePublished - May 1 2003
Externally publishedYes

Fingerprint

Monotone Boolean Function
Average Complexity
Query Complexity
Boolean functions
Sufficiency
Percent
Computational Results
Query
Inference
Model

Keywords

  • Average query complexity
  • Guided inference
  • Membership queries
  • Nested monotone Boolean functions
  • Partially ordered sets (posets)
  • Query selection criteria

ASJC Scopus subject areas

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

Cite this

Guided inference of nested monotone Boolean functions. / Torvik, Vetle I.; Triantaphyllou, Evangelos.

In: Information Sciences, Vol. 151, No. SUPPL, 01.05.2003, p. 171-200.

Research output: Contribution to journalArticle

Torvik, Vetle I. ; Triantaphyllou, Evangelos. / Guided inference of nested monotone Boolean functions. In: Information Sciences. 2003 ; Vol. 151, No. SUPPL. pp. 171-200.
@article{55b3683a8ae04ef89b7a6ed17a527ef2,
title = "Guided inference of nested monotone Boolean functions",
abstract = "This paper addresses the problem of minimizing the average query complexity of inferring a pair of nested monotone Boolean functions defined on {0,1}n using a pair of oracles. Here, nested refers to the case when one of the functions is always greater than or equal to the other function. It is shown that the nested case is equivalent to inferring the single function case defined on {0,1}n+1 when access to the two oracles is unrestricted. Two common examples of restricted oracles, namely sequential oracles and a single three-valued oracle, are also analyzed. The most efficient known approach to minimizing the average query complexity in inferring a single monotone Boolean function is based on a query selection criterion. It is shown that the selection criterion approach is easily modified for use with restricted oracles. Several real world examples illustrate the necessity and sufficiency of the nested monotone Boolean function model. Extensive computational results indicate that the nestedness assumption reduces the average query complexity by a few percent. This is a dramatic improvement considering the fact that this complexity is exponential in n.",
keywords = "Average query complexity, Guided inference, Membership queries, Nested monotone Boolean functions, Partially ordered sets (posets), Query selection criteria",
author = "Torvik, {Vetle I.} and Evangelos Triantaphyllou",
year = "2003",
month = "5",
day = "1",
doi = "10.1016/S0020-0255(03)00062-8",
language = "English (US)",
volume = "151",
pages = "171--200",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Inc.",
number = "SUPPL",

}

TY - JOUR

T1 - Guided inference of nested monotone Boolean functions

AU - Torvik, Vetle I.

AU - Triantaphyllou, Evangelos

PY - 2003/5/1

Y1 - 2003/5/1

N2 - This paper addresses the problem of minimizing the average query complexity of inferring a pair of nested monotone Boolean functions defined on {0,1}n using a pair of oracles. Here, nested refers to the case when one of the functions is always greater than or equal to the other function. It is shown that the nested case is equivalent to inferring the single function case defined on {0,1}n+1 when access to the two oracles is unrestricted. Two common examples of restricted oracles, namely sequential oracles and a single three-valued oracle, are also analyzed. The most efficient known approach to minimizing the average query complexity in inferring a single monotone Boolean function is based on a query selection criterion. It is shown that the selection criterion approach is easily modified for use with restricted oracles. Several real world examples illustrate the necessity and sufficiency of the nested monotone Boolean function model. Extensive computational results indicate that the nestedness assumption reduces the average query complexity by a few percent. This is a dramatic improvement considering the fact that this complexity is exponential in n.

AB - This paper addresses the problem of minimizing the average query complexity of inferring a pair of nested monotone Boolean functions defined on {0,1}n using a pair of oracles. Here, nested refers to the case when one of the functions is always greater than or equal to the other function. It is shown that the nested case is equivalent to inferring the single function case defined on {0,1}n+1 when access to the two oracles is unrestricted. Two common examples of restricted oracles, namely sequential oracles and a single three-valued oracle, are also analyzed. The most efficient known approach to minimizing the average query complexity in inferring a single monotone Boolean function is based on a query selection criterion. It is shown that the selection criterion approach is easily modified for use with restricted oracles. Several real world examples illustrate the necessity and sufficiency of the nested monotone Boolean function model. Extensive computational results indicate that the nestedness assumption reduces the average query complexity by a few percent. This is a dramatic improvement considering the fact that this complexity is exponential in n.

KW - Average query complexity

KW - Guided inference

KW - Membership queries

KW - Nested monotone Boolean functions

KW - Partially ordered sets (posets)

KW - Query selection criteria

UR - http://www.scopus.com/inward/record.url?scp=0037402643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037402643&partnerID=8YFLogxK

U2 - 10.1016/S0020-0255(03)00062-8

DO - 10.1016/S0020-0255(03)00062-8

M3 - Article

AN - SCOPUS:0037402643

VL - 151

SP - 171

EP - 200

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

IS - SUPPL

ER -