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
ZHU Kai1,2, WU Guo-qing1, YUAN Meng-ting1
CLC Number:
[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. |
|