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 the set of positive integers.
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://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 SP - 69 EP - 82 VL - 42 IS - 1 PB - EDP-Sciences UR - http://www.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://www.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://www.numdam.org/articles/10.1051/ita:2007053/
[1] and , Domains and Lambda-Calculi. Cambridge Tracts in Theor. Comput. Sci. 46. Cambridge University Press (1998). | MR | Zbl
[2] , Séquentialité de l'évaluation formelle des lambda-expressions. 3ème Colloque International sur la Programmation, Paris (1978). | Zbl
[3] and , Sequential algorithms, deterministic parallelism, and intensional expressiveness, in 22nd Annual Symposium on POPL (1995).
[4] , About primitive recursive algorithms. Theor. Comput. Sci. 372 (1989). | MR | Zbl
[5] , About primitive recursive algorithms. Lect. Notes Comput. Sci. 83 (1991) 57-69. | Zbl
[6] and , System t, call-by-value and the minimum problem. Theor. Comput. Sci. 206 (1998). | MR | Zbl
[7] , Une preuve directe du théclvorème d'ultime obstination. C. R. Acad. Sci. Sér. I 314 (1992). | MR | Zbl
[8] , and , On the expressive power of loop language. Nordic J. Comput. 13 (2006) 46-57. | MR
[9] and , Programming language expressiveness and circuit complexity, In Internat. Conf. on the Mathematical Foundations of Programming Semantics (1996).
[10] , On the asymptotic behaviour of primitive recursive algorithms. Theor. Comput. Sci. 266 (2001) 159-193. | MR | Zbl
[11] , Generating the greatest common divisor, and limitations of primitive recursive algorithms, in Foundations of Computational Mathematics (2003) to appear. | MR | Zbl
[12] , On lazy natural numbers with applications. SIGACT News 24 (1993).
[13] , Computing minimum with primitive recursion over lists. Theor. Comput. Sci. 163 (1996). | MR | Zbl
[14] , and , Proofs and Types. Cambridge Tracts in Theor. Comput. Sci. 7. Cambridge University Press (1989). | MR | Zbl
[15] , On primitive recursive algorithms and the greatest common divisor function. Theor. Comput. Sci. 301 (2003) 1-30. | MR | Zbl
[16] , Contribution à l'etude du comportement intentionel des algorithmes: le cas de la récursion primitive. PhD. Thesis, Université P 7 (1996).
[17] , Intensionality vs. extensionality and primitive recursion. ASIAN Computing Science Conference. Lect. Notes. Comput. Sci. 1179 (1996).
Cité par Sources :
