Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Unboundedness Problems for Languages of Vector Addition Systems

Uproszczony widok
dc.abstract.enA vector addition system (VAS) with an initial and a final marking and transition labels induces a language. In part because the reachability problem in VAS remains far from being well-understood, it is difficult to devise decision procedures for such languages. This is especially true for checking properties that state the existence of infinitely many words of a particular shape. Informally, we call these unboundedness properties. We present a simple set of axioms for predicates that can express unboundedness properties. Our main result is that such a predicate is decidable for VAS languages as soon as it is decidable for regular languages. Among other results, this allows us to show decidability of (i) separability by bounded regular languages, (ii) unboundedness of occurring factors from a language K with mild conditions on K, and (iii) universality of the set of factors.
dc.affiliationUniwersytet Warszawski
dc.conference.countryCzechy
dc.conference.datefinish2018-07-13
dc.conference.datestart2018-07-09
dc.conference.placePraha
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2018
dc.conference.weblinkhttps://iuuk.mff.cuni.cz/events/icalp2018/
dc.contributor.authorCzerwiński, Wojciech
dc.contributor.authorZetzsche, Georg
dc.contributor.authorHofman, Piotr
dc.date.accessioned2024-01-26T11:18:48Z
dc.date.available2024-01-26T11:18:48Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.identifier.doi10.4230/LIPICS.ICALP.2018.119
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/124139
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2018/9123/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages119:1--119:15
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleUnboundedness Problems for Languages of Vector Addition Systems
dc.typeJournalArticle
dspace.entity.typePublication