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

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

Fingerprint Dive into the research topics of 'Guided inference of nested monotone Boolean functions'. Together they form a unique fingerprint.

  • Cite this