Leroux, J. and Praveen, M. and Schnoebelen, Ph. and Sutre, G. - On Functions Weakly Computable by Pushdown Petri Nets and Related Systems

lmcs:5362 - Logical Methods in Computer Science, December 18, 2019, Volume 15, Issue 4
On Functions Weakly Computable by Pushdown Petri Nets and Related Systems

Authors: Leroux, J. and Praveen, M. and Schnoebelen, Ph. and Sutre, G.

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.


Source : oai:arXiv.org:1904.04090
Volume: Volume 15, Issue 4
Published on: December 18, 2019
Submitted on: April 9, 2019
Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science


Share