一句话：证明语法控制向量加法系统（GVAS）能弱计算所有快速增长函数 F_α（α<ω^ω），但不能弱计算反函数或任何次线性函数。
本文研究由文法控制的向量加法系统（GVAS，下推 Petri 网的一种变体）对数值函数的弱可计算能力。GVAS 是无限状态系统，作者刻画其可生成的函数类：证明对每个 α<ω^ω，快速增长函数 F_α 都可由 GVAS 弱计算，因此其计算能力强于标准向量加法系统。相反，GVAS 不能弱计算这些函数的反函数 F_α^{-1}，也不能弱计算任何次线性函数，说明其能力存在明确上界。核心证明技术是 GVAS 游程（run）的泵引理，该引理本身具有独立价值，可望用于分析下推 Petri 网及相关系统的计算边界。
We consider numerical functions weakly computable by grammar-controlled vector addition systems (GVASes, a variant of pushdown Petri nets). GVASes can weakly compute all fast growing functions $F_\alpha$ for $\alpha<\omega^\omega$, hence they are computationally more powerful than standard vector addition systems. On the other hand they cannot weakly compute the inverses $F_\alpha^{-1}$ or indeed any sublinear function. The proof relies on a pumping lemma for runs of GVASes that is of independent interest.
@article{paperbot737,
title = {On Functions Weakly Computable by Pushdown Petri Nets and Related Systems},
author = {J. Leroux and M. Praveen and Ph. Schnoebelen and G. Sutre},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 4},
year = {2019},
doi = {10.23638/lmcs-15(4:15)2019}
}