Checking Tests for Read-Once Functions over Arbitrary Bases

Details Checking Tests for Read-Once Functions over Arbitrary Bases Checking Tests for Read-Once Functions over Arbitrary Bases

2012-03-03

arxiv.org/abs/1203.0631v2

Computer Science

Discrete Mathematics

Accepted to the 7th International Computer Science Symposium in Russia (CSR 2012), revised version

Scientific paper

A Boolean function is called read-once over a basis B if it can be expressed by a formula over B where no variable appears more than once. A checking test for a read-once function f over B depending on all its variables is a set of input vectors distinguishing f from all other read-once functions of the same variables. We show that every read-once function f over B has a checking test containing O(n^l) vectors, where n is the number of relevant variables of f and l is the largest arity of functions in B. For some functions, this bound cannot be improved by more than a constant factor. The employed technique involves reconstructing f from its l-variable projections and provides a stronger form of Kuznetsov's classic theorem on read-once representations.

Affiliated with

Also associated with

No associations

Rating

Checking Tests for Read-Once Functions over Arbitrary Bases 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 Checking Tests for Read-Once Functions over Arbitrary Bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Checking Tests for Read-Once Functions over Arbitrary Bases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345405