diff options
| author | Erin van der Veen | 2018-04-19 09:51:08 +0200 |
|---|---|---|
| committer | Erin van der Veen | 2018-04-19 09:51:08 +0200 |
| commit | cef8271999ce007abe7be1d0190f8c01ff6fd993 (patch) | |
| tree | c732f15530006b75b2182b515fa2da6c4e64d10c /Assignment1/exercises.tex | |
| parent | Safra's determinization algorithm (diff) | |
| parent | Example: protocol dependencies (diff) | |
Merge branch 'master' of gitlab.science.ru.nl:eveen/Model-Checking
Diffstat (limited to 'Assignment1/exercises.tex')
| -rw-r--r-- | Assignment1/exercises.tex | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/Assignment1/exercises.tex b/Assignment1/exercises.tex index 647755e..ba056d5 100644 --- a/Assignment1/exercises.tex +++ b/Assignment1/exercises.tex @@ -64,6 +64,7 @@ \end{exercise} \begin{exercise} + \label{ex:succinctness} In this exercise we prove that PLTL formulas can be exponentially more succinct. The proof followed here is that of \citet{Markey2003} which, in turn, is based on work by \citet{Etessami2002}. The proof is achieved by giving an example of a formula which can be expressed in $\mathcal O(n)$ in PLTL but requires $\Omega(n)$ in LTL. |