论文部分内容阅读
代数方法从“构造”的角度研究抽象数据类型的语义,并且已经在抽象数据类型、计算机语言的形式语义等领域有了广泛的应用。而代数的对偶概念—共代数,从上世纪90年代以来,才得到计算机学者的广泛关注,并逐步成为理论计算机科学的研究热点之一。共代数从“观察”的角度考察系统及其性质,并已经在自动机理论、并发程序的形式语义、面向对象程序的规范等领域有了广泛的应用。
共代数理论作为新兴的理论,正在发展之中,许多方面还不成熟,要对共代数理论作全面研究目前仍有不小的困难,流共代数作为一种特殊的共代数,其性质相对简单,但通过对它的研究有助于认识并探讨一般的共代数理论。
流共代数存在唯一到终结共代数的同态射,而终结共代数的状态集可以看作一系列流的集合。本文正是基于终结共代数研究了流演算,包括实数域上流演算和比特流演算,并用程序实现流的一些操作,例如卷积、混合积等,特别地,在J.Rutten等人工作的基础上进一步探讨了实数域上流演算在差分与微分方程中的应用和比特流在电路分析与设计中的应用。在流演算的基础上介绍了加权流自动机以及其在计数难题方面的应用,进一步,介绍了有理流与加权流自动机之间的相互转换,并设计、实现有理流到加权流自动机的转换。