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

• Autorzy: Chistikov D. , Fedorova V. , Voronenko A.

Identyfikatory

DOI

10.3233/FI-2014-1032

• Języki publikacji: EN

Abstrakty

EN

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 x₁ ... x_s ∨ x₁ … x_s we show that there exist n-variable functions requiring Ω(n^s−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.

Słowa kluczowe

EN

certificate of non-membership; read-once function

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 63--77
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Chistikov D.

• Max Planck Institute for Software Systems (MPI-SWS), Germany

autor

Fedorova V.

• Moscow State University, Russia

autor

Voronenko A.

• Moscow State University, Russia

Bibliografia

• [1] M. Arias, R. Khardon, R. A. Servedio. Polynomial certificates for propositional classes. Information and Computation, 204(5), 2006, 816–834.
• [2] D. Angluin, L. Hellerstein, M. Karpinski. Learning read-once formulas with queries. Journal of the ACM, 40, 1993, 185–210.
• [3] N. H. Bshouty, T. R. Hancock, L. Hellerstein. Learning Boolean read-once formulas over generalized bases. Journal of Computer and System Sciences, 50(3), 1995, 521–542.
• [4] D. G. Corneil, H. Lerchs, L. Stewart Burlingham. Complement reducible graphs. Discrete Applied Mathematics, 3(3), 1981, 163–174.
• [5] A. Feigelson, L. Hellerstein. The forbidden projections of unate functions. Discrete Applied Mathematics, 77(3), 1997, 221–236.
• [6] M. C. Golumbic, V. Gurvich. Read-once functions (book chapter). In: Y. Crama, P. L. Hammer, Boolean Functions: Theory, Algorithms and Applications. Encyclopedia of Mathematics and Its Applications 142, Cambridge University Press, 2011.
• [7] V. Gurvich. On the normal form of positional games. Soviet Mathematics Doklady, 25(3), 1982, 572–575.
• [8] T. Hegedűs. Generalized teaching dimensions and the query complexity of learning. Proceedings of COLT 1995, ACM, 1995. 108–117.
• [9] P. Heggernes, D. Kratsch. Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic Journal of Computing, 14, 2007, 87–108.
• [10] L. Hellerstein. On generalized constraints and certificates. Discrete Mathematics, 226, 2001, 211–232.
• [11] L. Hellerstein, K. Pillaipakkamnatt, V. Raghavan, D.Wilkins. How many queries are needed to learn? Journal of the ACM, 43(5), 1996, 840–862.
• [12] R. M. McConnell, K. Mehlhorn, S. Näher, P. Schweitzer. Certifying algorithms. Computer Science Review, 5(2), 2011, 119–161.
• [13] N. A. Peryazev. Weakly read-many functions over the binary basis. Diskretnaya Matematika i Informatika 4, Izdatel’stvo Irkutskogo universiteta, Irkutsk, 1998 (in Russian).
• [14] P. Savický, A. R. Woods. The number of Boolean functions computed by formulas of a given size. Random Structures and Algorithms, 13(3–4), 1998, 349–382.
• [15] P. Sen, A. Deshpande, L. Getoor. Read-once functions and query evaluation in probabilistic databases. Proceedings of the VLDB Endowment, 3(1–2), 2010, 1068–1079.
• [16] V. A. Stetsenko. On almost bad Boolean bases. Theoretical Computer Science, 136(2), 1994, 419–469.
• [17] B. A. Subbotovskaya. Comparison of bases in the realization by formulas of functions of the algebra of logic. Soviet Mathematics Doklady, 4, 1963, 478–481.
• [18] R. Thomas. Recent excluded minor theorems for graphs. In: Surveys in combinatorics. London Mathematical Society Lecture Note Series 267, Cambridge University Press, Cambridge, 1999, 201–222.
• [19] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984, 1134–1142.
• [20] V. A. Voblyi. The asymptotics of the number of repetition-free Boolean functions in the basis B1. Discrete Mathematics and Applications, 20(5–6), 2011, 707–708.
• [21] A. A. Voronenko. On the Shannon function for read-many certificate length in one base family. Moscow University Computational Mathematics and Cybernetics, 37(4), 2013, 202–204.
• [22] A. A. Voronenko. On the complexity of proving that a Boolean function is not binary read-once. Prikladnaya Diskretnaya Matematika, 13, 2011, 12–16 (in Russian).
• [23] A. A. Voronenko, V. S. Fedorova, D. V. Chistikov. Iterated Boolean functions in the elementary basis. Russian Mathematics (Iz. VUZ), 55(11), 2011, 61–65.