Branching bisimilarity of normed BPA processes is in NEXPTIME

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F15%3A86096903" target="_blank" >RIV/61989100:27240/15:86096903 - isvavai.cz</a>
Result on the web
<a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7174879" target="_blank" >http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7174879</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/LICS.2015.25" target="_blank" >10.1109/LICS.2015.25</a>

Result language
angličtina
Original language name
Branching bisimilarity of normed BPA processes is in NEXPTIME
Original language description
Branching bisimilarity of normed Basic Process Algebra (BPA) processes was shown to be decidable by Yuxi Fu (ICALP 2013) but his proof has not provided any upper complexity bound. We present a simpler approach based on relative prime decompositions thatleads to a nondeterministic exponential-time algorithm. We also derive that semantic finiteness (the question if a given normed BPA process is branching bisimilar with some finite-state process) belongs to NExpTime as well.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA15-13784S" target="_blank" >GA15-13784S: Computational complexity of selected verification problems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings - Symposium on Logic in Computer Science 2015
ISBN
978-1-4799-8875-4
ISSN
1043-6871
e-ISSN
—
Number of pages
12
Pages from-to
168-179
Publisher name
Institute of Electrical and Electronics Engineers
Place of publication
New York
Event location
Kyoto
Event date
Jul 6, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)