Search

We consider the construction of a universal function for classes of modulo 2 sums of three arguments. The definition domain of the universal functions is of cardinality Θ(log n). [ABSTRACT FROM AUTHOR]

We consider the notion of universal function such that a subset of the function's values defines any function from some set. For the set of linear functions, we consider all the combinations of the number of variables and the number of values, except four-valued functions of two variables. [ABSTRACT FROM AUTHOR]

The following problem is considered: specify a Boolean function of n variables such that every bilinear (polylinear) function is reduced, on a certain number of tuples of the specified function, to a unique bilinear (polylinear) function that is identical with the specified function on these tuples. We show that this is feasible for bilinear functions and for polylinear functions with a fixed number of parentheses k, starting with some n, and we can restrict the analysis to a sequence of functions with definition domain of cardinality O(n). [ABSTRACT FROM AUTHOR]

The article describes the construction of discrete functions which, by some of their values, specify (generate) arbitrary linear functions. The cases of prime and sufficiently large composite k have been considered previously. In the present study we finally solve the problem of existence of such functions for almost all k and n variables. The proof of the probabilistic upper bound and the general approach are due to A. A. Voronenko. The proof for small k has been developed by N. K. Voronova. The proof for k from 21 to 48 is the result of indispensable cooperation of V. P. Il'yutko and A. A. Voronenko. [ABSTRACT FROM AUTHOR]

In this article we describe the construction of discrete functions such that some of their values specify (generate) arbitrary pairs of literals under two mutually exclusive assumptions: the function is equal to one of the variables or to its negation. We prove the existence of such functions with at least seven arguments and show that for sufficiently large n this function can be defined on O( n log n) tuples. We also consider the problem of simultaneous generation of k literals. We show that with k < n − log n+log(log 4 −1) , functions generating arbitrary k literals exist, and if ( n−log n−k) → ∞ as n → ∞ , then almost all functions generate arbitrary k literals. [ABSTRACT FROM AUTHOR]

The article examines the construction of discrete functions such that a part of their value set specifies (generates) arbitrary linear functions. For prime k greater than 5, we prove the existence of such partial functions with no fewer than two variables and derive linear upper and lower bounds in the number of variables for the size of their definition domain. [ABSTRACT FROM AUTHOR]

The article proves the read-many property of Boolean functions in the basis of all functions of l variables. The length of the minimal read-many certificate in this basis is known to be upper bounded by a polynomial of degree l - 1 in the number of function variables. In this article, we prove that the upper bound on the length of the minimal read-many certificate for functions in this basis is a polynomial of degree not exceeding l. [ABSTRACT FROM AUTHOR]

The article considers the problem of constructing a conditional diagnostic test (the exact identification problem) on the set of all read-once functions essentially dependent on the specified variables in an arbitrary hereditary basis. We use standard queries on function values at points and also parity queries on the number of ones in subfunctions obtained by substituting constants for variables (subcube parity queries return the modulo-2 sum of the function values on a subcube of the Boolean cube). For the elementary basis consisting of conjunction, disjunction, and negation, we prove the existence of a conditional diagnostic test with a quadratic (in the number of variables) number of queries. For bases that allow read-once expression of all elementary-basis functions (containing at least one nonmonotone and at least one nonlinear function) and are essentially different from the elementary basis, we prove the necessity of using an exponential (in the number of variables) number of queries in the worst case. Our analysis thus establishes the boundary between polynomial and exponential complexity problems. [ABSTRACT FROM AUTHOR]

Testing relative to a nonrepeating alternative in a conjunction-disjunction basis is considered. A lower bound on the test length is established for all nonrepeating functions in this basis. A subsequence of easily testable functions is constructed and the corresponding tests are described. Individual lower test length bounds are proved for functions of a special form; minimality of the tests is established for the functions of the constructed subsequence. [ABSTRACT FROM AUTHOR]

For a given nonrepeating function f(x1, … , xn) that essentially depends on all its variables we estimate the length of the diagnostic test on the set of all nonrepeating functions arbitrarily dependent on the variables x1, … , xn. Previously the author has shown that the corresponding Shannon function is of order &thetas;(n2). In this article nonrepeating functions f(x1, … , xn) are constructed for which the length of the minimal test increases superlinearly but not faster than n2/2. [ABSTRACT FROM AUTHOR]