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

Shortest paths in one-counter systems

Uproszczony widok
dc.abstract.enWe show that any one-counter automaton with n states, if its language is non-empty, accepts some word of length at most O(n2). This closes the gap between the previously known upper bound of O(n3) and lower bound of Ω(n2). More generally, we prove a tight upper bound on the length of shortest paths between arbitrary configurations in one-counter transition systems (weaker bounds have previously appeared in the literature).
dc.affiliationUniwersytet Warszawski
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorChistikov, Dmitry
dc.contributor.authorCzerwiński, Wojciech
dc.contributor.authorWehar, Michael
dc.contributor.authorHofman, Piotr
dc.date.accessioned2024-01-26T07:36:00Z
dc.date.available2024-01-26T07:36:00Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.description.number1
dc.description.volume15
dc.identifier.doi10.23638/LMCS-15(1:19)2019
dc.identifier.issn1860-5974
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/119760
dc.identifier.weblinkhttps://lmcs.episciences.org/5251
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLogical Methods in Computer Science
dc.relation.pages19:1–19:28
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleShortest paths in one-counter systems
dc.typeJournalArticle
dspace.entity.typePublication