A master thesis from Aalborg University
Certifying Time Complexity of Agda Programs Using Complexity Signatures
[Certificering af Tidskompleksitet af Agda Programmer Ved Brug af Kompleksitetssignaturer]
Author(s)
Term
4. term
Education
Publication year
2020
Submitted on
2020-06-14
Pages
86 pages
Abstract
Danielsson and others have shown that by annotating functions it becomes possible to perform time complexity analysis in functional languages, however the idea of how little annotation is necessary has not been explored. This paper describes a small library which enables a method for minimal annotation of functions to certify time complexity with a Timed monad. Using this method we develop a library of matrix functions with certified time complexity and implement the Cocke-Younger-Kasami (CYK) parsing algorithm for context-free-grammars which we certify to have a complexity of O(n⁵) in Agda, a dependently typed programming language.
Keywords
Documents
Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.
If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.