Parity games, separations, and the modal µ-calculus

DITTMANN, Christoph Taal: Engels

Paperback

€ 14,95

Dit artikel kunt u momenteel niet bestellen. Mogelijk is het wel op voorraad bij een van de aangesloten boekhandels. Bekijk de winkelvoorraad hieronder ↓
Koop lokaal, ook online!
Bekijk winkelvoorraad
Ik wil advies
Vraag de boekhandel

Die Themen dieser Dissertation sind der modale µ-Kalkül und Paritätsspiele. Der modale µ-Kalkül ist eine häufig eingesetzte Logik im Bereich des Model-Checkings in der Informatik. Das Model-Checking-Problem des modalen µ-Kalküls ist polynomialzeitäquivalent zum Lösen von Paritätsspielen, einem 2-Spielerspiel auf beschrifteten, gerichteten Graphen. Wir präsentieren die ersten FPT-Algorithmen (fixed-parameter tractable) für das Model-Checking-Problem des modalen µ-Kalküls auf Klassen von Graphen mit beschränkter Kelly-Weite oder beschränkter DAG-Weite. Für diesen Zweck beweisen wir einen allgemeineren Zerlegungssatz für den modalen µ-Kalkül und stellen eine nützliche Definition von Typen für diese Logik vor. Angenommen, eine Klasse von Paritätsspielen hat einen Polynomialzeit-Lösungs-Algorithmus, betrachten wir danach das Problem, diese Klassen zu erweitern auf eine Weise, sodass Polynomialzeit-Lösbarkeit erhalten bleibt. Wir zeigen, dass dies beim Join von Paritätsspielen, beim Pasting und beim Hinzufügen einzelner Knoten der Fall ist. Wir folgern daraus, dass das Lösen von Paritätsspielen in Polynomialzeit möglich ist, falls der unterliegende ungerichtete Graph ein Tournament, ein vollständiger bipartiter Graph oder ein Blockgraph ist. Im letzten Kapitel präsentieren wir den ersten nicht-trivialen formalen Beweis über Paritätsspiele. Wir stellen einen formalen Beweis für die positionale Determiniertheit von Paritätsspielen im Beweis-Assistenten Isabelle/HOL vor.
ISBN
9783798328877
Vorm
Paperback
Uitgever
Van Ditmar Boekenimport B.V.
Druk
1e
Verschenen
01-01-2017
Taal
Engels
Genre
Technische wetenschappen
Geen recensies beschikbaar.
pro-mbooks2 : libris