Testing Formula Satisfaction

Details Testing Formula Satisfaction Testing Formula Satisfaction

2012-04-16

arxiv.org/abs/1204.3413v1

Computer Science

Data Structures and Algorithms

Scientific paper

We study the query complexity of testing for properties defined by read once formulae, as instances of {\em massively parametrized properties}, and prove several testability and non-testability results. First we prove the testability of any property accepted by a Boolean read-once formula involving any bounded arity gates, with a number of queries exponential in $\epsilon$ and independent of all other parameters. When the gates are limited to being monotone, we prove that there is an {\em estimation} algorithm, that outputs an approximation of the distance of the input from satisfying the property. For formulae only involving And/Or gates, we provide a more efficient test whose query complexity is only quasipolynomial in $\epsilon$. On the other hand we show that such testability results do not hold in general for formulae over non-Boolean alphabets; specifically we construct a property defined by a read-once arity 2 (non-Boolean) formula over alphabets of size 4, such that any 1/4-test for it requires a number of queries depending on the formula size.

Affiliated with

Also associated with

No associations

Rating

Testing Formula Satisfaction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing Formula Satisfaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing Formula Satisfaction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6171