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:
Download file(s):
File Description SizeFormat 
185016.pdfFulltext911.29 kBAdobe PDFView/Open
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBååth Sjöblom, Thomas
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.description.abstractParsing 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.
dc.subjectData- och informationsvetenskap
dc.subjectComputer and Information Science
dc.titleAn Agda proof of the correctness of Valiant’s algorithm for context free parsing
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
Collection:Examensarbeten för masterexamen // Master Theses

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