En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

Fixpoint games

Sélection Signaler une erreur
Multi angle
Auteurs : König, Barbara (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...

Résumé : Solving fixpoint equations is a recurring problem in several domains: the result of a dataflow analysis can be characterized as either a least or greatest fixpoint. It is well-known that bisimilarity - the largest bisimulation - admits a characterization as a greatest fixpoint and furthermore mu-calculus model-checking requires to solve systems of nested fixpoint equations.
Often, these fixpoint equations or equation systems are defined over powerset lattices, however in several applications - such as lattice-valued or real-valued mu-calculi - the lattice under consideration is not a powerset.
Hence we extend the notion of fixpoint games (or unfolding games, introduced by Venema) to games for equation systems over more general lattices. In particular continuous lattices admit a very elegant characterization of the solution.
We will also describe how to define progress measures which describe winning strategies for the existential players and explain how abstractions and up-to functions can be integrated into the framework.
(Joint work with Paolo Baldan, Tommaso Padoan, Christina Mika-Michalski) .

Keywords : lattices; fixpoints; parity games

Codes MSC :
03B70 - Logic of programming, See also {68Q55, 68Q60}
68Q60 - Specification and verification (program logics, model checking, etc.)

Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2398/Slides/Koenig.pdf

    Informations sur la Vidéo

    Réalisateur : Recanzone, Luca
    Langue : Anglais
    Date de publication : 26/11/2021
    Date de captation : 05/11/2021
    Sous collection : Research talks
    arXiv category : Logic in Computer Science
    Domaine : Computer Science ; Logic and Foundations
    Format : MP4 (.mp4) - HD
    Durée : 01:00:52
    Audience : Researchers
    Download : https://videos.cirm-math.fr/2021-11-5_Koenig.mp4

Informations sur la Rencontre

Nom de la rencontre : 19th International Conference on Relational and Algebraic Methods in Computer Science / 19ème Conférence internationale de méthodes relationnelles et algébriques en informatique
Organisateurs de la rencontre : Fahrenberg, Uli ; Gehrke, Mai ; Santocanale, Luigi ; Winter, Michael
Dates : 02/11/2021 - 06/11/2021
Année de la rencontre : 2021
URL Congrès : https://conferences.cirm-math.fr/2398.html

Données de citation

DOI : 10.24350/CIRM.V.19827703
Citer cette vidéo: König, Barbara (2021). Fixpoint games. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19827703
URI : http://dx.doi.org/10.24350/CIRM.V.19827703

Voir aussi

Bibliographie

  • BALDAN, Paolo, KÖNIG, Barbara, MIKA-MICHALSKI, Christina, et al. Fixpoint games on continuous lattices. Proceedings of the ACM on Programming Languages, 2019, vol. 3, no POPL, p. 1-29. - https://doi.org/10.1145/3290339



Sélection Signaler une erreur