Samson Abramsky ; Yoàv Montacute ; Nihil Shah - Linear Arboreal Categories

entics:14830 - Electronic Notes in Theoretical Informatics and Computer Science, December 11, 2024, Volume 4 - Proceedings of MFPS XL - https://doi.org/10.46298/entics.14830
Linear Arboreal CategoriesArticle

Authors: Samson Abramsky ; Yoàv Montacute ; Nihil Shah

    Arboreal categories, introduced by Abramsky and Reggio, axiomatise categories with tree-shaped objects. These categories provide a categorical language for formalising behavioural notions such as simulation, bisimulation, and resource-indexing. In this paper, we strengthen the axioms of an arboreal category to exclude `branching' behaviour, obtaining a notion of `linear arboreal category'. We then demonstrate that every arboreal category satisfying a linearisability condition has an associated linear arboreal subcategory related via an adjunction. This identifies the relationship between the pebble-relation comonad, of Montacute and Shah, and the pebbling comonad, of Abramsky, Dawar, and Wang, and generalises it further. As another outcome of this new framework, we obtain a linear variant of the arboreal category for modal logic. By doing so we recover different linear-time equivalences between transition systems as instances of their categorical definitions. We conclude with new preservation and characterisation theorems relating trace inclusion and trace equivalence with different linear fragments of modal logic.


    Volume: Volume 4 - Proceedings of MFPS XL
    Published on: December 11, 2024
    Accepted on: November 22, 2024
    Submitted on: November 22, 2024
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Category Theory,Mathematics - Logic

    Consultation statistics

    This page has been seen 22 times.
    This article's PDF has been downloaded 9 times.