Istituto di Scienza e Tecnologie dell'Informazione     
Degano P., Sirovich F. On solving the equivalence problem for a subclass of primitive recursive functions. Gia' apparsa come nota scientifica dell'Istituto di Scienze dell'Informazione, Universita di Pisa, giugno. Dicembre 1979. Internal note IEI-B79-34, 1979.
In the paper we constructively define the sub-class P of primitive recursive functions which can be defined from the base functions 0, s, x+y and x.y, and closed under composition. We show that the equivalence problem for P is solvable by reducing the function definitions according to a Church-Rosser Noetherian term rewriting system and testing the resulting irreducuble terms for identity. Finally, we define an effective mapping from primitive recursive definitions to the definitions of the class P.
Subject equivalence of functions
primitive recursive functions
term rewriting systems
Church-Rosser and Noetherian properties

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional