Document RAIRO-Theor. Inf. Appl. 42, 69-82 (2008)
DOI: 10.1051/ita:2007053
A complete characterization of primitive recursive intensional behaviours
P. ValarcherLACL, Université Paris Est, France; valarcher@univ-paris12.fr
(Published online: 18 January 2008)
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.
Mathematics Subject Classification. 68Q25, 68Q55, 68W40
Key words: Intensional behaviour -- semantics -- primitive recursion
© EDP Sciences 2007