Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2014

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Certificates of Non-Membership for Classes of Read-Once Functions

Chistikov D., Fedorova V., Voronenko A.

Fundamenta Informaticae

2014

Vol. 132, nr 1

63--77

A certificate of non-membership for a Boolean function f with respect to a class C, f ∉ C, is a set S of input strings such that the values of f on strings from S are inconsistent with any function h ∈ C. We study certificates of non-membership with respect to several classes of read-once functions, generated by their bases. For the basis {&, ∨, ¬}, we determine the optimal certificate size for every function outside the class and deduce that 6 strings always suffice. For the same basis augmented with a function x1 ... xs ∨ x1 … xs we show that there exist n-variable functions requiring Ω(ns−1) strings in a certificate as n → ∞. For s = 2, we show that this bound is tight by constructing certificates of size O(n) for all functions outside the class.