УДК 519.714

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

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

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

Библиогр. 8.

К оглавлению номера  Go!