IJSEA Volume 7 Issue 4

EFFICIENT ALGORITHM TO TRANSFORM MINIMALIST SUBSET OF LTL FORMULA INTO FINITE STATE MODELS

Bilal Kanso, Ali Kansou,
10.7753/IJSEA0704.1004
keywords : Linear Temporal Logic, Bchi automata, Model checking, Compositional modelling

PDF
The translation of LTL formula into equivalent B?chi automata plays an important role in many algorithms for LTL model checking, which consist in obtaining a B?chi automaton that is equivalent to the software system specification and another one that is equivalent to the negation of the property. The intersection of the two B?chi automata is empty if the model satisfies the property. Generating the B?chi automaton corresponding to an LTL formula may, in the worst case, be exponential in the size of the formula, making the model checking effort exponential in the size of the original formula. There is no polynomial solution for checking emptiness of the intersection. That comes from the translation step of LTL formula into finite state models. This makes verification methods hard or even impossible to be implemented in practice. In this paper, we propose a subset of LTL formula which can be converted to B?chi automata whose the size is polynomial.
@artical{b742018ijsea07041004,
Title = "EFFICIENT ALGORITHM TO TRANSFORM MINIMALIST SUBSET OF LTL FORMULA INTO FINITE STATE MODELS",
Journal ="International Journal of Science and Engineering Applications (IJSEA)",
Volume = "7",
Issue ="4",
Pages ="54 - 63",
Year = "2018",
Authors ="Bilal Kanso, Ali Kansou, "}