2026-07-22T08:34:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11565 2024-03-06T10:48:19Z ddc:004 open_access

Finkel Was Right: Counter-Examples to Several Conjectures on Variants of Vector Addition Systems (Invited Talk) Lazić, Ranko Petri nets vector addition systems reachability Studying one-dimensional grammar vector addition systems has long been advocated by Alain Finkel. In this presentation, we shall see how research on those systems has led to the recent breakthrough tower lower bound for the reachability problem on vector addition systems, obtained by Czerwiński et al. In fact, we shall look at how appropriate modifications of an underlying technical construction can lead to counter-examples to several conjectures on one-dimensional grammar vector addition systems, fixed-dimensional vector addition systems, and fixed-dimensional flat vector addition systems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ranko Lazić 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.3 urn:nbn:de:0030-drops-115653 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.3 eng https://creativecommons.org/licenses/by/3.0/legalcode