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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 2 scientific papers (total in 2 papers)

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
Received: 20.06.2005

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet  crossref  mathscinet  isi
    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  mathnet  crossref  mathscinet
  • Дискретная математика
    Number of views:
    This page:301
    Full text:151
    References:33
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020