?
Delay in networks of functional elements in a model with an arbitrary distribution of basis element input delays
Computational Mathematics and Modeling. 2012. Vol. 23. No. 4. P. 487-506.
Lozhkin S. A., Danilov B.R.
The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements may have different input delays. Asymptotic bounds of the form τ B n±O(1), where τ B is a constant that depends only on the basis B, are obtained for the delay ofamultiplexerfunctionoforder n, i.e., afunctionwith n addressinputsand 2 n datainputswhosevalue equals the data input with index formed by the binary values of the address inputs. These bounds are used in the given model to obtain high-accuracy asymptotic bounds of the form τ B (n − loglogn) ± O(1) for the corresponding Shannon function, i.e., for the delay of the “worst” Boolean function of the given n variables.
Ложкин С. А., Danilov B. R., Прикладная математика и информатика 2011 № 39 С. 107-129
The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements may have different input delays. Asymptotic bounds of the form τ_B n ± O(1), where τ_B is a constant that depends only on the basis B, are obtained for ...
Added: December 2, 2019
Ложкин С. А., Шуплецов М. С., Коноводов В. А. et al., Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС) 2016 Т. 1 С. 40-47
The synthesis of optimal or suboptimal switching circuits is an actual problem of theory of discrete control
systems. Libraries of such circuits could be used in various algorithms of logic synthesis (e.g., see [1]). The structure
analysis of optimal circuits for functions of few variables may be useful in the development of standard cell libraries.
The first catalogs ...
Added: December 2, 2019
Danilov B.R., Lozhkin S. A., Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 129-136
The article proposes a synthesis method for amplifying networks of functional elements (ANFE) that establishes the asymptotic behavior of the Shannon function for th ANFE generalized depth, i.e., the depth of the "worst" Boolean function of n given variables, in a special basis (the depth model) where the element depth is determined both by its ...
Added: December 1, 2019
Danilov B. R., Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика 2013 Т. 4 С. 25-33
В~работе изучается модель задержки схем из функциональных элементов в произвольном конечном полном базисе~$\lBase$, в которой задержки базисных элементов задаются произвольными положительными действительными числами для каждого входа и каждого входного набора переменных, поступающих на остальные входы. В~рассматриваемой модели для задержки мультиплексорной функции порядка~$n$ получены асимптотические оценки вида~$\tau_{\lBase} n \pm O(\log n)$, где~$\tau_{\lBase}$ "--- константа, зависящая только ...
Added: December 2, 2019
Danilov B. R., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2015 Т. 4 № 36 С. 58-77
Background
The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem ...
Added: December 2, 2019
Danilov B. R., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2014 Т. 3 № 31 С. 78-100
Background
The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem ...
Added: December 2, 2019
М. : МАКС Пресс, 2017
The collection represents proceedings of the XVIII international conference “Problems of Theoretical Cybernetics” (Penza, 19–23 June, 2017), that is sponsored by Russian Foundation for Basic Research (project N 17-01-20217-г). The conference subject area includes: control systems synthesis, complexity, reliability, and diagnostics; automata; computer languages and programming; graph theory; combinatorics; coding theory; theory of pattern recognition; ...
Added: August 25, 2017
Sysoeva L., Вестник Московского университета. Серия 1: Математика. Механика 2019 № 6 С. 51-55
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n > 0.
Построен пример инициального булева автомата с минимальным количеством константных состояний и n входами, реализующего максимальное возможное число булевых функций от n фиксированных переменных, при ...
Added: October 14, 2018
Danilov B.R., Moscow University Computational Mathematics and Cybernetics 2013 Vol. 37 No. 4 P. 180-188
The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements delays are arbitrary positive real numbers that are specified for each input and each set of boolean variables supplied on the other inputs. Asymptotic bounds of the form τ ...
Added: December 2, 2019
М. : МАКС Пресс, 2015
The collection represents proceedings of the nineth international conference "Discrete Models in Control Systems Theory" that is held by Lomonosov Moscow State Uneversity and is dedicated in 90th anniversary of Sergey Vsevolodovich Yablonsky's birth. The conference subject are includes: discrete functional systems; discrete functions properties; control systems synthesis, complexity, reliability, and diagnostics; automata; graph theory; ...
Added: March 28, 2015
М. : Изд-во механико-математического факультета МГУ, 2016
Сборник содержит материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О.Б. Лупанова, проходившего на механико-математическом факультете МГУ имени М. В. Ломоносова с 20 по 25 июня 2016 г. при поддержке Российского фонда фундаментальных исследований (проект 16–01–20345). Для студентов, аспирантов и научных работников в области дискретной математики и математической кибернетики. ...
Added: August 29, 2016
Ivchenko G., Медведев Ю. И., Математические вопросы криптографии 2012 Т. 3 № 3 С. 21-34
Предлагается общая вероятностная модель для булевых функций от n переменных, задаваемая произвольной вероятностной мерой на множестве всех таких функций. Выводится характеристическая функция спектра Уолша случайной функции и находятся точные и асимптотические (при n→∞) распределения некоторых его характеристик для случая
параметрической меры. ...
Added: November 19, 2012
Fomin D., Математические вопросы криптографии 2019 Vol. 10 No. 2 P. 169-180
This work introduces new classes of 8-bit permutation based on a butterfly structure. These classes set up a new way for generating 2n-bit permutation from n-bit ones. We introduce some classes that contain permutations with good cryptographic properties and could be efficiently implemented for hardware and software applications. ...
Added: May 4, 2019
М. : МАКС Пресс, 2017
The collection represents proceedings of the XVIII international conference “Problems of Theoretical Cybernetics” (Penza, 19–23 June, 2017), that is sponsored by Russian Foundation for Basic Research (project N 17-01-20217-г). The conference subject area includes: control systems synthesis, complexity, reliability, and diagnostics; automata; computer languages and programming; graph theory; combinatorics; coding theory; theory of pattern recognition; ...
Added: September 21, 2017
Sysoeva L., Moscow University Mathematics Bulletin 2016 Vol. 71 No. 4 P. 140-145
The problem of realization of Boolean functions by initial Boolean automata with two constant states and n inputs is considered. An initial Boolean automaton with two constant states and n inputs is an initial automaton with output such that in all states the output functions are n-ary constant Boolean functions 0 or 1. The maximum ...
Added: February 28, 2017
Sysoeva L., Вестник Московского университета. Серия 1: Математика. Механика 2016 № 4 С. 12-17
The problem of realization of Boolean functions by initial Boolean automata with two constant states and n inputs is considered. Initial Boolean automaton with two constant states and n inputs is an initial automaton with output such that in all states output functions are n-ary constant Boolean functions 0 or 1. The maximum cardinality of ...
Added: February 28, 2017
Коврижных М. А., Fomin D., Прикладная дискретная математика. Приложение 2021 № 14 С. 181-184
Bijective vector Boolean functions (permuta- tions) are used as nonlinear primitives of many symmetric ciphers. In this paper, we study a generalized construction of (2m, 2m)-functions using monomial and arbitrary m-bit per- mutations as constituent elements. A heuristic algorithm for obtaining bijective Boolean functions with given nonlinearity and differential uniformity, based on this construction, is proposed. For ...
Added: September 22, 2021
Kochergin V. V., Kochergin D. V., Moscow University Mathematics Bulletin 2016 Vol. 71 No. 2 P. 55-60
The problem of the complexity of word assembly is studied. The complexity of the word refers to the minimum number of concatenation operations sufficient to obtain this word on the basis of one-letter words over a finite alphabet $A$ (repeated use of the received words is permitted). Let $L_A^c(n)$ be maximum complexity of words of ...
Added: October 8, 2018
Sysoeva L., Moscow University Mathematics Bulletin 2017 Vol. 72 No. 2 P. 61-69
The problem of realization of Boolean functions by initial Boolean automata with constant states and n inputs is considered. Such automata are those whose output function coincides with one of n-ary constant Boolean functions 0 or 1 in all states. The exact value of the maximum number of n-ary Boolean functions, where n > 1, ...
Added: May 17, 2017
Sysoeva L., Вестник Московского университета. Серия 1: Математика. Механика 2017 № 2 С. 19-28
The problem of realization of Boolean functions by initial Boolean automata with constant states and n inputs is considered. Initial Boolean automaton with constant states and n inputs is an initial automaton with output such that in all states output functions are n-ary constant Boolean functions 0 or 1. The exact value of the maximum ...
Added: February 28, 2017
Sysoeva L., Ученые записки Казанского университета. Серия: Физико-математические науки 2014 Т. 156 № 3 С. 116-122
In this paper, we consider the problem of implementation of Boolean functions by generalized alpha-formulas. The notion of generalized alpha-formula is introduced. For a given set of Boolean functions, we define the notion of a universal set of generalized alpha-formulas. We also propose the notion of dual generalized alpha-formulas and formulate the principle of duality ...
Added: November 11, 2017
Fedorov S., Математические вопросы криптографии 2019 Vol. 10 No. 2 P. 159-168
Рассматривается недавно предложенный подход к исследованию булевых функций, в основе которого лежит понятие класса Δ-эквивалентности: множества булевых функций с одной и той же функцией автокорреляции. Такая классификация представляется полезной, поскольку многие криптографические характеристики булевых функций, принадлежащих одному и тому же классу Δ-эквивалентности, одинаковы. ...
Added: September 4, 2019
Podolskii V. V., Logical Methods in Computer Science 2013 Vol. 9 No. 2 P. 1-17
An integer polynomial p of n variables is called a threshold gate for a Boolean function f of n variables if for all x∈{0,1}n f(x)=1 if and only if p(x) > 0. The weight of a threshold gate is the sum of its absolute values. In this paper we study how large a weight might be needed if ...
Added: October 20, 2014
Sysoeva L., Интеллектуальные системы. Теория и приложения 2016 Т. 20 № 4 С. 98-103
The problem of realization of Boolean functions by initial Boolean automata with constant states and n inputs is considered. Initial Boolean automaton with constant states and n inputs is an initial automaton with output such that in all states output functions are n-ary constant Boolean functions 0 or 1. All sets of the maximum cardinality ...
Added: February 28, 2017