| Identifikační kód | RIV/00216224:14330/15:00081184 |
|---|
| Název v anglickém jazyce | Parameterized Algorithms for Parity Games |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 5 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Jakub Gajarský (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 9663207)
Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo)
Michael Lampis (státní příslušnost: GR - Řecká republika)
Valia Mitsou (státní příslušnost: GR - Řecká republika)
Kazuhisa Makino (státní příslušnost: JP - Japonsko) |
|---|
| Popis výsledku v anglickém jazyce | Determining the winner of a Parity Game is a major problem in computational complexity with a number of applications in verification. In a parameterized complexity setting, the problem has often been considered with parameters such as (directed versionsof) treewidth or clique-width, by applying dynamic programming techniques. In this paper we adopt a parameterized approach which is more inspired by well-known (non-parameterized) algorithms for this problem. We consider a number of natural parameterizations, such as by Directed Feedback Vertex Set, Distance to Tournament, and Modular Width. We show that, for these parameters, it is possible to obtain recursive parameterized algorithms which are simpler, faster and only require polynomial space. We complement these results with some algorithmic lower bounds which, among others, rule out a possible avenue for improving the best-known sub-exponential time algorithm for parity games. |
|---|
| Klíčová slova oddělená středníkem | parity games; model checking; modular-width |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/978-3-662-48054-0_28 |
|---|