On Functions Weakly Computable by Pushdown Petri Nets and Related
SystemsArticle
Authors: J. Leroux ; M. Praveen ; Ph. Schnoebelen ; G. Sutre
NULL##NULL##NULL##NULL
J. Leroux;M. Praveen;Ph. Schnoebelen;G. Sutre
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α for
α<ωω, hence they are computationally more powerful than
standard vector addition systems. On the other hand they cannot weakly compute
the inverses F−1α or indeed any sublinear function. The proof relies
on a pumping lemma for runs of GVASes that is of independent interest.