Verified Efficient Implementation of Gabow's Strongly Connected Components Algorithm

Peter Lammich

28 May 2014

Abstract

We present an Isabelle/HOL formalization of Gabow's algorithm for finding the strongly connected components of a directed graph. Using data refinement techniques, we extract efficient code that performs comparable to a reference implementation in Java. Our style of formalization allows for re-using large parts of the proofs when defining variants of the algorithm. We demonstrate this by verifying an algorithm for the emptiness check of generalized B├╝chi automata, re-using most of the existing proofs.
BSD License

Depends On

Used by

Topics

Related Entries

Theories