• 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