Boolean reducibility
Sergey Seraphimovich Marchenkov · Discrete Mathematics and Applications · 2003
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 ℒ Q of all Q -degrees, namely, the existence of maximal, minimal and the greatest elements, infinite chains and antichains, and upper bounds.