计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 14-21.doi: 10.11896/jsjkx.200200073
所属专题: 理论计算机科学
朱凯1,2, 毋国庆1, 袁梦霆1
ZHU Kai1,2, WU Guo-qing1, YUAN Meng-ting1
摘要: 自动机是可同步的是指它具有满足以下性质的同步字:不论自动机当前所处的状态,以同步字为输入执行后它一定会到达某个特定状态。同步自动机问题的核心是计算最短同步字。聚焦于这一核心问题,文中就一类称为部分规约的确定的有限自动机的最短同步字问题,研究了近似计算这类自动机的最短同步字的复杂性,即近似计算它的难度,该工作有助于其近似算法的分析与设计。通过建立由两个优化问题(MAX SAT问题以及MAX FA-INT问题)到最短同步字长度计算这一问题(即Shortest-Syn)的归约,利用与概率可检验证明(Probabilistically Checkable Proofs,PCP)定理和概率可检验辩论(Probabilistically Checkable Debate,PCD)定理有关的若干结果证明了文中的主要结论:对于部分规约的确定的有限自动机,在某个近似因子内Shortest-Syn的近似难度是NP-难的和PSPACE-难的,除非NP和PSPACE分别坍塌到P。
中图分类号:
[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问题 Uniform Solution to QAST Problem by Communication P Systems with MembraneDivision and Promoters 计算机科学, 2020, 47(5): 38-42. https://doi.org/10.11896/jsjkx.191100204 |
[2] | 孙士远, 何勇. 自动机终结字查找算法的设计与实现 Designs and Implementations of Algorithms for Searching Terminal Words of Automata 计算机科学, 2020, 47(11A): 599-603. https://doi.org/10.11896/jsjkx.200300096 |
[3] | 陈雪萍, 何勇, 肖芬芳. 一类同步自动机及损耗函数分析 Synchronization of a Certain Family of Automata and Consumption Function Analysis 计算机科学, 2019, 46(11A): 535-538. |
[4] | 余建军, 吴春明. 虚拟网映射问题的计算复杂性分析 Computational Complexity Analysis of Virtual Network Mapping Problem 计算机科学, 2018, 45(11): 87-91. https://doi.org/10.11896/j.issn.1002-137X.2018.11.012 |
[5] | 陆正福, 普艳红, 倪盛斌, 许辰铭, 杨春尧. 有限理性公平数据交换协议的设计与仿真 Design and Simulation of Fair Data Exchange Protocol with Bounded Rationality 计算机科学, 2018, 45(11): 115-123. https://doi.org/10.11896/j.issn.1002-137X.2018.11.017 |
[6] | 董昱,高雪娟. 基于场景的联锁软件形式化模型生成方法 Method for Generating Formal Interlocking Software Model Based on Scenario 计算机科学, 2015, 42(1): 193-195. https://doi.org/10.11896/j.issn.1002-137X.2015.01.043 |
[7] | 张亚红,张琳琳,赵楷,陈佳丽,冯在文. 基于UML2.0序列图的Web服务运行时验证方法 Runtime Verification Method for Web Service Based on UML2.0Sequence Diagrams 计算机科学, 2013, 40(7): 138-138. |
[8] | 陈亚瑞. Ising图模型概率推理的计算复杂性 Computational Complexity of Probabilistic Inference in Icing Graphical Model 计算机科学, 2013, 40(2): 253-256. |
[9] | 杜文超,陈庶樵,胡宇翔. 基于DoLFA的高效正则表达式匹配算法 Efficient Regular Expression Matching Algorithm Based on DoLFA 计算机科学, 2012, 39(9): 15-19. |
[10] | 肖芬芳,何勇,胡斌梁,王志喜. 拟陷阱同步自动机的最短同步字的长度 Length of the Shortest Synchronizing Words for Quasi-trapped Synchronizing Automata 计算机科学, 2012, 39(11): 191-193. |
[11] | 王晶 戎玫 张广泉 祝义. 基于概率模型检测的Web服务组合验证 Validation of Web Service Composition Based on Probabilistic Model Checking 计算机科学, 2012, 39(1): 120-123. |
[12] | . BPEL应用程序验证模型研究 计算机科学, 2009, 36(4): 163-165. |
[13] | 覃泳睿 孙未未 张卓瑶 余平. 基于有限自动机的XML过滤技术研究综述 计算机科学, 2008, 35(12): 19-23. |
[14] | . G3逻辑中的弱合取范式 计算机科学, 2007, 34(4): 158-162. |
[15] | . 有限状态自动机的并行确定化及过程分析 计算机科学, 2006, 33(10): 293-294. |
|