A relational model for temporal logic (Q4383696)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1138544
Language Label Description Also known as
default for all languages
No label defined
    English
    A relational model for temporal logic
    scientific article; zbMATH DE number 1138544

      Statements

      A relational model for temporal logic (English)
      0 references
      0 references
      0 references
      4 February 1999
      0 references
      relational algebra
      0 references
      reactive systems
      0 references
      temporal algebra
      0 references
      linear temporal logic
      0 references
      algebra of programs
      0 references
      time diagram
      0 references
      The main goal of the paper is an integration of two models of computation. One of them is based on a simple idea to represent a program as a binary relation between initial and final states. Algebraic properties of this model of computation are expressed by a structure known as a (homogeneous, complete) relational algebra. Another model is linear temporal logic (LTL). The logic was designed for decribing properties of reactive systems, where the behaviour between initiation and terminationis also important. Therefore, intermediate states are considered. Lacking features of both models provide a motivation for the integration. It is impossible to express reactive behaviour, temporal specifications (consequently, reasoning about real time) and imperative programs in relational algebra. On the other hand, unlike the calculus of relations, LTL has no operator for sequential composition and the standard model of LTL is unsuitable as a semantic domain for programs. The contribution of the paper is an embedding of LTL into relational algebra. Hence, the relational calculus is enriched with temporal connectives and conversely, LTL is extended by operators of composition and transposition. Denotational domains are created which can be used for modelling programs as well as specifications. As a result it has become possible to express temporal specifications and imperative programs in the same algebra, so that specifications may be transformed into programs by stepwise refinement. The paper consists of three main parts. In the first part an algebraic foundation for integrating relation algebra with linear temporal logic is created. A basic algebra of programs is defined, then a function that associates with every state the time point is added. A structure, called time diagram, is introduced in order to refine the model by recording the intermediate states. Next, temporal connectives are introduced into the algebra of programs. Finally, the results are extended from discrete time to dense time.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references