Satisfiability and Model Checking for MSO-definable Temporal Logics are in PSPACE.
Paul GastinDietrich KuskePublished in: CONCUR (2003)
Keyphrases
- temporal logic
- model checking
- satisfiability problem
- finite state
- mazurkiewicz traces
- monadic second order logic
- pspace complete
- bounded model checking
- modal logic
- expressive power
- formal verification
- decision procedures
- temporal properties
- tree automata
- formal specification
- first order logic
- model checker
- verification method
- data complexity
- computation tree logic
- transition systems
- regular expressions
- linear temporal logic
- concurrent systems
- formal methods
- np complete
- query language
- phase transition
- reactive systems
- epistemic logic
- propositional logic
- computational complexity
- linear time temporal logic
- data flow