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

Finding shortest D-synchronizing words for nondeterministic finite automata

研究了非确定有限自动机的最短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.