Verifying the LTL to Büchi Automata Translation via Very Weak Alternating Automata
Authors: Simon Jantsch and Michael Norrish
Paper Information
Title: | Verifying the LTL to Büchi Automata Translation via Very Weak Alternating Automata |
Authors: | Simon Jantsch and Michael Norrish |
Proceedings: | ITP Papers |
Editors: | Jeremy Avigad and Assia Mahboubi |
Keywords: | model checking, formal verification, HOL |
Abstract: | ABSTRACT. We present a formalization of a translation from LTL formulae to generalized Büchi Automata in the HOL4 theorem prover. Translations from temporal logics to automata are at the core of model checking algorithms based on automata-theoretic techniques. The translation we verify proceeds in two steps: it produces Very Weak Alternating Automata at an intermediate stage, and then ultimately produces a generalized Büchi Automaton. After verifying both transformations, we also encode both of these automata models using a generic, functional graph type, and use the CakeML compiler to generate fully verified machine code implementing the translation. |
Pages: | 19 |
Talk: | Jul 12 09:30 (Session 70C) |
Paper: |