Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-19T05:19:41.121Z Has data issue: false hasContentIssue false
  • English
  • Français

Effectivity and effective continuity of multifunctions

Published online by Cambridge University Press:  12 March 2014

Dieter Spreen
Dieter Spreen*
Affiliation:
Theoretische Informatik, Fachbereich Mathematik, Universität Siegen, 57068 Siegen, Germany. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

If one wants to compute with infinite objects like real numbers or data streams, continuity is a necessary requirement: better and better (finite) approximations of the input are transformed into better and better (finite) approximations of the output. In case the objects are constructively generated, they can be represented by a finite description of the generating procedure. By effectively transforming such descriptions for the generation of the input (respectively, their codes) into (the code of) a description for the generation of the output another type of computable operation is obtained. Such operations are also called effective. The relationship of both classes of operations has always been a question of great interest.

In this paper the setting is extended to the case of multifunctions. Various ways of coding (indexing) sets are discussed and their relationship is investigated. Moreover, effective versions of several continuity notions for multifunctions are introduced. For each of these notions an indexing system for sets is exhibited so that the multifunctions that are effective with respect to this indexing system are exactly the multifunction which are effectively continuous with respect to the continuity notion under consideration. Mostly, in addition to being effective the multifunctions need also possess certain witnessing functions. Important special cases are discussed where such witnessing functions always exist.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 2 , June 2010 , pp. 602 - 640
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Abramsky, S. and Jung, A., Domain theory, Handbook of logic in computer science, Vol. 3 (Abramsky, S.et al., editors), Oxford Univ. Press, New York, 1994, pp. 1–168.Google Scholar
[2]Aubin, J-P and Frankowska, H., Set-valued analysis, Birkhäuser Boston, 1990.Google Scholar
[3]Beer, G. A., Topologies on closed and closed convex sets, Kluwer, Dordrecht, 1993.CrossRefGoogle Scholar
[4]Berge, C., Topological spaces, Dover Publications, Mineola, NY, 1997.Google Scholar
[5]Berger, U., Total sets and objects in domain theory, Annals of Pure and Applied Logic, vol. 60 (1993), pp. 91–117.CrossRefGoogle Scholar
[6]Blanck, J., Domain representabilily of metric spaces, Annals of Pure and Applied Logic, vol. 83 (1997), pp. 225–247.CrossRefGoogle Scholar
[7]Blanck, J., Domain representations of topological spaces. Theoretical Computer Science, vol. 247 (2000), pp. 229–255.CrossRefGoogle Scholar
[8]Brattka, V., Random numbers and an incomplete immune recursive set, Automata, languages and programming (Widmayer, P.et al., editors), Lecture Notes in Computer Science, vol. 2380. Springer-Verlag, Berlin, 2002, pp. 950–961.CrossRefGoogle Scholar
[9]Brattka, V. and Hertling, P., Feasible real random access machines, Journal of Complexity, vol. 14 (1998), pp. 490–526.CrossRefGoogle Scholar
[10]Brattka, V. and Presser, G., Computability on subsets of metric spaces. Theoretical Computer Science, vol. 305 (2003), pp. 43–76.CrossRefGoogle Scholar
[11]Brattka, V. and Weihrauch, K., Computability on subsets of Euclidean space. I. Closed and compact subsets, Theoretical Computer Science, vol. 219 (1999), pp. 65–93.CrossRefGoogle Scholar
[12]Ceĭtin, G. S., Algorithmic operators in constructive metric spaces, Trudy Matematicheskogo Instituia imeni V. A. Steklova, vol. 67 (1962), pp. 295–361, English translation: American Mathematical Society Translation, series 2, vol. 64 (1967), pp. 1–80.Google Scholar
[13]Collins, P., Continuity and computability of reachable sets, Theoretical Computer Science, vol. 341 (2005), pp. 162–195.CrossRefGoogle Scholar
[14]Dahlgren, F., A domain theoretic approach to effective distribution theory, U.U.D.M. Report 2007:37, Uppsala University. 2007.Google Scholar
[15]Edalat, A., Domains for computation in mathematics, physics and exact real arithmetic, The Bulletin of Symbolic Logic, vol. 3 (1997), pp. 401–452.CrossRefGoogle Scholar
[16]Egli, H. and Constable, R. L.. Computability concepts for programming language semantics, Theoretical Computer Science, vol. 2 (1976), pp. 133–145.CrossRefGoogle Scholar
[17]Eršov, Yu. L., Computable functional of finite type, Algebra i Logika, vol. 11 (1972). pp. 367–437, English translation: Algebra and Logic, vol. 11 (1972), pp. 203–242.Google Scholar
[18]Eršov, Yu. L., Continuous lattices and A-spaces. Doklady Akademii Nauk SSSR, vol. 207 (1972), pp. 523–526, English translation: Soviet Mathematics Doklady, vol. 13 (1972), pp. 1551–1555.Google Scholar
[19]Eršov, Yu. L., The theory of A-spaces, Algebra i Logika, vol. 12 (1973), pp. 369–416, English translation: Algebra and Logic, vol. 12 (1973), pp. 209–232.Google Scholar
[20]Eršov, Yu. L., Theorie der Numerierungen. II, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 473–584.CrossRefGoogle Scholar
[21]Eršov, Yu. L., Theory of numberings, Nauka, Moscow, 1977, (in Russian).Google Scholar
[22]Friedberg, R., Un contre-exemple relatif aux fonctionnelles récursives, Comptes Rendus de l'Académie des Sciences, vol. 247 (1958), pp. 852–854.Google Scholar
[23]Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M., and Scott, D. S., Continuous lattices and domains, Cambridge University Press, Cambridge, 2003.CrossRefGoogle Scholar
[24]Kreisel, G., Lacombe, D., and Shoenfield, J. R., Partial recursive functionals and effective operations, Constructivity in mathematics (Heyting, A., editor), North-Holland, Amsterdam, 1957, pp. 290–297.Google Scholar
[25]Luckhardt, H., A fundamental effect in computations on real numbers, Theoretical Computer Science, vol. 5 (1977/1978), pp. 321–324.CrossRefGoogle Scholar
[26]Mal'cev, A. I., The metamathematics of algebraic systems. Collected papers: 1936–1967, North-Holland, Amsterdam, 1971.Google Scholar
[27]Melton, A., Topological spaces for Cpos, Categorical methods in computer science (Ehrig, H.et al., editors). Lecture Notes in Computer Science, vol. 393, Springer, Berlin, 1989, pp. 302–314.Google Scholar
[28]Moschovakis, Y. N., Recursive analysis, Ph.D. thesis, University of Wisconsin, Madison, Wisconsin. 1963.Google Scholar
[29]Moschovakis, Y. N., Recursive metric spaces, Fundamenta Mathematicae, vol. 55 (1964), pp. 215–238.CrossRefGoogle Scholar
[30]Myhill, J. and Shepherdson, J. C., Effective operations on partial recursive functions, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 310–317.CrossRefGoogle Scholar
[31]Pour-El, M. B. and Richards, J. I., Computability in analysis and physics, Springer-Verlag, Berlin, 1989.CrossRefGoogle Scholar
[32]Rockafellar, R. T. and Wetts, R. J.-B., Variational analysis, Springer-Verlag, Berlin, 1998.CrossRefGoogle Scholar
[33]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York, 1967.Google Scholar
[34]Sigstam, I., Formal spaces and their effective presentations, Archive for Mathematical Logic, vol. 34 (1995), pp. 211–246.CrossRefGoogle Scholar
[35]Smyth, M. B., Power domains and predicate transformers: a topological view, Automata, languages and programming (Diaz, J., editor). Lecture Notes in Computer Science, vol. 154, Springer-Verlag, Berlin, 1983, pp. 662–675.CrossRefGoogle Scholar
[36]Spreen, D., On some decision problems in programming, Information and Computation, vol. 122 (1995), pp. 120–139, corrections D. Spreen, On some decision problems in programming, Information and Computation, vol. 148 (1999), pp. 241–244.CrossRefGoogle Scholar
[37]Spreen, D., On effective topological spaces, this Journal, vol. 63 (1998), pp. 185–221, corrections D. Spreen On effective topological spaces, this Journal, vol. 65 (2000), pp. 1917–1918.Google Scholar
[38]Spreen, D., On some problems in computable topology, Logic Colloquium 2005 (Dimitracopoulos, C.et al., editors), ASL and Cambridge University Press, 2008, pp. 221–254.Google Scholar
[39]Stoltenberg-Hansen, V. and Tucker, J. V., Effective algebras, Handbook of logic in computer science, Vol. 4 (Abramsky, S.et al., editors), Clarendon Press, Oxford, 1995, pp. 357–526.CrossRefGoogle Scholar
[40]Sturm, C. F., Mémoire sur la résolution des équations numériques, Annales Mathématiques pures applicées, vol. 6 (1835), pp. 271–318.Google Scholar
[41]Tucker, J. V. and Zucker, J. I., Abstract versus concrete computation on metric partial algebras, ACM Transactions on Computational Logic, vol. 5 (2004), pp. 611–668.CrossRefGoogle Scholar
[42]Weihrauch, K., Computable analysis, an introduction, Springer, Berlin, 2000.CrossRefGoogle Scholar
[43]Weihrauch, K. and Deil, T., Berechenbarkeit auf cpo's, Schriften zur Angewandten Mathematik und Informatik, no. 63, Rheinisch-Westfälische Technische Hochschule Aachen, 1980.Google Scholar