非确定有限自动机的最短D1-同步字求解  

Finding shortest D-synchronizing words for nondeterministic finite automata

作　　者：朱凯 毋国庆[1] 袁梦霆[1] 杨磊[2] ZHU Kai;WU Guoqing;YUAN Mengting;YANG Lei(School of Computer Science,Wuhan University,Wuhan 430072,China;College of Mathematics and Informatics,South China Agricultural University,Guangzhou 510642,China)

机构地区：[1]武汉大学计算机学院,湖北武汉430072 [2]华南农业大学数学与信息学院,广东广州510642

出　　处：《华中科技大学学报（自然科学版）》2021年第2期68-73,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61640221,61872272);广东省自然科学基金面上项目(2020A1515010691)。

摘　　要：研究了非确定有限自动机的最短D1-同步字的计算问题。针对这种自动机定义了D1W问题及其参数化版本问题p-D1W和最优问题shortest-p-D1W,证明了p-D1W和shortest-p-D1W分别属于para-NP和para-DP。利用均匀分布模型随机生成大量的非确定的有限自动机进行实验,结果表明:在定长的参数下几乎所有随机产生的自动机实例都不是D1-可同步的,一旦将自动机上每个状态和字母的变迁函数的像数量限制在2以内,会出现少量的D1-可同步的自动机,且绝大多数最短同步字长不超过状态数的2倍。This work is about a problem of finding the shortest D1-synchronizing word for a given nondeterministic finite automaton.For this kind of automata,the D1W problem,its parameterized version p-D1W,and its optimized version shortest-pD1W were defined,and then that p-D1W is in para-NP and that shortest-p-D1W is in para-DP were proved.Some experiments on many randomly generated nondeterministic finite automata using uniform distribution model were made.And the results are as follow:Under fixed-length parameters,almost all randomly generated automata instances are not D1-synchronizable.However,a small account of D1-synchronizing nondeterministic finite automata appear when the size of image set of the transition function for each state and symbol is at most 2.And at the same time,by an overwhelming majority,the length of the shortest D1-synchronizing word is no more than 2 times the number of the automaton′s states.

关 键 词：非确定有限自动机 同步字 固定参数易解的归约 可满足问题 参数化复杂性 参数化算法 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]