Computing persistent homology within Coq/SSReflect

Jónathan Heras, Thierry Coquand, Anders Mörtberg, Vincent Siles

    Research output: Contribution to journalArticle

    7 Citations (Scopus)

    Abstract

    Persistent homology is one of the most active branches of computational algebraic topology with applications in several contexts such as optical character recognition or analysis of point cloud data. In this article, we report on the formal development of certified programs to compute persistent Betti numbers, an instrumental tool of persistent homology, using the COQ proof assistant together with the SSREFLECT extension. To this aim it has been necessary to formalize the underlying mathematical theory of these algorithms. This is another example showing that interactive theorem provers have reached a point where they are mature enough to tackle the formalization of nontrivial mathematical theories.
    Original languageEnglish
    Article number26
    JournalACM Transactions on Computational Logic
    Volume14
    Issue number4
    DOIs
    Publication statusPublished - 1 Nov 2013

    Fingerprint Dive into the research topics of 'Computing persistent homology within Coq/SSReflect'. Together they form a unique fingerprint.

  • Projects

    Cite this