A proof of the interpretability of P/PML in a relational setting

Abstract

In [1] we presented the logic P=PML, a formalism suitable for the speci cation and construction of Real-Time systems. The main algebraic result, namely, the interpretability of P/PML into an equa- tional calculus based on w-closure fork algebras (which allows to reason about Real-Time systems in an equational calculus) was stated but not proved because of the lack of space. In this paper we present a detailed proof of the interpretability theorem, as well as the proof of the representation theorem for w-closure fork alge- bras which provides a very natural semantics based on binary relations for the equational calculus.