You are here: Home :: Area NEM :: Mathematics

S. S. Marchenkov

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 ?_Q of all Q-degrees, namely, the existence of maximal, minimal and the greatest elements, infinite chains and antichains, and upper bounds.

Discrete Mathematics and Applications, Walter de Gruyter

Print ISSN: 0924-9266
Volume: 13, 08/2003
Pages: 331 - 342

Show full article (external site)

Show all available items of this journal

 

Area NEM