Boolean reducibility

We define the operator of Boolean reducibility on the set of all infinite binary sequences. This operator is a variant of the operator of finite-automaton transformability when automata with several inputs and one state are considered. Each set $Q$ of Boolean functions containing a selector function and closed with respect to the operation of superposition of a special form defines the $Q$-reducibility and $Q$-degrees, that is, the sets of $Q$-equivalent sequences. We study properties of the partially ordered set $\mathcal L_Q$ of all $Q$-degrees, namely, the existence of maximal, minimal and the greatest elements, infinite chains and antichains, and upper bounds.
The research was supported by the Russian Foundation for Basic Research, grant 03–01–00783.