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 : 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},
     mrnumber = {2382552},
     zbl = {1148.68388},
     language = {en},
     url = {http://archive.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
SP  - 69
EP  - 82
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2007053/
DO  - 10.1051/ita:2007053
LA  - en
ID  - ITA_2008__42_1_69_0
ER  - 
%0 Journal Article
%A Valarcher, P.
%T A complete characterization of primitive recursive intensional behaviours
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 69-82
%V 42
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2007053/
%R 10.1051/ita:2007053
%G en
%F 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) no. 1, pp. 69-82. doi : 10.1051/ita:2007053. http://archive.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 | Zbl

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

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

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

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

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

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

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

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

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

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

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

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