Comparing Expressibility of Normed BPA and Normed BPP Processes.

ČERNÁ, Ivana; Mojmír KŘETÍNSKÝ a Antonín KUČERA. Comparing Expressibility of Normed BPA and Normed BPP Processes. Acta informatica. Berlin: Springer-Verlag, 1999, roč. 36, č. 3, s. 233-256. ISSN 0001-5903.

Základní údaje

Originální název

Comparing Expressibility of Normed BPA and Normed BPP Processes.

Autoři

ČERNÁ, Ivana ORCID (203 Česká republika, garant); Mojmír KŘETÍNSKÝ (203 Česká republika) a Antonín KUČERA (203 Česká republika)

Vydání

Acta informatica, Berlin, Springer-Verlag, 1999, 0001-5903

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

20206 Computer hardware and architecture

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.321

Kód RIV

RIV/00216224:14330/99:00000703

Organizační jednotka

Fakulta informatiky

UT WoS

000079817400003

Klíčová slova anglicky

concurrency; bisimilarity; infinite-state systems

Štítky

bisimilarity, concurrency, infinite-state systems

---

Anotace

V originále

We present an exact characterization of those transition systems which can be equivalently (up to bisimilarity) defined by the syntax of normed \BPA\ and normed \BPP\ processes. We provide such a characterization for classes of normed BPA and normed BPP processes as well. Next we demonstrate decidability of the problem whether for a given normed \BPA\ process $\Delta$ there is some unspecified normed \BPP\ process $\Delta'$ such that $\Delta$ and $\Delta'$ are bisimilar. The algorithm is polynomial. Furthermore, we show that if the answer to the previous question is positive, then the process $\Delta'$ is effectively constructible. Analogous algorithms are provided for normed \BPP\ processes. Simplified versions of the mentioned algorithms which work for nBPA and nBPP are given too. As a simple consequence we obtain decidability of bisimilarity in the union of normed \BPA\ and normed \BPP\ processes.

Česky

uvádíme přesnou charakterizaci těch přechodových systémů s návěštími, které lze (až na bisimulačni ekvivalenci) vyjádřit jak pomocí syntaxe normovaných BPA procesů a normovaných BPP procesů. Ukazujeme algoritmickou řešitelnost problému, kdy je dán normovaný BPA proces a jest rozhodnout, zda existuje s ním bisimulačně ekvivaletní normovaný BPP proces. Dále ukazujeme, že pokud odpověď na tento problém ANO, pak lze ekvivaletní BPP proces efektivně zkonstruovat.

---

Návaznosti

GA201/97/0456, projekt VaV	Název: Meze algoritmické verifikovatelnosti nekonečně stavových systémů Investor: Grantová agentura ČR, Meze algoritmické verifikovatelnosti nekonečně stavových systémů
GA201/98/P046, projekt VaV	Název: Rozhodnutelné problémy v algebrách procesů Investor: Grantová agentura ČR, Rozhodnutelné problémy v algebrách procesů
MSM 143300001, záměr	Název: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů