An Efficient Algorithm for Transforming LTL Formula to Biichi Automaton
Model checking is an automatic technique for verifying finite state concurrent systems. A rapid solution for the model checking problem is checking the emptiness of prod uct Biichi automaton ( BA ) of the automaton for finite system and the one for the linear temporal logic (LTL) formula, so the algorithm for transforming LTL formula to BA is one of the bases of the whole model checking procedure. In this ar ticle, we propose a new efficient algorithm for transforming LTL formula to BA basing on analysis of the tableau struc tares of LTL formulae, which could efficiently reduce the size of the automaton, but not increases the spatiotemporal complexity, potentially the efficiency of the whole procedure of verification can be improved.
Tableau structure Biichi automaton Linear Temporal Logic
Anping He Jinzhao Wu Lian Li
School of Information Science and Engineering Lanzhou University, China School of Computer and Information Technology Beijing Jiaotong University Beijing 100044, China Scho
国际会议
长沙
英文
1215-1219
2008-10-20（万方平台首次上网日期，不代表论文的发表时间）