%0 Conference Paper %1 conf/rp/LerouxS14 %A Leroux, Jérôme %A Schnoebelen, Philippe %B RP %D 2014 %E Ouaknine, Joël %E Potapov, Igor %E Worrell, James %I Springer %K petrinets reachability weakcomputation %P 190-202 %T On Functions Weakly Computable by Petri Nets and Vector Addition Systems. %U http://www.lsv.fr/Publis/PAPERS/PDF/LS-rp14.pdf %V 8762 %X We show that any unbounded function weakly computable by a Petri net or a VASS cannot be sublinear. This answers a long-standing folklore conjec-ture about weakly computing the inverses of some fast-growing functions. The proof relies on a pumping lemma for sets of runs in Petri nets or VASSes. %@ 978-3-319-11438-5

@inproceedings{conf/rp/LerouxS14, abstract = {We show that any unbounded function weakly computable by a Petri net or a VASS cannot be sublinear. This answers a long-standing folklore conjec-ture about weakly computing the inverses of some fast-growing functions. The proof relies on a pumping lemma for sets of runs in Petri nets or VASSes.}, added-at = {2020-01-17T15:24:29.000+0100}, author = {Leroux, Jérôme and Schnoebelen, Philippe}, biburl = {https://www.bibsonomy.org/bibtex/29f98d71c116ed5cfd3fdd09f0975814e/paves_intern}, booktitle = {RP}, crossref = {conf/rp/2014}, editor = {Ouaknine, Joël and Potapov, Igor and Worrell, James}, ee = {https://doi.org/10.1007/978-3-319-11439-2_15}, interhash = {b31e715991787496e3209eb30a6f15c9}, intrahash = {9f98d71c116ed5cfd3fdd09f0975814e}, isbn = {978-3-319-11438-5}, keywords = {petrinets reachability weakcomputation}, pages = {190-202}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2020-01-17T15:24:29.000+0100}, title = {On Functions Weakly Computable by Petri Nets and Vector Addition Systems.}, url = {http://www.lsv.fr/Publis/PAPERS/PDF/LS-rp14.pdf}, volume = 8762, year = 2014 }