ATL Satisfiability is Indeed EXPTIME-complete

DOI10.1093/logcom/exl009zbMath1118.03010OpenAlexW1982773655MaRDI QIDQ3431973

Frank Wolter, Michael Wooldridge, Dirk Walther, Carsten Lutz

Publication date: 13 April 2007

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b12d3794a384ce42c0c1b7d7a5e1898eb904578d

zbMATH Keywords

computational complexitysatisfiability problemalternating-time temporal logicelimination construction

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items (10)

Optimal Tableau Method for Constructive Satisfiability Testing and Model Synthesis in the Alternating-Time Temporal Logic ATL ⁺ ⋮ Complete axiomatization and decidability of alternating-time temporal logic ⋮ Ordered Resolution for Coalition Logic ⋮ Complexity of finite-variable fragments of propositional temporal and modal logics of computation ⋮ Complexity results of STIT fragments ⋮ Augmenting ATL with strategy contexts ⋮ HyperATL*: A Logic for Hyperproperties in Multi-Agent Systems ⋮ ATL* Satisfiability Is 2EXPTIME-Complete ⋮ Natural strategic ability ⋮ Alternating-time temporal logic ATL with finitely bounded semantics

This page was built for publication: ATL Satisfiability is Indeed EXPTIME-complete