Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

New Pumping Technique for 2-Dimensional VASS

Uproszczony widok
dc.abstract.enWe propose a new pumping technique for 2-dimensional vector addition systems with states (2-VASS) building on natural geometric properties of runs. We illustrate its applicability by reproving an exponential bound on the length of the shortest accepting run, and by proving a new pumping lemma for languages of 2-VASS. The technique is expected to be useful for settling questions concerning languages of 2-VASS, e.g., for establishing decidability status of the regular separability problem.
dc.affiliationUniwersytet Warszawski
dc.conference.countryNiemcy
dc.conference.datefinish2019-08-30
dc.conference.datestart2019-08-26
dc.conference.placeAachen
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesshortcutMFCS
dc.conference.shortcutMFCS 2019
dc.conference.weblinkhttps://tcs.rwth-aachen.de/mfcs2019/
dc.contributor.authorLasota, Sławomir
dc.contributor.authorCzerwiński, Wojciech
dc.contributor.authorLöding,
dc.contributor.authorPiórkowski, Radosław
dc.date.accessioned2024-01-25T13:48:34Z
dc.date.available2024-01-25T13:48:34Z
dc.date.copyright2019-08-20
dc.date.issued2019
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.description.volume138
dc.identifier.doi10.4230/LIPICS.MFCS.2019.62
dc.identifier.issn1868-8969
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/113614
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2019/11006/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLeibniz International Proceedings in Informatics
dc.relation.pages62:1--62:14
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleNew Pumping Technique for 2-Dimensional VASS
dc.typeJournalArticle
dspace.entity.typePublication