I'm reading Sistla and Clarke's paper "The Complexity of Propositional Linear Temporal Logics". In section 4 they start with the following set up:

Let $S=(s, \xi), T=(t, \pi)$ be structures such that, for some $m \geq 0$, the following conditions are satisfied: $$ \forall i, 0 \leq i \leq m, t_{i}=s_{i} ; \quad \forall i, i>m+1, t_{i}=s_{i-1} \text {, } $$ and $\pi$ is an extension of $\xi$, that is $$ \pi(t_r) = \begin{cases} \xi(s_r) & 0 \le r \le m \\ \xi(s_{r-1}) & m < r \end{cases} $$ such that $$ \pi\left(t_{m+1}\right)=\pi\left(t_{m}\right) $$ that is, $T$ is obtained by duplicating the $m$-th state in $S$ successively once. The following lemma is easily proved by induction on the formula $f$.


For any $f \in L(\mathbf{U})$,

$T, t_{m} \vDash f$ iff $T, t_{m+1} \vDash f$ and for any $\delta$ in $s$, $S, \delta \vDash f$ iff $T, \delta \vDash f$.

Note that I added what they mean by extension myself.

After the lemma, which I proved, they say:

Note that the lemma is not true for $\mathbf{L}(\mathbf{U}, \mathbf{X})$.

I've been playing around with formulas in $\mathbf{L}(\mathbf{U}, \mathbf{X})$, however, I could not find the counterexample. Is this counterexample standard?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.