近期，理论计算机领域权威国际会议CONCUR在丹麦奥胡斯大学举办。上海交通大学计算机学院理论计算机科学研究所博士生郑扬珞发表的独立作者论文 Reachability in Vector Addition Systems with States Parameterized by Geometric Dimension 获得最佳学生论文奖。CONCUR全称International Conference on Concurrency Theory，是聚焦于并发计算系统理论的知名国际会议。该会议自1990年起已连续举办36届。这是亚洲学生首次获得该会议最佳学生论文奖。

获奖论文介绍

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

BASICS师生讨论研究工作

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