Parameterized Algorithms for Parity Games

D 2015

Parameterized Algorithms for Parity Games

GAJARSKÝ, Jakub, Sebastian ORDYNIAK, Michael LAMPIS, Valia MITSOU, Kazuhisa MAKINO et. al.

Základní údaje

Originální název

Parameterized Algorithms for Parity Games

Autoři

GAJARSKÝ, Jakub (703 Slovensko, garant, domácí), Sebastian ORDYNIAK (276 Německo), Michael LAMPIS (300 Řecko), Valia MITSOU (300 Řecko) a Kazuhisa MAKINO (392 Japonsko)

Vydání

9235. vyd. Berlin, MFCS 2015, LNCS 9235, od s. 336-347, 12 s. 2015

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/15:00081184

Organizační jednotka

Fakulta informatiky

ISBN

978-3-662-48053-3

ISSN

DOI

http://dx.doi.org/10.1007/978-3-662-48054-0_28

UT WoS

000371027300028

Klíčová slova anglicky

parity games; model checking; modular-width

Štítky

core_A, firank_A

Změněno: 28. 4. 2016 15:11, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 versions of) 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.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

MUNI/A/1159/2014, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV.

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

MUNI/A/1206/2014, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

GAJARSKÝ, Jakub, Sebastian ORDYNIAK, Michael LAMPIS, Valia MITSOU a Kazuhisa MAKINO. Parameterized Algorithms for Parity Games. Online. In Italiano, Giuseppe F. , Pighizzini, Giovanni, Sannella, Donald T. MFCS 2015, LNCS 9235. 9235. vyd. Berlin: Springer, 2015, s. 336-347. ISBN 978-3-662-48053-3. Dostupné z: https://dx.doi.org/10.1007/978-3-662-48054-0_28.

@inproceedings{1316738,
   author = {Gajarský, Jakub and Ordyniak, Sebastian and Lampis, Michael and Mitsou, Valia and Makino, Kazuhisa},
   address = {Berlin},
   booktitle = {MFCS 2015, LNCS 9235},
   doi = {http://dx.doi.org/10.1007/978-3-662-48054-0_28},
   edition = {9235},
   editor = {Italiano, Giuseppe F. , Pighizzini, Giovanni, Sannella, Donald T.},
   keywords = {parity games; model checking; modular-width},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Berlin},
   isbn = {978-3-662-48053-3},
   pages = {336-347},
   publisher = {Springer},
   title = {Parameterized Algorithms for Parity Games},
   year = {2015}
}

TY  - JOUR
ID  - 1316738
AU  - Gajarský, Jakub - Ordyniak, Sebastian - Lampis, Michael - Mitsou, Valia - Makino, Kazuhisa
PY  - 2015
TI  - Parameterized Algorithms for Parity Games
PB  - Springer
CY  - Berlin
SN  - 9783662480533
KW  - parity games
KW  - model checking
KW  - modular-width
N2  - 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 versions of) 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.
ER  -

GAJARSKÝ, Jakub, Sebastian ORDYNIAK, Michael LAMPIS, Valia MITSOU a Kazuhisa MAKINO. Parameterized Algorithms for Parity Games. Online. In Italiano, Giuseppe F. , Pighizzini, Giovanni, Sannella, Donald T. \textit{MFCS 2015, LNCS 9235}. 9235. vyd. Berlin: Springer, 2015, s.~336-347. ISBN~978-3-662-48053-3. Dostupné z: https://dx.doi.org/10.1007/978-3-662-48054-0\_{}28.

Podrobný výpis o publikaci