Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T06:01:12.931Z Has data issue: false hasContentIssue false
  • English
  • Français

A complete characterization of primitive recursive intensionalbehaviours

Published online by Cambridge University Press:  18 January 2008

P. Valarcher
P. Valarcher*
Affiliation:
LACL, Université Paris Est, France; [email protected]
Get access

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.

Keywords

Intensional behavioursemanticsprimitive recursion
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 1: A nonstandard spirit among computer scientists:a tribute to Serge Grigorieff at the occasion of his 60th birthday , January 2008 , pp. 69 - 82
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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).
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).
Colson, L., About primitive recursive algorithms. Lect. Notes Comput. Sci. 83 (1991) 57–69.
L. Colson and D. Fredholm, System t, call-by-value and the minimum problem. Theor. Comput. Sci. 206 (1998).
T. Coquand, Une preuve directe du théclvorème d'ultime obstination. C. R. Acad. Sci. Sér. I 314 (1992).
Crolard, T., Lacas, S. and Valarcher, P., On the expressive power of loop language. Nordic J. Comput. 13 (2006) 46–57.
D. Dancanet and S. Brookes, Programming language expressiveness and circuit complexity, In Internat. Conf. on the Mathematical Foundations of Programming Semantics (1996).
David, R., On the asymptotic behaviour of primitive recursive algorithms. Theor. Comput. Sci. 266 (2001) 159–193. CrossRef
L. Van Den Dries, Generating the greatest common divisor, and limitations of primitive recursive algorithms, in Foundations of Computational Mathematics (2003) to appear.
M.H. Escardo, On lazy natural numbers with applications. SIGACT News 24 (1993).
D. Fredholm, Computing minimum with primitive recursion over lists. Theor. Comput. Sci. 163 (1996).
P. Taylor, J.Y. Girard and Y. Lafont, Proofs and Types. Cambridge Tracts in Theor. Comput. Sci. 7. Cambridge University Press (1989).
Moschovakis, Y.N., On primitive recursive algorithms and the greatest common divisor function. Theor. Comput. Sci. 301 (2003) 1–30. CrossRef
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).