自动机的分支同步字研究

To consider the orientation problem in industrial automation, the branch problem of electronic devices or decision making systems as well as the cooperative control problem of complex systems, we introduce a type of automata called branch-synchronizing automaton. The accessibility between two states of an automaton and synchronizing automata may be seen as two extreme cases of branch-synchronizing automata. The essential character of branch-synchronizing automata is that they equip with a kind of special input-words called branch-synchronizing word. In the present project, as the initiation of theoretical researches on branch-synchronizing automata, we focus on the branch-synchronizing words of automata. By using the relative techniques in the algebraic theory of semigroups, combinatorial theory, graph theory and the theory of weighted automata, we will investigate the existence, finding method, performance evaluation as well as the length of branch-synchronizing words of automata. The concrete aims are: (1) to propose efficient methods to test the existence of branch-synchronizing words of an arbitrary automaton and then find a branch-synchronizing word when it exists, and thus solve the basic problem in researches and applications of branch-synchronizing automata; (2) to establish a performance evaluation model of branch-synchronizing words for optimizing the applications of branch-synchronizing automata; (3) to describe the least upper bound d(n,k) of the length of the shortest completely k-branch-synchronizing words of all n-state automata, and then improve the researches on Cerny Conjecture concerning the length of the shortest synchronizing words of synchronizing automata.

分支同步自动机是我们针对工业自动化中的定位问题、电子装置或决策系统的分支问题、复杂系统的协同控制问题等不同领域的工程问题定义的一类自动机。自动机状态间的可达性和同步自动机是这类自动机的两个具有不同表象的极端情形。分支同步自动机的本质特征是具有一种称为“分支同步字”的特殊输入字。作为分支同步自动机理论研究的肇始，本项目将以自动机的分支同步字为研究对象，综合运用半群代数理论、组合理论、图论及加权自动机理论中的相关技术，对分支同步字的存在性、查找方法、性能评价及长度等进行研究。具体目标是：提出自动机的分支同步字存在性判定和查找的有效方法，解决分支同步自动机理论研究和实际应用的基本问题；建立分支同步字性能评价模型，为优化分支同步自动机的应用提供理论参考；描述所有n-状态自动机的最短完全k-分支同步字长度的上确界d(n,k)，进一步推进关于同步自动机最短同步字长度的Cerny猜想的研究。

自动机的分支同步字问题源于工业自动化中的定位问题、电子装置或决策系统的定向问题、复杂系统的协同控制问题，与自动机组合理论领域的Pin猜想、秩猜想、Černý猜想以及Trahtman猜想等公开问题有直接关联，与形式语言学、码论等理论计算机科学的分支方向以及半群代数理论、图论、组合数学、矩阵论等数学分支有紧密联系。本项目对自动机的分支同步字问题及其相关问题进行了比较深入系统的研究。主要研究内容及获得的主要结果如下：.（1）基础研究。利用组合分析方法给出了两个前缀码共轭的充分必要条件，并在此基础上针对前缀码解决了Ratoandromanana问题和共轭问题。相关论文的责任编委认为：“This is a nice paper on a very difficult topic”。.（2）可定向函数问题的复杂性研究。将分支同步字问题转换为可定向函数问题，并确定可定向函数的判定问题、定向字问题、最短定向字问题为核心研究课题。揭示了可定向函数的判定问题、最短定向字问题与半群代数理论领域中的变换幺半群的成员问题、变换的高度问题之间的联系，然后借助相关领域的研究结果描述了可定向函数的判定问题、最短定向字问题以及它们的一些特殊情形的时间复杂度。.（3）自动机的r阶输入字以及Pin猜想和秩猜想的研究。抽象刻画了自动机的合并图。利用合并图设计并实现了计算自动机的秩、终结字、终结集、最短定向字的算法，并应用这些算法实验验证了秩猜想。发掘了利用合并图的特征对Pin猜想进行分类研究的新线路，证实了Pin猜想和秩猜想对合并图是1-正则图的自动机都成立。.（4）同步自动机以及Černý猜想和Trahtman猜想的研究。发掘了从序的角度对Černý猜想进行分类研究的新线路，证实了Černý猜想对同步格自动机、同步有界偏序自动机、同步树自动机等偏序自动机类都成立。利用复杂的组合分析证实了Trahtman猜想对循环自动机成立（即不存在未知的最短同步字长度恰好为(n-1)2的n状态同步循环自动机），将Trahtman猜想的研究推进了一大步。.（5）自动机定向字的性能评价研究。提出了自动机定向字的性能评价模型。.（6）拓展研究。从以上各部分研究工作中发现的新问题、新思想、新方法出发，在网络信息安全和人工智能两方面开展了拓展研究工作。