С. А. Ложкин, В. А. Коноводов, “О сложности реализации булевых функций из некоторых классов, связанных с конечными грамматиками, формулами глубины альтернирования $3$”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2014, номер 3,страницы 14

Математика

О сложности реализации булевых функций из некоторых классов, связанных с конечными грамматиками, формулами глубины альтернирования $3$

С. А. Ложкин, В. А. Коноводов

Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики

Аннотация: Исследуется сложность реализации булевых функций, связанных с конечными грамматиками, в классе формул с глубиной альтернирования 3. Для соответствующей функции Шеннона получены асимптотические оценки высокой степени точности.

Ключевые слова: булевы формулы, сложность, глубина альтернирования, функция Шеннона, оценки высокой степени точности.

УДК: 519.714

Поступила в редакцию: 13.02.2013