D 2004

Highly Undecidable Questions for Process Algebras

JANCAR, Petr a Jiří SRBA

Základní údaje

Originální název

Highly Undecidable Questions for Process Algebras

Název česky

Vysoce nerozhodnutelne problemy pro algebry procesu

Autoři

JANCAR, Petr a Jiří SRBA

Vydání

USA, Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04), od s. ?, 14 s. 2004

Nakladatel

Kluwer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

Kód RIV

RIV/00216224:14330/04:00010073

Organizační jednotka

Fakulta informatiky

UT WoS

000227054700039

Klíčová slova anglicky

high undecidability; process rewrite systems; completeness

Štítky

Změněno: 18. 1. 2005 17:32, Prof. Jiří Srba, Ph.D.

Anotace

ORIG CZ

V originále

We show Sigma^1_1-completeness of weak bisimilarity for PA (process algebra), and of weak simulation preorder/equivalence for PDA (pushdown automata), PA and PN (Petri nets). We also show Pi^1_1-hardness of weak omega-trace equivalence for the (sub)classes BPA (basic process algebra) and BPP (basic parallel processes).

Česky

V clanku je ukazana Sigma^1_1 uplnost slabe bisimilarity pro tridu PA a slabeho simulacniho predusporadani/ekvivalence pro zasobnikove automaty, PA a Petriho site. Rovnez jsou studovany problemy slabe omega-jazykove ekvivalence pro BPA a BPP.

Návaznosti

GA201/03/1161, projekt VaV
Název: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
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ů