首页    期刊浏览 2024年11月09日 星期六
登录注册

文章基本信息

  • 标题:General Ramified Recurrence is Sound for Polynomial Time
  • 本地全文:下载
  • 作者:Ugo Dal Lago ; Simone Martini ; Margherita Zorzi
  • 期刊名称:Electronic Proceedings in Theoretical Computer Science
  • 电子版ISSN:2075-2180
  • 出版年度:2010
  • 卷号:23
  • 页码:47-62
  • DOI:10.4204/EPTCS.23.4
  • 出版社:Open Publishing Association
  • 摘要: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 take at most one argument. 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 sharing of identical subterms can be exploited.
国家哲学社会科学文献中心版权所有