?
Certain properties of generalized α-formulas
Moscow University Mathematics Bulletin. 2013. Vol. 68. No. 4. P. 211-214.
Sysoeva L.
Translator: V. Valedinskii
The problem of realization of Boolean functions by generalized α-formulas is considered. The notion of a universal set of generalized α-formulas is introduced for a given set of Boolean functions. Universal sets of generalized α-formulas are constructed for the set of constant-preserving Boolean functions.
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: Математика. Механика 2019 № 6 С. 51-55
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n > 0.
Построен пример инициального булева автомата с минимальным количеством константных состояний и n входами, реализующего максимальное возможное число булевых функций от n фиксированных переменных, при ...
Added: October 14, 2018
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
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., Moscow University Mathematics Bulletin 2019 Vol. 74 No. 6 P. 241-245
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 the output functions are n-ary constant Boolean functions 0 or 1. An example of an initial Boolean automaton with the minimum ...
Added: November 22, 2020
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
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., В кн. : Дискретные модели в теории управляющих систем : IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды. : М. : МАКС Пресс, 2015. С. 239-241.
Рассматривается задача о порождении булевых функций инициальными константными автоматами с двумя состояниями и n входами, то есть такими автоматами с двумя состояниями, что в любом из них функция выхода совпадает с одной из булевых функций 0 или 1. Найдена максимальная возможная мощность множества булевых функций, реализуемых константным автоматом с двумя состояниями и n входами, где n ...
Added: March 1, 2017
Sysoeva L., Вестник Московского университета. Серия 1: Математика. Механика 2013 № 4 С. 51-55
The problem of realization of Boolean functions by generalized alpha-formulas is considered. For a given set of Boolean functions universal set of generalized alpha-formulas is determined. For the set of constant-preserving Boolean functions universal sets of generalized alpha-formulas are obtained. ...
Added: November 11, 2017
Sysoeva L., В кн. : Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019). : М. : Изд-во механико-математического факультета МГУ, 2019. Гл. 3. С. 184-187.
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 example of an initial Boolean automaton with the ...
Added: October 31, 2019
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
Sysoeva L., В кн. : Материалы X молодежной научной школы по дискретной математике и ее приложениям. : М. : Издательство ИПМ РАН, 2015. С. 74-78.
В данной работе, построен пример инициального булевого автомата с тремя константными состояниями реализующего 2^{2^n} − 2^2^{n−1} − 1 различных булевых функций от n фиксированных переменных. Таким образом, в отличие от случая инициальных автоматов с двумя состояниями, среди инициальных булевых автоматов с тремя константными состояниями существуют автоматы, доля функций f(x1,x2,...,xn), реализуемых которыми, стремится к 1 с ...
Added: March 1, 2017
Sysoeva L., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 229-232.
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n>1. Получены точные оценки на максимальное число булевых функций от n фиксированных переменных, реализуемых инициальным булевым автоматом ...
Added: March 1, 2017
Sysoeva L., В кн. : Материалы XI Международного семинара «Дискретная математика и её приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.). : М. : Механико-математический факультет МГУ, 2012. С. 218-220.
В работе рассматривается задача о реализации булевых функций обобщенными альфа-формулами. Вводится понятие универсального множества обобщенных альфа-формул для заданного множества булевых функций. Показывается, что для каждого n≥2 для множества всех булевых функций от переменных, сохраняющих константы 0 и 1, существуют универсальные множества. ...
Added: November 11, 2017
Sysoeva L., В кн. : Материалы XVII международной конференции "Проблемы теоретической кибернетики". : Каз. : Отечество, 2014. С. 268-270.
В работе рассматривается задача о реализации булевых функций обобщенными альфа-формулами. Вводится понятие универсального множества обобщенных альфа-формул для заданного множества булевых функций. Формулируется принцип двойственности для обобщенных альфа-формул. Показывается, что для каждого n ≥ 2 для множеств всех булевых функций от n переменных, сохраняющих константу 0 или 1, существуют универсальные множества. ...
Added: November 11, 2017
Ivchenko G., Медведев Ю. И., Математические вопросы криптографии 2012 Т. 3 № 3 С. 21-34
Предлагается общая вероятностная модель для булевых функций от n переменных, задаваемая произвольной вероятностной мерой на множестве всех таких функций. Выводится характеристическая функция спектра Уолша случайной функции и находятся точные и асимптотические (при n→∞) распределения некоторых его характеристик для случая
параметрической меры. ...
Added: November 19, 2012
Sysoeva L., Дискретный анализ и исследование операций 2019
На множестве функций k-значной логики вводится операция автоматного замыкания: рассматриваются автоматные формулы --- формулы над конечным множеством автоматов, таких, что в каждом состоянии автомата функция выхода содержится в некотором исходном множестве функций k-значной логики. Cчитается, что автоматная формула реализует функцию k-значной логики, если при последовательной подстановке в некотором порядке всех наборов значений переменных функции в ...
Added: October 31, 2019
Ложкин С. А., 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
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
Lozhkin S. A., Danilov B.R., Computational Mathematics and Modeling 2012 Vol. 23 No. 4 P. 487-506
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
Fedorov S., Математические вопросы криптографии 2019 Vol. 10 No. 2 P. 159-168
Рассматривается недавно предложенный подход к исследованию булевых функций, в основе которого лежит понятие класса Δ-эквивалентности: множества булевых функций с одной и той же функцией автокорреляции. Такая классификация представляется полезной, поскольку многие криптографические характеристики булевых функций, принадлежащих одному и тому же классу Δ-эквивалентности, одинаковы. ...
Added: September 4, 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
Yashunsky A., Вестник Московского университета. Серия 1: Математика. Механика 2019 № 4 С. 3-9
We consider systems of Boolean functions inducing algebras of Bernoulli distributions, whose universal set has a single limit point. We establish a criterion for an algebra generated by a given set of distributions to have a unique limit point. ...
Added: September 9, 2020
Fedorov S., Логачёв О. А., Ященко В. В., Дискретная математика 2021 Т. 33 № 2 С. 66-85
Рассматривается действие на множестве булевых функций расширения G полной аффинной группы преобразований с помощью группы аффинных функций: действие заключается в преобразовании булевых функций невырожденными аффинными заменами переменных и сложением с аффинными булевыми функциями. Введены и исследованы параметры булевых функций, инвариантные относительно действия группы G: амплитуда (тесно связанная с нелинейностью), размерность функции и некоторые другие. Эти ...
Added: June 16, 2021