A complete characterization of primitive recursive intensional behaviours

P. Valarcher

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.