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

Collection 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

Organizer(s) Fahrenberg, Uli ; Gehrke, Mai ; Santocanale, Luigi ; Winter, Michael

Date(s) 02/11/2021 - 06/11/2021

linked URL https://conferences.cirm-math.fr/2398.html

00:00:00 / 00:00:00

4 5

Fixpoint games

By Barbara König

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) .

Information about the video

Date of recording 05/11/2021
Date of publication 26/11/2021
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers
Director(s) Luca Recanzone
Format MP4

Citation data

DOI 10.24350/CIRM.V.19827703
Cite this video König, Barbara (05/11/2021). Fixpoint games. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19827703
URL https://dx.doi.org/10.24350/CIRM.V.19827703

Domain(s)

Logic in Computer Science

Bibliography

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

MSC codes

Document(s)

https://www.cirm-math.fr/RepOrga/2398/Slides/Koenig.pdf

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

01:03:09

published on November 26, 2021

Relational tight field bounds for distributed analysis of programs

By Marcelo Frias

44:23

published on November 26, 2021

Quantified constraint satisfaction problem: towards the classification of complexity

By Dmitriy Zhuk

25:24

published on November 26, 2021

Time warps, from algebra to algorithms

By Simon Santschi

01:00:52

published on November 26, 2021

Fixpoint games

By Barbara König

29:45

published on November 26, 2021

Relational models for the Lambek calculus with intersection and unit

By Stepan Kuznetsov

Copyright Carmin.tv 2024

Give feedback