状态机的若干代数性质

摘要

自动机就是自动化系统的模型, 它作为一种有效的形式化工具无论是在理论还是在实践中都有着重要的作用. 自动机理论主要研究离散数字系统的功能、结构及两者关系,旨在自动机的分析与综合问题. 随着微电子及信息等科学技术的迅猛发展, 自动机理论已逐步向不同领域渗透, 成为许多学科的重要理论和应用基础,状态机是指无输出的有限自动机. 状态机理论是有限自动机理论的一个研究方向. 许多的国内外学者借助不同的数学工具如微分方程、泛函分析、代数及概率论等对其进行讨论, 促进了自动机理论的发展.本论文以代数为工具对状态机理论进行研究, 主要工作包括两个： 一个是使用范畴论的方法, 对固定输入集的状态机定义一个范畴, 讨论它的性质； 另一个是用矩阵代数的知识来刻画有限交换环上的线性元胞自动机, 借此来分析其演化结构.第二部分是本文的主要结果, 共分成3章第1章是引言, 简单介绍了自动机在计算机科学中的重要位置以及它与其它科学分支的密切关系. 着重介绍了状态机与元胞自动机的代数研究背景. 并给出了状态机和元胞自动机的基本概念和记号.第2章是关于完全状态机范畴的性质的研究. 考虑到任何状态机均可以完全化,本章主要讨论了完全状态机范畴的性质, 先验证了所有的完全状态机可以构成一个范畴, 并讨论了这个范畴的始对象、 终对象、 和零对象的问题.再给出了完全状态机范畴的同态基本定理.所得主要结果如下：命题2.2.3 中任一到的同态的核是的相允关系； 若为满同态, 则为同构的充分必要条件是是上的单位相允.定理2.2.4 (1)设是中的状态机同态, 为的相允且, <；WP=4>；则存在唯一同态,使下图交换 其中 (2)当时, 则为单的. 若为满的, 则也是满的. 特别地, 当且是满的时, 有, 即为同构. 推论2.2.5 设是上的相允关系,且,则有中状态机的同构, 其中. 接着,找到了有限个完全状态机的直和与直积,并且证明了任一个完全状态机可以一分解为一些不可分解的状态机的直和.如下：定理2.3.1设 为中有限个对象,令, 其中. 并对,, .则为在范畴中的直积. 且在同构意义下是唯一的.定理2.3.2设,为中有限个对象,令为不交并,作,其中,,存在唯一,使,令.那么为在范畴中的直和,且在同构意义下是唯一的.定理2.4.4 完全状态机是不可分状态机的充分必要条件是的状态变换图是连通的. <；WP=5>；定理2.4.5 一个完全状态机可以唯一地分解为一些不可分解的完全状态机的直和.第3章是关于有限交换环上的线性元胞自动机的研究. 本章对一类特殊的状态机—元胞自动机进行了专门的讨论,定义了齐次线性元胞自动机, 并在齐次线性元胞自动机矩阵表示的基础上证明了有限交换环上的齐次线性元胞自动机的一组定理, 同时借此分析某些典型齐次线性元胞自动机的演化性质. 最后简要讨论了非齐次线性元胞自动机的群性质.所得主要结果如下：命题3.1.2 设为上演化规则和边界条件为的？-元胞齐次线性元胞自动机,则存在中的矩阵, 使对的任意状态 ,有.定理3.2.2 已知有一个, 为其特征矩阵, 则有该为群的充分必要条件是在中可逆.定理3.2.4 设为一个的特征矩阵, 若存在一个非零初始状态在长为的圈或长为的因子的圈上,则有在中不可逆.命题3.2.5 设为一个的特征矩阵, 且为群, 若的阶为合数, 则该的状态变换图中的圈长只能为的因子.定理3.2.6设为一个的特征矩阵, 若在中可逆,从而是群, 那么该的状态变换图为一些圈的并, 并且所有的圈长均整除, 其中.定理3.2.7 设有一个 ( )上的,为它的特征矩阵. 若为指数为 的幂零矩阵, 那么这个的状态变换图为高度为的树； 并且此树中的非叶子点有个, 每个非叶子点有个前趋, 其中为方程在中解的个数； 0是唯一的稳定点.定理3.2.9 设为一个的特征矩阵,那么(1)若这个的状态变换图为树,则为幂零矩阵且的幂零指数为树的高度.(2)若这个的状态变换图为若干圈的并,则为可逆的.定理3.3.5 设分别为齐次线性元胞自动机的状态变换图, 分别为它们的特征矩阵, 则 <；WP=6>；(1)若均有圈, 则的状态变换图中的极大圈长为max. (2)若均为树且其高度分别为 ,则的状态变换图为树,其高度为.定理3.3.6 设有两个齐次线性元胞自动机, 分别是它们的状态变换图, 分别为它们的特征矩阵.若为一个长为的圈, 为一个高度为的树,则的状态变换图为下面这样的一个有向图： 有一个长为的圈且以该圈上的每一点为根有一棵树, 这些树与均同构.定理3.3.7 设有一个的特征矩阵为, 那么总存在齐次线性元胞自动机 ,使.其中若设分别为的特征矩阵, 那么为可逆, 为幂零的.定理 3.4.3 设为一个的特征矩阵且以为特征矩阵的齐次线性元胞自动机为群元胞自动机, 则该也为群元胞自动机.

目录

第一部分

中文摘要

英文摘要

第二部分

第1章 引言

1.1 自动机的研究与发展

1.2 状态机的研究背景及基本概念

1.3 范畴论的基本概念

1.4 元胞自动机的研究背景及定义

第2章 完全状态机范畴的性质

2.1 完全状态机范畴的定义和基本性质

2.2 完全状态机范畴的同态基本定理

2.3 完全状态机范畴的直和与直积

2.4 完全状态机范畴中对象的分解

第3章 有限交换环上的线性元胞自动机

3.1 齐次线性元胞自动机的定义及矩阵表示

3.2 齐次线性元胞自动机的群性质和演化性质

3.3 有限个齐次线性元胞自动机的直积和有向图的直积

3.4 非齐次线性元胞自动机的定义和群性质

第三部分 参考文献

致谢