关于自动机表示理论的研究

By using the idea of representation theory in algebra, we study the representation theory of automata. We are aiming at providing representations of automata and solving the classification problem of automata. . Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces and describing its algebraic operations in terms of matrix addition and matrix multiplication. Representation theory is a powerful tool because it reduces problems in abstract algebra to problems in linear algebra, a subject that is well understood. . In order to classify the automata, we try to reduce the structures of automats into structures of linear algebras. This drive us to provide representations of automata by representing the states of automata as vectors in the vector spaces constructed from the endomorphisms and describing the state transitions in terms of matrix operations. Throughout the work, the semigroups theory and the centralizers of transformations are involved..

从代数学的观点出发, 研究自动机的结构与表示理论. 旨在提出有效的表示自动机的方法, 从而阐明自动机在结构上的分类问题. . 代数学中的表示论是指将代数结构中的元素表作向量空间上的线性变换(即矩阵), 并使得原结构中的运算对应到矩阵的运算, 从而将抽象的代数问题转化为较具体的线性代数问题. . 本项目借助代数表示论的思想, 利用变换半群的中心化子理论, 研究自动机的自同态幺半群和同余关系, 拟将自动机中的状态表作向量空间中的元素(即向量), 并使得自动机中的状态迁移对应到矩阵运算，从而将自动机中的问题转化为较具体的线性代数问题, 并实现自动机在结构上的分类.

描述自动机的结构并提供表示自动机的方法，是自动机进行分类的重要手段。有效的表示方法可以准确、迅速的构造出人们需要的自动机。本项目利用代数学中向量空间的基本思想和半群的代数理论，通过分析几类自动机的结构，提出了表示它们的有效方法。主要研究了以Clifford幺半群、交换的幂等元幺半群半格和群作为自同态幺半群的自动机的结构特征和表示方法。首先，通过自动机状态集上的若干二元关系，对自动机状态集做出横向和纵向的分类（这一分类效果类似于半群理论中格林关系对半群的分类），再利用状态迁移函数，描述各个类别之间的状态迁移的共性，进而刻画出了上述三类自动机的结构特征。基于这些自动机的结构特征，给出一个自动机的自同态幺半群分别是Clifford幺半群、半格和群的充分比要条件。最后，利用有限Clifford幺半群、半格和群构造向量和矩阵代数，并以此为工具建立幺半群矩阵型自动机，用以表示上述三类自动机。达到了将自动机的状态与向量相对应，和用向量与矩阵的乘积表示自动机状态迁移函数的目的。研究过程中，利用了半群的代数理论的思想和方法，扩展了可被表示自动机的范畴，推广了日本学者M. Ito关于表示强连通自动机的结果。.此外，本课题还初步探讨了自动机表示理论这一领域的前导课题和后继问题。前导课题是指提出一些有被表示价值的自动机，如实践中经常用到的识别前缀码的自动机。课题组研究了字自由语言的三个子类，给出了它们的组合性质和代数特征，并通过构造识别这些语言的自动机解决了与之相关的子问题。后继问题是指以表示自动机的工具——幺半群矩阵自动机为研究对象，讨论它的商自动机、极小化问题等经典问题。