On Functions Weakly Computable by Pushdown Petri Nets and Related Systems

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...

Full description

Saved in:
Bibliographic Details
Published in:Logical methods in computer science 2019-12, Vol.15 (4)
Main Authors: Leroux, Jérôme, Praveen, M., Schnoebelen, Philippe, Sutre, Grégoire
Format: Article
Language:English
Subjects:
Computer Science
computer science - formal languages and automata theory
computer science - logic in computer science
Formal Languages and Automata Theory
Logic in Computer Science
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1860-5974
DOI:10.23638/LMCS-15(4:15)2019