A Better Translation From LTL to Transition-Based Generalized Büchi Automata

Abstract

Translating linear temporal logic (LTL) formulas into Büchi automata is one of the most important aspects of LTL model checking. Certain successful algorithms, such as LTL2BA and SPOT, first translate an LTL formula into a transition-based generalized Büchi automaton (TGBA) and then degeneralize it into a Büchi automaton. This paper focuses on achieving a better translation from LTL to TGBA and analyzing the performance of every step of the algorithm. We decompose the translation into three steps to give a step-wise description and improve all three steps. The first step is the basic translation without acceptance conditions and simplifications, which combines the advantages of both LTL2BA and SPOT. Second, we introduce a new definition of acceptance conditions. Our proofs and experiments have shown that our technique is more efficient and improves the degeneralization ability. Finally, we introduce the simplifications of our algorithm. We focus on not only producing better final Büchi automata but also minimizing intermediate automata, which can reduce the execution time.

Keywords

• Büchi Automata
• model checking
• LTL
• TGBA