抽象数据类型的双代数结构

作者：苏锦钿; 余珊珊

来源：华南理工大学学报(自然科学版), 2011, (12): 44-50.

• 抽象数据类型
• 共代数
• 双代数
• 共递归 abstract data type
• coalgebras
• bialgebras
• corecursion

对抽象数据类型的语法构造和动态行为的性质及两者的关系而言,单纯利用代数或共代数方法进行研究存在一定的不足.文中结合范畴论及分配律给出抽象数据类型的双代数结构,并通过λ-双代数自然地描述了语法构造与动态行为之间的转换关系;分别利用分配律对共代数函子及代数函子进行函子化提升,证明这种函子化提升可以将初始代数(或终结共代数)提升为初始(或终结)λ-双代数,并将其应用于递归及共递归函数的定义及计算中.实例表明,这种函子化提升可以扩展代数中的归纳原理和共代数中的共归纳原理,从而提高程序语言对抽象数据类型的描述与性质证明能力.

• 单位
  华南理工大学; 中山大学