Gabbay's separation theorem

Key takeaways

Gabbay's separation theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Gabbay's separation theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Gabbay's separation theorem from memory before moving on to harder problems.

Reference excerpt

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 F {\displaystyle \mathbf {F} } and the past operator P {\displaystyle \mathbf {P} } 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. 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 F {\displaystyle \mathbf {F} } and P {\displaystyle \mathbf {P} } . The formula F ( a ∧ ¬ P ¬ b ) {\displaystyle \mathbf {F} (a\land \neg \mathbf {P} \neg b)} cannot be separated, where a , b {\displaystyle a,b} are atomic propositions. LTL restricted to the next operator X {\displaystyle \mathbf {X} } and the yesterday operator Y {\displaystyle \mathbf {Y} } has the separation property, but is not expressively complete as it cannot express F {\displaystyle \mathbf {F} } .

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 {\displaystyle a_{i},b_{i}} are boolean combinations of atomic propositions:

⋁ i = 1 n ( G F a i ) ∧ ( F G b i ) {\displaystyle \bigvee _{i=1}^{n}(\mathbf {G} \mathbf {F} a_{i})\land (\mathbf {F} \mathbf {G} 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 {\displaystyle P_{i}} is only concerned with the past, and F i {\displaystyle F_{i}} is only concerned with the future:

G ( ⋀ i = 1 n P i → F i ) {\displaystyle \mathbf {G} \left(\bigwedge _{i=1}^{n}P_{i}\to F_{i}\right)}

This form has been used for specifications in executable temporal logic, where F i {\displaystyle F_{i}} can be executed when the current history satisfies P i {\displaystyle P_{i}} . MetateM is an example of a language that uses this paradigm.

References

Worked examples

Example 1 — a first encounter with Gabbay's separation theorem

Start with the simplest possible case. Write down what Gabbay's separation theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Gabbay's separation theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Gabbay's separation theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Gabbay's separation theorem

In research: Gabbay's separation theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Gabbay's separation theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Gabbay's separation theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Artificial intelligence, Temporal logic, Theorems, so understanding it makes those chapters shorter.
In everyday life: Look for Gabbay's separation theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Gabbay's separation theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Gabbay's separation theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Gabbay's separation theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Gabbay's separation theorem in simple terms?

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 D…

Why does Gabbay's separation theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Gabbay's separation theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Gabbay's separation theorem.