Hierarchies of function classes defined by the first-value operator

Armin Hemmerling

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

  • Volume: 42, Issue: 2, page 253-270
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Hemmerling, Armin. "Hierarchies of function classes defined by the first-value operator." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 42.2 (2008): 253-270. <http://eudml.org/doc/244667>.

@article{Hemmerling2008,
abstract = {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 $\Delta ^\{0\}_2$. 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 $\Delta ^\{B\}_2$. Finally, the effective version over approximately computable real functions forms a hierarchy which provides a useful tool in computable analysis.},
author = {Hemmerling, Armin},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {hierarchies of functions; degree of discontinuity; computable analysis; effective descriptive set theory; Hausdorff hierarchy; Ershov hierarchy},
language = {eng},
number = {2},
pages = {253-270},
publisher = {EDP-Sciences},
title = {Hierarchies of function classes defined by the first-value operator},
url = {http://eudml.org/doc/244667},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Hemmerling, Armin
TI - Hierarchies of function classes defined by the first-value operator
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2008
PB - EDP-Sciences
VL - 42
IS - 2
SP - 253
EP - 270
AB - 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 $\Delta ^{0}_2$. 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 $\Delta ^{B}_2$. Finally, the effective version over approximately computable real functions forms a hierarchy which provides a useful tool in computable analysis.
LA - eng
KW - hierarchies of functions; degree of discontinuity; computable analysis; effective descriptive set theory; Hausdorff hierarchy; Ershov hierarchy
UR - http://eudml.org/doc/244667
ER -

References

top
  1. [1] V. Brattka, Effective Borel measurability and reducibility of functions. Math. Logic Quart. 51 (2005) 19–44. Zbl1059.03074MR2099383
  2. [2] R. Engelking, General topology. Heldermann Verlag, Berlin (1989). Zbl0684.54001MR1039321
  3. [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. Zbl0467.03046MR619859
  4. [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.). Zbl0233.02017MR270912
  5. [5] F. Hausdorff, Grundzüge der Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig (1914); Reprint: Chelsea P.C., New York (1949). MR31025JFM45.0123.01
  6. [6] F. Hausdorff, Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig (1927). JFM53.0169.01
  7. [7] A. Hemmerling, Approximate decidability in Euclidean spaces. Math. Logic Quart. 49 (2003) 34–56. Zbl1024.03045MR1952430
  8. [8] A. Hemmerling, Characterizations of the class Δ 2 t a over Euclidean spaces. Math. Logic Quart. 50 (2004) 507–519. Zbl1058.03045MR2090395
  9. [9] A. Hemmerling, The Hausdorff-Ershov hierarchy in Euclidean spaces. Arch. Math. Logic 45 (2006) 323–350. Zbl1095.03031MR2209561
  10. [10] P. Hertling, Unstetigkeitsgrade von Funktionen in der effektiven Analysis. Dissertation. Informatik Berichte 208-11/1996, Fern-Uni Hagen (1996). 
  11. [11] P. Hertling, Topological complexity with continuous operations. J. Complexity 12 (1996) 315–338. Zbl0862.68060MR1422714
  12. [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. [13] A.S. Kechris, Classical descriptive set theory. Springer Verlag, New York (1995). Zbl0819.04002MR1321597
  14. [14] K.-I. Ko, Complexity theory of real functions. Birkhäuser, Boston (1991). Zbl0791.03019MR1137517
  15. [15] K.-I. Ko and H. Friedman, Computational complexity of real functions. Theoret. Comput. Sci. 20 (1982) 323–352. Zbl0498.03047MR666209
  16. [16] C. Kreitz and K. Weihrauch, Complexity theory on real numbers and functions. Lect. Notes. Comput. Sci. 145 (1982) 165–174. Zbl0501.03025
  17. [17] Y.N. Moschovakis, Descriptive set theory. North-Holland, Amsterdam (1980). Zbl0433.03025MR561709
  18. [18] P. Odifreddi, Classical recursion theory. North–Holland, Amsterdam (1989). Zbl0661.03029MR982269
  19. [19] H. Rogers Jr., Theory of recursive functions and effective computability. McGraw-Hill, New York (1967). Zbl0183.01401MR224462
  20. [20] V.L. Selivanov, Wadge degrees of ω -languages of deterministic Turing machines. RAIRO-Theor. Inf. Appl. 37 (2003) 67–84. Zbl1048.03031MR1991752
  21. [21] R.I. Soare, Recursively enumerable sets and degrees. Springer-Verlag, Berlin (1987). Zbl0667.03030MR882921
  22. [22] K. Weihrauch, Computable analysis. Springer-Verlag, Berlin (2000). Zbl0956.68056MR1795407

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.