Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{725120,
author = {Obdržálek, Jan},
address = {Berlin},
booktitle = {Computer Science Logic 2007, proceedings},
keywords = {parity games; mu-calculus; clique-width},
language = {eng},
location = {Berlin},
isbn = {978-3-540-74914-1},
pages = {54-68},
publisher = {Springer-Verlag},
title = {Clique-Width and Parity Games},
year = {2007}
}
TY - JOUR
ID - 725120
AU - Obdržálek, Jan
PY - 2007
TI - Clique-Width and Parity Games
PB - Springer-Verlag
CY - Berlin
SN - 9783540749141
KW - parity games
KW - mu-calculus
KW - clique-width
N2 - The question of the exact complexity of solving parity games is one of the major open problems in system verification, as it is equivalent to the problem of model-checking the modal $\mu$-calculus. The known upper bound is NP$\cap$co-NP, but no polynomial algorithm is known. It was shown that on tree-like graphs (of bounded tree-width and DAG-width) a polynomial-time algorithm does exist. Here we present a polynomial-time algorithm for parity games on graphs of bounded clique-width (class of graphs containing e.g. complete bipartite graphs and cliques), thus completing the picture. This also extends the tree-width result, as graphs of bounded tree-width are a subclass of graphs of bounded clique-width. The algorithm works in a different way to the tree-width case and relies heavily on an interesting structural property of parity games.
ER -
OBDRŽÁLEK, Jan. Clique-Width and Parity Games. In \textit{Computer Science Logic 2007, proceedings}. Berlin: Springer-Verlag, 2007, s.~54-68. ISBN~978-3-540-74914-1.
|
