paperbot · PL 论文追踪

RSS

On Functions Weakly Computable by Pushdown Petri Nets and Related Systems

LMCS vol.Volume 15, Issue 42019
J. Leroux, M. Praveen, Ph. Schnoebelen, G. Sutre

尚未生成 AI 速览(可能缺少 API key 或等待下次运行补跑)。

原文摘要(Abstract)

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 原文 ·

BibTeX
@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}
}