An Agda proof of the correctness of Valiant’s algorithm for context free parsing

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/185016
Download file(s):
File Description SizeFormat 
185016.pdfFulltext911.29 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: An Agda proof of the correctness of Valiant’s algorithm for context free parsing
Authors: Bååth Sjöblom, Thomas
Abstract: Parsing is an important problem with applications ranging from compilers to bioinformatics. To perform the parsing more quickly, it would be desirable to be able to parse in parallel. Valiant’s algorithm [Valiant, 1975] is a divide and conquer algorithm for parsing and can be used to perform a large part of the work in parallel. It is fairly easy to implement in a functional programming languages, using pattern matching. Agda is a dependently typed functional programming language that doubles as a proof assistant and is hence very suitable for implementing and proving the correctness of Valiant’s algorithm. In this thesis, we provide a very natural specification for the parsing problem and prove that it is equivalent to the specification of the transitive closure used in [Valiant, 1975], that is further removed from both parsing and proving. We compare the two specifications and use our specification to derive Valiant’s algorithm. We then implement it in Agda and prove our implementation correct (we prove that it satisfies our specification). We also give short introductions to parsing, programming and proving with Agda and to using algebraic structures in Agda.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2013
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/185016
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.