Techniques for Modelling Structured Operational and Denotational Semantics Definitions with Term Rewriting Systems

A fundamental requirement for the application of automatic proof support for program verification is that the semantics of programs be appropriately formalized using the object language underlying the proof tool. This means that the semantics definition must not only be stated as syntactically correct input for the proof tool to be used, but also in such a way that the desired proofs can be performed without too many artificial complications. And it must be clear, of course, that the translation from mathematical metalanguage into the object language is correct. The objective of this work is to present methods for the formalization of structured operational and denotational semantics definitions that meet these requirements. It combines techniques known from implementation of the $\lambda$-calculus with a new way to control term rewriting on object level, thus reaching a conceptually simple representation based on unconditional rewriting. This deduction formalism is available within many of the existent proof tools, and therefore application of the representation methods is not restricted to a particular tool. Correctness of the representations is achieved by proving that the non-trivial formalizations yield results that are equivalent to the meta-level definitions in a strong sense. Since the representation algorithms have been implemented in form of executable programs, there is no need to carry out tedious coding schemes by hand. Semantics definitions can be stated in a format very close to the usual meta language format, and they can be transformed automatically into an object-level representation that is accessible to proof tools. The formalizations of the two semantics definition styles are designed in a consistent way, both making use of the same modelling of the underlying mathematical basis. Therefore, they can be used simultaneously in proofs. This is demonstrated in a larger example, where an operational and a denotational semantics definition for a programming language are proved to be equivalent using the Larch Prover. This proof has been carried out by hand before, and so the characteristics of the automated proof can be made quite clear.


Logo BII



Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.


Citation style:
Could not load citation form.