|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Асимптотические оценки высокой степени точности для сложности булевых формул в некоторых базисах, состоящих из элементов с прямыми и итеративными входамистатья
- Автор: Коноводов В.А.
- Сборник: Дискретные модели в теории управляющих систем. IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г
- Редакторы: Алексеев Валерий Борисович, Данилов Борис Радиславович, Романов Дмитрий Сергеевич
- Серия: ISBN 978-5-317-04970-6
- Год издания: 2015
- Место издания: МАКС Пресс Москва
- Первая страница: 110
- Последняя страница: 113
- Аннотация: Работа продолжает исследование поведения функции Шеннона для сложности формул алгебры логики в базисах, элементы которых имеют входы двух типов - прямые и итеративные. Итеративные входы служат для присоединения к ним выходов других элементов, а прямые входы являются входами формулы. Ранее было показано существование асимптотики функции Шеннона для случая полных базисов, итеративное замыкание которых содержит класс монотонных функций. В таких базисах порядок роста этой функции является "стандартным" - 2^n / log n, известен также способ нахождения константы в асимптотике. В настоящей работе показано, что для некоторых из таких базисов возможно получение асимптотических оценок высокой степени точности для соответствующей функции Шеннона, т. е. оценок, устанавливающих асимптотику второго члена ее асимптотического разложения. В частности, эти оценки могут быть получены для специальных итеративных модификаций стандартного базиса, состоящего из элементов, реализующих конъюнкцию, дизъюнкцию и отрицание.
- Добавил в систему: Коноводов Владимир Александрович