uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Program Analysis and Verification Based on Kleene Algebra in Isabelle/HOL
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (Mobility)
2013 (English)In: Interactive Theorem Proving: ITP 2013, Springer Berlin/Heidelberg, 2013, 197-212 p.Conference paper (Refereed)
Abstract [en]

Schematic Kleene algebra with tests (SKAT) supports the equational verification of flowchart scheme equivalence and captures simple while-programs with assignment statements. We formalise SKAT in Isabelle/HOL, using the quotient type package to reason equationally in this algebra. We apply this formalisation to a complex flowchart transformation proof from the literature. We extend SKAT with assertion statements and derive the inference rules of Hoare logic. We apply this extension in simple program verification examples and the derivation of additional Hoare-style rules. This shows that algebra can provide an abstract semantic layer from which different program analysis and verification tasks can be implemented in a simple lightweight way.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013. 197-212 p.
, Lecture Notes in Computer Science, 7998
National Category
Computer Science
URN: urn:nbn:se:uu:diva-207378DOI: 10.1007/978-3-642-39634-2_16ISBN: 978-3-642-39633-5OAI: oai:DiVA.org:uu-207378DiVA: diva2:647919
4th International Conference on Interactive Theorem Proving (ITP); Rennes, France; July 22-26, 2013
Available from: 2013-09-12 Created: 2013-09-12 Last updated: 2013-09-13Bibliographically approved

Open Access in DiVA

fulltext(682 kB)198 downloads
File information
File name FULLTEXT01.pdfFile size 682 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Weber, Tjark
By organisation
Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 198 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 251 hits
ReferencesLink to record
Permanent link

Direct link