计算机科学 ›› 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
  • 基金资助:
    国家自然科学基金(61640221,61872272)

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

中图分类号: 

  • 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问题
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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!