A complete characterization of primitive recursive intensional behaviours
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 69-82.

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.

DOI : https://doi.org/10.1051/ita:2007053
Classification : 68Q25,  68Q55,  68W40
Mots clés : intensional behaviour, semantics, primitive recursion
@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},
     pages = {69--82},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {1},
     year = {2008},
     doi = {10.1051/ita:2007053},
     zbl = {1148.68388},
     mrnumber = {2382552},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007053/}
}
TY  - JOUR
AU  - Valarcher, P.
TI  - A complete characterization of primitive recursive intensional behaviours
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
DA  - 2008///
SP  - 69
EP  - 82
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007053/
UR  - https://zbmath.org/?q=an%3A1148.68388
UR  - https://www.ams.org/mathscinet-getitem?mr=2382552
UR  - https://doi.org/10.1051/ita:2007053
DO  - 10.1051/ita:2007053
LA  - en
ID  - ITA_2008__42_1_69_0
ER  - 
Valarcher, P. A complete characterization of primitive recursive intensional behaviours. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 69-82. doi : 10.1051/ita:2007053. http://www.numdam.org/articles/10.1051/ita:2007053/

[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

[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).

Cité par Sources :