加权有穷自动机的代数性质
在计算机科学中，白动机用作计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。1961年，S chutzenberge:首先提出了加权自动机的概念，并提出了半环上的形式幂级数的概念，证明了Kleene-Schutzenberger定理，即加权有穷自动机所识别的形式幂级数和有理幂级数是一致的。在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的.并通过引入加权有穷自动机的可交换性分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性分离性、(强)连通性及层的关系.
计算机技术 加权有穷自动机 形式幂级数 强同态 连通性
张丽霞
安庆师范学院数学与计算科学学院,安徽 安庆 246013
国内会议
济南
中文
1-7
2014-10-16（万方平台首次上网日期，不代表论文的发表时间）