Some Problems Related to Bisimilarity on BPP

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F04%3A00010321" target="_blank" >RIV/61989100:27240/04:00010321 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Some Problems Related to Bisimilarity on BPP

Original language description

Jančar has in 2003 shown that bisimilarity on Basic Parallel Processes (BPP) can be decided in polynomial space. Bisimilarity is studied on various subclasses of BPP as well. We present summary of known complexity bounds of some such bisimilarity problems. Moreover is here shown that deciding regularity of a BPP is PSPACE-complete. So far this problem was only known to be PSPACE-hard.

Czech name

Some Problems Related to Bisimilarity on BPP

Czech description

Jančar has in 2003 shown that bisimilarity on Basic Parallel Processes (BPP) can be decided in polynomial space.

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F03%2F1161" target="_blank" >GA201/03/1161: Verification of infinite-state systems</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2004

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 of Movep'04

ISBN

—

ISSN

—

e-ISSN

—

Number of pages

7

Pages from-to

96-102

Publisher name

Université Libre de Bruxelles

Place of publication

Brussels

Event location

Brussels

Event date

Jan 1, 2004

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—