General Ramified Recurrence is Sound for Polynomial Time

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

Full description

Bibliographic Details
Main Authors: Ugo Dal Lago, Simone Martini, Margherita Zorzi
Format: Article
Language:English
Published: Open Publishing Association 2010-05-01
Series:Electronic Proceedings in Theoretical Computer Science
Online Access:http://arxiv.org/pdf/1005.0521v1