FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
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: