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

文章基本信息

  • 标题:Observation of implicit complexity by non confluence
  • 本地全文:下载
  • 作者:Guillaume Bonfante
  • 期刊名称:Electronic Proceedings in Theoretical Computer Science
  • 电子版ISSN:2075-2180
  • 出版年度:2010
  • 卷号:23
  • 页码:15-29
  • DOI:10.4204/EPTCS.23.2
  • 出版社:Open Publishing Association
  • 摘要:We propose to consider non confluence with respect to implicit complexity. We come back to some well known classes of first-order functional program, for which we have a characterization of their intentional properties, namely the class of cons-free programs, the class of programs with an interpretation, and the class of programs with a quasi-interpretation together with a termination proof by the product path ordering. They all correspond to PTIME. We prove that adding non confluence to the rules leads to respectively PTIME, NPTIME and PSPACE. Our thesis is that the separation of the classes is actually a witness of the intentional properties of the initial classes of programs.
国家哲学社会科学文献中心版权所有