RAIRO-Theor. Inf. Appl.
Volume 42, Number 2, April-June 2008
|253 - 270
|25 December 2007
Hierarchies of function classes defined by the first-value operator
Ernst-Moritz-Arndt–Universität Greifswald, Institut für Mathematik und Informatik, Friedrich-Ludwig-Jahn–Str. 15a, 17487 Greifswald, Germany;
Accepted: 1 February 2007
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 . 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 . Finally, the effective version over approximately computable real functions forms a hierarchy which provides a useful tool in computable analysis.
Mathematics Subject Classification: 03D55 / 03D65 / 03E15 / 03F60
Key words: Hierarchies of functions / degree of discontinuity / computable analysis / effective descriptive set theory / Hausdorff hierarchy / Ershov hierarchy
© EDP Sciences, 2007
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.