Overview

Temporal logic is a class of logics used to specify properties of computations over time. In the provided hardware-verification evidence, temporal logic expressions are used to describe the behavior of a synchronous sequential system, where discrete time steps correspond to clock cycles of the described system. [C1]

Temporal logic is also used in program and system correctness settings. The public literature context distinguishes standard temporal logics, which refer to one computation path at a time, from extensions that quantify explicitly over paths in order to express hyperproperties such as noninterference. [C2]

Use in hardware and formal verification

In the ITL verification language, temporal logic expressions describe synchronous sequential behavior. ITL properties commonly have an implication structure: when expressions in an assume part evaluate to true, expressions in a prove part must hold. [C3]

The evidence describes temporal operators such as next and prev, which shift an enclosed expression one clock cycle into the future or past, respectively. ITL also supports freeze variables that bind an expression to a fixed time point, so the value can be referenced independently of the current temporal context. [C4]

Temporal-logic-style safety properties can be used with SAT-based verification methods. The evidence gives a safety property form AG(φ) and states that it can be translated to a Boolean function checking validity at a time point; interval property checking then searches for counterexamples by solving a SAT instance over an unrolled bounded time interval. [C5]

Extensions and variants

Temporal logic for hyperproperties

Hyperproperties characterize correctness as a condition on a set of computation paths. According to the public context for A Temporal Logic for Hyperproperties, standard temporal logics can only refer to a single path at a time and therefore cannot express many hyperproperties of interest, including noninterference. The cited work extends temporal logic with explicit path variables and reports that model checking for temporal logic with path quantification is decidable; for alternation depth 1, its complexity matches linear-time temporal logic in being PSPACE in formula length and NLOGSPACE in system size. [C2]

Reactive temporal logic

The public context for Reactive Temporal Logic states that standard treatments of temporal logic are adequate for closed systems but fall short for reactive systems that interact with their environment by synchronizing actions. Reactive temporal logic is introduced as a form adapted to reactive systems, with examples including definitions of a fair scheduler and a correct mutual exclusion protocol. [C6]

Related tools

• ITL — a verification language in which temporal logic expressions are used to describe the behavior of synchronous sequential systems. [C1]