J. Leroux ; M. Praveen ; Ph. Schnoebelen ; G. Sutre - 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 - https://doi.org/10.23638/LMCS-15(4:15)2019
On Functions Weakly Computable by Pushdown Petri Nets and Related SystemsArticle

Authors: J. Leroux ; M. Praveen ; Ph. Schnoebelen ; G. Sutre ORCID

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.


Volume: Volume 15, Issue 4
Published on: December 18, 2019
Accepted on: November 26, 2019
Submitted on: April 9, 2019
Keywords: Computer Science - Formal Languages and Automata Theory, Computer Science - Logic in Computer Science
Funding:
    Source : OpenAIRE Graph
  • IDEAL-BASED ALGORITHMS FOR VASSES AND WELL-STRUCTURED SYSTEMS; Funder: French National Research Agency (ANR); Code: ANR-17-CE40-0028

1 Document citing this article

Consultation statistics

This page has been seen 3108 times.
This article's PDF has been downloaded 367 times.