Abstraction-Based Model Checking of Linear Temporal Properties. Mondok, M. and Vörös, A. In Proceedings of the 27th PhD Mini-Symposium, pages 29–32, 2020. Budapest University of Technology and Economics, Department of Measurement and Information Systems.
Abstraction-Based Model Checking of Linear Temporal Properties [pdf]Pdf  abstract   bibtex   10 downloads  
Even though the expressiveness of linear temporal logic (LTL) supports engineering application, model checking of such properties is a computationally complex task and state space explosion often hinders successful verification. LTL model checking consists of constructing automata from the property and the system, generating the synchronous product of the two automata and checking its language emptiness. We propose a novel LTL model checking algorithm that uses abstraction to tackle the challenge of state space explosion. This algorithm combines the advantages of two commonly used model checking approaches, counterexample-guided abstraction refinement and automata theoretic LTL model checking. The main challenge in combining these is the refinement of "lasso"-shaped counterexamples, for which task we propose a novel refinement strategy based on interpolation.
@inproceedings{minisy2020mm,
    author     = {Mondok, Mil\'an and V\"or\"os, Andr\'as},
    title      = {Abstraction-Based Model Checking of Linear Temporal Properties},
    year       = {2020},
    booktitle  = {Proceedings of the 27th PhD Mini-Symposium},
    location   = {Budapest, Hungary},
    publisher  = {Budapest University of Technology and Economics, Department of Measurement and Information Systems},
    editor     = {Renczes, Bal\'azs},
    pages      = {29--32},

    type       = {Local event},
    url_pdf    = {minisy2020mm.pdf},
    abstract   = {Even though the expressiveness of linear temporal logic (LTL) supports engineering application, model checking of such properties is a computationally complex task and state space explosion often hinders successful verification. LTL model checking consists of constructing automata from the property and the system, generating the synchronous product of the two automata and checking its language emptiness. We propose a novel LTL model checking algorithm that uses abstraction to tackle the challenge of state space explosion. This algorithm combines the advantages of two commonly used model checking approaches, counterexample-guided abstraction refinement and automata theoretic LTL model checking. The main challenge in combining these is the refinement of "lasso"-shaped counterexamples, for which task we propose a novel refinement strategy based on interpolation.},
}
Downloads: 10