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

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

—

Hlavní účastníci

Masarykova univerzita / Fakulta informatiky

Druh soutěže

—

Číslo smlouvy

—

Název projektu anglicky

Decidability and complexity of observational equivalences on infinite - state processes

Anotace anglicky

The aim of the project is to contribute new knowledge to the study of concurrent systems, inparticular with regard to the decidability of the problems connected to verification of infinite - state processes. The main question we want to address is the testing of certain observational equivalences on potentially infinite - state processes. In particular we want to study strong, and weak bisimulation equivalences on various process algebras, mainly BPA and BPPA, and their extensions PDA and PDDA, from thepoint of view of decidability and computational optimality of decision procedures that might exist. For strong bisimulation equivalence we want to find out whether there exist feasible (polynomial) decision algorithms for the aforementionedprocess algebras. In the case of weak bisimulation equivalence we want to investigate whether it is decidable on these classes of processes.

Kategorie VaV

—

CEP - hlavní obor

BC - Teorie a systémy řízení

CEP - vedlejší obor

—

CEP - další vedlejší obor

—

OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Projekt byl předčasně ukončen vzhledem k pracovnímu pobytu řešitelky v USA. Práce na projektu má teoretické výstupy obsažené ve dvou výzkumných zprávách. Výsledky projektu se týkají teorie souběžnosti. Čerpání finančních prostředků nevykazuje žádné nedos

Zahájení řešení

1. 1. 1999

Ukončení řešení

1. 1. 2002

Poslední stav řešení

S - Zastavený (předčasně ukončený) víceletý projekt

Poslední uvolnění podpory

—

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP/2001/GA0/GA01GA/U/N/9:4

Datum dodání záznamu

—

Celkové uznané náklady

231 tis. Kč

Výše podpory ze státního rozpočtu

231 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč