LTL to Smaller Self-Loop Alternating Automata and Back

• Autoři: BLAHOUDEK František; MAJOR Juraj; STREJČEK Jan
• Rok publikování: 2019
• Druh: Článek ve sborníku
• Konference: Theoretical Aspects of Computing - ICTAC 2019 - 16th International Colloquium, Hammamet, Tunisia, October 31 - November 4, 2019, Proceedings
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: https://link.springer.com/chapter/10.1007/978-3-030-32505-3_10
• Doi: http://dx.doi.org/10.1007/978-3-030-32505-3_10
• Klíčová slova: LTL; linear temporal logic; automata; automata over infinite words; alternating automata; LTL to automata; ltl3tela
• Popis: Self-loop alternating automata (SLAA) with Büchi or co-Büchi acceptance are popular intermediate formalisms in translations of LTL to deterministic or nondeterministic automata. This paper considers SLAA with generic transition-based Emerson-Lei acceptance and presents translations of LTL to these automata and back. Importantly, the translation of LTL to SLAA with generic acceptance produces considerably smaller automata than previous translations of LTL to Büchi or co-Büchi SLAA. Our translation is already implemented in the tool LTL3TELA, where it helps to produce small deterministic or nondeterministic automata for given LTL formulae.

Související projekty

• Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII.
• Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 19
• Automata for Decision Procedures and Verification