尚未生成 AI 速览(可能缺少 API key 或等待下次运行补跑)。
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.
DOI 原文 ·
@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}
}