УДК 519.714
О сложности реализации булевых функций из некоторых классов, связанных с конечными грамматиками, формулами глубины альтернирования 3 / С. А. Ложкин, В. А. Коноводов. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2014. № 3. С. 14-19.
Исследуется сложность реализации булевых функций, связанных с конечными грамматиками, в классе формул с глубиной альтернирования 3. Для соответствующей функции Шеннона получены асимптотические оценки высокой степени точности.
Ключевые слова: булевы формулы, сложность, глубина альтернирования, функция Шеннона, оценки высокой степени точности.
Библиогр. 8.
