Modelirovanie i Analiz Informatsionnykh Sistem
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






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


Modelirovanie i Analiz Informatsionnykh Sistem, 2022, Volume 29, Number 2, Pages 104–114
DOI: https://doi.org/10.18255/1818-1015-2022-2-104-114
(Mi mais770)
 

Discrete mathematics in relation to computer science

Enumeration degrees of the bounded sets

B. Y. Solon

Ivanovo State University, 39 Ermaka str, Ivanovo 153025, Russia
References:
Abstract: The term “total enumeration degree” is related to the fact that the $e$-degree is total if and only if it contains a graph of some total function. In a number of works by the author and a group of mathematicians from the University of Wisconsin-Madison, the so-called “graph-cototal enumeration degrees” were considered, i.e. $e$-degrees containing the complement of the graph of some total function $f(x)$. In this article, the next step is taken – the enumeration degrees of sets bounded from above or below by a graph of a total function are considered. More precisely, the set $A$ is bounded from above if $A=\{\langle x,y\rangle:y < f(x)\}$ for some total function $f(x)$ and the set $A$ is bounded from below if $A=\{\langle x,y\rangle:y > f(x)\}$ for some total function $f(x)$.
The article presents a number of results showing the existence of nontotal enumeration degrees containing bounded sets, and the constructed $e$-degrees are quasi-minimal. An important result is the one stating that bounded sets have the Friedberg property related to the jump inversion.
Keywords: enumeration degrees, quasi-minimal enumeration degrees, bounded sets.
Received: 27.04.2022
Revised: 23.05.2022
Accepted: 25.05.2022
Bibliographic databases:
Document Type: Article
UDC: 510.676, 519.7
MSC: 03D25
Language: Russian
Citation: B. Y. Solon, “Enumeration degrees of the bounded sets”, Model. Anal. Inform. Sist., 29:2 (2022), 104–114
Citation in format AMSBIB
\Bibitem{Sol22}
\by B.~Y.~Solon
\paper Enumeration degrees of the bounded sets
\jour Model. Anal. Inform. Sist.
\yr 2022
\vol 29
\issue 2
\pages 104--114
\mathnet{http://mi.mathnet.ru/mais770}
\crossref{https://doi.org/10.18255/1818-1015-2022-2-104-114}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=4456625}
Linking options:
  • https://www.mathnet.ru/eng/mais770
  • https://www.mathnet.ru/eng/mais/v29/i2/p104
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025