Transformation of Kripke Structure With Linear Temporal Logic Formula to Büchi Automata
Nut Rungsetthaphat, Wiwat Vatanawood · 2023
In general, a Kripke structure, also known as a transition system, is utilized to represent the finite states and their transitions in an infinite execution system. Traditional Kripke structures do not include accepting states. When performing model checking for linear temporal logic (LTL) properties and considering emptiness checking in the automata language containment technique, the given Kripke structure needs to be transformed into a corresponding Büchi automata. This transformation ensures that the resulting Büchi automata are assigned with appropriate accepting states for the subsequent emptiness checking with the second Büchi automata derived from the LTL formula representing the desired properties. In this paper, an alternative approach to transform the given Kripke structure is proposed, together with the LTL formula representing the desired properties, into a corresponding Büchi automata with the adequate numbers of accepting states based on the provided LTL formula. It apparently reduces complexity and increases clarity of the overall structure and make easier to interpret and reason about the acceptance conditions and the desired behaviors of the system. By performing model checking on these modified Büchi automata, which now have the appropriate accepting states and correspond to the desired LTL formula properties, we can accurately assess their satisfiability.