Fixpoint equations and systems of equations are ubiquitous in model checking, so a recurring problem is how to solve them. Often however it's enough to know whether a member of the domain is under a certain element of the solution. This is known to be equivalent to a parity game, which can be solved by various algorithms. We'll focus on adapting a local strategy iteration algorithm for parity games to solve this reduced problem for fixpoint systems and comparing it with alternative solutions.

Fixpoint equations and systems of equations are ubiquitous in model checking, so a recurring problem is how to solve them. Often however it's enough to know whether a member of the domain is under a certain element of the solution. This is known to be equivalent to a parity game, which can be solved by various algorithms. We'll focus on adapting a local strategy iteration algorithm for parity games to solve this reduced problem for fixpoint systems and comparing it with alternative solutions.

Solving Systems of Fixpoint Equations via Strategy Iteration

STEVANATO, GIACOMO
2023/2024

Abstract

Fixpoint equations and systems of equations are ubiquitous in model checking, so a recurring problem is how to solve them. Often however it's enough to know whether a member of the domain is under a certain element of the solution. This is known to be equivalent to a parity game, which can be solved by various algorithms. We'll focus on adapting a local strategy iteration algorithm for parity games to solve this reduced problem for fixpoint systems and comparing it with alternative solutions.
2023
Solving Systems of Fixpoint Equations via Strategy Iteration
Fixpoint equations and systems of equations are ubiquitous in model checking, so a recurring problem is how to solve them. Often however it's enough to know whether a member of the domain is under a certain element of the solution. This is known to be equivalent to a parity game, which can be solved by various algorithms. We'll focus on adapting a local strategy iteration algorithm for parity games to solve this reduced problem for fixpoint systems and comparing it with alternative solutions.
Fixpoint
Parity games
Strategy iteration
File in questo prodotto:
File Dimensione Formato  
Stevanato_Giacomo.pdf

accesso aperto

Dimensione 707.65 kB
Formato Adobe PDF
707.65 kB Adobe PDF Visualizza/Apri

The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/70923