Publication details

Almost Linear Büchi Automata

Investor logo
Investor logo
Authors

BABIAK Tomáš ŘEHÁK Vojtěch STREJČEK Jan

Year of publication 2009
Type Article in Proceedings
Conference Proceedings 16th International Workshop on Expressiveness in Concurrency 2009 (EXPRESS'09)
MU Faculty or unit

Faculty of Informatics

Citation
Web DOI
Field Informatics
Keywords LTL; linear time logic; model checking
Description We introduce a new fragment of Linear temporal logic (LTL) called LIO and a new class of Büchi automata (BA) called Almost linear Büchi automata (ALBA). We provide effective translations between LIO and ALBA showing that the two formalisms are expressively equivalent. While standard translations of LTL into BA use some intermediate formalisms, the presented translation of LIO into ALBA is direct. As we expect applications of ALBA in model checking, we compare the expressiveness of ALBA with other classes of Büchi automata studied in this context and we indicate possible applications.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info