Výpočetní složitost vybraných verifikačních problémů
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 19 (SGA0201500001)
Hlavní účastníci
Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
15-13784S
Alternativní jazyk
Název projektu anglicky
Computational complexity of selected verification problems
Anotace anglicky
Verification of hardware and software systems is increasingly recognized as a non-dispensable part of their development. Exploring the bounds of automated verification has exposed several interesting problems whose computational complexity remains elusive despite a considerable effort of the research community. One such problem is the equivalence of first-order schemes, which can be phrased as language equivalence of deterministic pushdown automata. Its decidability is the celebrated result by G. Sénizergues, but the known complexity lies somewhere between polynomial time and the tower of exponentials. The main aim of the project is to explore this and related problems in more detail, continuing the previous research of the project team that clarified the complexity of some subcases. An important part of the project is the development of a software tool that will allow to experiment with problem instances, which should bring a new research insight into the equivalence problems.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
IN - Informatika
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í dokončeného projektu
Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Projekt dosáhl zajímavých odborných výsledků, ale počet časopiseckých publikací v návrhu projektu nebyl ani zdaleka dosažen, a to ani po započítání článků nabídnutých. Finanční prostředky byly čerpány dle pravidel s malým zbytkem osobních prostředků vráceným donátorovi.
Termíny řešení
Zahájení řešení
1. 1. 2015
Ukončení řešení
31. 12. 2017
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
5. 4. 2017
Dodání dat do CEP
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
CEP18-GA0-GA-U/02:1
Datum dodání záznamu
4. 5. 2018
Finance
Celkové uznané náklady
1 940 tis. Kč
Výše podpory ze státního rozpočtu
1 940 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč