计算机学院理论计算机科学研究所博士生郑扬珞获CONCUR 2025 最佳学生论文奖

获奖论文介绍

获奖论文着眼于向量加法系统的可达性问题。向量加法系统是与Petri网等价的重要理论模型，其可达性问题作为理论计算机中重要的开放问题，直到2021年才基本得到解决。郑扬珞的论文聚集于向量加法系统的几何维度这一参数，重点考察几何二维向量加法系统的可达性问题，利用2019年Czerwinski等人提出的路径泵引技术证明了该问题是PSPACE完备的。这一结果改进了此前基于2015年Blondin等人线性路径模式技术得到的EXPSPACE上界，并在技术上构建了几何二维与传统二维向量加法系统之间的桥梁。目前这一研究成果已被华沙大学Czerwinski等人发表在ICALP 2025上的最新工作引用。

图：BASICS师生讨论研究工作

获奖学生的导师傅育熙教授（右一）此前在无穷状态系统领域已深耕多年。2024年，傅育熙教授与组内博士生郑扬珞（右三）、毕业生杨启哲博士（右二）合作，将固定维度向量加法系统的复杂性由2019年的F_d+4上界改进至F_d，并首次明确定义了几何维度这一概念。这一工作已于当年发表在国际知名会议ICALP 2024上。无穷状态系统是理论计算机科学的重要分支，但在国内鲜有学者涉足。近年来团队在向量加法系统研究中取得的成就也是对傅育熙教授长期钻研的再次肯定。