Recognizing safety and liveness
Distributed ComputingPublished 1 September 1987
Bowen Alpern, Fred B. Schneider
Citations552
SJR quartileQ1
SJR score0.81
SNIP1.21
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A formal characterization for safety properties and liveness properties is given in terms of the structure of the Buchi automaton that specifies the property.
Abstract
A formal characterization for safety properties and liveness properties is given in terms of the structure of the Buchi automaton that specifies the property. The characterizations permit a property to be decomposed into a safety property and a liveness property whose conjunction is the original. The characterizations also give insight into techniques required to prove a large class of safety and liveness properties.
Keywords
Computer Science
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
ACM Transactions on Programming Languages and SystemsAutomatic verification of finite-state concurrent systems using temporal logic specifications
3,555 Citations1986E. M. Clarke, E. Allen Emerson +1 more
It is argued that this technique can provide a practical alternative to manual proof construction or use of a mechanical theorem prover for verifying many finite-state concurrent systems.
IEEE Transactions on Software EngineeringProving the Correctness of Multiprocess Programs
1,101 Citations1977Leslie Lamport
The inductive assertion method is generalized to permit formal, machine-verifiable proofs of correctness for multiprocess programs, represented by ordinary flowcharts, and no special synchronization mechanisms are assumed.
Information Processing LettersDefining liveness
1,025 Citations1985Bowen Alpern, Fred B. Schneider
A formal definition for liveness properties is proposed, and every property is shown to be the intersection of a safety property and a liveness property.
Distributed ComputingRecognizing safety and liveness
552 Citations1987Bowen Alpern, Fred B. Schneider
A formal characterization for safety properties and liveness properties is given in terms of the structure of the Buchi automaton that specifies the property.
Lecture notes in computer scienceThe glory of the past
461 Citations1985Orna Lichtenstein, Amir Pnueli +1 more
The notion of α-fairness is presented which is proved to fully capture the behavior of probabilistic finite state programs.
IFIP CongressWhat Good is Temporal Logic
444 Citations1983Leslie Lamport
This was an invited paper and describes the state of my views on specification and verification at the time, notable for introducing the idea of invariance under stuttering and explaining why it’s a vital attribute of a specification logic.
Verification of Concurrent Programs. Part I. The Temporal Framework,
323 Citations1981Zohar Manna, Amir Pnueli
The temporal formalism is introduced as a tool for reasoning about sequences of states and the set of interesting properties is classified into invariance (safety), eventuality (liveness, and precedence) properties.
Specification and verification of concurrent programs by A ∀ automata
93 Citations1987Z. Monna, Amir Pnueli
It is shown that ∀-automata are as expressive as extended-temporal-logic (ETL), and in some cases provide a more compact representation of properties than temporal logic.
On characterization of safety and liveness properties in temporal logic
47 Citations1985A. Prasad Sistla
Annals of Pure and Applied LogicVerification of concurrent programs: the automata-theoretic framework*
47 Citations1991Moshe Y. Vardi
An automata-theoretic framework to the verification of concurrent and nondeterministic programs and unifies previous works on verification of fair termination and verification of temporal properties.
Information Processing LettersSafety without stuttering
28 Citations1986Bowen Alpern, Alan Demers +1 more
A new formalization of safety properties agrees with the informal definition—that a safety property stipulates that some ‘bad thing’ does not happen during execution—for properties that are not invariant under stuttering, as well as for property that are.
eCommons (Cornell University)Proving Boolean Combinations of Deterministic Properties
26 Citations1987Bowen Alpern, Fred B. Schneider
eCommons (Cornell University)Verifying Temporal Properties without using Temporal Logic
24 Citations2001Bowen Alpern, Fred B. Schneider
An approach to proving temporal properties of concurrent programs that does not use temporal logic as an inference system is presented and is shown to be sound and relatively complete.
eCommons (Cornell University)Proving temporal properties of concurrent programs: a non-temporal approach
8 Citations1986Bowen Alpern
A new method for proving properties of concurrent programs is developed and formal definitions for safety and liveness are given and every property is shown to be the intersection of a safety property and a liveness property.