Hostname: page-component-6898cfcb55-th4rj Total loading time: 0 Render date: 2026-11-11T10:18:51.071Z 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; valarcher@univ-paris12.fr
Get access

Abstract

We give a complete characterization of the class of functions that arethe intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic caseof 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

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

Article purchase

Temporarily unavailable

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