Artículo

Artículo de Acceso Abierto. Puede ser descargado en su versión final
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Registro:

Documento: Artículo
Título:Recursion and topology on 2≤ω for possibly infinite computations
Autor:Becher, V.; Grigorieff, S.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina
LIAFA, Université Paris 7, France
UFR d'Informatique, Universite Paris 7, 2 Place Jussieu, Paris Cedex 05 F-75251, France
Palabras clave:Computer science; Problem solving; Set theory; Theorem proving; Topology; Turing machines; Computable maps; Infinite words; Metric spaces; Computability and decidability
Año:2004
Volumen:322
Número:1 SPEC ISS
Página de inicio:85
Página de fin:136
DOI: http://dx.doi.org/10.1016/j.tcs.2004.03.026
Handle:http://hdl.handle.net/20.500.12110/paper_03043975_v322_n1SPECISS_p85_Becher
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v322_n1SPECISS_p85_Becher.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v322_n1SPECISS_p85_Becher

Referencias:

  • Becher, V., Grigorieff, S., Recursion and Topology on 2≤ω (II): Effective Wadge Reductions, , in preparation
  • Becher, V., Grigorieff, S., Recursion and Topology on 2≤ω (III): Partial Maps, , in preparation
  • Becher, V., Grigorieff, S., θ′ -Random Reals and Outputs of Possibly Infinite Computations, , submitted for publication
  • Boasson, L., Nivat, M., Adherences of languages (1980) J. Comput. System Sci., 20, pp. 285-309
  • Bourbaki, N., (1965) Topologie Générale, , Livre III, Chap. 1, 4ème éd., Hermann, Paris. English translation available
  • Brattka, V., Recursive characterization of computable real-valued functions and relations (1996) Theoret. Comput. Sci., 162, pp. 45-77
  • Brattka, V., Bibliography on Constructivity, Computability and Complexity in Analysis, , http://cca-net.de/publications/bibliography.html
  • Chaitin, G.J., A theory of program size formally identical to information theory (1975) J. ACM, 22, pp. 329-340. , http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
  • Chaitin, G.J., Algorithmic entropy of sets (1976) Comput. Math. Appl., 2, pp. 233-245. , http://www.cs.auckland.ac.nz/CDMTCS/chaitin/#PL
  • Duparc, J., Wadge hierarchy and Veblen hierarchy, Part I: Borel sets of finite rank (2001) J. Symbolic Logic, 66 (1), pp. 56-86
  • Engelfriet, J., Hoogeboom, H.J., X-automata on ω -words (1993) Theoret. Comput. Sci., 110, pp. 1-51
  • Ershov, Y., Computable functionals of finite type (1972) Algebra and Logic, 11 (4), pp. 203-242
  • Ferbus-Zanda, M., Grigorieff, S., Refinement of the "up to a constant" ordering using constructive co-immunity Application to the Oracular Min/Max Hierarchy of Kolmogorov Complexity, , in preparation
  • Freund, R., Staiger, L., Numbers defined by turing machines (1996) Annals of the Kurt Gödel Society, 2, pp. 118-137. , http://www.informatik.uni-halle.de/~staiger/, Collegium Logicum
  • Grzegorczyk, A., Computable functionals (1955) Fund. Math., 42, pp. 168-202
  • Grzegorczyk, A., On the definition of computable functionals (1955) Fund. Math., 42, pp. 232-239
  • Grzegorczyk, A., On the definition of computable real continuous functions (1957) Fund. Math., 44, pp. 61-71
  • Head, T., The adherences of languages as topological spaces (1985) Lecture Notes in Computer Science, 192, pp. 147-163. , M. Nivat, D. Perrin (Eds.), Automata and Infinite Words, Springer, Berlin
  • Head, T., The topological structure of adherence of regular languages (1986) RAIRO, Theoret. Inform. Appl., 20, pp. 31-41
  • Kechris, A.S., (1995) Classical Descriptive Set Theory, , Berlin: Springer
  • Kuratowski, K., (1966) Topology, 1. , Academic Press, New York
  • Lacombe, D., Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles I, II, III (1955) C. R. Acad. Sci. Paris., 240, pp. 2478-2480
  • Lacombe, D., Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles I, II, III (1955) C. R. Acad. Sci. Paris., 241, pp. 13-14
  • Lacombe, D., Quelques procédés de définition en topologie récursive (1958) Constructivity in Mathematics, pp. 129-158. , A. Heyting. Amsterdam: North-Holland
  • Levin, L., On the notion of random sequence (1973) Soviet Math. Dokl., 14 (5), pp. 1413-1416
  • Li, M., Vitanyi, P., (1997) An Introduction to Kolmogorov Complexity and Its Applications 2nd Edition, , Amsterdam: Springer
  • Moschovakis, Y.N., (1980) Descriptive Set Theory, , Amsterdam: North-Holland
  • Mostowski, A., On computable sequences (1957) Fund. Math., 44, pp. 37-51
  • Odifreddi, P.G., (1989) Classical Recursion Theory, 1. , North-Holland, Amsterdam
  • Perrin, D., Pin, J.E., (2004) Infinite Words, Pure and Applied Mathematics, 141. , Academic Press, New York
  • Pierce, R.S., Compact zero-dimensional metric spaces of finite type (1972) Mem. Amer. Math. Soc., 130, pp. 1-64
  • Redziejowski, R., Infinite word languages and continuous mappings (1986) Theoret. Comput. Sci., 43, pp. 59-79
  • Rogers Jr., H., (1967) Theory of Recursive Functions and Effective Computability 2nd Edition, , 1987, New York: McGraw-Hill
  • Schnorr, C.P., Process complexity and effective random tests (1973) J. Comput. System Sci., 7, pp. 376-388
  • Schnorr, C.P., A survey of the theory of random sequences (1977) Basic Problems in Methodology and Linguistics, pp. 193-210. , R.E. Butts, J. Hintikka (Eds.), D. Reidel, Dordrecht
  • Shoenfield, J.R., On degrees of unsolvability (1959) Ann. Math., 69, pp. 644-653
  • Shoenfield, J.R., Recursion theory (1993) Lecture Notes in Logic, 1. , (reprinted 2001) A. K. Peters, Natick, Massachussets
  • Solovay, R.M., On random r.e. sets (1977) Non-classical Logics, Model Theory and Computability, pp. 283-307. , A.I. Arruda, N.C.A. da Costa, & R. Chuaqui. Amsterdam: North-Holland
  • Staiger, L., Hierarchies of recursive ω -languages (1986) J. Inform. Process. Cybernet., EIK 22 (5-6), pp. 219-241
  • Staiger, L., Sequential mappings of ω -languages (1987) J. Inform. Process. Cybernet., EIK 23 (8-9), pp. 415-439
  • Staiger, L., ω -languages (1997) Handbook of Formal Languages, 3, pp. 339-387. , http://www.informatik.uni-halle.de/~staiger/, G. Rozenberg, A. Salomaa (Eds.), Springer, Berlin
  • Staiger, L., On the power of reading the whole input tape (2000) Finite Versus Infinite: Contributions to an Eternal Dilemma, Discrete Mathematics and Theoretical Computer Science, pp. 335-348. , http://www.informatik.uni-halle.de/~staiger/, C.S. Calude, Gh. Pau (Eds.), Springer, Berlin. Preprint 99-15, 1999
  • Staiger, L., Wagner, K., Rekursive Folgenmengen I (1978) Z. Math. Logik Grundlagen Math., 24, pp. 523-538
  • Turing, A., On computable numbers, with an application to the Entscheidungsproblem (1936) Proceedings of the London Mathematical Society, 2nd Series, 42, pp. 230-265. , Correction, Ibid, 43:544-546, 1937
  • Wagner, K., Arithmetische Operatoren (1976) Z. Math. Logik Grundlagen Math., 22, pp. 553-570
  • Wagner, K., Staiger, L., Recursive ω -languages (1977) Lecture Notes in Computer Science, 56, pp. 532-537. , FCT'77
  • Weihrauch, K., Type 2 recursion theory (1985) Theoret. Comput. Sci., 38, pp. 17-33
  • Weihrauch, K., (1987) Computability, , Berlin: Springer
  • Weihrauch, K., Computability on computable metric spaces (1993) Theoret. Comput. Sci., 113, pp. 191-210
  • Weihrauch, K., (2000) Computable Analysis, An introduction, , Berlin: Springer
  • Weihrauch, K., Kreitz, C., Theory of representations (1985) Theoret. Comput. Sci., 38, pp. 35-53
  • Weihrauch, K., Kreitz, C., Type 2 computational complexity of functions on Cantor space (1991) Theoret. Comput. Sci., 82, pp. 1-18
  • Zhong, N., Weihrauch, K., Computability theory of generalized functions (2003) J. ACM, 50 (4), pp. 469-505

Citas:

---------- APA ----------
Becher, V. & Grigorieff, S. (2004) . Recursion and topology on 2≤ω for possibly infinite computations. Theoretical Computer Science, 322(1 SPEC ISS), 85-136.
http://dx.doi.org/10.1016/j.tcs.2004.03.026
---------- CHICAGO ----------
Becher, V., Grigorieff, S. "Recursion and topology on 2≤ω for possibly infinite computations" . Theoretical Computer Science 322, no. 1 SPEC ISS (2004) : 85-136.
http://dx.doi.org/10.1016/j.tcs.2004.03.026
---------- MLA ----------
Becher, V., Grigorieff, S. "Recursion and topology on 2≤ω for possibly infinite computations" . Theoretical Computer Science, vol. 322, no. 1 SPEC ISS, 2004, pp. 85-136.
http://dx.doi.org/10.1016/j.tcs.2004.03.026
---------- VANCOUVER ----------
Becher, V., Grigorieff, S. Recursion and topology on 2≤ω for possibly infinite computations. Theor Comput Sci. 2004;322(1 SPEC ISS):85-136.
http://dx.doi.org/10.1016/j.tcs.2004.03.026