Page 34 - 《软件学报》2026年第1期

陈蔚骏 等: 向量加法系统可达性问题复杂性下界研究综述 31

2) 其他开放问题. 除此之外, 我们认为如下开放问题也是重要的.
(1) 是否存在一族二进制 3-VASS 可达性问题实例, 使得它们的证据长度至少是 2-exp(n) ?
(2) 是否存在一族二进制 7-VASS 可达性问题实例, 使得它们的证据长度至少是 3-exp(n) ?
(3) 一进制 7-VASS 是否是 EXPSPACE-难的?
(4) 1 -PVASS 可覆盖性问题是否是 EXPSPACE-难的?
关于问题 2(1)、2(2), 我们倾向于相信二进制 3-VASS 可达性问题是 Tower-完备的, 但是目前却找不到任何

严格长于 2 Ω(n) 的实例. 一进制 7-VASS 目前已知是 PSPACE-难的, 但是 8-VASS 即是 Tower-难, 二者差距较大,
因此 7-VASS 大概率有更好的下界.
VASS 模型有不少变种, 这些变种上的可达性问题难度更大, 有些问题的可判定性目前都无从知晓. PVASS
(pushdown VASS) 是 VASS 的一个常见拓展模型, 它比普通 VASS 增加了一个栈, 目前已知 1-PVASS 可覆盖性问
题是 PSPACE-难的, 且在 EXPSPACE 中, 也是一个上下界较为接近但仍旧没有定论的开放问题. 关于更多限制
或拓展模型的相关验证问题, 可以参考文献 [16].

References
[1] Petri CA. Kommunikation mit Automaten [Ph.D. Thesis]. Bonn: Institute für Instrumentelle Mathematik, 1962.
[2] van Glabbeek R, Vaandrager F. Petri net models for algebraic theories of concurrency. In: Proc. of the 1987 Int’l Conf. on Parallel
Architectures and Languages Europe (PARLE). Eindhoven: Springer, 1987. 224–242. [doi: 10.1007/3-540-17945-3_13]
[3] Reisig W. Elements of Distributed Algorithms: Modeling and Analysis with Petri Nets. Berlin, Heidelberg: Springer, 2013. [doi: 10.1007/
978-3-662-03687-7]
[4] Zurawski R, Zhou MC. Petri nets and industrial applications: A tutorial. IEEE Trans. on Industrial Electronics, 1994, 41(6): 567–583.
[doi: 10.1109/41.334574]
[5] Chaouiya C. Petri net modelling of biological networks. Briefings in Bioinformatics, 2007, 8(4): 210–219. [doi: 10.1093/bib/bbm029]
[6] Hamadi R, Benatallah B. A Petri net-based model for Web service composition. In: Proc. of the 14th Australasian Database Conf.
Adelaide: Australian Computer Society Inc., 2003. 191–200.
[7] Angeli D, De Leenheer P, Sontag ED. A Petri net approach to the study of persistence in chemical reaction networks. Mathematical
Biosciences, 2007, 210(2): 598–618. [doi: 10.1016/j.mbs.2007.07.003]
[8] Lohmann N, Verbeek E, Dijkman R. Petri net transformations for business processes—A survey. In: Trans. on Petri Nets and Other
Models of Concurrency II: Special Issue on Concurrency in Process-aware Information Systems. Berlin, Heidelberg: Springer, 2009.
46–63. [doi:10.1007/978-3-642-00899-3_3]
[9] van der Aalst WMP. Petri-net-based workflow management software. In: Proc. of the 1996 NFS Workshop on Workflow and Process
Automation in Information Systems. 1996. 114–118.
[10] Sun J, Qin SY, Song YH. Fault diagnosis of electric power systems based on fuzzy Petri nets. IEEE Trans. on Power Systems, 2004,
19(4): 2053–2059. [doi: 10.1109/TPWRS.2004.836256]
[11] Karp RM, Miller RE. Parallel program schemata. Journal of Computer and System Sciences, 1969, 3(2): 147–195. [doi: 10.1016/S0022-
0000(69)80011-5]
[12] Hopcroft J, Pansiot JJ. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 1979, 8(2):
135–159. [doi: 10.1016/0304-3975(79)90041-0]
[13] Rackoff C. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 1978, 6(2): 223–231.
[doi: 10.1016/0304-3975(78)90036-1]
[14] Czerwiński W, Orlikowski Ł. Reachability in vector addition systems is Ackermann-complete. In: Proc. of the 62nd IEEE Annual Symp.
on Foundations of Computer Science (FOCS 2021). Denver: IEEE, 2022. 1229–1240. [doi: 10.1109/FOCS52979.2021.00120]
[15] Leroux J. The reachability problem for Petri nets is not primitive recursive. In: Proc. of the 62nd IEEE Annual Symp. on Foundations of
Computer Science (FOCS 2021). Denver: IEEE, 2022. 1241–1252. [doi: 10.1109/FOCS52979.2021.00121]
[16] Zhang WB, Long H. State-of-the-art survey on verification of vector addition systems. Ruan Jian Xue Bao/Journal of Software, 2018,
29(6): 1566–1581 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5465.htm [doi: 10.13328/j.cnki.jos.005465]
[17] Yang QZ. The study of vector addition system [Ph.D. Thesis]. Shanghai: Shanghai Jiao Tong University, 2022 (in Chinese with English
abstract). [doi: 10.27307/d.cnki.gsjtu.2022.000038]