B 2000

Some Remarks on Weak Bisimilarity of BPA-Processes

ČERNÁ, Ivana a Jitka STŘÍBRNÁ

Základní údaje

Originální název

Some Remarks on Weak Bisimilarity of BPA-Processes

Autoři

ČERNÁ, Ivana a Jitka STŘÍBRNÁ

Vydání

Brno, 26 s. FIMU-RS-2000-09, 2000

Nakladatel

FI MU Brno

Další údaje

Jazyk

angličtina

Typ výsledku

Odborná kniha

Obor

10000 1. Natural Sciences

Stát vydavatele

Česká republika

Utajení

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

Odkazy

Kód RIV

RIV/00216224:14330/00:00002688

Organizační jednotka

Fakulta informatiky
Změněno: 26. 2. 2001 07:26, prof. RNDr. Ivana Černá, CSc.

Anotace

V originále

The purpose of this work is to examine the decidability problem of weak bisimilarity for BPA-processes. It has been known that strong bisimilarity, which may be considered a special case of weak bisimilarity, where the internal (silent) action tau is treated equally to observable actions, is decidable for BPA-processes. For strong bisimilarity, these processes are finitely branching and so for two non-bisimilar processes there exists a level n that distinguishes the two processes. Additionally, from the decidability of whether two processes are equivalent at a given level n, semidecidability of strong non-bisimilarity directly follows. We examine the following two closely related approaches to semidecidability of strong equivalence: 1.construction of a (finite) bisimulation or expansion tree, 2.construction of a finite Caucal base. We have attempted to find out if any of the above mentioned approaches could be generalized to (semi)decide weak bisimilarity. Our findings indicate that a direct generalization is not sufficient and an efficient (semi)decision procedure cannot be obtained in this way.

Návaznosti

GA201/00/0400, projekt VaV
Název: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Nekonečně stavové souběžné systémy - modely a verifikace
GA201/99/D026, projekt VaV
Název: Rozhodnutelnost a složitost observačních ekvivalencí na nekonečně stavových procesech
Investor: Grantová agentura ČR, Rozhodnutelnost a složitost observačních ekvivalencí na nekonečně stavových procesech
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ů