| 摘要: |
| 并发与可扩展性是绝大多数复杂系统的关键性质. 作为并发建模的常用语言, Petri网被大量应用于众多领域. Petri网的数学抽象, 即向量加法系统是计算机科学中的重要研究对象, 向量加法系统的可达性问题的算法与复杂性刻画是过去50年理论计算机科学中最重要的问题之一. 对向量加法系统可达性问题的复杂性下界研究进行系统而全面的总结与阐述, 主要内容包括: (1) 向量加法系统的定义、等价模型、向量加法系统的可达性问题; (2) 向量加法系统可达性问题复杂性的研究进展; (3) 固定维度的可达性问题的下界证明方法及其之间的联系 ; (4) 当前的研究瓶颈及有待解决的问题、未来的研究方向与挑战. |
| 关键词: Petri 网 向量加法系统 可达性 计算复杂性 |
| DOI：10.13328/j.cnki.jos.007441 |
| 分类号:TP301 |
| 基金项目:国家自然科学基金(62072299); 上海市科委“科技创新行动计划” (24BC3200500, 24BC3200300) |
|
| Survey on Complexity Lower Bound Research for Reachability Problem in Vector Addition Systems |
|
CHEN Wei-Jun1, FU Yu-Xi2, LONG Huan2
|
|
1.School of Software, Shanghai Jiao Tong University, Shanghai 200240, China;2.Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
|
| Abstract: |
| Concurrency and scalability are fundamental properties of most complex systems. As a widely used formalism for modeling concurrency, Petri nets have been applied across various fields. Their mathematical abstraction, the vector addition system (VAS), has become a central object of study in theoretical computer science. The reachability problem of VAS, along with its algorithmic and complexity characterizations, has been regarded as one of the most fundamental and long-standing challenges in the field over the last 50 years. This study presents a comprehensive survey of the research on the complexity lower bounds of the VAS reachability problem. The definitions of VAS, their equivalent models, and the core verification problem, the reachability problem, are introduced. Known completeness results concerning the complexity of the reachability problem are reviewed. For the fixed-dimension case, proof frameworks based on multiplication triples and amplifiers are outlined, and the state-of-the-art achievements as well as core proof techniques are summarized. Finally, the current research bottlenecks, major open problems, and future challenges are discussed. |
| Key words: Petri net vector addition system (VAS) reachability computational complexity |
