RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. RAN. Ser. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Izv. Akad. Nauk SSSR Ser. Mat., 1991, Volume 55, Issue 2, Pages 227–253 (Mi izv1008)  

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

On ways of characterizing complete sets

V. K. Bulitko


Abstract: The traditional method for constructing criteria for completeness with respect to reducibility is by describing the property of (in general, weakened) productiveness satisfied by the complement of a set which is complete with respect to the given reducibility. Originally this property was tied to the reducibility of a creative set to the complete set. Such a method appeals directly to the universality of the creative set in the class of all recursively enumerable sets.
However, for several reducibilities it is possible to determine the completeness of a recursively enumerable set from the fact that a certain set of degree below the degree of the creative sets is reducible to the given set. This second, “test” set is, of course, not recursively enumerable. In addition, in place of the property of effective nonrecursive enumerability which productive sets have, it is possible to substitute variants of the property of diagonal nonrecursiveness, although not for all reducibilities.
In this paper we examine the connection between these two approaches – specifically, between different weakenings of the property of productiveness on the one hand, and diagonal nonrecursiveness on the other – and we present results obtained by these methods for Turing and truth-table reducibilities.

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

English version:
Mathematics of the USSR-Izvestiya, 1992, 38:2, 225–249

Bibliographic databases:

UDC: 517.11+518.5
MSC: 03D25
Received: 27.12.1988

Citation: V. K. Bulitko, “On ways of characterizing complete sets”, Izv. Akad. Nauk SSSR Ser. Mat., 55:2 (1991), 227–253; Math. USSR-Izv., 38:2 (1992), 225–249

Citation in format AMSBIB
\Bibitem{Bul91}
\by V.~K.~Bulitko
\paper On ways of characterizing complete sets
\jour Izv. Akad. Nauk SSSR Ser. Mat.
\yr 1991
\vol 55
\issue 2
\pages 227--253
\mathnet{http://mi.mathnet.ru/izv1008}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1133297}
\zmath{https://zbmath.org/?q=an:0743.03032}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?1992IzMat..38..225B}
\transl
\jour Math. USSR-Izv.
\yr 1992
\vol 38
\issue 2
\pages 225--249
\crossref{https://doi.org/10.1070/IM1992v038n02ABEH002197}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1992HR86300001}


Linking options:
  • http://mi.mathnet.ru/eng/izv1008
  • http://mi.mathnet.ru/eng/izv/v55/i2/p227

    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
    Erratum

    This publication is cited in the following articles:
    1. V. K. Bulitko, “Letter to the editor”, Russian Acad. Sci. Izv. Math., 41:1 (1993), 185–185  mathnet  crossref  mathscinet  zmath  adsnasa
    2. R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $sQ$-completeness”, Math. Notes, 62:3 (1997), 356–359  mathnet  crossref  crossref  mathscinet  zmath  isi
    3. R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $bsQ$-completeness”, Math. Notes, 68:4 (2000), 476–480  mathnet  crossref  crossref  mathscinet  zmath  isi
  • Известия Академии наук СССР. Серия математическая Izvestiya: Mathematics
    Number of views:
    This page:149
    Full text:60
    References:26
    First page:1

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