scientific article; zbMATH DE number 4016870
[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.
- Characterizing finite Kripke structures in propositional temporal logic
- A model checker for linear time temporal logic
- Positive announcements
- Characteristic invariants in Hennessy-Milner logic
- Semantics for knowledge and change of awareness
- Parameter Synthesis for Timed Kripke Structures
- Temporal normal form for linear temporal logic formulae
- On the definability of simulability and bisimilarity by finite epistemic models
- A context dependent equivalence relation between Kripke structures. (Extended abstract)
- Equivalences for fair Kripke structures
- Refinement modal logic
- A topological characterization of weakness
- To be announced
- Encapsulating deontic and branching time specifications
- A generalized nexttime operator in temporal logic
- Branching versus linear logics yet again
- SnS can be modally characterized
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 Q3028984)