Popkov, Kirill A.
Published in
Discrete Mathematics and Applications

The following results are proved: any nonconstant Boolean function may be implemented by an irredundant circuit of gates in the basis {x& y, x, x ⊕ y ⊕ z} admitting a single fault detection test of length at most 2 with respect to arbitrary stuck-at faults at outputs of gates, there exists a six-place Boolean function ψ such that any nonconstant Bo...

Burov, Dmitry A.
Published in
Discrete Mathematics and Applications

We find a relation between the W-intersection matrix (which characterizes the degree of “nonhomomorphy”) of a transformation and the difference distribution table and the correlation matrix (which characterize the degree nonlinearity of a transformation). An upper estimate for the dimension of a subspace invariant under almost bent functions is put...

Alekseev, Valeriy B.
Published in
Discrete Mathematics and Applications

Let A be a precomplete class (a maximal clone) in k-valued logic and T(A) be the family of all closed classes (under superposition) in partial k-valued logic that contain A. A simple test is put forward capable of finding out from a partial order defining the precomplete class A of monotone functions whether the family T(A) is finite or infinite. T...

Cheremushkin, Aleksandr V.
Published in
Discrete Mathematics and Applications

The paper contains an extension of Malyshev theorem for n-ary quasigroups with a right or left weak invertibility property to the case of strongly dependent n-ary operations. As a corollary a new proof of Gluskin–Hosszú theorem for strongly dependent n-ary semigroups is obtained.

Malyshev, Fedor M.
Published in
Discrete Mathematics and Applications

The paper is concerned with systems of generators of permutation groups on Cartesian products of residue rings. Each separate permutation from the system of generators is constructed on the basis of additions, is characterized by the local action, and leaves fixed the major parts of the components of the element being transformed. A criterion of 2-...

Gu, Ze
Published in
Discrete Mathematics and Applications

Given a numerical semigroup S, a nonnegative integer a and m ∈ S ∖ {0}, we introduce the set C(S, a, m) = {s + aw(s mod m) | s ∈ S}, where {w(0), w(1), ⋯, w(m – 1)} is the Apéry set of m in S. In this paper we characterize the pairs (a, m) such that C(S, a, m) is a numerical semigroup. We study the principal invariants of C(S, a, m) which are given...

Mikhailov, V. G.
Published in
Discrete Mathematics and Applications

We consider a special function ρ(H) of the subset H of n-dimensional vector linear space over the field K. This function is used in the estimates of accuracy of the Poisson approximation for the distribution of the number of solutions of systems of random equations and random inclusions over K. For the case when K = GF(2) and H is a sphere or ball ...

Vasin, Anton R.
Published in
Discrete Mathematics and Applications

We study the frequencies of tuples in linear recurring sequences (LRS) of vectors over Galois rings. By means of an estimate of an exponential sum some nontrivial bounds on the frequencies of elements in LRS are derived. It is shown that these bounds are in some cases sharper than known results.

Pavlov, Yurii L. Cheplyukova, Irina A.
Published in
Discrete Mathematics and Applications

We consider configuration graphs with N vertices. The degrees of vertices are independent identically distributed random variables having the power-law distribution with positive parameter τ. $\tau .$We study properties of random graphs such that the sum of vertex degrees does not exceed n and the parameter is a random variable uniformly distribute...

Timashev, Aleksandr N.
Published in
Discrete Mathematics and Applications

We consider problems on the convergence of distributions of the total number of components and numbers of components with given volume to the Poisson law. Sufficient conditions of such convergence are given. Our results generalize known statemets on the limit Poisson laws of the number of components (cycles, unrooted and rooted trees, blocks and ot...