Vasiliev, Denis I. Gasanov, Élyar É. Kudryavtsev, Valerii B.
Published in
Discrete Mathematics and Applications

A dynamic system of cities with migrants is considered. The wage function is each city depends on the number of migrants in the city. The system is modeled by an automaton whose state is the vector consisting of the numbers of migrants in the cities. The transition function of the automaton reflects the conditions for transfers of migrants between ...

Zhukov, Vladimir V. Lozhkin, Sergey A.
Published in
Discrete Mathematics and Applications

Models of multi-output and scalar recursive Boolean circuits of bounded depth in an arbitrary basis are considered. Methods for lower and upper estimates for the Shannon function for the complexity of circuits of these classes are provided. Based on these methods, an asymptotic formula for the Shannon function is put forward. Moreover, in the above...

Logachev, Oleg A. Fedorov, Sergey N. Yashchenko, Valerii V.
Published in
Discrete Mathematics and Applications

A new equivalence relation on the set of Boolean functions is introduced: functions are declared to be Δ-equivalent if their autocorrelation functions are equal. It turns out that this classification agrees well with the cryptographic properties of Boolean functions: for functions belonging to the same Δ-equivalence class a number of their cryptogr...

Vasin, Anton R.
Published in
Discrete Mathematics and Applications

We study the discrepancy of linear recurring sequences over Galois rings. By means of an estimate of an exponential sum some nontrivial bounds on the discrepancy are derived. It is shown that these bounds are asymptotically not worse than known estimates for maximal period linear recurring sequences over prime fields.

Popkov, Kirill A.
Published in
Discrete Mathematics and Applications

We prove that, for n ⩾ 2, any n-place Boolean function may be implemented by a two-pole contact circuit which is irredundant and allows a diagnostic test with length not exceeding n + k(n − 2) under at most k contact breaks. It is shown that with k = k(n) ⩽ 2n−4, for almost all n-place Boolean functions, the least possible length of such a test is ...

Starostin, Mikhail V.
Published in
Discrete Mathematics and Applications

The paper is concerned with the completeness problem in implicit expressibility in a multi-valued logics Pk. For each k ≥ 2 and any nontrivial order relation on the set {0, 1, …, k − 1} we find two implicitly precomplete classes of functions which are monotone with respect to this order

Marchenkov, Sergey S.
Published in
Discrete Mathematics and Applications

A completeness criterion for the enumeration closure operator in three-valued logic is obtained, and all 13 precomplete classes are described.

Polin, Sergey V.
Published in
Discrete Mathematics and Applications

Previously, in the process of investigating systems of equations over the given family 𝔖 of quasigroup operations, the author proved the following fact: applicability of Gaussian elimination to the systems considered requires that generalized distributivity and transitivity identities hold for the operations from 𝔖. The present paper describes all ...

Pogorelov, Boris A. Pudovkina, Marina A.
Published in
Discrete Mathematics and Applications

The Jevons group AS̃n is an isometry group of the Hamming metric on the n-dimensional vector space Vn over GF(2). It is generated by the group of all permutation (n × n)-matrices over GF(2) and the translation group on Vn. Earlier the authors of the present paper classified the submetrics of the Hamming metric on Vn for n ⩾ 4, and all overgroups of...

Redkin, Nikolay P.
Published in
Discrete Mathematics and Applications

We study generalized (in terms of bases) complexity of implementation of linear Boolean functions by Boolean circuits in arbitrary functionally complete bases; the complexity of a circuit is defined as the number of gates. Let L*(n) be the minimal number of gates sufficient for implementation of an arbitrary linear Boolean function of n variables i...