论文部分内容阅读
正如树自动机理论是字(word)自动机理论的一个扩展,我们将R.Milner的顺序进程演算扩展到树进程演算。为此,我们建立了一个正确和完备的推演系统用来描述树进程之间的互模拟关系。作为推论,我们获得了一个新的树自动机之间的等价关系,它严格弱于中定义的自动机之间的互模拟相等关系,同时严格强于自动机经典意义下的相等关系,也就是语言相等。
我们还研究了进程演算到概率进程演算的扩展,提出一种新的概率自动机模型,以及由此导出的概率进程演算系统,定义了标号迁移系统、互模拟关系,并且提出给出了一个公理系统来描述该互模拟关系。新提出的互模拟关系在强的情况下跟传统方式的定义是等价的,在弱的情况下严格弱于传统的定义。该项工作的重要性在于可以解决已有的互模拟理论无法解决的带有环形不可见动作序列的进程的互模拟判定问题。