Improved algorithms for parity and Streett objectives

DOI10.23638/LMCS-13(3:26)2017MaRDI QIDQ5367065zbMATH OpenFDO

Authors Krishnendu Chatterjee, Veronika Loitzenbauer, Monika R. Henzinger

Publication date 12 October 2017

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

zbMATH Keywords

computer-aided verificationgraph algorithmsgraph gamesparity gamesStreett automatasynthesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Recommendations

• Improved algorithms for one-pair and k-pair Streett objectives
• Faster algorithms for mean-payoff parity games
• Improved set-based symbolic algorithms for parity games
• Algorithms for Parity Games
• Conditionally Optimal Algorithms for Generalized B\"uchi Games

Cited in

(11)

• Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
• Generic emptiness check for fun and profit
• Improved algorithms for one-pair and k-pair Streett objectives
• Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
• Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning
• Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification
• An \(O(n^2)\) time algorithm for alternating Büchi games
• Near-linear time algorithms for Streett objectives in graphs and MDPs
• Improved learning of \(k\)-parities
• Symbolic algorithms for graphs and Markov decision processes with fairness objectives
• Fine-grained complexity lower bounds for problems in computer aided verification

This page was built for publication: Improved algorithms for parity and Streett objectives

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