| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/12:00057563 |
| Název v původním jazyce | EXPTIME-Completeness of Thorough Refinement on Modal Transition Systems |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2012 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 2 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | Jimp - Článek v impaktovaném časopise evidovaném ve Web of Science |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Výsledek hodnocený již v předchozím hodnocení, body se přebírají |
| Bodové ohodnocení | 20,759 |
| Faktor korekce | 90,8 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 18,853 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 85,7 % | 17,793 | 16,160 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 4 |
| Počet domácích tvůrců | 3 |
| Tvůrce | Beneš Nikola (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 2050587) |
| Tvůrce | Křetínský Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 3503054) |
| Tvůrce | Larsen Kim G. (státní příslušnost: DK - Dánské království) |
| Tvůrce | Srba Jiří (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 2753057) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | Modal transition systems (MTS), a specification formalism introduced more than 20 years ago, has recently received a considerable attention in several different areas. Many of the fundamental questions related to MTSs have already been answered. However, the problem of the exact computational complexity of thorough refinement checking between two finite MTSs remained unsolved. We settle down this question by showing EXPTIME-completeness of thorough refinement checking on finite MTSs. The upper-bound result relies on a novel algorithm running in single exponential time providing a direct goal-oriented way to decide thorough refinement. If the right-hand side MTS is moreover deterministic, or has a fixed size, the running time of the algorithm becomes polynomial. The lower-bound proof is achieved by reduction from the acceptance problem of alternating linear bounded automata and the problem remains EXPTIME-hard even if the left-hand side MTS is fixed and deterministic. |
| Klíčová slova | modal transition systems; refinement; computational complexity |
| Kód UT ISI | 000309195100004 |
| Název periodka | Information and Computation |
| Rozsah stran | 54-68 |
| ISSN | 0890-5401 |
| Svazek periodika | 218 |
| Číslo periodika v rámci uvedeného svazku | September |
| Stát vydavatele periodika | NL - Nizozemsko |
| Počet stran výsledku | 15 |
| DOI výsledku | 10.1016/j.ic.2012.08.001 |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2013 |
| Systémové označení dodávky dat | RIV13-MSM-14330___/02:2 |
| Specifikace | RIV/00216224:14330/12:00057563!RIV13-MSM-14330___ |
| Kontrolní kód | [AAB1D84CDABB] |
| Další výskyty tohoto výsledku od stejného předkladatele |
| Dodáno GA ČR v roce 2013 | Záznam s identifikačním kódem RIV/00216224:14330/12:00057563 v dodávce dat RIV13-GA0-14330___/02:2 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GAP202/10/1469 - Formální metody pro analýzu a verifikaci komplexních systémů (2010-2014, GA0/GA) |
| Projekt | GAP202/11/0312 - Vývoj a verifikace softwarových komponent v zapouzdřených systémech (2011-2013, GA0/GA) |
| S - Specifický výzkum na vysokých školách |
| I - Instit. podpora na rozvoj výzkumné organizace |