Auteurs : König, Barbara (Auteur de la conférence)
CIRM (Editeur )
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) .
Mots-Clés : 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 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 de la Rencontre : https://conferences.cirm-math.fr/2398.html
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