arXiv (Cornell University) · 2011 · 77 citations · 3 references
ComputingComputer ScienceFormal MethodsGame TheoryTheory Of ComputationModel CheckingModel TheoryTemporal LogicFormal Proof SystemsFormal ReasoningImperfect Information GamesLearning With Imperfect InformationPerfect RecallTemporal Logic Verification
We propose a formal proof of the undecidability of the model checking problem for alternating- time temporal logic under imperfect information and perfect recall semantics. This problem was announced to be undecidable according to a personal communication on multi-player games with imperfect information, but no formal proof was ever published. Our proof is based on a direct reduction from the non-halting problem for Turing machines.
3
Alternating-time temporal logic
Rajeev Alur, Thomas A. Henzinger, Orna Kupferman · Journal of the ACM · 2002 · 1.4K citations