"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."@en . "DE - Spolkov\u00E1 republika N\u011Bmecko" . . . "15"^^ . . "413922" . . "P(1M0545)" . "Obdr\u017E\u00E1lek, Jan" . "1"^^ . . "1"^^ . . . "Clique-Width and Parity Games"@en . "14330" . "Lecture Notes in Computer Science" . "RIV/00216224:14330/07:00022579!RIV08-MSM-14330___" . "4646" . "Klikov\u00E1 \u0161\u00ED\u0159ka a paritn\u00ED hry"@cs . "0302-9743" . "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." . . . "Clique-Width and Parity Games"@en . . . "[60799F9ED06C]" . . "Klikov\u00E1 \u0161\u00ED\u0159ka a paritn\u00ED hry"@cs . "Clique-Width and Parity Games" . "RIV/00216224:14330/07:00022579" . . "1" . "parity games; mu-calculus; clique-width"@en . "Clique-Width and Parity Games" . . "54-68" . . "Ot\u00E1zka p\u0159esn\u00E9 slo\u017Eitosti \u0159e\u0161en\u00ED paritn\u00EDch her je jedn\u00EDm hlavn\u00EDch otev\u0159en\u00FDch probl\u00E9m\u016F ve verifikaci syst\u00E9m\u016F, nebo\u0165 je ekvivaletn\u00EDm probl\u00E9mu ov\u011B\u0159ov\u00E1n\u00ED modelu pro mod\u00E1ln\u00ED mu-kalkul. Zn\u00E1m\u00E1 horn\u00ED hranice je NP a co-NP, ale nen\u00ED zn\u00E1m \u017E\u00E1dn\u00FD polynomi\u00E1ln\u00ED algoritmus. Bylo uk\u00E1z\u00E1no, \u017Ee na grafech podobn\u00FDch strom\u016Fm (grafy s omezenou stromovou \u0161\u00ED\u0159kou a DAG-\u0161\u00ED\u0159kou) takov\u00FD algoritmus existuje. Zde p\u0159edkl\u00E1d\u00E1me polynomi\u00E1ln\u00ED algoritmus pro paritn\u00ED hry na grafech s omezenou klikovou \u0161\u00ED\u0159kou (t\u0159\u00EDda graf\u016F obsahuj\u00EDc\u00ED nap\u0159\u00EDklad \u00FApln\u00E9 bipartitin\u00ED grafy a kliky), \u010D\u00EDm\u017E dopl\u0148ujeme obr\u00E1zek dan\u00E9 oblasti. Tento v\u00FDsledek tak\u00E9 roz\u0161i\u0159uje v\u00FDsledek pro stromovou \u0161\u00ED\u0159ku, nebo\u0165 grafy s omezenou stromovou \u0161\u00ED\u0159kou maj\u00ED i omezenou klikovou \u0161\u00ED\u0159ku. Algoritmus pracuje odli\u0161n\u011B od sv\u00E9ho prot\u011Bj\u0161ku pro omezenou stromovou \u0161\u00ED\u0159ku a zna\u010Dn\u011B vyu\u017E\u00EDv\u00E1 zaj\u00EDmav\u00E9 vlastnosti paritn\u00EDch her."@cs .