Why Does Propositional Quantification Make Modal and Temporal Logics on Trees Robustly Hard?

Bartosz Bednarczyk (1, 2) , Stéphane Demri (3, 4)

1 Uniwersytet Wroclawski = University of Wroclaw
2 Faculty of Computer Science [TU Dresden]
3 LMF - Laboratoire Méthodes Formelles
4 CNRS - Centre National de la Recherche Scientifique

Adding propositional quantification to the modal logics K, T or S4 is known to lead to undecidability but CTL with propositional quantification under the tree semantics (QCTLt) admits a non-elementary Tower-complete satisfiability problem. We investigate the complexity of strict fragments of QCTLt as well as of the modal logic K with propositional quantification under the tree semantics. More specifically, we show that QCTLt restricted to the temporal operator EX is already Tower-hard, which is unexpected as EX can only enforce local properties. When QCTLt restricted to EX is interpreted on N-bounded trees for some N ≥ 2, we prove that the satisfiability problem is AExppol-complete; AExppol- hardness is established by reduction from a recently introduced tiling problem, instrumental for studying the model-checking problem for interval temporal logics. As consequences of our proof method, we prove Tower-hardness of QCTLt restricted to EF or to EXEF and of the well-known modal logics such as K, KD, GL, K4 and S4 with propositional quantification under a semantics based on classes of trees.

Domaines: Informatique [cs]; Logique en informatique [cs.LO]; Complexité [cs.CC]

Bartosz Bednarczyk, Stéphane Demri. Why Does Propositional Quantification Make Modal and Temporal Logics on Trees Robustly Hard?. Logical Methods in Computer Science, 2022, 18 (3), pp.5:1--5:46. ⟨10.46298/lmcs-18(3:5)2022⟩. ⟨hal-03749464⟩