GENERATING AND IDENTIFICATION OF MONOTONE BOOLEAN FUNCTIONS


Бакоев, Валентин (2003) GENERATING AND IDENTIFICATION OF MONOTONE BOOLEAN FUNCTIONS MATHEMATICS AND EDUCATION IN MATHEMATICS, Sofia, 2003, pp 226-232, (Proceedings of the Thirty Second Spring Conference of the Union of Bulgarian Mathematicians, Sunny Beach, April 5–8, 2003). ISBN 954-8880-14-8, http://www.math.bas.bg/smb/2001_2003_PK/2003/pdf/226-232.pdf


 Three algorithms, based on a matrix structure, are described here. First of them generates all monotone Boolean functions of n variables in lexicographic order. The second one determines the first (resp. the last) lexicographically minimal true (resp. maximal false) vector of an unknown function. It serves the third algorithm, which identifies an unknown monotone Boolean function f of n variables by using member- ship queries only. For up to 6 variables it determines f with at most m.n queries, where m is the combined size of the sets of minimal true and maximal false vectors of f.
  Доклад
 Monotone Boolean functions, generating, identification, Dedekind’s problem


Природни науки, математика и информатика

Natural sciences, mathematics and informatics

 Издадено
  15983
 Валентин Бакоев

Научният архив поддържа инициативата за отворен достъп OAI 2.0 с начален адрес: http://da.uni-vt.bg/oai2/