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] Domains and Lambda-Calculi. Cambridge Tracts in Theor. Comput. Sci. 46. Cambridge University Press (1998). | MR | Zbl
and ,[2] Séquentialité de l'évaluation formelle des lambda-expressions. 3ème Colloque International sur la Programmation, Paris (1978). | Zbl
,[3] Sequential algorithms, deterministic parallelism, and intensional expressiveness, in 22nd Annual Symposium on POPL (1995).
and ,[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] System t, call-by-value and the minimum problem. Theor. Comput. Sci. 206 (1998). | MR | Zbl
and ,[7] Une preuve directe du théclvorème d'ultime obstination. C. R. Acad. Sci. Sér. I 314 (1992). | MR | Zbl
,[8] On the expressive power of loop language. Nordic J. Comput. 13 (2006) 46-57. | MR
, and ,[9] Programming language expressiveness and circuit complexity, In Internat. Conf. on the Mathematical Foundations of Programming Semantics (1996).
and ,[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] Proofs and Types. Cambridge Tracts in Theor. Comput. Sci. 7. Cambridge University Press (1989). | MR | Zbl
, and ,[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 :