Strategy synthesis for multi-dimensional quantitative objectives

DOI10.1007/s00236-013-0182-6zbMath1360.68208arXiv1201.5073OpenAlexW2785504350MaRDI QIDQ2249657

Mickael Randour, Jean-François Raskin, Krishnendu Chatterjee

Publication date: 3 July 2014

Published in: Acta Informatica, Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Games involving graphs (91A43) Applications of game theory (91A80) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Distributed systems (68M14)

Related Items (29)

Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time ⋮ Graph Games and Reactive Synthesis ⋮ Compositional strategy synthesis for stochastic games with multiple objectives ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Safraless LTL synthesis considering maximal realizability ⋮ Average-energy games ⋮ Reachability games with relaxed energy constraints ⋮ Synthesis for Multi-weighted Games with Branching-Time Winning Conditions ⋮ Model checking and synthesis for branching multi-weighted logics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounding Average-Energy Games ⋮ Percentile queries in multi-dimensional Markov decision processes ⋮ Unnamed Item ⋮ Non-deterministic Weighted Automata on Random Words ⋮ Strategy synthesis for multi-dimensional quantitative objectives ⋮ Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games ⋮ Non-deterministic weighted automata evaluated over Markov chains ⋮ On Values of Games ⋮ Unnamed Item ⋮ Playing with Repetitions in Data Words Using Energy Games ⋮ Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions ⋮ The complexity of multi-mean-payoff and multi-energy games ⋮ Looking at mean-payoff and total-payoff through windows ⋮ Verification of multiplayer stochastic games via abstract dependency graphs

Uses Software

• Antichains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulation distances
• Positional strategies for mean payoff games
• Borel determinacy
• The covering and boundedness problems for vector addition systems
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• The complexity of mean payoff games on graphs
• A multiparameter analysis of the boundedness problem for vector addition systems
• Fair simulation
• Automata, logics, and infinite games. A guide to current research
• Strategy synthesis for multi-dimensional quantitative objectives
• Synthesizing robust systems
• Generalized Mean-payoff and Energy Games
• Quantitative languages
• Church Synthesis Problem for Noisy Input
• Energy and Mean-Payoff Parity Markov Decision Processes
• Energy Games in Multiweighted Automata
• Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited
• Alternating-time temporal logic
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Antichain Algorithms for Finite Automata
• When Simulation Meets Antichains
• Reachability Games on Extended Vector Addition Systems with States
• Energy Parity Games
• Better Quality in Synthesis through Quantitative Objectives
• Supervisory Control of a Class of Discrete Event Processes
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• The determinacy of Blackwell games
• Permissive strategies: from parity games to safety games
• Synthesis from LTL Specifications with Mean-Payoff Objectives
• Antichains: A New Algorithm for Checking Universality of Finite Automata

This page was built for publication: Strategy synthesis for multi-dimensional quantitative objectives