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

Universality Problem for Unambiguous VASS

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:37:12Z
dc.abstract.enWe study languages of unambiguous VASS, that is, Vector Addition Systems with States, whose transitions read letters from a finite alphabet, and whose acceptance condition is defined by a set of final states (i.e., the coverability language). We show that the problem of universality for unambiguous VASS is ExpSpace-complete, in sheer contrast to Ackermann-completeness for arbitrary VASS, even in dimension 1. When the dimension d ∈ N is fixed, the universality problem is PSpace-complete if d ≥ 2, and coNP-hard for 1-dimensional VASSes (also known as One Counter Nets).
dc.affiliationUniwersytet Warszawski
dc.conference.countryAustria
dc.conference.datefinish2020-09-04
dc.conference.datestart2020-09-01
dc.conference.placeVienna
dc.conference.seriesInternational Conference on Concurrency Theory
dc.conference.seriesInternational Conference on Concurrency Theory
dc.conference.seriesshortcutCONCUR
dc.conference.shortcutCONCUR 2020
dc.conference.weblinkhttp://concur2020.forsyte.at/registration.html
dc.contributor.authorCzerwiński, Wojciech
dc.contributor.authorFigueira, Diego
dc.contributor.authorHofman, Piotr
dc.date.accessioned2024-01-26T11:19:36Z
dc.date.available2024-01-26T11:19:36Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.CONCUR.2020.36
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/124220
dc.identifier.weblinkhttps://doi.org/10.4230/LIPIcs.CONCUR.2020.36
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleUniversality Problem for Unambiguous VASS
dc.typeJournalArticle
dspace.entity.typePublication