scientific article; zbMATH DE number 7445162

MaRDI QIDQ3384167zbMATH OpenFDO

Authors Massimo Benerecetti, Daniele Dell'Erba, Fabio Mogavero

Publication date 14 December 2021

Full work available at URL https://arxiv.org/abs/1709.02099, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GANDALF2017.9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Games involving graphs (91A43)

Recommendations

• Robust worst cases for parity games algorithms
• A randomized subexponential algorithm for parity games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• scientific article; zbMATH DE number 1962853
• A recursive approach to solving parity games in quasipolynomial time
• The fixpoint-iteration algorithm for parity games
• A subexponential lower bound for the random facet algorithm for parity games
• Robustness of structurally equivalent concurrent parity games
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games

Cites work

• A delayed promotion policy for parity games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A deterministic subexponential algorithm for solving parity games
• Alternating tree automata, parity games, and modal -calculus
• Alternating-time temporal logic
• ATL* Satisfiability Is 2EXPTIME-Complete
• Automata, logics, and infinite games. A guide to current research
• Benchmark Graphs for Practical Graph Isomorphism
• Borel determinacy
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Deciding parity games in quasipolynomial time
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Fixed-point logics and solitaire games
• Generalized mean-payoff and energy games
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 5869590 (Why is no real title available?)
• scientific article; zbMATH DE number 3990873 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 1775458 (Why is no real title available?)
• scientific article; zbMATH DE number 3993574 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• On model checking for the -calculus and its fragments
• Positional strategies for mean payoff games
• Reasoning about strategies
• Reasoning about strategies: on the model-checking problem
• Reasoning about strategies: on the satisfiability problem
• Recursive algorithm for parity games requires exponential time
• Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
• Solving Parity Games in Big Steps
• Solving parity games in practice
• Solving parity games via priority promotion
• Strategy logic
• Substructure Temporal Logic
• Succinct progress measures for solving parity games
• The complexity of mean payoff games on graphs
• What makes \textsc{Atl}* decidable? A decidable fragment of strategy logic

Cited in

(5)

• A delayed promotion policy for parity games
• Robust worst cases for parity games algorithms
• A parity game tale of two counters
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Priority promotion with Parysian flair

This page was built for publication:

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