Show simple item record

dc.contributor.authorSapozhnikov, Brian Leo
dc.date.accessioned2020-08-28T09:41:00Z
dc.date.created2019-05
dc.date.issued2019-08-23
dc.date.submitted2019
dc.identifier.citationSapozhnikov, Brian Leo. 2019. Practical Verification of Logic Program Termination. Bachelor's thesis, Harvard College.
dc.identifier.urihttps://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37364644*
dc.description.abstractDatalog is a simple and canonical logic programming language, variants of which are being used for data analytics and program analyses. While termination is guaranteed for programs written in pure Datalog, some variants include language features that make them Turing-complete. Krishnamurthy et al. [1996] introduce an algorithm for checking whether a program with these additional language features will terminate. We implement this algorithm and evaluate its practicality for real-world programs. We find that the algorithm does have a potential to be practical, though the current implementation does not reach this potential. We also modify the theoretical underpinnings of the algorithm’s correctness, allowing us to formally demonstrate the validity of our implementation. Finally, the results of our implementation ground a discussion of extensions of the algorithm that may lead to truly practical termination-checking for this domain.
dc.description.sponsorshipComputer Science
dc.description.sponsorshipComputer Science
dc.format.mimetypeapplication/pdf
dc.language.isoen
dash.licenseLAA
dc.titlePractical Verification of Logic Program Termination
dc.typeThesis or Dissertation
dash.depositing.authorSapozhnikov, Brian Leo
dc.date.available2020-08-28T09:41:00Z
thesis.degree.date2019
thesis.degree.grantorHarvard College
thesis.degree.grantorHarvard College
thesis.degree.levelUndergraduate
thesis.degree.levelUndergraduate
thesis.degree.nameAB
thesis.degree.nameAB
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.departmentComputer Science
dash.identifier.vireo
dc.identifier.orcid0000-0003-1509-6618
dash.author.emailbrian.sapozhnikov@gmail.com


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record