Gabbay's separation theorem

Template:Short description In mathematical logic and computer science, Gabbay's separation theorem states that any formula in linear temporal logic (LTL) with past operators can be rewritten as a boolean combination of formulas that are only concerned with the past, present, or future. This theorem was stated and proven by Dov Gabbay.

Applications

Expressive Completeness

A formula is separated if it is a boolean combination of formulas that are only concerned with the past, present, or future. An arbitrary temporal logic has the separation property if each formula is equivalent to a separated formula. Gabbay shows that a temporal logic that can express the future operator $𝐅$ and the past operator $𝐏$ of LTL has the separation property if and only if the logic is expressively complete. Here, a logic is expressively complete if it is expressively equivalent to the monadic first-order logic of order. Separation was first used to prove Kamp's theorem. Before, the only known method to prove expressive completeness was a pure syntactic argument.

An example of a logic without the separation property is LTL restricted to the operators $𝐅$ and $𝐏$. The formula $𝐅(a\wedge \mathrm{\neg }𝐏\mathrm{\neg }b)$ cannot be separated, where $a,b$ are atomic propositions. LTL restricted to the next operator $𝐗$ and the yesterday operator $𝐘$ has the separation property, but is not expressively complete as it cannot express $𝐅$.

Expressiveness of Past Operators

Gabbay showed that LTL formulas can be separated. When evaluating a formula over the natural numbers at time 0, formulas only concerning the past are trivial as there is no past at time 0. Thus, every LTL formula using past operators has an equivalent form without past operators at time 0. That is, the addition of past operators do not increase the expressive power of LTL. A corollary is that CTL* with past operators has the same expressive power as CTL* over rooted trees. Hodkinson and Reynolds suggest that this is the reason researchers tend to use future-only versions of LTL, CTL, and CTL*. While LTL with past and LTL have the same expressive power, the inclusion of past operators can make formulas exponentially more succinct.

Normal Forms

The separation theorem is used to prove various normal forms for temporal formulas.

Safety-Liveness Form

Lichtenstein et al. gives us the safety-liveness form, where every formula in LTL is equivalent to a formula of the following form, where $a_i,b_i$ are boolean combinations of atomic propositions:

$\underset{i=1}{\overset{n}{\bigvee }}(𝐆𝐅a_i)\wedge (𝐅𝐆b_i)$

Separated Normal Form

Fisher gives us the separated normal form, where each formula in LTL can be written in the following form, such that each $P_i$ is only concerned with the past, and $F_i$ is only concerned with the future:

$𝐆(\underset{i=1}{\overset{n}{\bigwedge }}{P}_i\to F_i)$

This form has been used for specifications in executable temporal logic, where $F_i$ can be executed when the current history satisfies $P_i$. MetateM is an example of a language that uses this paradigm.