动态项重写计算  

Dynamic Term Rewriting Calculus

作　　者：冯速[1] 

机构地区：[1]北京师范大学信息科学院

出　　处：《计算机科学》2002年第8期13-14,12,共3页Computer Science

基　　金：国家自然科学基金(重点项目)(19931020);教育部留学回国人员科研启动基金

摘　　要：1.引言 项重写系统是一种受到广泛研究和应用的形式计算模型.一个项重写系统由一组称为重写规则的定向等式组成.它的计算基于代入、匹配和替换,除具有方向性外,与等式推导一致.虽然项重写系统形式简单、计算单纯,但它同时又具有与λ计算及图灵机相同的计算能力.正是它的简洁性及计算能力使它受到广泛的研究和应用:项重写系统为抽象数据类型提供类型、为函数型语言提供操作语义、为定理自动证明提供推理工具.对于项重写系统本身也有大量的研究:如合流性、终止性、等价性等[1-5].Dynamic term rewriting calculus is a formal computation model for meta-computation of term rewriting systems.which has characteristic features as hierarchical declaration and dynamic rewriting,and is applied to automated formal proving for inductive theorem and termination of term rewriting systems. Here,we describe syntax,operational semantics and characteristic features of dynamic term rewriting calculus.

关 键 词：动态项重写计算 完备化算法 形式计算模型 元计算 计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]