Deciding the Common Fragment of CTL with Past and LTL
Massimo Benerecetti, Dario Della Monica, Angelo Matteo, Fabio Mogavero, Gabriele Puppis · 2026
Read Deciding the Common Fragment of CTL with Past and LTL by Massimo Benerecetti, Dario Della Monica, Angelo Matteo, Fabio Mogavero, Gabriele Puppis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30405.txt.
Introduction
Massimo Benerecetti and four colleagues prove that the shared expressive core of two temporal logics can be decided mechanically. Temporal logics state properties of systems over time. LTL reasons along single paths; CTL branches over futures. Adding past operators to CTL gives PCTL. The common fragment is what both formalisms can express. Deciding membership in that fragment was open.
Both membership directions turn out decidable, the authors prove. One direction combines known results in a suitable way. The other needs a new automata characterization of PCTL. They introduce counter-free hesitant weak tree automata for it. These automata capture exactly PCTL's expressiveness. A word language defined by LTL lifts to trees recognizably just when a deterministic Büchi automaton recognizes it. That final problem is known to be decidable. The longstanding problem about LTL and plain CTL shrinks accordingly. It now reduces to eliminating past operators.
Catalog record
| CREATOR | Massimo Benerecetti, Dario Della Monica, Angelo Matteo, Fabio Mogavero, Gabriele Puppis |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 125 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30405
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deciding the Common Fragment of CTL with Past and LTL Massimo Benerecetti, Dario Della Monica, Angelo Matteo, Fabio Mogavero, Gabriele Puppis Abstract 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 1 F_{1} and F 2 F_{2} , that is, effectively characterise the class F 1 ∩ F 2 F_{1}\cap F_{2} 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 1 F_{1} or F 2 F_{2} , decide whether the same property can be also expressed in F 1 ∩ F 2 F_{1}\cap F_{2} . A question closely related to this is the membership problem , denoted F 1 ↦ F 2 F_{1}\mapsto F_{2} , which asks whether a property expressed in F 1 F_{1} can be also expressed in F 2 F_{2} . 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 \text{LTL}\cap\text{PCTL} is decidable, where PCTL denotes CTL extended with past operators . We do this by showing that both membership problems, LTL ↦ PCTL \text{LTL}\mapsto\text{PCTL} and PCTL ↦ LTL \text{PCTL}\mapsto\text{LTL} , are decidable. The direction PCTL ↦ LTL \text{PCTL}\mapsto\text{LTL} follows from suitable combinations of known results. The converse direction, LTL ↦ PCTL \text{LTL}\mapsto\text{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 L defined by an LTL formula, the associated tree language △ [ L ] \triangle[L] is recognisable by an HWT cf if and only if L 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 \text{LTL}\cap\text{CTL} . Indeed, that problem can now be reduced to PCTL ↦ CTL \text{PCTL}\mapsto\text{CTL} , that is, the question of when past operators can be eliminated. Università degli Studi di Napoli “Federico II”, [email protected]://orcid.org/0000-0003-4664-6061 Università degli Studi di Udine, [email protected]://orcid.org/0000-0001-9743-665X Università degli Studi di Udine, [email protected]://orcid.org/0009-0009-4663-1522 Università degli Studi di Napoli “Federico II”, [email protected]://orcid.org/0000-0002-5140-5783 Università degli Studi di Udine, [email protected]://orcid.org/0000-0001-9831-3264 {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003766.10003772¡/concept_id¿ ¡concept_desc¿Theory of computation Tree languages¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10003793¡/concept_id¿ ¡concept_desc¿Theory of computation Modal and temporal logics¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10002990¡/concept_id¿ ¡concept_desc¿Theory of computation Logic and verification¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003766.10003770¡/concept_id¿ ¡concept_desc¿Theory of computation Automata over infinite objects¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Tree languages ccs Theory of computation Modal and temporal logics ccs Theory of computation Logic and verification ccs Theory of computation Automata over infinite objects keywords Membership problems, tree languages, tree logics, tree automata, Monadic Path Logic, CTL ∗ , CTL with past † † runningauthor: M. Benerecetti, D. Della Monica, A. Matteo, F. Mogavero and G. Puppis † † copyright: Massimo Benerecetti, Dario Della Monica, Angelo Matteo, Fabio Mogavero and Gabriele Puppis 1 Introduction The notion of a common fragment is central to expressiveness theory: given two formalisms F_{1} and F_{2} , the aim is to effectively characterise the class F_{1}\cap F_{2} of properties that are definable in both. Closely related is the associated membership problem F_{1}\mapsto F_{2} : given a specification in F_{1} , determine whether it can be transformed into an equivalent specification in F_{2} . Of course, deciding the common fragment F_{1}\cap F_{2} reduces to solving two membership problems, i.e. F_{1}\mapsto F_{2} and F_{2}\mapsto F_{1} . These questions have a long history in language theory, tracing back at least to Schützenberger’s theorem on star-free word languages and aperiodic monoids [ 49 ] and to Kamp’s theorem connecting Prior’s tense logic [ 45 ] with first-order logic over linearly ordered structures [ 23 ] . From these seminal works, a rich line of research has emerged, yielding a remarkably complete picture for languages of finite and infinite words, where predicate logics [ 10 , 11 , 12 , 31 ] , temporal logics [ 43 , 44 , 53 ] , automata [ 34 , 33 , 14 , 29 ] , and algebraic structures [ 40 ] are tied together by deep and elegant correspondences [ 41 ] . By contrast, for regular tree languages the situation is considerably more difficult and far more fragmented. A milestone is Rabin’s work on the monadic second-order theory of infinite trees, which established a decisive connection between Monadic Second-Order Logic ( MSO ) and tree automata [ 47 ] . This connection made it possible to study logical questions about decidability and definability by means of automata. Within this framework, full MSO corresponds to automata with parity conditions, whereas weaker logics correspond to weaker acceptance mechanisms. In particular, Weak MSO ( WMSO ), where second-order quantification ranges only over finite sets, admits an automaton-based characterisation in terms of alternating weak tree automata ( AWT ) [ 38 ] , a subclass of alternating parity tree automata where each strongly connected component of the transition graph has a single priority. Thanks to this characterisation, the membership problem \text{MSO}\mapsto\text{WMSO} can be viewed automata-theoretically as the problem of deciding when a parity tree automaton can be replaced by an equivalent weak one. The same parity-versus-weakness boundary also appears with bisimulation-invariant properies, where it governs the comparison between the modal \mu -calculus ( L μ ) [ 24 ] and its alternation-free fragment ( AFL μ ). More precisely, thanks to the celebrated characterisation theorem of Janin and Walukiewicz [ 22 ] , L μ captures precisely the bisimulation-invariant fragment of MSO , and admits a standard presentation in terms of alternating parity tree automata [ 52 ] . Its alternation-free fragment, in turn, corresponds to weak alternating automata, as well as to the bisimulation-invariant fragment of WMSO . Thus, the question whether a L μ property is definable in AFL μ can again be reduced to a membership problem between classes of automata, namely, \text{APT}\mapsto\text{AWT} ; in other words, deciding when parity can be replaced by weakness. This viewpoint has become central in verification: many logical formalisms can be analysed via their corresponding automata models, and suitable restrictions can often be identified, both at the logic level and at the automaton level, that support a number of effective verification procedures [ 25 ] . Within this landscape, the two formalisms most relevant to us are AFL μ and CTL ∗ . Over infinite binary trees, these formalisms correspond to natural fragments of MSO . Indeed, we have already seen that AFL μ corresponds to WMSO (note that the bisimulation relation is trivial over binary trees). As for CTL ∗ , this corresponds to the path-quantification fragment of MSO ( MPL ) [ 20 , 35 , 36 ] . Moreover, recent automata-theoretic characterisations of CTL ∗