计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 14-21.doi: 10.11896/jsjkx.200200073

• 理论计算机科学 • 上一篇    下一篇


朱凯1,2, 毋国庆1, 袁梦霆1   

  1. 1 武汉大学计算机学院 武汉430072
    2 华南农业大学数学与信息学院 广州510642
  • 收稿日期:2020-01-15 出版日期:2020-05-15 发布日期:2020-05-19
  • 通讯作者: 袁梦霆(ymt@whu.edu.cn)
  • 作者简介:zhukaics@aliyun.com
  • 基金资助:

On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata

ZHU Kai1,2, WU Guo-qing1, YUAN Meng-ting1   

  1. 1 School of Computer Science,Wuhan University,Wuhan 430072,China
    2 College of Mathematics and Informatics,South China Agricultural University,Guangzhou 510642,China
  • Received:2020-01-15 Online:2020-05-15 Published:2020-05-19
  • About author:ZHU Kai,born in 1979,doctorial stu-dent,lecturer.His main research interests include theoretical computer science and formal method.
    YUAN Meng-ting,born in 1976,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include programming language theory,compiler optimization and software engineering.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61640221,61872272)

摘要: 自动机是可同步的是指它具有满足以下性质的同步字:不论自动机当前所处的状态,以同步字为输入执行后它一定会到达某个特定状态。同步自动机问题的核心是计算最短同步字。聚焦于这一核心问题,文中就一类称为部分规约的确定的有限自动机的最短同步字问题,研究了近似计算这类自动机的最短同步字的复杂性,即近似计算它的难度,该工作有助于其近似算法的分析与设计。通过建立由两个优化问题(MAX SAT问题以及MAX FA-INT问题)到最短同步字长度计算这一问题(即Shortest-Syn)的归约,利用与概率可检验证明(Probabilistically Checkable Proofs,PCP)定理和概率可检验辩论(Probabilistically Checkable Debate,PCD)定理有关的若干结果证明了文中的主要结论:对于部分规约的确定的有限自动机,在某个近似因子内Shortest-Syn的近似难度是NP-难的和PSPACE-难的,除非NP和PSPACE分别坍塌到P。

关键词: 有限自动机, 同步字, 计算复杂性, 近似难度, QSAT问题

Abstract: An automaton is synchronizing means it is with a word that has the following property:no matter which state the automaton is in,it will always reach a certain state after executing with a synchronizing word as input.For the problem of synchronization of automata,the core is to compute the shortest synchronizing word.Focusing on this core problem,this paper studies the complexity of approximate computing,i.e.the hardness of approximating,the shortest synchronizing word for a class of automata called partially specified deterministic finite automata,which is helpful for the analysis and design of its approximate algorithm.By two reductions from MAX SAT and MAX FA-INT,which are two optimizing problems,to the problem of computing the length of the shortest synchronizing word (i.e.,Shortest-Syn),respectively,and by some existing results related to Probabilistically Checkable Proofs theorem and Probabilistically Checkable Debate theorem,the main results are proved.The results are as follows:for the partially specified deterministic finite automata,approximate computing the problem of Shortest-Syn is NP-hard and PSPACE-hard within some certain approximate ratios,unless NP and PSPACE collapse to P,respectively.

Key words: Finite automata, Synchronizing word, Computational complexity, Hardness of approximation, QSAT problem


  • TP301.5
[1] JÜRGENSEN H.Synchronization[J].Information and Computation,2008,206(9/10):1033-1044.
[2] ČERNÝJ.Poznámka k-homogénnym eksperimentom s konečnýmiautomatami[J].Mathematicko-fyzikalny časopis Slovenskej,Akadémie Vied,1964,14(3):208-216.
[3] VOLKOV M V.Synchronizing automata and the černý conjecture[C]//International Conference on Language and Automata Theory and Applications.Springer,Berlin,Heidelberg,2008:11-27.
[4] POMERANZ I,REDDY S M.On achieving complete testability of synchronous sequential circuits with synchronizing sequences[C]//Proceedings.,International Test Conference.IEEE,1994:1007-1016.
[5] SANDBERG S.Homing and Synchronizing Sequences[M]//Model-based testing of reactive systems.Springer,Berlin,Heidelberg,2005:5-33.
[6] BENENSON Y,ADAR R,PAZ-ELIZUR T,et al.DNA molecule provides a computing machine with both data and fuel[J].Proceedings of the National Academy of Sciences,2003,100(5):2191-2196.
[7] EPPSTEIN D.Reset sequences for monotonic automata[J].SI-AM Journal on Computing,1990,19(3):500-510.
[8] GOLDBERG K Y.Orienting polygonal parts without sensors[J].Algorithmica,1993,10(2/3/4):201-225.
[9] BISKUP M T,Plandowski W.Shortest synchronizing strings for Huffman codes[J].Theoretical computer science,2009,410(38/39/40):3925-3941.
[10] FERNAU H,HEGGERNES P,VILLANGER Y.A multi-pa-rameter analysis of hard problems on deterministic finite auto-mata[J].Journal of Computer and System Sciences,2015,81(4):747-765.
[11] BERLINKOV M V.On calculating length of minimal synchronizing words[J].arXiv:0909.3787v1.
[12] GERBUSH M,HEERINGA B.Approximating minimum resetsequences[C]//International Conference on Implementation and Application of Automata.Springer,Berlin,Heidelberg,2010:154-162.
[13] ANANICHEV D S,GUSEV V V.Approximation of resetthresholds with greedy algorithms[J].Fundamenta Informaticae,2016,145(3):221-227.
[14] BERLINKOV M V.Approximating the minimum length of synchronizing words is hard[C]//International Computer Science Symposium in Russia.Springer,Berlin,Heidelberg,2010:37-47.
[15] BERLINKOV M V.On two algorithmic problems about syn-chronizing automata[C]//International Conference on Developments in Language Theory.Springer,Cham,2014:61-67.
[16] GAWRYCHOWSKI P,STRASZAK D.Strong inapproximability of the shortest reset word[C]//International Symposium on Mathematical Foundations of Computer Science.Springer,Berlin,Heidelberg,2015:243-255.
[17] QUAAS K,SHIRMOHAMMADI M.Synchronizing DataWords for Register Automata[J].ACM Transactions on Computational Logic (TOCL),2019,20(2):1-27.
[18] Doyen L,Massart T,Shirmohammadi M.The complexity of synchronizing Markov decision processes[J].Journal of computer and system sciences,2019,100:96-129.
[19] ZHU K,WU G Q,WU L H,et al.Computational complexity of several problems for resetting timed automata[J].Ruan Jian Xue Bao/Journal of Software,2019,30(7):2033-2051.
[20] MARTYUGIN P.Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata[J].Theory of Computing Systems,2014,54(2):293-304.
[21] MARX D.Parameterized complexity and approximation algo-rithms[J].The Computer Journal,2008,51(1):60-78.
[22] DU D Z,GE K Y,WANG J.Introduction to computational complexity[M].Higher Eeucation Press,2002.
[23] ARORA S,BARAK B.Computational complexity:a modern approach[M].Cambridge University Press,2009.
[24] ARORA S,SAFRA S.Probabilistic checking of proofs; A new characterization of NP[C]//33rd Annual Symposium on Foundations of Computer Science,FOCS 1992.IEEE Computer Society,1992:2-13.
[25] ARORA S,LUND C,MOTWANI R,et al.Proof verificationand hardness of approximation problems[C]//Proceedings.,33rd Annual Symposium on Foundations of Computer Science.IEEE,1992:14-23.
[26] XU D Y.PCP theorem and its applications to research on non-approximatable problems[J].Journal of frontiers of computer science and technology,2008,2(1):20-31.
[27] CONDON A,FEIGENBAUM J,LUND C,et al.Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions[C]//Proceedings of the twenty-fifth annual ACM symposium on Theory of computing.1993:305-314.
[28] CONDON A,FEIGENBAUM J,LUND C,et al.Probabilistically Checkable Debate Systems and Nonapproximability Results for PSPACE-Hard Functions[J].Chicago J.Theoretical Computer Science,1995(4):1-35.
[29] KOZEN D.Lower bounds for natural proof systems[C]//18th Annual Symposium on Foundations of Computer Science (SFCS).IEEE,1977:254-266.
[30] KUPFERMAN O,VARDI M Y,WOLPER P.An automata-theo-retic approach to branching-time model checking[J].Journal of the ACM (JACM),2000,47(2):312-360.
[31] COHEN A,WIGDERSON A.Dispersers,deterministic amplification,and weak random sources[C]//30th Annual Symposium on Foundations of Computer Science (SFCS).IEEE,1989:14-19.
[32] WAREHAM H T.The parameterized complexity of intersectionand composition operations on sets of finite-state automata[C]//International Conference on Implementation and Application of Automata.Berlin:Springer,2000:302-310.
[33] DE BONDT M,DON H,ZANTEMA H.Lower bounds for synchronizing word lengths in partial automata[J].International Journal of Foundations of Computer Science,2019,30(1):29-60.
[34] SHABANA H,VOLKOV M V.Using Sat solvers for synchronization issues in partial deterministic automata[C]//International Conference on Mathematical Optimization Theory and Operations Research.Springer,Cham,2019:103-118.
[35] SHABANA H.Exact synchronization in partial deterministicautomata[J].Journal of Physics:Conference Series,2019,1352(1):012047.
[36] CUI Z H,HE Y,SUN S Y.Synchronizing bounded partially ordered automata[J].Chinese Journal of Computers,2019(3):610-623.
[37] CHALERMSOOK P,CYGAN M,KORTSARZ G,et al.Fromgap-eth to fpt-inapproximability:Clique,dominating set,and more[C]//2017 IEEE 58th Annual Symposium on Foundations of Computer Science (SFCS).IEEE,2017:743-754.
[38] LAEKHANUKIT B,MANURANGSI P.On the parameterized complexity of approximating dominating set[C]//Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing(STOC).ACM,2018:1283-1296.
[1] 宋勃升, 程玉. 带膜分裂和促进剂的通讯膜系统求解QSAT问题[J]. 计算机科学, 2020, 47(5): 38-42.
[2] 孙士远, 何勇. 自动机终结字查找算法的设计与实现[J]. 计算机科学, 2020, 47(11A): 599-603.
[3] 陈雪萍, 何勇, 肖芬芳. 一类同步自动机及损耗函数分析[J]. 计算机科学, 2019, 46(11A): 535-538.
[4] 余建军, 吴春明. 虚拟网映射问题的计算复杂性分析[J]. 计算机科学, 2018, 45(11): 87-91.
[5] 陆正福, 普艳红, 倪盛斌, 许辰铭, 杨春尧. 有限理性公平数据交换协议的设计与仿真[J]. 计算机科学, 2018, 45(11): 115-123.
[6] 董昱,高雪娟. 基于场景的联锁软件形式化模型生成方法[J]. 计算机科学, 2015, 42(1): 193-195.
[7] 张亚红,张琳琳,赵楷,陈佳丽,冯在文. 基于UML2.0序列图的Web服务运行时验证方法[J]. 计算机科学, 2013, 40(7): 138-138.
[8] 陈亚瑞. Ising图模型概率推理的计算复杂性[J]. 计算机科学, 2013, 40(2): 253-256.
[9] 杜文超,陈庶樵,胡宇翔. 基于DoLFA的高效正则表达式匹配算法[J]. 计算机科学, 2012, 39(9): 15-19.
[10] 肖芬芳,何勇,胡斌梁,王志喜. 拟陷阱同步自动机的最短同步字的长度[J]. 计算机科学, 2012, 39(11): 191-193.
[11] 王晶 戎玫 张广泉 祝义. 基于概率模型检测的Web服务组合验证[J]. 计算机科学, 2012, 39(1): 120-123.
[12] . BPEL应用程序验证模型研究[J]. 计算机科学, 2009, 36(4): 163-165.
[13] 覃泳睿 孙未未 张卓瑶 余平. 基于有限自动机的XML过滤技术研究综述[J]. 计算机科学, 2008, 35(12): 19-23.
[14] . G3逻辑中的弱合取范式[J]. 计算机科学, 2007, 34(4): 158-162.
[15] . 有限状态自动机的并行确定化及过程分析[J]. 计算机科学, 2006, 33(10): 293-294.
Full text



[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .