On Average-Case Hardness of Higher-Order Model Checking.
Yoshiki NakamuraKazuyuki AsadaNaoki KobayashiRyoma Sin'yaTakeshi TsukadaPublished in: FSCD (2020)
Keyphrases
- average case
- model checking
- higher order
- worst case
- temporal logic
- temporal properties
- formal verification
- uniform distribution
- formal specification
- bounded model checking
- model checker
- reachability analysis
- pairwise
- automated verification
- transition systems
- symbolic model checking
- verification method
- computational complexity
- computation tree logic
- timed automata
- finite state
- upper bound
- np hard
- lower bound
- phase transition
- np complete
- epistemic logic
- asynchronous circuits
- pspace complete
- linear temporal logic
- np hardness
- reactive systems
- formal methods
- boolean functions