10.23638/LMCS-15(4:15)2019
Leroux, J.
J.
Leroux
Praveen, M.
M.
Praveen
Schnoebelen, Ph.
Ph.
Schnoebelen
Sutre, G.
G.
Sutre
On Functions Weakly Computable by Pushdown Petri Nets and Related
Systems
episciences.org
2019
Computer Science - Formal Languages and Automata Theory
Computer Science - Logic in Computer Science
contact@episciences.org
episciences.org
2019-04-09T10:45:58+02:00
2020-02-03T18:21:42+01:00
2019-12-18
eng
Journal article
https://lmcs.episciences.org/5362
arXiv:1904.04090
1860-5974
PDF
1
Logical Methods in Computer Science ; Volume 15, Issue 4 ; 1860-5974
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.