No label defined (Q3028984)

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 4016870
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4016870

      Statements

      0 references
      0 references
      0 references
      1987
      0 references
      temporal logics
      0 references
      finite Kripke structure
      0 references
      bisimulation
      0 references
      reasoning about concurrent systems
      0 references
      shuttering
      0 references
      polynomial algorithm
      0 references
      [For the entire collection see Zbl 0605.00015.] The comparison between branching-time and linear-time temporal logics as a tool for reasoning about concurrent programs has attracted much attention of theoretical computer scientists. This paper shows that any finite Kripke structure M can be characterized, up to equivalence reminiscent of \textit{R. Milner}'s [A calculus of communicating systems (1980; Zbl 0452.68027)] bisimulation, by a CTL formula \(F_ M\) containing possibly the nexttime operator. Since the nexttime operator may be dangerous in reasoning about concurrent systems [see, e.g., \textit{L. Lamport}, Proceedings of the International Federation for Information Processing, 657-668 (1983)], the authors proceed further to introduce another notion of equivalence, say equivalence with respect to shuttering, so as to obtain another characterization theorem without the nexttime operator. A polynomial algorithm for determining if two states are equivalent up to shuttering is also given.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references