Büchi Complementation

Julian Brunner 🌐

October 19, 2017

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

This entry provides a verified implementation of rank-based Büchi Complementation. The verification is done in three steps:
  1. Definition of odd rankings and proof that an automaton rejects a word iff there exists an odd ranking for it.
  2. Definition of the complement automaton and proof that it accepts exactly those words for which there is an odd ranking.
  3. Verified implementation of the complement automaton using the Isabelle Collections Framework.

License

BSD License

Topics

Session Buchi_Complementation

Depends on

Cite

× 
@article{Buchi_Complementation-AFP,
  author  = {Julian Brunner},
  title   = {Büchi Complementation},
  journal = {Archive of Formal Proofs},
  month   = {October},
  year    = {2017},
  note    = {\url{https://isa-afp.org/entries/Buchi_Complementation.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download

Download

× Download latest

Older releases: