软件学报

作者：陈蔚骏，傅育熙，龙环

单位：陈蔚骏，上海交通大学 软件学院, 上海 20024011,傅育熙，上海交通大学 计算机科学与工程系, 上海 20024002,龙环，上海交通大学 计算机科学与工程系, 上海 20024003

关键词：Petri 网;向量加法系统;可达性;计算复杂性

基金：国家自然科学基金(62072299); 上海市科委“科技创新行动计划” (24BC3200500, 24BC3200300)

并发与可扩展性是绝大多数复杂系统的关键性质. 作为并发建模的常用语言, Petri网被大量应用于众多领域. Petri网的数学抽象, 即向量加法系统是计算机科学中的重要研究对象, 向量加法系统的可达性问题的算法与复杂性刻画是过去50年理论计算机科学中最重要的问题之一. 对向量加法系统可达性问题的复杂性下界研究进行系统而全面的总结与阐述, 主要内容包括: (1) 向量加法系统的定义、等价模型、向量加法系统的可达性问题; (2) 向量加法系统可达性问题复杂性的研究进展; (3) 固定维度的可达性问题的下界证明方法及其之间的联系 ; (4) 当前的研究瓶颈及有待解决的问题、未来的研究方向与挑战.

来源：2026年第1期

《软件学报》期刊编辑部

查看软件学报杂志2026年第1期