RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

 Diskr. Mat., 2006, Volume 18, Issue 1, Pages 63–75 (Mi dm32)

On the structure of partially ordered sets of Boolean degrees

S. S. Marchenkov

Abstract: 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.

DOI: https://doi.org/10.4213/dm32

Full text: PDF file (1356 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2006, 16:1, 87–97

Bibliographic databases:

UDC: 519.716

Citation: S. S. Marchenkov, “On the structure of partially ordered sets of Boolean degrees”, Diskr. Mat., 18:1 (2006), 63–75; Discrete Math. Appl., 16:1 (2006), 87–97

Citation in format AMSBIB
\Bibitem{Mar06} \by S.~S.~Marchenkov \paper On the structure of partially ordered sets of Boolean degrees \jour Diskr. Mat. \yr 2006 \vol 18 \issue 1 \pages 63--75 \mathnet{http://mi.mathnet.ru/dm32} \crossref{https://doi.org/10.4213/dm32} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2254735} \zmath{https://zbmath.org/?q=an:1103.94038} \elib{https://elibrary.ru/item.asp?id=9188332} \transl \jour Discrete Math. Appl. \yr 2006 \vol 16 \issue 1 \pages 87--97 \crossref{https://doi.org/10.1515/156939206776241237} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33744823047} 

• http://mi.mathnet.ru/eng/dm32
• https://doi.org/10.4213/dm32
• http://mi.mathnet.ru/eng/dm/v18/i1/p63

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. S. S. Marchenkov, “Complete and incomplete Boolean degrees”, Problems Inform. Transmission, 46:4 (2010), 346–352
2. S. S. Marchenkov, “On maximal and minimal elements in partially ordered sets of Boolean degrees”, J. Appl. Industr. Math., 7:4 (2013), 549–556
•  Number of views: This page: 301 Full text: 151 References: 33 First page: 1