Faster algorithms for bounded liveness in graphs and game graphs

DOI10.4230/LIPICS.ICALP.2021.124MaRDI QIDQ7241224zbMATH OpenFDO

Authors Krishnendu Chatterjee, Monika R. Henzinger, Sagar Sudhir Kale, Alexander Svozil

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.124

zbMATH Keywords

Büchigame graphsgraphs

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Borel determinacy
• Conditionally Optimal Algorithms for Generalized B\"uchi Games
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Defining liveness
• Depth-First Search and Linear Graph Algorithms
• Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
• Finitary winning in \({\omega}\)-regular games
• From liveness to promptness
• Handbook of model checking
• scientific article; zbMATH DE number 4124989 (Why is no real title available?)
• scientific article; zbMATH DE number 3189696 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
• Number of quantifiers is better than number of tape cells
• On the menbership problem for functional and multivalued dependencies in relational databases
• Popular conjectures imply strong lower bounds for dynamic problems

This page was built for publication: Faster algorithms for bounded liveness in graphs and game graphs

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