{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/389464"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/389464","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"From game comonads to dynamical systems: property-preserving maps as a logical unifying principle","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Montacute, Yoàv"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Dawar, Anuj"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-09-30","date_published":"2024-09-30","updated_at":"2026-07-22T22:24:21Z","subjects":["Algorithms","Category Theory","Computational Complexity","Descriptive Complexity","Dynamical Systems","Finite Model Theory","Logic","Modal Logic","Theoretical Computer Science","Topology"],"languages":["eng"],"rights":[],"rights_urls":["https://www.repository.cam.ac.uk/bitstreams/cc0e9b75-ffa7-4c30-b024-1e6e18a627be/download","http://purl.org/NET/rdflicense/allrightsreserved"],"identifier_entries":[{"key":"dc:creator.authoridentifier","label":"Author Identifier","values":["0000000198147323"],"render_values":[{"text":"0000-0001-9814-7323","href":"https://orcid.org/0000-0001-9814-7323","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.121336","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Dawar, Anuj"]},{"key":"dc:creator","label":"Author","values":["Montacute, Yoàv"]},{"key":"dc:creator.authoridentifier","label":"Author Identifier","values":["0000000198147323"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2024-09-30"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/389464"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Algorithms","Category Theory","Computational Complexity","Descriptive Complexity","Dynamical Systems","Finite Model Theory","Logic","Modal Logic","Theoretical Computer Science","Topology"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://www.repository.cam.ac.uk/bitstreams/cc0e9b75-ffa7-4c30-b024-1e6e18a627be/download","http://purl.org/NET/rdflicense/allrightsreserved"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.17863/CAM.121336"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://www.repository.cam.ac.uk/bitstreams/e2d4c4bd-4400-485b-b619-771c17c42ca7/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["518c39e2f5942965964ab2e6e81625e7","87eda9de84448d1f82354d60eee3eb5f"]},{"key":"dc:title","label":"Title","values":["From game comonads to dynamical systems: property-preserving maps as a logical unifying principle"]}]}],"canonical_facts":{"dc:contributor.advisor":["Dawar, Anuj"],"dc:creator":["Montacute, Yoàv"],"dc:creator.authoridentifier":["0000000198147323"],"dc:date.issued":["2024-09-30"],"dc:description.abstract":["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."],"dc:format.checksum.md5":["518c39e2f5942965964ab2e6e81625e7","87eda9de84448d1f82354d60eee3eb5f"],"dc:identifier.doi":["https://doi.org/10.17863/CAM.121336"],"dc:identifier.uri":["https://www.repository.cam.ac.uk/bitstreams/e2d4c4bd-4400-485b-b619-771c17c42ca7/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/389464"],"dc:rights":["https://www.repository.cam.ac.uk/bitstreams/cc0e9b75-ffa7-4c30-b024-1e6e18a627be/download","http://purl.org/NET/rdflicense/allrightsreserved"],"dc:subject":["Algorithms","Category Theory","Computational Complexity","Descriptive Complexity","Dynamical Systems","Finite Model Theory","Logic","Modal Logic","Theoretical Computer Science","Topology"],"dc:title":["From game comonads to dynamical systems: property-preserving maps as a logical unifying principle"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:21Z"}