A complete characterization of primitive recursive intensional behaviours
Valarcher, P.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 69-82 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2007053
Classification:  68Q25,  68Q55,  68W40 
@article{ITA_2008__42_1_69_0,
     author = {Valarcher, P.},
     title = {A complete characterization of primitive recursive intensional behaviours},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {69-82},
     doi = {10.1051/ita:2007053},
     mrnumber = {2382552},
     zbl = {1148.68388},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_1_69_0}
}

Valarcher, P. A complete characterization of primitive recursive intensional behaviours. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 69-82. doi : 10.1051/ita:2007053. http://gdmltest.u-ga.fr/item/ITA_2008__42_1_69_0/

[1] R. Amadio and P.-L. Curien, Domains and Lambda-Calculi. Cambridge Tracts in Theor. Comput. Sci. 46. Cambridge University Press (1998). | MR 1694538 | Zbl 0962.03001

[2] G. Berry, Séquentialité de l'évaluation formelle des lambda-expressions. 3ème Colloque International sur la Programmation, Paris (1978). | Zbl 0416.03017

[3] S. Brookes and D. Dancanet, Sequential algorithms, deterministic parallelism, and intensional expressiveness, in 22nd Annual Symposium on POPL (1995).

[4] L. Colson, About primitive recursive algorithms. Theor. Comput. Sci. 372 (1989). | MR 1037053 | Zbl 0744.03042

[5] L. Colson, About primitive recursive algorithms. Lect. Notes Comput. Sci. 83 (1991) 57-69. | Zbl 0744.03042

[6] L. Colson and D. Fredholm, System t, call-by-value and the minimum problem. Theor. Comput. Sci. 206 (1998). | MR 1641651 | Zbl 0912.68012

[7] T. Coquand, Une preuve directe du théclvorème d'ultime obstination. C. R. Acad. Sci. Sér. I 314 (1992). | MR 1154393 | Zbl 0749.68052

[8] T. Crolard, S. Lacas and P. Valarcher, On the expressive power of loop language. Nordic J. Comput. 13 (2006) 46-57. | MR 2248249 | Zbl pre05141410

[9] D. Dancanet and S. Brookes, Programming language expressiveness and circuit complexity, In Internat. Conf. on the Mathematical Foundations of Programming Semantics (1996).

[10] R. David, On the asymptotic behaviour of primitive recursive algorithms. Theor. Comput. Sci. 266 (2001) 159-193. | MR 1850268 | Zbl 0989.68061

[11] L. Van Den Dries, Generating the greatest common divisor, and limitations of primitive recursive algorithms, in Foundations of Computational Mathematics (2003) to appear. | MR 1989479 | Zbl 1019.03027

[12] M.H. Escardo, On lazy natural numbers with applications. SIGACT News 24 (1993).

[13] D. Fredholm, Computing minimum with primitive recursion over lists. Theor. Comput. Sci. 163 (1996). | MR 1407026 | Zbl 0874.68146

[14] P. Taylor, J.Y. Girard and Y. Lafont, Proofs and Types. Cambridge Tracts in Theor. Comput. Sci. 7. Cambridge University Press (1989). | MR 1003608 | Zbl 0671.68002

[15] Y.N. Moschovakis, On primitive recursive algorithms and the greatest common divisor function. Theor. Comput. Sci. 301 (2003) 1-30. | MR 1975218 | Zbl 1022.68129

[16] P. Valarcher, Contribution à l'etude du comportement intentionel des algorithmes: le cas de la récursion primitive. PhD. Thesis, Université P 7 (1996).

[17] P. Valarcher, Intensionality vs. extensionality and primitive recursion. ASIAN Computing Science Conference. Lect. Notes. Comput. Sci. 1179 (1996).