diff options
| author | Camil Staps | 2018-04-15 12:25:38 +0200 |
|---|---|---|
| committer | Camil Staps | 2018-04-15 12:25:38 +0200 |
| commit | 4a8205f8d47db9bd7b677de1fb379a882dd0f291 (patch) | |
| tree | f61a48c0ccdb7a20d63030290a266fbcd57c7b7e /Assignment1/intro.tex | |
| parent | Add two summary points, this means we do not need a comparison subsection any... (diff) | |
Add result by Sistla (1985): complexity of model checking for PLTL is the same as for LTL
Diffstat (limited to 'Assignment1/intro.tex')
| -rw-r--r-- | Assignment1/intro.tex | 5 |
1 files changed, 3 insertions, 2 deletions
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, |