Informace o projektu
Rozhodnutelnost a složitost observačních ekvivalencí na nekonečně stavových procesech

Logo poskytovatele
Kód projektu
GA201/99/D026
Období řešení
9/1999 - 8/2002
Investor / Programový rámec / typ projektu
Grantová agentura ČR
Fakulta / Pracoviště MU
Fakulta informatiky
WWW stránky projektu
http://www.fi.muni.cz/usr/stribrna/js-D026.html

Projekt si klade za cíl přispět novými poznatky ke studiu souběžných systémů, zejména v oblasti algoritmické rozhodnutelnosti problémů souvisejících s verifikací procesů s nekonečně mnoha stavy. Hlavním problémem, na který se chceme zaměřit, je testování jistých observačních ekvivalencí na potenciálně nekonečně stavových procesech. Konkrétně chceme zkoumat silnou a slabou bisimulační ekvivalenci na různých algebrách procesů, především BPA a BPPA, a jejich nadtřídách PDA, PDDA, z hlediska rozhodnutelnosti a algoritmické optimálnosti eventuálních rozhodovacích procedur. Pro silnou bisimulaci chceme zjistit, zda existují efektivní (polynomiální) rozhodovací algoritmy pro tyto algebry. V případě slabé bisimulace chceme zkoumat, zda je vůbec rozhodnutelná na těchto třídách procesů.

Publikace

Počet publikací: 4


Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info