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

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

以体系结构为中心的模型转换的语义描述框架

在对类型范畴理论进行扩展的基础上,将其与进程代数相结合,为软件体系结构模型及其间的转换关系提供了一种统一的语义描述框架.模型的结构语义由类型范畴图表来指代,其行为语义则由范畴附带的进程行为迹来表示,模型间的映射关系用范畴理论中的态射和函子来形式化描述.该描述框架可用于模型转换中特性保持问题的描述、分析和判定,从而为模型驱动的软件开发提供有力的支持.     

元Chi进程互模拟等价的一致性

Chi-演算是将π-演算中两类受限名统一后得到的.多态Chi-演算扩充了Chi-演算的通信能力,使得一次通信可传递多个信息.元Chi-演算是在省略多态Chi-演算的前缀操作子之后得到的子语言.研究了元Chi-演算的互模拟等价关系,证明了在某种意义下,元Chi-进程之间只有一个互模拟等价关系.     

基于π演算的多实例工作流模式的建模方法

π演算是一种移动进程代数,可用于对并发和动态变化的系统进行建模.根据π演算的语法,利用π演算对多实例工作流模式进行了建模.提出的方法具有较强的语义表达能力,同时使过程模型的语义更加精确.     

一个移动进程演算的互模拟同余定义框架

并发计算模型是理论计算机科学研究的重要领域之一。以π演算为代表的移动进程演算是目前并发理论的研究热点。互模拟等价定义是移动进程演算研究中的核心概念和问题，而传名机制使得移动进程演算中的互模拟同余关系更加复杂和有趣。本文在分析了常见的互模拟同余定义的基础上，通过抽取定义的核心要素，提出了一个三维的互模拟同余定义模型，从而将一般文献中常见的互模拟定义纳入到一个统一的框架中来，加深了我们对移动进程演算中互模拟概念的理解；同时本文利用这个模型，系统分析了各种互模拟之阿的关系。模型的优点在于它的普适性和开放性。     

计算机科学中的范畴数据类型的研究综述

范畴数据类型是指以范畴论为数学理论基础研究数据类型的描述、计算、语义和应用。早期的范畴数据类型研究以归纳数据类型为主,采用代数从归纳的角度研究有限数据类型的构造语义和递归性质。近年来,归纳数据类型的对偶概念——共归纳数据类型逐渐引起计算机科学工作者的关注与研究,他们采用共代数从观察的角度研究无限数据类型的行为语义和共递归性质。利用范畴论可以为数据类型研究提供统一的数学理论基础,并将代数和共代数中的各种重要研究成果有机地融合在一起,如语法构造与动态行为、递归与共递归、同余与互模拟等。目前,范畴数据类型已经在程序语言、计算描述、理论证明器和并行计算等领域得到广泛的应用。对范畴数据类型的基本概念、数学理论基础、逻辑基础及应用等方面的最新研究成果进行介绍,以引起国内外相关研究领域的学者对计算机科学中的范畴数据类型理论的关注。     

基于Fibrations理论的共享系统数据模型

传统共享系统数据模型的建模方法在语义性质分析和语义行为描述方面存在不足,针对以上问题提出了一种基于Fibrations理论的共享系统数据模型。主要工作体现在两个方面:首先,应用真值函子、保持真值的提升与内涵函子并结合代数方法精确分析了语义性质,应用等式函子、保持等式的提升及商函子并结合共代数方法形式化描述了语义行为;其次,在Fibrations理论框架内构造复杂归纳与共归纳数据结构上参数化的递归与共递归操作,抽象描述具有普适意义的归纳与共归纳规则,结合实例简要介绍了Fibrations理论的应用。相对于范畴论等传统方法,简洁描述与灵活扩展的Fibrations理论对共享系统数据模型的语义性质和语义行为进行了精确分析与形式化描述,抽象描述了复杂数据结构具有普适性的归纳与共归纳规则。     

ABC转运器的π-演算模型及其验证

将描述并行、分布式和可移动系统的进程代数应用于系统生物学的形式化描述和行为模拟,给出了SBP依赖式ABC转运器的π-演算模型,分析了其基于状态迁移规则的动态行为演变和构象变化过程,并用自动验证π-演算、通信系统演算CCS的移动工作台MWB对该模型进行了状态跟踪和性能验证. π-演算能够在统一的框架之下捕获分子生物系统的两个关键属性:模块化组织和动态行为,对其既能进行质的又能进行量的推理,证明了π-演算用于分子生物过程抽象描述的可行性.     

非对称χ≠-演算的互模拟格

非对称χ≠-演算是一种移动计算模型.通过研究该演算的互模拟格,能够增强理解非对称性和不等名算子对移动进程代数理论的影响.在给出非对称χ≠-演算的语法和转移语义系统的基础上,定义了该演算的L-互模拟关系.研究表明非对称χ≠-演算的63个L-互模拟关系重叠为12个不同的互模拟关系,而且这12个互模拟关系构成了一个关于集包含的互模拟格.最后证明了barbed互模拟和开互模拟分别与该互模拟格的顶元和底元互模拟关系相重合.     

基于价格进程代数的Web服务组合描述和成本分析

进程代数可有效地用于Web服务组合的描述和验证,然而缺乏对服务组合成本建模和分析的能力.提出一种扩展了价格信息的进程代数PPA, 在CCS基础上为进程动作和状态扩展价格函数, 给进程动作的执行标记价格,给进程的迁移状态标记成本.给出了PPA的语法和语义,定义了PPA成本弱互模拟并分析了其与CCS弱互模拟的关系,证明了PPA在CCS基础上扩展了成本建模能力,给出了成本状态空间构造算法,该算法支持选择成本优化的组合服务.实验分析了PPA用于Web服务组合成本建模和分析的可行性.     

程序语言中共归纳数据类型的一种fibrations方法

范畴论与共代数是程序语言中共归纳数据类型研究的传统方法,这些方法在语义行为分析与共归纳规则描述等方面存在一定的不足。针对以上问题,提出了一种fibrations方法以对共归纳数据类型的语义行为与共归纳规则进行研究。该方法系统分析了fibration上共归纳数据类型的重索引函子、对偶重索引函子与真值函子等基本逻辑结构,应用等式函子与商函子等工具建立共归纳数据类型与其语义行为在程序逻辑上的对应关系,深入分析共归纳数据类型的语义行为;并以基范畴上自函子及其在全范畴上保持等式的提升为工具构造共递归操作,抽象描述共归纳数据类型具有普适意义的共归纳规则;最后通过实例分析简要介绍了fibrations方法的应用。     

一种扩充的π-演算及事务性等价关系研究

为了保证Web服务事务获得正确的执行和一致的结果,对Web服务事务处理的形式化研究是很重要的.现有研究集中在事务的建模和协议验证上,对事务特性仍缺乏深入研究.已有的事务建模方法主要采用增加额外的操作算子来描述事务补偿语义,而过于复杂的语法和迁移规则不利于对事务特性的进一步分析.在不增加新的操作算子的前提下,引入事务膜的位置概念来表示事务作用域,将进程的交互动作与消息相对事务膜的传递过程相关联,对π-演算进行扩充.结合进程行为的事务依赖性,提出了一种弱事务性开互模拟,来刻画可见事务行为的等价关系,利用互模拟等价理论分析了弱事务性等价关系的基本性质,为研究Web服务的事务特性提供了理论基础.     

GSOS算子下共变-异变模拟的公理刻画

进程的行为理论是进程演算研究的核心内容之一,其侧重于讨论进程间的行为等价和模拟关系。共变-异变模拟(Covariant-Contravariant Simulation,CC-模拟)的概念是对经典(互)模拟概念的推广,它通过区分动作类型,刻画了规范与实现对系统主动、被动和通讯动作在精化关系中的不同要求。行为关系的(前)同余性和公理刻画是进程演算代数特征的集中体现,它们对规范及实现的分析和推理至关重要。一般而言,行为关系(前)同余性的证明和公理系统的构造需要基于不同进程演算系统的结构化操作语义(Structural Operational Semantics,SOS)分别展开。为了避免这类研究工作中的重复劳动,学术界针对一般化SOS规则形式的元理论开展了研究,GSOS是其中被广泛研究的规则形式之一。文中在考量了动作类型的基础上,基于CC-模拟对GSOS规则形式做出扩充,提出了CC-GSOS规则类型,证明了CC-模拟相对于CC-GSOS算子具有前同余性,并给出了在这些算子下CC-模拟的可靠完备公理系统的一般性构造方法。     

移动进程演算中的开互模拟

该文就移动进程演算中的弱开同余关系进行了研究。文中考虑了一种简单的非确定性移动进程演算模型,证明了Milner的三条tau规则在有等名测试算子时不足以将强开同余关系的完全公理化系统提升到同余关系的完全公理化系统,文中提出了第四条tau规则,处理了在前缀操作下的等名测试算子,并证明了强开同余关系的完全公理化系统加上四条tau规则可得到弱开同余关系的完全公理化系统。该文的结论否定了关于Milner的三条tau规则足以将π－演算中的强同余关系的完全公理化系统提升到弱同余关系的完全公理化系统的猜想。     

π-演算互模拟判定算法的优化和实现

π-演算采用互模拟作为进程等价的准则.对有限状态的π-演算进程互模拟等价是可判定的,由此提出了互模拟检测算法的一种优化技术.该技术基于只将输入名字实例化为在以后的等名测试中用到的自由名字.通过实例说明这一优化技术可大大减少所用的时间和空间,并证明了优化算法的正确性.     

π-网的强互模拟等价

该文建立了π-网的强互模拟等价关系,对π-网的结构作了进一步的研究．π-网是一类新型的基于π-演算语义的模块化高级Petri网,是对两类并发模型Petri网和π-演算的有效结合,它的并发语义既是“真正并发”的又是“交互”的．π-网的强互模拟等价是针对π-网的交互性并发语义的,是基于π-网的标号操作语义规则,并直接用π-网作为计算单元来实现的互模拟计算,使得π-网的行为能够从动态和静态两方面得到考察．该文证明了对于任意的一个π-网N,都存在一个π-进程P,在π-网与π-演算系统等价映射Ψ下,Ψ(N)与N是强互模拟的这一重要的结论．     

非对称χ≠-演算的基同余

该文研究非对称χ^≠-演算的基同余．文中引入一组L-互模拟关系,并确定基互模拟就是由L-互模拟定义导出的12个互异的互模拟关系中的最小关系,给出了某些L-互模拟的开模拟性质,利用开模拟性质引入开基互模拟概念,并证明开基互模拟与基互模拟是一致的,构造了基于基同余的可靠和完备的等式系统,最后给出了基同余的完备性定理．     

基于行为描述的Web服务组合兼容性检查*

定义了服务的基调视图和行为视图,设计了将Web服务行为转换为π演算进程表达的建模方法,并给出了实现服务视图向π演算进程自动转换的算法;最后借助π演算的操作语义和形式化推理技术实现了对Web服务组合时的兼容性进行检查。     

带Mismatch算子的高阶π演算

主要研究带mismatch的高阶进程演算的公理化问题。首先,建立存在mismatch时高阶进程的开弱高阶互模拟理论,证明了等价关系、同余性等重要性质;其次,沿用线性的方法,构建得到带 mismatch 的有限进程上的公理系统;最后,基于对开弱高阶互模拟的刻画,证明了该公理系统的完备性定理。该工作为带 mismatch 的高阶进程上互模拟判定的有效算法的设计与实现,进而为相关的应用建模工作提供了理论借鉴。     

一种基于共代数的面向对象形式语义

针对面向对象方法的数学理论基础相对薄弱的问题,利用共代数方法从范畴论及观察的角度研究面向对象的形式语义及行为关系。首先,给出类和对象的共代数描述,其中抽象类定义成一个类规范,类定义为满足类规范的共代数,类的各个对象则看成共代数状态空间上的元素,并分别利用强Monads理论和断言给出方法的行为的参数化描述和语义约束;接着,利用共代数互模拟探讨了不同对象在强Monads下的行为等价关系;最后用实例说明如何通过PVS工具证明类规范的一致性及对象的行为关系。