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