ATL Satisfiability is Indeed EXPTIME-complete

DOI10.1093/LOGCOM/EXL009MaRDI QIDQ3431973zbMATH OpenOpenAlexFDO

Authors D. Walther, Carsten Lutz, F. Wolter, M. J. Wooldridge

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

alternating-time temporal logiccomputational complexityelimination constructionsatisfiability problem

Mathematics Subject Classification ID

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

Recommendations

• ATL* Satisfiability Is 2EXPTIME-Complete
• On the Expressiveness and Complexity of ATL
• Alternating-time temporal logic
• Model checking abilities of agents: a closer look
• On the Expressiveness and Complexity of ATL

Cited in

(15)

• Complexity results of STIT fragments
• Complexity of finite-variable fragments of propositional temporal and modal logics of computation
• QUIXO is EXPTIME-complete
• Natural strategic ability
• Alternating-time temporal logic ATL with finitely bounded semantics
• Complete axiomatization and decidability of alternating-time temporal logic
• On the complexity of \(\mathsf{ATL}\) and \(\mathsf{ATL}^*\) module checking
• Ordered resolution for coalition logic
• On the Expressiveness and Complexity of ATL
• ATL* Satisfiability Is 2EXPTIME-Complete
• Optimal tableau method for constructive satisfiability testing and model synthesis in the alternating-time temporal logic \(\mathrm{ATL}^+\)
• On the Expressiveness and Complexity of ATL
• HyperATL*: A Logic for Hyperproperties in Multi-Agent Systems
• Robust alternating-time temporal logic
• Augmenting ATL with strategy contexts

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

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