diff options
| author | Camil Staps | 2018-04-18 21:48:33 +0200 |
|---|---|---|
| committer | Camil Staps | 2018-04-18 21:48:33 +0200 |
| commit | 25ffc622afc727baa7c5c2918ee602b98bb291a3 (patch) | |
| tree | f1bffb5db779cc505c70892b91acdfc3e13f24dc /Assignment1/exercises.tex | |
| parent | Bars everywhere (diff) | |
Example: protocol dependencies
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. |