Model Checking Games

DOI10.1016/S1571-0661(04)80538-3zbMath1261.68086OpenAlexW2025902224MaRDI QIDQ4916199

Erich Grädel

Publication date: 19 April 2013

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s1571-0661(04)80538-3

zbMATH Keywords

complexityparity gamesmodel checkingfixed-point logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Classical first-order logic (03B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

A Dynamic Algorithm for Reachability Games Played on Trees ⋮ Model-Checking Games for Fixpoint Logics with Partial Order Models ⋮ Abstract argument games via modal logic ⋮ Model-checking games for fixpoint logics with partial order models ⋮ An Application of Model Checking Games to Abstract Argumentation ⋮ On the expressive power of monadic least fixed point logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Borel determinacy
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• On logics with two variables
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Unification as a complexity measure for logic programming
• On the synthesis of strategies in infinite games
• Rudiments of \(\mu\)-calculus

This page was built for publication: Model Checking Games