DocumentCode
3223620
Title
Focus games for satisfiability and completeness of temporal logic
Author
Lange, Martin ; Stirling, Colin
Author_Institution
Div. of Inf., Edinburgh Univ., UK
fYear
2001
fDate
2001
Firstpage
357
Lastpage
365
Abstract
Introduce a simple game-theoretic approach to satisfiability checking of temporal logic, for LTL (linear time logic) and CTL (computation tree logic), which has the same complexity as using automata. The mechanisms involved are both explicit and transparent, and underpin a novel approach to developing complete axiom systems for temporal logic. The axiom systems are naturally factored into what happens locally and what happens in the limit. The completeness proofs utilise the game-theoretic construction for satisfiability: if a finite set of formulas is consistent then there is a winning strategy (and therefore construction of an explicit model is avoided)
Keywords
computability; computational complexity; game theory; temporal logic; CTL; LTL; automata; axiom systems; completeness; complexity; computation tree logic; consistent finite formula set; explicit model; explicit transparent mechanisms; focus games; game-theoretic construction; linear time logic; satisfiability checking; temporal logic; winning strategy; Automata; Books; Calculus; Costs; Game theory; Impedance; Informatics; Logic; Plugs; Testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science, 2001. Proceedings. 16th Annual IEEE Symposium on
Conference_Location
Boston, MA
ISSN
1043-6871
Print_ISBN
0-7695-1281-X
Type
conf
DOI
10.1109/LICS.2001.932511
Filename
932511
Link To Document