On Functions Weakly Computable by Pushdown Petri Nets and Related Systems

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.

References in corpus (2)

• Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
• The Power of Priority Channel Systems

Cited by in corpus (1)

• Verifying Unboundedness via Amalgamation