抽象数据类型的双代数结构及其计算

被引：10

作者：

苏锦钿 ^{[1
]}

余珊珊 ^{[2
]}

机构：

[1] 华南理工大学计算机科学与工程学院

[2] 中山大学信息科学与技术学院

来源：

计算机研究与发展 | 2012年 / 49卷 / 08期

基金：

高等学校博士学科点专项科研基金;

关键词：

抽象数据类型; 代数; 共代数; 双代数; 递归; 共递归;

D O I：

暂无

中图分类号：

TP311.12 [];

学科分类号：

摘要：

程序语言中的许多抽象数据类型包含了可递归定义的语法构造和可共递归定义的动态行为特征,因此单纯利用代数或共代数难以给出完整的描述.双代数是同一载体集上的代数和共代数对,提供了一种从范畴论的角度探讨抽象数据类型上的语法构造和动态行为关系及性质的可行途径.给出抽象数据类型的双代数结构,并利用代数函子对共代数函子的分配律描述了语法构造与动态行为之间的自然转换关系;利用分配律对共代数和代数函子进行函子化提升,给出一种构造初始代数(或终结共代数)上的共代数(或代数)结构,并将其提升为初始(或终结)λ-双代数的方法.在此基础上,进一步将函子化提升应用于各种递归(包括迭代和原始递归)及共递归函数(包括共迭代和原始共递归)的定义及计算中,并给出相应的计算定律.

引用

页码：1787 / 1803

页数：17

共 12 条

[1]

GSOS for probabilistic transition systems.[J].Falk Bartels.Electronic Notes in Theoretical Computer Science.2002, 1

[2]

Generalised Coinduction.[J].F. Bartels.Electronic Notes in Theoretical Computer Science.2001, 1

[3]

π-calculus in (Co)inductive-type theory [J].