Yoàv Montacute

Leo Lobski, Yoàv Montacute

Biochemical systems involve both the flow of matter, in which entities transform into one another via reactions, and the flow of information, in which entities regulate which reactions may occur. Boolean networks capture the latter; reaction networks capture the former. Yet no unified qualitative formalism treats regulated reactions as its principal objects of study, despite their prominence in standards such as the Systems Biology Graphical Notation Process Description (SBGN-PD) language. We introduce modulation-reaction networks (MR-networks), a mathematical framework in which entities modulate reactions through activations and inhibitions, and study their synchronous Boolean semantics. To reason about MR-networks we develop Modulation-Reaction Logic (MRL), a hybrid modal $μ$-calculus whose modalities reason about the structure of the network and whose fixed-point operators capture temporal evolution of the computation. We establish a collection of validities, including a complete characterisation of the one-step update rule, and demonstrate the expressive power of MRL by formalising properties of biological interest such as reachability, sustained production, and presence of attractors. We show that MRL admits model-checking via an evaluation game, and introduce a bisimulation relation for MR-networks, which is proved to be invariant for all MRL-formulas. As a step towards a biologically more realistic computational model, we sketch the asynchronous semantics of MR-networks, and outline how the developments for the synchronous case transfer to the study of the asynchronous one.

Takahiro Sanada, Yoàv Montacute, Kittiphon Phalakarn et al.

The Dijkstra algorithm is a classical method for solving the shortest path problem on weighted graphs. There are several variations of the Dijkstra algorithm, including algorithms for the widest path problem and for two-player games. In this paper, we introduce the coalgebraic shortest path problem (CSPP), a unifying framework for a broad class of optimization problems on state-transition systems. This framework encompasses not only the aforementioned problems but also new ones such as the shortest binary tree problem. We further present a coalgebraic Dijkstra algorithm for solving the CSPP efficiently under a suitable condition. Our condition is necessary and sufficient for the algorithm to return correct solutions, thereby providing a precise criterion for when Dijkstra-style acceleration is possible. We also show that the proposed algorithm achieves asymptotic complexity comparable to that of the classical Dijkstra algorithm.

Soichiro Fujii, Yun Chen Tsai, Yoàv Montacute et al.

We present a categorical theory of monads and distributive laws in substructural contexts. In the study of distributive laws, the roles of (the absence of) structural rules for variable contexts have been recognized; our theory formalizes these substructural situations using Tronin's verbal categories $\mathbf W$, in a uniform and presentation-independent manner. We introduce the classes of $\mathbf W$-operadic monads (those defined via the structural rules in $\mathbf W$) and of $\mathbf W$-commutative monads (those invariant under the structural rules in $\mathbf W$). We give a canonical construction of a distributive law $ST\to TS$ of monads on $\mathbf{Set}$; it is applicable when $S$ is $\mathbf W$-operadic and $T$ is $\mathbf W$-commutative (under mild conditions). This accounts for many known and new distributive laws. Even when $S$ fails to be $\mathbf W$-operadic, we can refine $S$ and force $\mathbf W$-operadicity; this captures Varacca and Winskel's construction of indexed valuations.