Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions

DOI10.4230/LIPICS.FSTTCS.2018.38MaRDI QIDQ5090979zbMATH OpenOpenAlexFDO

Authors Stéphane Le Roux, Arno Pauly, Mickael Randour

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1808.05791

zbMATH Keywords

finite-memory determinacygames on graphsmultiple objectives

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Extending finite-memory determinacy to multi-player games
• Finite-memory strategies in two-player infinite games
• Finitary winning in \({\omega}\)-regular games
• Tools and Algorithms for the Construction and Analysis of Systems
• Games where you can play optimally with arena-independent finite memory

Cites work

• Automata, logics, and infinite games. A guide to current research
• Average-energy games
• Borel determinacy
• Bounding Average-Energy Games
• Computer Science Logic
• CONCUR 2005 – Concurrency Theory
• Energy parity games
• Extending finite-memory determinacy to multi-player games
• Fixed-dimensional energy games are in pseudo-polynomial time
• Generalized Parity Games
• Graph Games and Reactive Synthesis
• Half-Positional Determinacy of Infinite Games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Looking at mean-payoff and total-payoff through windows
• Mathematical Foundations of Computer Science 2004
• Non-zero sum games for reactive synthesis
• On the complexity of heterogeneous multidimensional games
• Positional strategies for mean payoff games
• Robust multidimensional mean-payoff games are undecidable
• The complexity of multi-mean-payoff and multi-energy games
• Window parity games: an alternative approach toward parity games with time bounds

Cited in

(11)

• Timed games with bounded window parity objectives
• Games where you can play optimally with arena-independent finite memory
• scientific article; zbMATH DE number 7559480 (Why is no real title available?)
• Synthesis for multi-weighted games with branching-time winning conditions
• Life is random, time is not: Markov decision processes with window objectives
• Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs
• Characterizing positionality in games of Infinite duration over infinite graphs
• Half-positional objectives recognized by deterministic Büchi automata
• Different strokes in randomised strategies: revisiting Kuhn's theorem under finite-memory assumptions
• Characterizing positionality in games of infinite duration over infinite graphs
• Reachability games and friends: a journey through the Lens of memory and complexity (invited talk)

This page was built for publication: Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090979)