Anchored LTL Separation

Gabbay’s separation theorem is a fundamental result for linear temporal logic (LTL). We show that separating a restricted class of LTL formulas, called anchored LTL, is elementary if and only if the translation from LTL to the linear temporal logic with only future temporal connectives is elementary. To prove this result, we define a canonical separation for LTL, and establish a correspondence between a canonical separation of anchored LTL formulas and the ω-automata that recognize these formulas. The canonical separation of anchored LTL formulas has two further applications. First, we constructively prove that the safety closure of any LTL property is an LTL property, thus proving the decomposition theorem for LTL: every LTL formula is equivalent to the conjunction of a safety LTL formula and a liveness LTL for-mula. Second, we characterize safety, liveness, absolute liveness, stable, and fairness properties in LTL. Our characterization is effec-tive: We reduce the problem of deciding whether an LTL formula defines any of these properties to the validity problem for LTL. Categories and Subject Descriptors Theory of computation [Logic]: Modal and temporal logics; Theory of computation [For-mal languages and automata theory]: Automata over infinite ob-jects; Theory of computation [Formal languages and automata theory]: Regular language