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

文章基本信息

  • 标题:Polygraphic Programs and Polynomial-time Functions
  • 本地全文:下载
  • 作者:Guillaume Bonfante ; Yves Guiraud
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2009
  • 卷号:5
  • 期号:02
  • DOI:10.2168/LMCS-5(2:14)2009
  • 出版社:Technical University of Braunschweig
  • 摘要:

    We study the computational model of polygraphs. For that, we consider polygraphic programs, a subclass of these objects, as a formal description of first-order functional programs. We explain their semantics and prove that they form a Turing-complete computational model. Their algebraic structure is used by analysis tools, called polygraphic interpretations, for complexity analysis. In particular, we delineate a subclass of polygraphic programs that compute exactly the functions that are Turing-computable in polynomial time.

  • 关键词:Functional Programs;Algebraic Structures;Analysis Tools;Polynomial Time
国家哲学社会科学文献中心版权所有