2026-10-10T21:18:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27704 2026-10-10T19:48:19Z ddc:004 open_access

The Satisfiability Problem of Temporal-Spatial Logics over Quasi-Temporal Graphs Alsmann, Eric Lange, Martin Semezies, Igor linear-time temporal logic modal logic temporal graphs computational complexity automated reasoning Temporal Graph Neural Networks (TGNN) are used to detect patterns in so-called temporal graphs (TG): graphs in which edges may be added or removed over time. Sälzer et al. suggested to study the expressive power of TGNNs through temporal-spatial logics, specifically the combination of the linear-time temporal logic LTL and modal logic K. In this paper we investigate the computational complexity of the satisfiability problem for this logic and its natural extension in which the LTL part is replaced by a linear-time μ-calculus, reflecting TGNNs' ability to recognise not just star-free (word) languages. We consider their interpretation over a more natural class of models which we call quasi-temporal graphs (QTG), relaxing certain conditions on the temporal evolutions of nodes that are indifferent to the logic. We formalise this by giving an adjusted notion of bisimulation which preserves satisfaction in these logics. It turns out that satisfiability over the class of QTGs is PSPACE-complete for the temporal-spatial logic based on LTL but becomes EXPTIME-complete when based on the μ-calculus. This is in contrast to the situation on words where both logics are PSPACE-complete. We also discuss consequences for the special satisfiability problems over the class of TGs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Alsmann and Martin Lange and Igor Semezies 2026 Is Part Of OASIcs, Volume 146, 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.TIME.2026.8 urn:nbn:de:0030-drops-277049 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TIME.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode