Publication details
Almost Linear Büchi Automata
| Basic information | |
|---|---|
| Original title: | Almost Linear Büchi Automata |
| Authors: | Tomáš Babiak, Vojtěch Řehák, Jan Strejček |
| Further information | |
|---|---|
| Citation: | BABIAK, Tomáš  - ŘEHÁK, Vojtěch - STREJČEK, Jan. Almost Linear Büchi Automata. In Proceedings 16th International Workshop on Expressiveness in Concurrency 2009 (EXPRESS'09). Vyd. 1st ed. internet : EPTCS, 2009. pp. 16-25. 2009, Bologna, Italia. |
| Original language: | English |
| Field: | Informatika |
| WWW: |  DOI |
| Type: | Article in Proceedings |
| Keywords: | LTL; linear time logic; model checking |
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:
- Institute for Theoretical Computer Science
- Highly Parallel and Distributed Computing Systems
- Formal verification: algorithms, properties of modelling formalisms amd temporal logics
- New possibilities in automatic verification of network protocols
