Alessandro Cimatti Created 2026-10-31 Updated 2026-11-05
Alessandro Cimatti coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]
Armin Biere Created 2026-10-31 Updated 2026-11-05
Armin Biere coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]
Edmund Clarke Created 2026-10-31 Updated 2026-11-05
Edmund Clarke coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]
Fairness assumption Created 2026-10-31 Updated 2026-11-05
A fairness assumption selects admissible infinite paths in a transition system, often to exclude executions that postpone an enabled activity forever. The notation quantifies only over initial paths in a transition system satisfying the chosen condition; without that qualification, an unfair execution can invalidate a progress claim.
In linear temporal logic, means that holds infinitely often, while means that holds permanently after some finite point. Therefore implies : once every position satisfies , every later suffix contains such a position. The converse fails on an alternating path in a transition system where is true at exactly the even positions. This distinction matters when specifying repeated service versus eventual permanent availability.
A fairness assumption must be justified by the environment or scheduling model; it does not itself supply an implementation that enforces the assumed progress.
Lasso path 2026-10-31
An infinite path in a transition system represented by a finite prefix followed by infinite repetition of a nonempty finite loop. If stored positions are and , the represented sequence is . The linear temporal logic condition holds exactly when occurs on the repeated part, and holds exactly when holds everywhere on that part.
Next-time operator 2026-10-31
The linear temporal logic operator , true at position of a path in a transition system exactly when is true at position . Thus tests two positions ahead.
Solutions to the paper whose cover dates the examination to 6 June 2015, 2:30–4:00 pm. Source: released examination archive, member 2015-cafv.pdf. All three questions are covered, although candidates were asked to attempt at most two. In the binary decision diagrams, dashed arrows mean zero and solid arrows mean one. In the linear temporal logic calculations, , and .
Use the two incoming initial arrows in the source figure: . An atomic proposition is true precisely at the states whose displayed labels contain it. In particular, is false at every state. Hence is true on every infinite path in a transition system, and the first implication in the fairness assumption imposes no restriction.
Write . The remaining implication is . By the linear temporal logic duality , it is equivalent to
since implies . Thus a path is fair exactly when it visits states not labelled with both and infinitely often. This condition also follows directly: if eventually holds forever, then eventually holds forever and the required is impossible; if does not eventually hold forever, the implication has a false antecedent.
Every initial path in a transition system in the upper component either alternates forever between and , or makes finitely many alternations and then stays at . These are all fair: the first visits infinitely often, and the second visits infinitely often; neither state satisfies .
In the lower component, a path in a transition system can stay at forever, or leave it after finitely many visits and pass through to . The constant path in a transition system is unfair because holds forever while never holds. Every departing path in a transition system is fair because satisfies neither nor . Here means infinite repetition of the finite word . Therefore
This notation lists initial paths in a transition system. If one instead allows arbitrary starting states, their suffixes starting at are fair as well; the fair paths in a transition system from each initial state, and hence all verdicts below, are unchanged.
A finite or infinite sequence of states in which for each consecutive pair. In infinite-path linear temporal logic semantics, paths are infinite; an initial path must also start in the specified initial set. Repeated states are allowed, unlike conventions for a simple path in a graph.
Strong until 2026-10-31
In linear temporal logic, holds at position exactly when some satisfies and every position with satisfies . The witness must exist. The case imposes no condition on .
Temporal logic Created 2026-10-31 Updated 2026-11-05
Temporal logic extends ordinary mathematical logic with assertions about successive states or times. Temporal operators express properties such as eventually holding, always holding, or holding until another condition occurs.
In linear temporal logic, says that every request is eventually answered along a trace. A safety property rules out a bad finite behavior; a liveness property requires future progress. Computation tree logic additionally distinguishes possible execution paths. The choice of linear or branching time determines exactly which system behaviors a formula quantifies over.
Temporal operator Created 2026-10-31 Updated 2026-11-05
A temporal operator states how a proposition behaves across time in a temporal logic. In linear temporal logic, means that holds at the next position, that it holds eventually, and that it holds at every later position, including the current one.
The binary strong until operator requires a future position where holds and requires at all earlier positions. Thus expresses that every request eventually gets a response. The temporal operators distinguish such behavior from an ordinary Boolean condition evaluated at one instant. Branching-time logics additionally quantify over possible execution paths.
Weak until 2026-10-31
In linear temporal logic, means . Thus it permits the left operand to hold forever without the right operand ever becoming true, unlike strong until.
Yunshan Zhu Created 2026-10-31 Updated 2026-11-05
Yunshan Zhu coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]