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

文章基本信息

  • 标题:Semi-continuous Sized Types and Termination
  • 本地全文:下载
  • 作者:Andreas Abel
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2008
  • 卷号:4
  • 期号:02
  • DOI:10.2168/LMCS-4(2:3)2008
  • 出版社:Technical University of Braunschweig
  • 摘要:

    Some type-based approaches to termination use sized types: an ordinal bound for the size of a data structure is stored in its type. A recursive function over a sized type is accepted if it is visible in the type system that recursive calls occur just at a smaller size. This approach is only sound if the type of the recursive function is admissible, i.e., depends on the size index in a certain way. To explore the space of admissible functions in the presence of higher-kinded data types and impredicative polymorphism, a semantics is developed where sized types are interpreted as functions from ordinals into sets of strongly normalizing terms. It is shown that upper semi-continuity of such functions is a sufficient semantic criterion for admissibility. To provide a syntactical criterion, a calculus for semi-continuous functions is developed.

  • 关键词:Termination;Data Structures;Polymorphism;Semantics
国家哲学社会科学文献中心版权所有