Relative Liveness: From Intuition to Automated Verification We define a new liveness condition for asynchronous circuits. Although finitary (finiteexecution) descriptions are not powerful enough to express general liveness properties, those liveness properties needed in practice appear to be related in a unique manner to finitary descriptions. Our liveness condition exploits this observation and is defined directly on finitary descriptions, in two forms: one on finite trace structures and the other on finite automata. We prove the equivalence of these two forms. We also introduce a safety condition and derive theorems for the modular and hierarchical verification theorems of both safety and liveness. Finally, we give an algorithm for verifying our liveness condition.

From liveness to promptness Liveness temporal properties state that something good eventually happens, e.g., every request is eventually granted. In Linear Temporal Logic (LTL), there is no a priori bound on the wait time for an eventuality to be fulfilled. That is, F ? asserts that ? holds eventually, but there is no bound on the time when ? will hold. This is troubling, as designers tend to interpret an eventuality F ? as an abstraction of a bounded eventuality F ?k ?, for an unknown k, and satisfaction of a liveness property is often not acceptable unless we can bound its wait time. We introduce here promptLTL, an extension of LTL with the prompteventually operator F p . A system S satisfies a promptLTL formula ? if there is some bound k on the wait time for all prompteventually subformulas of ? in all computations of S. We study various problems related to promptLTL, including realizability, model checking, and assumeguarantee model checking, and show that they can be solved by techniques that are quite close to the standard techniques for LTL.