Computer Science ›› 2020, Vol. 47 ›› Issue (5): 14-21.doi: 10.11896/jsjkx.200200073

Special Issue: Theoretical Computer Scinece

• Theoretical Computer Science • Previous Articles     Next Articles

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)

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: Computational complexity, Finite automata, Hardness of approximation, QSAT problem, Synchronizing word

CLC Number: 

  • 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] HUANG Hua-wei, LI Chun-hua. Security Analysis of A Key Exchange Protocol Based on Tropical Semi-ring [J]. Computer Science, 2022, 49(6A): 571-574.
[2] HAN Jie, CHEN Jun-fen, LI Yan, ZHAN Ze-cong. Self-supervised Deep Clustering Algorithm Based on Self-attention [J]. Computer Science, 2022, 49(3): 134-143.
[3] YOU Ling, GUAN Zhang-jun. Low-complexity Subcarrier Allocation Algorithm for Underwater OFDM Acoustic CommunicationSystems [J]. Computer Science, 2021, 48(6A): 387-391.
[4] SONG Bo-sheng, CHENG Yu. Uniform Solution to QAST Problem by Communication P Systems with MembraneDivision and Promoters [J]. Computer Science, 2020, 47(5): 38-42.
[5] SUN Shi-yuan, HE Yong. Designs and Implementations of Algorithms for Searching Terminal Words of Automata [J]. Computer Science, 2020, 47(11A): 599-603.
[6] CHEN Xue-ping, HE Yong, XIAO Fen-fang. Synchronization of a Certain Family of Automata and Consumption Function Analysis [J]. Computer Science, 2019, 46(11A): 535-538.
[7] YU Jian-jun, WU Chun-ming. Computational Complexity Analysis of Virtual Network Mapping Problem [J]. Computer Science, 2018, 45(11): 87-91.
[8] LU Zheng-fu, PU Yan-hong, NI Sheng-bin, XU Chen-ming, YANG Chun-yao. Design and Simulation of Fair Data Exchange Protocol with Bounded Rationality [J]. Computer Science, 2018, 45(11): 115-123.
[9] LU Zhao and ZHU Xiao-shu. Research on Image Processing Algorithm Based on Compressed Sensing [J]. Computer Science, 2017, 44(6): 312-316.
[10] ZHANG Ju-xiao. Application of Nondeterministic Finite Automata in Braille Transcoding [J]. Computer Science, 2017, 44(1): 271-276.
[11] CEN Yue-feng, WANG Wan-liang, YAO Xin-wei, WANG Chao-chao and PAN Tie-qiang. Decision Tree Based Coding Unit Splitting Algorithm for HEVC [J]. Computer Science, 2016, 43(4): 308-312.
[12] HE Kun,YAO Peng-cheng and LI Li-wen. Complete Algorithm for 2D Rectangular Packing Problem [J]. Computer Science, 2014, 41(8): 55-59.
[13] ZHANG Ya-hong,ZHANG Lin-lin,ZHAO Kai,CHEN Jia-li and FENG Zai-wen. Runtime Verification Method for Web Service Based on UML2.0Sequence Diagrams [J]. Computer Science, 2013, 40(7): 138-138.
[14] GUO Yan-yan and LIU Jing-lei. Formalization for Model Element of UML Statechart in RSL [J]. Computer Science, 2013, 40(5): 177-183.
[15] . Computational Complexity of Probabilistic Inference in Icing Graphical Model [J]. Computer Science, 2013, 40(2): 253-256.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!