Checking LTL[F, G, X] on compressed traces in polynomial time.
Minjian ZhangUmang MathurMahesh ViswanathanPublished in: ESEC/SIGSOFT FSE (2021)
Keyphrases
- deterministic automata
- finite automata
- conp complete
- model checking
- temporal logic
- data compression
- np complete
- data structure
- complexity theoretic
- special case
- consistency checking
- bounded model checking
- linear temporal logic
- computational complexity
- regular expressions
- approximation algorithms
- data exchange
- compressed domain
- worst case
- compressed data
- data sets
- execution traces
- np hard
- conjunctive queries
- upper bound