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

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

Namespace Prefixes

PrefixIRI
n10http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n18http://purl.org/net/nknouf/ns/bibtex#
n14http://localhost/temp/predkladatel/
n19http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n15http://linked.opendata.cz/resource/domain/vavai/projekt/
n8http://linked.opendata.cz/ontology/domain/vavai/
n20http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14330%2F07%3A00022579%21RIV10-MSM-14330___/
n16https://schema.org/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://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#
n12http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n13http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n21http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n11http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14330%2F07%3A00022579%21RIV10-MSM-14330___
rdf:type
n8: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.
dcterms:title
Clique-Width and Parity Games Clique-Width and Parity Games
skos:prefLabel
Clique-Width and Parity Games Clique-Width and Parity Games
skos:notation
RIV/00216224:14330/07:00022579!RIV10-MSM-14330___
n3:aktivita
n13:P
n3:aktivity
P(1M0545)
n3:dodaniDat
n11:2010
n3:domaciTvurceVysledku
n19:3294099
n3:druhVysledku
n7:D
n3:duvernostUdaju
n17:S
n3:entitaPredkladatele
n20:predkladatel
n3:idSjednocenehoVysledku
413921
n3:idVysledku
RIV/00216224:14330/07:00022579
n3:jazykVysledku
n4:eng
n3:klicovaSlova
parity games; mu-calculus; clique-width
n3:klicoveSlovo
n12:clique-width n12:parity%20games n12:mu-calculus
n3:kontrolniKodProRIV
[75C88693E037]
n3:mistoKonaniAkce
Lausanne, Switzerland
n3:mistoVydani
Berlin
n3:nazevZdroje
Computer Science Logic 2007, proceedings
n3:obor
n21:IN
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
1
n3:projekt
n15:1M0545
n3:rokUplatneniVysledku
n11:2007
n3:tvurceVysledku
Obdržálek, Jan
n3:typAkce
n10:WRD
n3:wos
000250338100007
n3:zahajeniAkce
2007-01-01+01:00
s:numberOfPages
15
n18:hasPublisher
Springer-Verlag
n16:isbn
978-3-540-74914-1
n14:organizacniJednotka
14330