# Simulation Games Michael Maurer

Yüklə 454 b.
 tarix 06.03.2018 ölçüsü 454 b. #44847 • ## Construction of (Bi)simulations as Parity Games • ## Efficiently reducing the size of finite-state automata (known as quotienting) • ## 4) fair simulation game, • ## If Duplicator can‘t move, the game halts and Spoiler wins • ## For each of the 4 simulation games there exist different rules to determine the winner • ## Ordinary simulation:

• Duplicator wins in any case
• Fairness conditions are ignored

• ## Direct simulation:

• D wins iff for all i, if then • ## Delayed simulation:

• D wins iff for all i, if then there exists j ≥ i such that
• ## Fair simulation:

• D wins iff there are infinitely many j such that
• or only finitely many i such that
• In other words: if there are infinitely many i such that
• , then there are also infinitely many j such that • ## For di, de, f: if then • ## Bisimulations define an equivalence relation • ## an accept state at position i of both runs • ## Not at all clear how such a quotient should be defined • ## Removing transition (1‘,a,1‘) would provide a simulation-equivalent quotient for A • ## Played by two players, Zero and One and the game starts by placing a pebble on • ## Considering the minimum priority kπ that occurs infinitely often in the run π; Zero wins, if kπ is even, One otherwise • ## The priority function: • ## EAf={((2,1,a),(2,2)),((3,1,a),(3,2)),((2,2,b),(2,2)),((2,2,a),(2,3)),..} U {((1,1),(2,1,a)),((1,2),(2,2,a)),((2,2),(2,3,b)),..} • ## pAf ((1,3)) = 0 ; • ## Parity Game constructed:

• Zero has a winning strategy from (q,q’), iff q is fairly simulated by q’
• Jurdzinkis algorithm as fast algorithm for computing fair (bi)simulation relations and delayed simulations
• Other relations can be constructed from the fair simulation formulas (Handout) • ## Carsten Fritz: Simulation-Based Simplification of omega-Automata. PhD thesis, Technische Fakultät der Christian Albrecht Universität zu Kiel (2005) available at http:/e-diss.uni-kiel.de/diss_1644/ Yüklə 454 b.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2022
rəhbərliyinə müraciət