?
On the Expressive Power of Some Extensions of Linear Temporal Logic
One of the most simple models of computation which is suitable for representation of reactive systems behaviour is a nite state transducer which operates over an input alphabet of control signals and an output alphabet of basic actions. A behaviour of such a reactive system displays itself in the correspondence between ows of control signals and compositions of basic actions performed by the system. We believe that behaviour of this kind requires more suitable and expressive means for formal speci cations than conventional LTL. In this paper we de ne some new (as far as we
know) extension LP-LTL of Linear Temporal Logic speci cally intended for describing the properties of transducers computations. In this extension the temporal operators are parameterized by sets of words (languages) which represent distinguished flows of control signals that impact on a reactive system. Basic predicates in our variant of temporal logic are also languages in the alphabet of basic actions of a transducer; they represent the expected response of a transducer to the specified environmental influences. In our earlier papers we considered model checking problem for LP-LTL and LP-CTL and showed that this problem has effective solutions. The aim of this paper is to estimate the expressive power of LP-LTL by comparing it with some well known logics widely used in computer science for specification of reactive systems behaviour. We discovered that a restricted variant LP-1-LTL of our
logic is more expressive than LTL and another.