Local Variable Scoping and Kleene Algebra with Tests | Zendy

Kamal Aboul-Hosn | Zendy; Dexter Kozen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Local Variable Scoping and Kleene Algebra with Tests

Author(s) -

Kamal Aboul-Hosn,

Dexter Kozen

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/11828563_5

Subject(s) - kleene algebra , computer science , axiom , programming language , equivalence (formal languages) , semantics (computer science) , categorical variable , kleene's recursion theorem , theoretical computer science , operational semantics , algebra over a field , algorithm , discrete mathematics , mathematics , geometry , machine learning , pure mathematics

Most previous work on the semantics of programs with local state involves complex storage modeling with pointers and memory cells, complicated categorical constructions, or reasoning in the presence of context. In this paper, we explore the extent to which relational semantics and axiomatic reasoning in the style of Kleene algebra can be used to avoid these complications. We provide (i) a fully compositional relational semantics for a first-order programming language with a construct for local variable scoping; and (ii) an equational proof system based on Kleene algebra with tests for proving equivalence of programs in this language. We show that the proof system is sound and complete relative to the underlying equational theory without local scoping. We illustrate the use of the system with several examples.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research