Evaluation of DNF formulas

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

Evaluation of DNF formulas

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

Research output: Contribution to conference › Paper › peer-review

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 = (x₁, ..., x_n), when there is a cost ci associated with obtaining the value of xi, each xi is equal to 1 with known probability p_i, and the x_i 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 language	English (US)
State	Published - Jan 1 2014
Event	2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 - Fort Lauderdale, United States Duration: Jan 6 2014 → Jan 8 2014

Conference

Conference	2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014
Country/Territory	United States
City	Fort Lauderdale
Period	1/6/14 → 1/8/14

ASJC Scopus subject areas

Applied Mathematics
Artificial Intelligence

Cite this

@conference{1489532dd39a4876a9d94999e0408f66,

title = "Evaluation of DNF formulas",

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.",

author = "Allen, {Sarah R.} and Lisa Hellerstein and Devorah Kletenik and Tongu{\c c} {\"U}nl{\"u}yurt",

year = "2014",

month = jan,

day = "1",

language = "English (US)",

note = "2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 ; Conference date: 06-01-2014 Through 08-01-2014",

}

TY - CONF

T1 - Evaluation of DNF formulas

AU - Allen, Sarah R.

AU - Hellerstein, Lisa

AU - Kletenik, Devorah

AU - Ünlüyurt, Tonguç

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

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

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

M3 - Paper

T2 - 2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014

Y2 - 6 January 2014 through 8 January 2014

ER -

Evaluation of DNF formulas

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this