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
topHow 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).
- 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).
- L. Colson, 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. I314 (1992).
- T. Crolard, S. Lacas and P. Valarcher, 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).
- R. David, On the asymptotic behaviour of primitive recursive algorithms. Theor. Comput. Sci.266 (2001) 159–193.
- 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 News24 (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).
- Y.N. Moschovakis, On primitive recursive algorithms and the greatest common divisor function. Theor. Comput. Sci.301 (2003) 1–30.
- 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 ?
topYou 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.