Hierarchies of function classes defined by the first-value operator
Hemmerling, Armin
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 253-270 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

The first-value operator assigns to any sequence of partial functions of the same type a new such function. Its domain is the union of the domains of the sequence functions, and its value at any point is just the value of the first function in the sequence which is defined at that point. In this paper, the first-value operator is applied to establish hierarchies of classes of functions under various settings. For effective sequences of computable discrete functions, we obtain a hierarchy connected with Ershov’s one within Δ 2 0 . The non-effective version over real functions is connected with the degrees of discontinuity and yields a hierarchy related to Hausdorff’s difference hierarchy in the Borel class Δ 2 B . Finally, the effective version over approximately computable real functions forms a hierarchy which provides a useful tool in computable analysis.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2007031
Classification:  03D55,  03D65,  03E15,  03F60 
@article{ITA_2008__42_2_253_0,
     author = {Hemmerling, Armin},
     title = {Hierarchies of function classes defined by the first-value operator},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {253-270},
     doi = {10.1051/ita:2007031},
     mrnumber = {2401261},
     zbl = {1146.03032},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_2_253_0}
}

Hemmerling, Armin. Hierarchies of function classes defined by the first-value operator. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 253-270. doi : 10.1051/ita:2007031. http://gdmltest.u-ga.fr/item/ITA_2008__42_2_253_0/

[1] V. Brattka, Effective Borel measurability and reducibility of functions. Math. Logic Quart. 51 (2005) 19-44. | MR 2099383 | Zbl 1059.03074

[2] R. Engelking, General topology. Heldermann Verlag, Berlin (1989). | MR 1039321 | Zbl 0684.54001

[3] R.L. Epstein, R. Haas and R.L. Kramer, Hierarchies of sets and degrees below 0 ' , in Logic Year 1979/80, Univ. of Connecticut, edited by M. Lerman, J.H. Schmerl and R.I. Soare. Lect. Notes Math. 859 32-48. | MR 619859 | Zbl 0467.03046

[4] Yu. L. Ershov, A hierarchy of sets. I; II; III. Algebra Logica 7 (1968) 15-47. Algebra Logica 7 (1968) 47-74. Algebra Logica 9 (1970) 34-51 (English translation by Plenum P.C.). | MR 270912 | Zbl 0233.02017

[5] F. Hausdorff, Grundzüge der Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig (1914); Reprint: Chelsea P.C., New York (1949). | JFM 45.0123.01 | MR 31025

[6] F. Hausdorff, Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig (1927). | JFM 53.0169.01

[7] A. Hemmerling, Approximate decidability in Euclidean spaces. Math. Logic Quart. 49 (2003) 34-56. | MR 1952430 | Zbl 1024.03045

[8] A. Hemmerling, Characterizations of the class Δ 2 ta over Euclidean spaces. Math. Logic Quart. 50 (2004) 507-519. | MR 2090395 | Zbl 1058.03045

[9] A. Hemmerling, The Hausdorff-Ershov hierarchy in Euclidean spaces. Arch. Math. Logic 45 (2006) 323-350. | MR 2209561 | Zbl 1095.03031

[10] P. Hertling, Unstetigkeitsgrade von Funktionen in der effektiven Analysis. Dissertation. Informatik Berichte 208-11/1996, Fern-Uni Hagen (1996).

[11] P. Hertling, Topological complexity with continuous operations. J. Complexity 12 (1996) 315-338. | MR 1422714 | Zbl 0862.68060

[12] P. Hertling and K. Weihrauch, Levels of degeneracy and exact lower complexity bounds for geometric algorithms, in Proc. of the 6th Canadian Conf. on Computational Geometry, Saskatoon (1994) 237-242.

[13] A.S. Kechris, Classical descriptive set theory. Springer Verlag, New York (1995). | MR 1321597 | Zbl 0819.04002

[14] K.-I. Ko, Complexity theory of real functions. Birkhäuser, Boston (1991). | MR 1137517 | Zbl 0791.03019

[15] K.-I. Ko and H. Friedman, Computational complexity of real functions. Theoret. Comput. Sci. 20 (1982) 323-352. | MR 666209 | Zbl 0498.03047

[16] C. Kreitz and K. Weihrauch, Complexity theory on real numbers and functions. Lect. Notes. Comput. Sci. 145 (1982) 165-174. | Zbl 0501.03025

[17] Y.N. Moschovakis, Descriptive set theory. North-Holland, Amsterdam (1980). | MR 561709 | Zbl 0433.03025

[18] P. Odifreddi, Classical recursion theory. North-Holland, Amsterdam (1989). | MR 982269 | Zbl 0661.03029

[19] H. Rogers Jr., Theory of recursive functions and effective computability. McGraw-Hill, New York (1967). | MR 224462 | Zbl 0183.01401

[20] V.L. Selivanov, Wadge degrees of ω-languages of deterministic Turing machines. RAIRO-Theor. Inf. Appl. 37 (2003) 67-84. | Numdam | MR 1991752 | Zbl 1048.03031

[21] R.I. Soare, Recursively enumerable sets and degrees. Springer-Verlag, Berlin (1987). | MR 882921 | Zbl 0667.03030

[22] K. Weihrauch, Computable analysis. Springer-Verlag, Berlin (2000). | MR 1795407 | Zbl 0956.68056