# A complete characterization of primitive recursive intensional behaviours

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 1, page 69-82
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topValarcher, P.. "A complete characterization of primitive recursive intensional behaviours." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 69-82. <http://eudml.org/doc/250342>.

@article{Valarcher2008,

abstract = {
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.
},

author = {Valarcher, P.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Intensional behaviour; semantics; primitive recursion; primitive recursive algorithms},

language = {eng},

month = {1},

number = {1},

pages = {69-82},

publisher = {EDP Sciences},

title = {A complete characterization of primitive recursive intensional behaviours},

url = {http://eudml.org/doc/250342},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Valarcher, P.

TI - A complete characterization of primitive recursive intensional behaviours

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/1//

PB - EDP Sciences

VL - 42

IS - 1

SP - 69

EP - 82

AB -
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.

LA - eng

KW - Intensional behaviour; semantics; primitive recursion; primitive recursive algorithms

UR - http://eudml.org/doc/250342

ER -

## References

top- R. Amadio and P.-L. Curien, Domains and Lambda-Calculi. Cambridge Tracts in Theor. Comput. Sci.46. Cambridge University Press (1998).
- G. Berry, Séquentialité de l'évaluation formelle des lambda-expressions. 3ème Colloque International sur la Programmation, Paris (1978). Zbl0416.03017
- S. Brookes and D. Dancanet, Sequential algorithms, deterministic parallelism, and intensional expressiveness, in 22nd Annual Symposium on POPL (1995).
- L. Colson, About primitive recursive algorithms. Theor. Comput. Sci.372 (1989). Zbl0744.03042
- L. Colson, About primitive recursive algorithms. Lect. Notes Comput. Sci.83 (1991) 57–69. Zbl0744.03042
- L. Colson and D. Fredholm, System t, call-by-value and the minimum problem. Theor. Comput. Sci.206 (1998). Zbl0912.68012
- T. Coquand, Une preuve directe du théclvorème d'ultime obstination. C. R. Acad. Sci. Sér. I314 (1992). Zbl0749.68052
- T. Crolard, S. Lacas and P. Valarcher, On the expressive power of loop language. Nordic J. Comput.13 (2006) 46–57. Zbl1161.68378
- D. Dancanet and S. Brookes, Programming language expressiveness and circuit complexity, In Internat. Conf. on the Mathematical Foundations of Programming Semantics (1996).
- R. David, On the asymptotic behaviour of primitive recursive algorithms. Theor. Comput. Sci.266 (2001) 159–193. Zbl0989.68061
- L. Van Den Dries, Generating the greatest common divisor, and limitations of primitive recursive algorithms, in Foundations of Computational Mathematics (2003) to appear. Zbl1019.03027
- M.H. Escardo, On lazy natural numbers with applications. SIGACT News24 (1993).
- D. Fredholm, Computing minimum with primitive recursion over lists. Theor. Comput. Sci.163 (1996). Zbl0874.68146
- P. Taylor, J.Y. Girard and Y. Lafont, Proofs and Types. Cambridge Tracts in Theor. Comput. Sci.7. Cambridge University Press (1989).
- Y.N. Moschovakis, On primitive recursive algorithms and the greatest common divisor function. Theor. Comput. Sci.301 (2003) 1–30. Zbl1022.68129
- P. Valarcher, Contribution à l'etude du comportement intentionel des algorithmes: le cas de la récursion primitive. PhD. Thesis, Université P 7 (1996).
- P. Valarcher, Intensionality vs. extensionality and primitive recursion. ASIAN Computing Science Conference.Lect. Notes. Comput. Sci.1179 (1996).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.