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

32 软件学报 2026 年第 37 卷第 1 期

[18] Valiant L G, Paterson MS. Deterministic one-counter automata. Journal of Computer and System Sciences, 1975, 10(3): 340–350. [doi:
10.1016/S0022-0000(75)80005-5]
[19] Travers S. The complexity of membership problems for circuits over sets of integers. Theoretical Computer Science, 2006, 369(1–3):
211–229. [doi: 10.1016/j.tcs.2006.08.017]
[20] Schmitz S. Complexity hierarchies beyond elementary. ACM Trans. on Computation Theory (TOCT), 2016, 8(1): 3. [doi: 10.1145/
2858784]
[21] Blondin M, Englert M, Finkel A, Göller S, Haase C, Lazić R, Mckenzie P, Totzke P. The reachability problem for two-dimensional vector
addition systems with states. Journal of the ACM (JACM), 2021, 68(5): 34. [doi: 10.1145/3464794]
[22] Lafourcade P, Lugiez D, Treinen R. Intruder deduction for AC-like equational theories with homomorphisms. In: Proc. of the 16th Int’l
Conf. on Term Rewriting and Applications. Nara: Springer, 2005. 308–322. [doi: 10.1007/978-3-540-32033-3_23]
[23] Haase C, Kreutzer S, Ouaknine J, Worrell J. Reachability in succinct and parametric one-counter automata. In: Proc. of the 20th Int’l
Conf. on Concurrency Theory. Bologna: Springer, 2009. 369–383. [doi: 10.1007/978-3-642-04081-8_25]
[24] Fearnley J, Jurdziński M. Reachability in two-clock timed automata is PSPACE-complete. Information and Computation, 2015, 243:
26–36. [doi: 10.1016/j.ic.2014.12.004]
[25] Mayr EW. An algorithm for the general Petri net reachability problem. In: Proc. of the 13th Annual ACM Symp. on Theory of
Computing. Milwaukee: ACM, 1981. 238–246. [doi: 10.1145/800076.802477]
[26] Kosaraju SR. Decidability of reachability in vector addition systems (Preliminary Version). In: Proc. of the 14th Annual ACM Symp. on
Theory of Computing. San Francisco: ACM, 1982. 267–281. [doi: 10.1145/800070.802201]
[27] Lambert JL. A structure to decide reachability in Petri nets. Theoretical Computer Science, 1992, 99(1): 79–104. [doi: 10.1016/0304-3975
(92)90173-D]
[28] Sacerdote GS, Tenney RL. The decidability of the reachability problem for vector addition systems (Preliminary Version). In: Proc. of the
9th Annual ACM Symp. on Theory of Computing. Boulder: ACM, 1977. 61–76. [doi: 10.1145/800105.803396]
[29] Leroux J, Schmitz S. Demystifying reachability in vector addition systems. In: Proc. of the 30th Annual ACM/IEEE Symp. on Logic in
Computer Science. Kyoto: IEEE, 2015. 56–67. [doi: 10.1109/LICS.2015.16]
[30] Leroux J, Schmitz S. Ideal decompositions for vector addition systems. In: Proc. of the 33rd Symp. on Theoretical Aspects of Computer
Science (STACS 2016). Orléans: Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2016. 1. [doi: 10.4230/LIPIcs.STACS.2016.1]
[31] Schmitz S. Algorithmic Complexity of Well-quasi-orders. Paris: École Normale Supérieure, 2017.
[32] Leroux J, Schmitz S. Reachability in vector addition systems is primitive-recursive in fixed dimension. In: Proc. of the 34th Annual
ACM/IEEE Symp. on Logic in Computer Science (LICS 2019). Vancouver: IEEE, 2019. 1–13. [doi: 10.1109/LICS.2019.8785796]
[33] Fu YX, Yang QZ, Zheng YL. Improved algorithm for reachability in d-VASS. In: Proc. of the 51st Int’l Colloquium on Automata,
Languages, and Programming (ICALP 2024). Tallinn: Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2024. 136. [doi: 10.4230/
LIPIcs.ICALP.2024.136]
[34] Lipton R. The reachability problem requires exponential space. Research Report, #63, New Haven: Department of Computer Science,
Yale University, 1976.
[35] Czerwiński W, Lasota S, Lazić R, Leroux J, Mazowiecki F. The reachability problem for Petri nets is not elementary. Journal of the ACM
(JACM), 2020, 68(1): 7. [doi: 10.1145/3422822]
[36] Czerwiński W, Lasota S, OrlikowskiŁ. Improved lower bounds for reachability in vector addition systems. In: Proc. of the 48th Int’l
Colloquium on Automata, Languages, and Programming (ICALP 2021). Dagstuhl: Schloss Dagstuhl—Leibniz-Zentrum für Informatik,
2021. 128. [doi: 10.4230/LIPIcs.ICALP.2021.128]
[37] Czerwiński W, Jecker I, Lasota S, Leroux J, Orlikowski Ł. New lower bounds for reachability in vector addition systems. In: Proc. of the
43rd IARCS Annual Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Telangana:
Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2023. 35. [doi: 10.4230/LIPIcs.FSTTCS.2023.35]
[38] Leroux J. The reachability problem for Petri nets is not primitive recursive. CoRR, abs/2104.12695, 2021.
[39] Czerwiński W, Orlikowski L. Lower bounds for the reachability problem in fixed dimensional vasses. In: Proc. of the 37th Annual
ACM/IEEE Symp. on Logic in Computer Science. Haifa: ACM, 2022. 40. [doi: 10.1145/3531130.3533357]
[40] Leroux J, Sutre G. On flatness for 2-dimensional vector addition systems with states. In: Proc. of the 15th Int’l Conf. on Concurrency
Theory. London: Springer, 2004. 402–416. [doi: 10.1007/978-3-540-28644-8_26]
[41] Leroux J. Flat Petri nets. In: Proc. of the 2021 Int’l Conf. on Applications and Theory of Petri Nets and Concurrency. Cham: Springer,
2021. 17–30. [doi: 10.1007/978-3-030-76983-3_2]
[42] Rosier LE, Yen HC. A multiparameter analysis of the boundedness problem for vector addition systems. Journal of Computer and System