Complexity of deciding bisimilarity between normed BPA and normed BPP

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F10%3A86075745" target="_blank" >RIV/61989100:27240/10:86075745 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Complexity of deciding bisimilarity between normed BPA and normed BPP
Popis výsledku v původním jazyce
We present a polynomial-time algorithm deciding bisimilarity between a normed BPA process and a normed BPP process, with running time O(n^7). This improves the previously known exponential upper bound. We first suggest an O(n^3) transformation of the BPPprocess into "prime form". Our algorithm then relies on a polynomial bound for a "finite-state core" of the transition system generated by the (transformed) BPP process.
Název v anglickém jazyce
Complexity of deciding bisimilarity between normed BPA and normed BPP
Popis výsledku anglicky
We present a polynomial-time algorithm deciding bisimilarity between a normed BPA process and a normed BPP process, with running time O(n^7). This improves the previously known exponential upper bound. We first suggest an O(n^3) transformation of the BPPprocess into "prime form". Our algorithm then relies on a polynomial bound for a "finite-state core" of the transition system generated by the (transformed) BPP process.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—

Projekt
<a href="/cs/project/1M0567" target="_blank" >1M0567: Centrum aplikované kybernetiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2010
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ů

Podobné výsledky(10)