Leivant's ramified recurrence is one of the earliest examples of an implicit characterization of the polytime functions as a subalgebra of the primitive recursive functions. Leivant's result, however, is originally stated and proved only for word algebras, i.e. free algebras whose constructors have arity at most 1. This paper presents an extension of these results to ramified functions on any free algebras, provided the underlying terms are represented as graphs rather than trees, so that we could exploit the sharing of identical subterms.

General ramified recurrence is sound for polynomial time

ZORZI, Margherita
2010-01-01

Abstract

Leivant's ramified recurrence is one of the earliest examples of an implicit characterization of the polytime functions as a subalgebra of the primitive recursive functions. Leivant's result, however, is originally stated and proved only for word algebras, i.e. free algebras whose constructors have arity at most 1. This paper presents an extension of these results to ramified functions on any free algebras, provided the underlying terms are represented as graphs rather than trees, so that we could exploit the sharing of identical subterms.
2010
Tired recursion; Ramification; Term graph rewriting; Implicit computational complexity; Polynomial time
File in questo prodotto:
File Dimensione Formato  
trtap.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Dominio pubblico
Dimensione 283.98 kB
Formato Adobe PDF
283.98 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/340101
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact