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

文章基本信息

  • 标题:Polynomial Path Orders
  • 本地全文:下载
  • 作者:Martin Avanzini ; Georg Moser
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2013
  • 卷号:9
  • 期号:4
  • 页码:1
  • DOI:10.2168/LMCS-9(4:9)2013
  • 出版社:Technical University of Braunschweig
  • 摘要:This paper is concerned with the complexity analysis of constructor term rewrite systems and its ramification in implicit computational complexity. We introduce a path order with multiset status, the polynomial path order POP*, that is applicable in two related, but distinct contexts. On the one hand POP* induces polynomial innermost runtime complexity and hence may serve as a syntactic, and fully automatable, method to analyse the innermost runtime complexity of term rewrite systems. On the other hand POP* provides an order-theoretic characterisation of the polytime computable functions: the polytime computable functions are exactly the functions computable by an orthogonal constructor TRS compatible with POP*.
  • 其他关键词:Term Rewriting, Complexity Analysis, Implicit Computational Complexity, Automation.
国家哲学社会科学文献中心版权所有