Search Results

A central goal of language theory is to compare formalisms by understanding both their expressive overlaps and their relative expressive power. One particularly challenging question in this direction is the problem of determining the common fragment of two formalisms F₁ and F₂, that is, effectively characterise the class F₁∩ F₂ of properties that can be expressed in both formalisms. This question can be equally phrased as a decision problem: given a property expressed in F₁ or F₂, decide whether the same property can be also expressed in F₁∩ F₂. A question closely related to this is the membership problem, denoted F₁ ↦ F₂, which asks whether a property expressed in F₁ can be also expressed in F₂. These problems become particularly difficult when branching-time formalisms are involved, in general due to the lack of equivalent algebraic characterizations. In this work, we prove that LTL ∩ PCTL is decidable, where PCTL denotes CTL extended with past operators. We do this by showing that both membership problems, LTL ↦ PCTL and PCTL ↦ LTL, are decidable. The direction PCTL ↦ LTL follows from suitable combinations of known results. The converse direction, LTL ↦ PCTL, requires an automata-theoretic characterisation of PCTL. Specifically, we introduce a new class of automata, called counter-free hesitant weak tree automata (HWT_cf) that capture precisely the expressiveness of PCTL, and that are obtained by combining two orthogonal restrictions on alternating parity tree automata, namely, counter-free hesitancy and weakness. We then prove that, for every word language L defined by an LTL formula, the associated tree language △[L] is recognisable by an HWT_cf if and only if L is recognized by a deterministic Büchi word automaton. Since the latter recognisability problem is known to be decidable, so is the former. This result advances the longstanding open problem of deciding LTL ∩ CTL. Indeed, that problem can now be reduced to PCTL ↦ CTL, that is, the question of when past operators can be eliminated.