Yoàv Montacute

Logic and computer science share a subtle relationship that depends on both syntax and semantics. While structural generalisations often rely on semantics alone, computational aspects such as complexity and decidability hinge on the syntactic properties of formal languages. This interplay frequently manifests through relations between structures, which establish their similarity in various ways and for different purposes. In this work, we focus on three distinct forms of relations between structures: coKleisli morphisms, games, and truth-preserving maps. By coordinating these concepts and proving their equivalence, we apply them across diverse contexts, selecting the appropriate framework for each scenario. CoKleisli morphisms are used to derive generalised theorems, which can then be applied to specific instances; games are used as algorithmic descriptions, crucial when discussing computational complexity; and truth-preserving maps between structures are essential for achieving results such as the finite model property, completeness, and decidability. To a large extent, one must control all manners of structural relations in order to achieve all types of results. We contribute to each of these areas: We extend the use of coKleisli morphisms to ‘linear’ variants of previously studied comonads. Using these results, we derive a novel homomorphism counting theorem for pathwidth. We further establish preservation and characterisation theorems for non-branching variants of the modal comonad. Additionally, using event structures from concurrency theory, we propose a structural alternative to games, providing a more specialised framework for deriving the underlying comonads. For games and computational complexity, we define new model comparison games and establish complexity results for an all-in-one variant of the k-pebble game. Finally, we employ truth-preserving maps to prove completeness and decidability for highly expressive spatiotemporal languages within the context of dynamical systems.

In nonstandard analysis the halo of a point in a topological space is the intersection of the nonstandard extensions of all its open neighbourhoods. We define a parametric family of modal operators from the halo by varying which elements of the nonstandard extension are admitted as witnesses, and identify four canonical instances. Two recover well-known modalities: the topological closure and the Cantor derivative. A third reduces to Kripke semantics over the specialisation preorder. The fourth, purely nonstandard instance admits only nonstandard witnesses. The Transfer Principle forces it to coincide with the ω-accumulation point operator, a classical topological notion not previously studied in modal logic. Unlike the Cantor derivative, the ω-accumulation operator maps arbitrary sets to closed sets without any separation axiom, yielding an ω-Cantor–Bendixson decomposition on all topological spaces. Axiom 4 holds universally, again without separation conditions. We prove that K4 is the complete logic over infinite spaces, and GL over infinite ω-scattered spaces.

Dynamical systems are abstract models of interaction between space and time. They are often used in fields such as physics and engineering to understand complex processes, but due to their general nature, they have found applications for studying computational processes, interaction in multi-agent systems, machine learning algorithms and other computer science related phenomena. In the vast majority of applications, a dynamical system consists of the action of a continuous `transition function' on a metric space. In this work, we consider decidable formal systems for reasoning about such structures. Spatial logics can be traced back to the 1940's, but our work follows a more dynamic turn that these logics have taken due to two recent developments: the study of the topological mu-calculus, and the the integration of linear temporal logic with logics based on the Cantor derivative. In this paper, we combine dynamic topological logics based on the Cantor derivative and the `next point in time' operators with an expressively complete fixed point operator to produce a combination of the topological mu-calculus with linear temporal logic. We show that the resulting logics are decidable and have a natural axiomatisation. Moreover, we prove that these logics are complete for interpretations on the Cantor space, the rational numbers, and subspaces thereof.

Dynamical systems are general models of change or movement over time with a broad area of applicability to many branches of science, including computer science and AI. Dynamic topological logic (DTL) is a formal framework for symbolic reasoning about dynamical systems. DTL can express various liveness and reachability conditions on such systems, but has the drawback that the only known axiomatisation requires an extended language. In this paper, we consider dynamic topological logic restricted to the class of scattered spaces. Scattered spaces appear in the context of computational logic as they provide semantics for provability and enjoy definable fixed points. We exhibit the first sound and complete dynamic topological logic in the original language of DTL. In particular, we show that the version of DTL based on the class of scattered spaces is finitely axiomatisable, and that the natural axiomatisation is sound and complete.

Topological semantics for modal logic based on the Cantor derivative operator gives rise to derivative logics, also referred to as d-logics. Unlike logics based on the topological closure operator, d-logics have not previously been studied in the framework of dynamical systems, which are pairs (X,f) consisting of a topological space X equipped with a continuous function f:X->X. We introduce the logics wK4C, K4C and GLC and show that they all have the finite Kripke model property and are sound and complete with respect to the d-semantics in this dynamical setting. In particular, we prove that wK4C is the d-logic of all dynamic topological systems, K4C is the d-logic of all T_D dynamic topological systems, and GLC is the d-logic of all dynamic topological systems based on a scattered space. We also prove a general result for the case where f is a homeomorphism, which in particular yields soundness and completeness for the corresponding systems wK4H, K4H and GLH. The main contribution of this work is the foundation of a general proof method for finite model property and completeness of dynamic topological d-logics. Furthermore, our result for GLC constitutes the first step towards a proof of completeness for the trimodal topo-temporal language with respect to a finite axiomatisation -- something known to be impossible over the class of all spaces.