# zbMATH — the first resource for mathematics

On functions weakly computable by pushdown Petri nets and related systems. (English) Zbl 1427.68203
Summary: 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.
##### MSC:
 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: