Published in Discrete Mathematics and Applications
We consider exact attribute-efficient learning of functions from Post closed classes using membership queries and obtain bounds on learning complexity.
Published in Discrete Mathematics and Applications
Formulas for distributions of number of ones (non-zeroes) in the cycle of the output sequence of generalized binary Pohl generator are obtained. Limit theorems for these distributions are derived in the case when the lengths of registers are coprime and tend to infinity, the contents of different registers are independent, but cell contents within ...
Published in Discrete Mathematics and Applications
We consider a generalized scheme of allocation of n particles (elements) over unordered cells (components) under the condition that the number of particles in each cell belongs to a fixed finite set A of positive integers. A new asymptotic estimates for the total number In(A) of variants of allocations of n particles are obtained under some conditi...
Published in Discrete Mathematics and Applications
We use an analogue of Gluskin–Hosszú theorem for strongly dependent finite n-ary semigroups to prove an analogue of Post coset theorem. We show that in fact these theorems are equivalent. Thus it turns our that the case of n-ary semigroups is fully similar to the case of n-groups.
Published in Discrete Mathematics and Applications
An easily implementable recursive parallelization strategy for solving the subset sum problem by the branch-and-bound method is proposed. Two different frontal and balanced variants of this strategy are compared. On an example of a particular case of the subset sum problem we show that the balanced variant is more effective than the frontal one. Mo...
Published in Discrete Mathematics and Applications
We consider Boolean circuits in Zhegalkin basis and describe all Boolean functions that can be implemented by a circuit admitting a complete fault detection test of length 1 in case of constant faults of type “1” at gate outputs.
Published in Discrete Mathematics and Applications
We consider universal function’s construction for classes of sums of two arguments modulo 2. We constructed functions with optimal domain cardinality O(log n).
Published in Discrete Mathematics and Applications
Asymptotic upper and lower bounds for the numbers of distinct subsets A + B in Abelian group of order n are derived, where |A|, |B| ≥ n(log n)−1/8.
Published in Discrete Mathematics and Applications
Let b, n be two positive integers such that b ≥ 2, and S(b, n) be the numerical semigroup generated by {bn+1+i+bn+i−1b−1∣i∈N} $\begin{array}{} \{b^{n+1+i}+\frac{b^{n+i}-1}{b-1}\mid i\in\mathbb{N}\} \end{array}$. Applying two order relations, we give formulas for computing the embedding dimension, the Frobenius number, the type and the genus of S(b,...
Published in Discrete Mathematics and Applications
We obtain a criterion for the minimal logarithmic growth rate for an arbitrary set with a given set of operations defined on it, i.e., we describe all finite sets A with operations on them such that the growth rate differs by at most a constant from the logarithmic growth rate to base ∣A∣.
