Almost linear Buchi automata

作者：Babiak Tomas^*; Rehak Vojtech; Strejcek Jan

来源：Mathematical Structures in Computer Science, 2012, 22(2): 203-235.

DOI：10.1017/S0960129511000399

We introduce a new fragment of linear temporal logic (LTL) called LIO and a new class of Buchi automata (BA) called almost linear Buchi automata (ALBA). We provide effective translations between LIO and ALBA showing that the two formalisms are expressively equivalent. As we expect there to be applications of our results in model checking, we use two standard sources of specification formulae, namely Spec Patterns and BEEM, to study the practical relevance of the LIO fragment, and to compare our translation of LIO to ALBA with two standard translations of LTL to BA using alternating automata. Finally, we demonstrate that the LIO to ALBA translation can be much faster than the standard translation, and the resulting automata can be substantially smaller.

• 出版日期2012-4