Булева сводимость

На множестве всех бесконечных двоичных последовательностей определяется оператор булевой сводимости — вариант оператора конечно-автоматной сводимости, когда рассматриваются автоматы с несколькими входами и одним состоянием. Каждое множество $Q$ булевых функций, содержащее селекторную функцию и замкнутое относительно операции суперпозиции специального вида, определяет $Q$-сводимость и $Q$-степени — множества $Q$-эквивалентных последовательностей. В работе исследуются свойства частично упорядоченного множества $\mathcal L_Q$ всех $Q$-степеней: наличие максимальных, минимальных и наибольшего элементов, существование бесконечных цепей и антицепей, существование верхних граней.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 03–01–00783.