Computation tree logic

<p>Computation tree logic (CTL) is a branching-time <a href="/facts/Mathematical_logic/SaI7Y3wN">logic</a>, meaning that its model of <a href="/facts/Time/HceJKUGB">time</a> is a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree-like</a> structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is realized. It is used in <a href="/facts/Formal_verification/BYD4GnJR">formal verification</a> of software or hardware artifacts, typically by software applications known as <a href="/facts/Model_checker/FwvKMlw9">model checkers</a>, which determine if a given artifact possesses <a href="/facts/Safety_and_Liveness_Properties/vBWq8Sdb">safety or liveness properties</a>. For example, CTL can specify that when some initial condition is satisfied (e.g., all program variables are positive or no cars on a highway straddle two lanes), then all possible executions of a program avoid some undesirable condition (e.g., dividing a number by zero or two cars colliding on a highway). In this example, the safety property could be verified by a model checker that explores all possible transitions out of program states satisfying the initial condition and ensures that all such executions satisfy the property. Computation tree logic belongs to a class of <a href="/facts/Temporal_logic/vANP39lc">temporal logics</a> that includes <a href="/facts/Linear_temporal_logic/Gh5yxXK7">linear temporal logic</a> (LTL). Although there are properties expressible only in CTL and properties expressible only in LTL, all properties expressible in either logic can also be expressed in <a href="/facts/CTL*/emAMSuXt">CTL*</a>.
</p>

Computation tree logic open-in-new

Computation tree logic