diff options
Diffstat (limited to 'Assignment1')
| -rw-r--r-- | Assignment1/assignment1.tex | 1 | ||||
| -rw-r--r-- | Assignment1/comparison.tex | 2 | ||||
| -rw-r--r-- | Assignment1/intro.tex | 5 | ||||
| -rwxr-xr-x | Assignment1/library.bib | 10 | ||||
| -rw-r--r-- | Assignment1/summary.tex | 12 |
5 files changed, 25 insertions, 5 deletions
diff --git a/Assignment1/assignment1.tex b/Assignment1/assignment1.tex index 3c9d766..b4ed04c 100644 --- a/Assignment1/assignment1.tex +++ b/Assignment1/assignment1.tex @@ -90,7 +90,6 @@ \input{semantics} \input{specifying-properties} \input{equivalence} -\input{comparison} \input{conversion} %TODO: (Section?) Assess if PLTL is actually more succinct using the examples from the SSH Paper \input{bad-prefix} diff --git a/Assignment1/comparison.tex b/Assignment1/comparison.tex deleted file mode 100644 index 5876153..0000000 --- a/Assignment1/comparison.tex +++ /dev/null @@ -1,2 +0,0 @@ -\subsubsection{LTL and PLTL} -%TODO: Consider/Analyse differences between LTL and PLTL diff --git a/Assignment1/intro.tex b/Assignment1/intro.tex index 0d359f3..6df3700 100644 --- a/Assignment1/intro.tex +++ b/Assignment1/intro.tex @@ -9,8 +9,9 @@ The combination of LTL and Past Modalities is often called \enquote{LTL-Past} or For the sake of brevity we will use the second (PLTL) to denote this combination. When temporal logic was first introduced by Arthur N. Prior in his 1957 book~\cite{Prior1957}, the logic consisted of both past and future modalities. -Only later, when it was shown that past modalities do not increase the expressive power of LTL~\cite{Gabbay1980}, -computing scientists stopped considering past modalities for reasons of minimality. +The complexity of the model problem does not increase with this extension~\citep{Sistla1985}, + but neither does the expressiveness of the system compared to LTL~\citep{Gabbay1980}. +Eventually, formal computing scientists stopped using past modalities for reasons of minimality. \erin In 2003, Nicolas Markey showed that while past modalities do not increase expressive power, diff --git a/Assignment1/library.bib b/Assignment1/library.bib index ade5101..23f73b8 100755 --- a/Assignment1/library.bib +++ b/Assignment1/library.bib @@ -87,3 +87,13 @@ year = 2002, pages = {279--295} } + +@article{Sistla1985, + author = {Sistla, A. P. and Clarke, E. M.}, + title = {The Complexity of Propositional Linear Temporal Logics}, + journal = {Journal of the ACM}, + volume = 32, + issue = 3, + year = 1985, + pages = {733--749} +} diff --git a/Assignment1/summary.tex b/Assignment1/summary.tex index 6f243b2..a888df8 100644 --- a/Assignment1/summary.tex +++ b/Assignment1/summary.tex @@ -1,2 +1,14 @@ \subsection{Summary} % TODO: points to be added to 5.3 +\camil +\begin{itemize} + \item + PLTL is an extension to LTL which adds \emph{past modalities}. + The extension is not more expressive, but PLTL formulas can be exponentially more succinct than their LTL equivalents. + + \item + Because PLTL formulas need to be able to \enquote{look back}, the satisfaction relation $\vDash$ becomes ternary: + it is a subset of $\left(2^{AP}\right)^\omega \times \mathbb N \times PLTL$, + where the natural number indicates the index at which a trace satisfies a formula. +\end{itemize} +\cbend |