Algebra and Combinatorics of Parity Games

Walid Belkhir 1, 2
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Parity games are the combinatorial description of the theory of binary infimums, and supremums, and of the least and greatest fixed points over complete lattices. Roughly speaking, the parity games formalism may be understood as a μ-calculus over complete lattices. Hierarchies and logical expressiveness are at the core of fixed-point theory. The first part of this the- sis is devoted to consider the variable hierarchy problem within the lattice μ-calculus. Earlier works on this problem within the propositional modal μ- calculus have derived a complexity measure, the so called entanglement. The latter is the combinatorial counterpart of the variable hierarchy. The second part of this thesis is devoted to consider the entanglement as a pure graph theoretic measure, independently of its origins in fixed-point theory. Further results will be proved in this direction, such that the recognization of graphs of bounded entanglement, the tree decomposition of these graphs, and the closure under minors.
Complete list of metadatas

Cited literature [74 references]  Display  Hide  Download

https://hal.inria.fr/tel-01277878
Contributor : Walid Belkhir <>
Submitted on : Tuesday, February 23, 2016 - 12:49:56 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:25 PM
Long-term archiving on : Tuesday, May 24, 2016 - 12:42:12 PM

Identifiers

  • HAL Id : tel-01277878, version 1

Citation

Walid Belkhir. Algebra and Combinatorics of Parity Games. Computer Science and Game Theory [cs.GT]. Aix-Marseille université, 2008. English. ⟨tel-01277878⟩

Share

Metrics

Record views

557

Files downloads

102