Informace o projektu

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

Kód projektu
GA201/99/D026
Období řešení
9/1999 - 8/2002
Investor/Program
Grantová agentura ČR
Programový rámec / typ projektu
Standardní projekty
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ů.

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

Další info