Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computing and Information Science
  4. Computing and Information Science Technical Reports
  5. Nonlocal Flow of Control and Kleene Algebra with Tests

Nonlocal Flow of Control and Kleene Algebra with Tests

File(s)
Nonlocal.pdf (213.75 KB)
Permanent Link(s)
https://hdl.handle.net/1813/10595
Collections
Computing and Information Science Technical Reports
Author
Kozen, Dexter
Abstract

Kleene algebra with tests (KAT) is an equational system for program verification that combines Kleene algebra (KA), or the algebra of regular expressions, with Boolean algebra. It can model basic programming and verification constructs such as conditional tests, while loops, and Hoare triples, thus providing a relatively simple equational approach to program equivalence and partial correctness. In this paper we show how KAT can be used to give a rigorous equational treatment of control constructs involving nonlocal transfer of control such as unconditional jumps, loop statements with multi-level breaks, and exception handlers. We develop a compositional semantics and a complete equational axiomatization. The approach has some novel technical features, including a treatment of multi-level break statements that is reminiscent of de Bruijn indices in the variable-free lambda calculus. We illustrate the use of the system by giving a purely calculational proof that every deterministic flowchart is equivalent to a loop program with multi-level breaks.

Date Issued
2008-04-11T13:51:45Z
Keywords
Kleene algebra
•
Kleene algebra with tests
•
control flow
•
program restructuring

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance