On the structure of partially ordered sets of Boolean degrees

S. S. Marchenkov

Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 63-75

Résumé

On the set of all infinite binary sequences, we consider the simplest form of algorithmic reducibility, namely, the Boolean reducibility. Each set $Q$ of Boolean functions which contains a selector function and is closed with respect to the superposition operation of special kind generates the $Q$-reducibility and $Q$-degrees, the sets of $Q$-equivalent sequences. The $Q$-degree of a sequence $\alpha$ characterises the relative ‘informational complexity’ of the sequence $\alpha$, in a sense, $Q$ is a set of operators of information retrieval from infinite sequences. In this paper, we study the partially ordered sets $\mathcal L_Q$ of all $Q$-degrees for the most important classes $Q$ of Boolean functions. We investigate the positions of periodic and narrow $Q$-degrees in $\mathcal L_Q$, find the number of minimal elements and atoms and also the initial segments isomorphic to given finite lattices. This research was supported by the Russian Foundation for Basic Research, grant 03–01–00783.