Sixteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2001)

Paper: Safety and Liveness in Branching Time (at LICS 2001)

Authors: Panagiotis Manolios Richard Trefler

Abstract

We extend the Alpern and Schneider linear time characterization of safety and liveness properties to branching time, where properties are sets of trees. We define two closure operators that give rise to the following four extremal types of properties: universally safe, existentially safe, universally live, and existentially live. The distinction between universal and existential properties captures the difference between the CTL path quantifiers A (for all paths) and E (there is a path). We show that every branching time property is the intersection of an existentially safe property and an existentially live property, a universally safe property and a universally live property, and an existentially safe property and a universally live property. We also examine how our closure operators behave on linear time properties. We then focus on sets of finitely branching trees and show that our closure operators agree on linear time safety properties. Furthermore, if a set of trees is given implicitly as a Rabin tree automaton, {\cal B}, we show that it is possible to compute the Rabin automata corresponding to the closures of the language of {\cal B}. This allows us to effectively compute {\cal B_{safe}} and {\cal B_{live}} such that the language of {\cal B} is the intersection of the languages of {\cal B_{safe}} and {\cal B_{live}}. As above, {\cal B_{safe}} and {\cal B_{live}} can be chosen so that their languages are existentially safe and existentially live, universally safe and universally live, or existentially safe and universally live.

BibTeX

  @InProceedings{ManoliosTrefler-SafetyandLivenessin,
    author = 	 {Panagiotis Manolios and Richard Trefler},
    title = 	 {Safety and Liveness in Branching Time},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {366--},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }