On the length of a read-many certificate in certain extended elementary basesстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 27 января 2016 г.
Аннотация:The following problem is considered: find a couple of sets (a certificate) with which we can verify if the functions of n variables in a given basis are read-once functions. This work obtains the logarithmic lower bound estimates of the Shannon function of certificate length for all functions of n variables in bases consisting of conjunction, disjunction, negation, and one of Stecenko monotone functions. It is thus shown that the elementary basis is the only one for which read-many certificate length is bound by a constant.