Branching bisimilarity of normed BPA processes is in NEXPTIME

Kód výsledku v 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>
Výsledek na webu
<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>

Jazyk výsledku
angličtina
Název v původním jazyce
Branching bisimilarity of normed BPA processes is in NEXPTIME
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Branching bisimilarity of normed BPA processes is in NEXPTIME
Popis výsledku anglicky
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.

Projekt
<a href="/cs/project/GA15-13784S" target="_blank" >GA15-13784S: Výpočetní složitost vybraných verifikačních problémů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2015
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Proceedings - Symposium on Logic in Computer Science 2015
ISBN
978-1-4799-8875-4
ISSN
1043-6871
e-ISSN
—
Počet stran výsledku
12
Strana od-do
168-179
Název nakladatele
Institute of Electrical and Electronics Engineers
Místo vydání
New York
Místo konání akce
Kyoto
Datum konání akce
6. 7. 2015
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)