Content deleted Content added
m Move paren into <math> |
Adding short description: "Theory in computer science" |
||
| (17 intermediate revisions by 10 users not shown) | |||
Line 1:
{{Short description|Theory in computer science}}
{{More footnotes|date=October 2015}}
'''Computation tree logic''' ('''CTL''') is a branching-time [[Mathematical logic|logic]], meaning that its model of [[time]] is a [[tree (graph theory)|tree-like]] 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 [[formal verification]] of software or hardware artifacts, typically by software applications known as [[model checker]]s, which determine if a given artifact possesses [[Safety
== History ==
CTL was first proposed by [[Edmund M. Clarke]] and [[E. Allen Emerson]] in 1981, who used it to synthesize so-called ''synchronisation skeletons'', ''i.e'' abstractions of [[concurrent program]]s.
Since the introduction of CTL, there has been debate about the relative merits of CTL and LTL. Because CTL is more computationally efficient to model check, it has become more common in industrial use, and many of the most successful model-checking tools use CTL as a specification language.<ref>{{cite book |last1=Vardi |first1=Moshe Y. |date=2001 |chapter=Branching vs. Linear Time: Final Showdown |journal=Tools and Algorithms for the Construction and Analysis of Systems |series=Lecture Notes in Computer Science |volume=2031 | publisher=Springer, Berlin |pages=1{{ndash}}22 |doi=10.1007/3-540-45319-9_1 |isbn=978-3-540-41865-8 |chapter-url=https://link.springer.com/content/pdf/10.1007/3-540-45319-9_1.pdf}}</ref>
== Syntax of CTL ==
Line 28 ⟶ 32:
:<math>\mbox{EF }\big(r \mbox{ U } q\big)</math>
The problem with this string is that <math>\mathrm U</math> can occur only when paired with an <math>\mathrm A</math> or an <math>\mathrm E</math>. <!-- TODO: explain it is evaluated over multiple paths /// here is a copy-paste from the LTL page: build up from proposition variables p1,p2,..., LTL formulas are generally evaluated over paths and a position on that path. A LTL formula as such is satisfied if and only if it is satisfied for position 0 on that path. -->
CTL uses [[First-order logic#Vocabulary|atomic propositions]] as its building blocks to make statements about the states of a system. <!-- TODO: give an example of an atomic proposition. --> These propositions are then combined into formulas using [[logical operator]]s and [[temporal logic|temporal operator]]s.
Line 50 ⟶ 54:
**''φ'' '''W''' ''ψ'' – '''W'''eak until: ''φ'' has to hold until ''ψ'' holds. The difference with '''U''' is that there is no guarantee that ''ψ'' will ever be verified. The '''W''' operator is sometimes called "unless".
In [[CTL*]], the temporal operators can be freely mixed. In CTL,
===Minimal set of operators===
Line 69 ⟶ 73:
===Definition===
CTL formulae are interpreted over [[transition system]]s. A transition system is a triple <math>\mathcal{M}=(S,{\rightarrow},L)</math>, where <math>S</math> is a set of states, <math>{\rightarrow} \subseteq S \times S</math> is a transition relation, assumed to be serial, i.e. every state has at least one successor, and <math>L</math> is a labelling function, assigning propositional letters to states. Let <math>\mathcal{M}=(S,\rightarrow,L)</math> be such a transition model, with <math>s \in S</math>, and <math>\phi \in F</math>, where <math>F</math> is the set of [[well-formed formula]]s over the [[Formal language|language]] of <math>\mathcal{M}</math>.
Then the relation of semantic [[entailment]] <math>(\mathcal{M}, s \models \phi)</math> is defined recursively on <math>\phi</math>:
Line 97 ⟶ 100:
This is denoted <math>\phi \equiv \psi</math>
It can be seen that <math>\mathrm A</math> and <math>\mathrm E</math> are duals, being universal and existential computation path quantifiers respectively:
<math>\neg \mathrm A\Phi \equiv \mathrm E \neg \Phi </math>.
Furthermore, so are <math>\mathrm G</math> and <math>\mathrm F</math>.
Hence an instance of [[De Morgan's laws]] can be formulated in CTL:
Line 109 ⟶ 112:
It can be shown using such identities that a subset of the CTL temporal connectives is adequate if it contains <math>EU</math>, at least one of <math>\{AX,EX\}</math> and at least one of <math>\{EG,AF,AU\}</math> and the boolean connectives.
The important equivalences below are called the '''expansion laws'''; they allow
:<math>AG\phi \equiv \phi \land AX AG \phi</math>
:<math>EG\phi \equiv \phi \land EX EG \phi</math>
Line 127 ⟶ 130:
:"It's always possible (AF) that I will suddenly start liking chocolate for the rest of time." (Note: not just the rest of my life, since my life is finite, while '''G''' is infinite).
*'''EG'''.'''AF'''.P
:"Depending on what happens in the future (E), it's possible that for the rest of time (G), I'll be guaranteed at least one (AF) chocolate-liking day still ahead of me. However, if something ever goes wrong, then all bets are off and there's no guarantee about whether I'll ever like chocolate."
The two following examples show the difference between CTL and CTL*, as they allow for the until operator to not be qualified with any path operator ('''A''' or '''E'''):
Line 146 ⟶ 149:
== Extensions ==
CTL has been extended with [[second-order logic|second-order]] quantification <math>\exists p</math> and <math>\forall p</math> to ''quantified computational tree logic'' (QCTL).<ref>{{Cite journal|
* the tree semantics. We label nodes of the computation tree. QCTL* = QCTL = [[monadic second-order logic|MSO]] over trees. Model checking and satisfiability are tower complete.
* the structure semantics. We label states. QCTL* = QCTL = MSO over [[Graph (discrete mathematics)|graph]]s. Model checking is [[PSPACE-complete]] but satisfiability is [[undecidable problem|undecidable]].
A reduction from the model-checking problem of QCTL with the structure semantics, to TQBF (true quantified Boolean formulae) has been proposed, in order to take advantage of the QBF solvers.<ref>{{Cite journal|
==See also==
Line 160 ⟶ 163:
==References==
{{Reflist}}
* {{cite
* {{cite book |author1=Michael Huth |author2=Mark Ryan | title=Logic in Computer Science
* {{cite journal |author1=Emerson, E. A. |author2=Halpern, J. Y. |author2link = Joseph Halpern| title=Decision procedures and expressiveness in the temporal logic of branching time | journal=[[Journal of Computer and System Sciences]]| year=1985| volume=30 | issue=1 | pages=1–24 | doi=10.1016/0022-0000(85)90001-7| citeseerx=10.1.1.221.6187}}
* {{cite journal |author1=Clarke, E. M. |author2=Emerson, E. A. |author3=Sistla, A. P. |name-list-style=amp | title=Automatic verification of finite-state concurrent systems using temporal logic specifications | journal=[[ACM Transactions on Programming Languages and Systems]]| year=1986| volume=8 | issue=2 | pages=244–263 | doi=10.1145/5397.5399|s2cid=52853200 | doi-access=free }}
* {{cite book | author=Emerson, E. A. | year=1990 | chapter =Temporal and modal logic | editor=Jan van Leeuwen | editor-link=Jan van Leeuwen | title=Handbook of Theoretical Computer Science, vol. B | pages=955–1072 | publisher=MIT Press | isbn=978-0-262-22039-2}}
| |||