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

    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 F1α 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 2238 times.
    This article's PDF has been downloaded 257 times.