scientific article; zbMATH DE number 4119617

From MaRDI portal
Publication:4733399





[For the entire collection see Zbl 0683.68001.] This paper presents some of the recent developments for the specification, verification and development of reactive programs in the temporal formal systems. The authors observe that the methodology of the present temporal logics is based on two major design decisions: (1) Only the future fragment is considered; and (2) Satisfiability and validity are evaluated at all positions in the computation. Relaxing one or both of these design decisions, some properties have a more natural expression when using the past operators. This is done by the special state predicate init, which characterizes the initial point in the computation. By adding the past fragment to temporal logic, it has been found that, while not increasing the expressive power of the language, important contributions to the utility of the language are done: (a) Many properties, including the generalization rule, have a more natural expression when using the past operators; (b) Classification of the properties expressible by temporal logic into several classes; (c) Closer connections between temporal logic and transition-based formalisms such as \(\omega\)-automata; (d) The relative cost of this expansion was found to be quite modest. The decision procedure for the propositional segment has the same complexity as that of the pure future fragment. A complete deductive system (for the propositional segment), and the model checking procedure have been derived. Section 2 analyzes some abstract and concrete (shared variables, synchronous message passing) computational models. Section 3 describes the language of the (extended) temporal logic with the four temporal operators: two for past (previous, and since), and two for future (next, and until). Section 4 is devoted to the classification of temporal properties using different criteria: semantical, topological characteristics, their expressiveness, predicate-automata characterization etc. The axiomatics, theorems, and derived rules of the temporal logic future fragment are exposed. Section 6 gives a general proof system of the temporal logic with the set of past operators. The proof system for proving specific properties met in (concurrent) programming languages represents the object of Section 7.




Cited in
(41)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4733399)