This HTML5 document contains 41 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n13http://localhost/temp/predkladatel/
n17http://linked.opendata.cz/resource/domain/vavai/projekt/
n10http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n16http://linked.opendata.cz/ontology/domain/vavai/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n6http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14330%2F07%3A00022579%21RIV08-MSM-14330___/
n11http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n8http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n15http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14330%2F07%3A00022579%21RIV08-MSM-14330___
rdf:type
n16:Vysledek skos:Concept
dcterms:description
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. 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. Otázka přesné složitosti řešení paritních her je jedním hlavních otevřených problémů ve verifikaci systémů, neboť je ekvivaletním problému ověřování modelu pro modální mu-kalkul. Známá horní hranice je NP a co-NP, ale není znám žádný polynomiální algoritmus. Bylo ukázáno, že na grafech podobných stromům (grafy s omezenou stromovou šířkou a DAG-šířkou) takový algoritmus existuje. Zde předkládáme polynomiální algoritmus pro paritní hry na grafech s omezenou klikovou šířkou (třída grafů obsahující například úplné bipartitiní grafy a kliky), čímž doplňujeme obrázek dané oblasti. Tento výsledek také rozšiřuje výsledek pro stromovou šířku, neboť grafy s omezenou stromovou šířkou mají i omezenou klikovou šířku. Algoritmus pracuje odlišně od svého protějšku pro omezenou stromovou šířku a značně využívá zajímavé vlastnosti paritních her.
dcterms:title
Clique-Width and Parity Games Kliková šířka a paritní hry Clique-Width and Parity Games
skos:prefLabel
Kliková šířka a paritní hry Clique-Width and Parity Games Clique-Width and Parity Games
skos:notation
RIV/00216224:14330/07:00022579!RIV08-MSM-14330___
n4:strany
54-68
n4:aktivita
n9:P
n4:aktivity
P(1M0545)
n4:cisloPeriodika
1
n4:dodaniDat
n15:2008
n4:domaciTvurceVysledku
n10:3294099
n4:druhVysledku
n12:J
n4:duvernostUdaju
n18:S
n4:entitaPredkladatele
n6:predkladatel
n4:idSjednocenehoVysledku
413922
n4:idVysledku
RIV/00216224:14330/07:00022579
n4:jazykVysledku
n11:eng
n4:klicovaSlova
parity games; mu-calculus; clique-width
n4:klicoveSlovo
n5:mu-calculus n5:parity%20games n5:clique-width
n4:kodStatuVydavatele
DE - Spolková republika Německo
n4:kontrolniKodProRIV
[60799F9ED06C]
n4:nazevZdroje
Lecture Notes in Computer Science
n4:obor
n8:IN
n4:pocetDomacichTvurcuVysledku
1
n4:pocetTvurcuVysledku
1
n4:projekt
n17:1M0545
n4:rokUplatneniVysledku
n15:2007
n4:svazekPeriodika
4646
n4:tvurceVysledku
Obdržálek, Jan
s:issn
0302-9743
s:numberOfPages
15
n13:organizacniJednotka
14330