| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/11:00050261 |
| Název v původním jazyce | Faster algorithms for mean-payoff games |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2011 |
| 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í | 23,697 |
| Faktor korekce | 100,9 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 23,917 |
| 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 | 57,1 % | 13,541 | 13,667 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 2 |
| Tvůrce | Brim Luboš (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 6500773) |
| Tvůrce | Chaloupka Jakub (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 5376327) |
| Tvůrce | Doyen Laurent (státní příslušnost: BE - Belgické království) |
| Tvůrce | Gentilini Raffaella (státní příslušnost: IT - Italská republika) |
| Tvůrce | Raskin Jean-François (státní příslušnost: BE - Belgické království) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time. |
| Klíčová slova | Mean payoff objectives; Algorithms and complexity upper bounds |
| Kód UT ISI | 000288671700001 |
| Rozsah stran | 97-118 |
| Název periodka | Formal Methods in System Design |
| ISSN | 0925-9856 |
| Svazek periodika | 38 |
| Číslo periodika v rámci uvedeného svazku | 2 |
| Stát vydavatele periodika | DE - Spolková republika Německo |
| Počet stran výsledku | 22 |
| DOI výsledku | 10.1007/s10703-010-0105-x |
| Ú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 | 2012 |
| Systémové označení dodávky dat | RIV12-MSM-14330___/01:1 |
| Specifikace | RIV/00216224:14330/11:00050261!RIV12-MSM-14330___ |
| Kontrolní kód | [1E6F8A851C7D] |
| Další výskyty tohoto výsledku od stejného předkladatele |
| Dodáno GA ČR v roce 2012 | Záznam s identifikačním kódem RIV/00216224:14330/11:00050261 v dodávce dat RIV12-GA0-14330___/02:1 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GA201/09/1389 - Verifikace a analýza velmi velkých počítačových systémů (2009-2011, GA0/GA) |
| Výzkumný záměr | MSM0021622419 - Vysoce paralelní a distribuované výpočetní systémy (2005-2011, MSM) |