Evaluation of DNF formulas

Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, Tonguç Ünlüyurt

    Research output: Contribution to conferencePaper

    Abstract

    We consider the Stochastic Boolean Function Evaluation (SBFE) problem for classes of DNF formulas. The SBFE problem for DNF formulas is a “sequential testing” problem where we need to determine the value of DNF formula on an initially unknown input x = (x1, ..., xn), when there is a cost ci associated with obtaining the value of xi, each xi is equal to 1 with known probability pi, and the xi are independent. The goal is to minimize expected cost. The SBFE problem is inapproximable for general DNF formulas. We give approximate and exact algorithms for two subclasses of DNF formulas: monotone k-DNF and monotone k-term DNF. We also prove a lower bound result for evaluation of monotone CDNF formulas.

    Original languageEnglish (US)
    StatePublished - Jan 1 2014
    Event2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 - Fort Lauderdale, United States
    Duration: Jan 6 2014Jan 8 2014

    Conference

    Conference2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014
    CountryUnited States
    CityFort Lauderdale
    Period1/6/141/8/14

    ASJC Scopus subject areas

    • Applied Mathematics
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'Evaluation of DNF formulas'. Together they form a unique fingerprint.

    Cite this