arXiv CSopen access

Time-Varying Data as Sheaves: an Invitation to Narratives

· arxiv_cs

arXiv CS · Papers · License: Open Access

artificial intelligence, reasoning, knowledge representation

Time-Varying Data as Sheaves: an Invitation to Narratives Wilmer Leal1*, Benjamin Merlin Bumpus2 , Jana K. Nickel3 , Johan Garcı́a4 , James Fairbanks1 , Warren Dixon1,5

arXiv:2609.09056v1 [cs.AI] 8 Sep 2026

Department of Mechanical and Aerospace Engineering, University of Florida, 1064 Center Drive, Gainesville, 32611-6250, Florida, USA . 2 Instituto de Matemática e Estatı́stica, Universidade de São Paulo, Rua do Matão, 1010, São Paulo, 05508–090, SP, Brasil. 3 Fachbereich Mathematik, Universität Hamburg, Bundesstraße 55, Hamburg, 20146, Germany. 4 Departamento de Matemáticas, Universidad Nacional de Colombia – sede Medellı́n, Calle 59A No. 63-20, Medellı́n, Colombia. 5 Virginia Tech, College of Engineering, Blacksburg, Virginia, 24061, USA . *Corresponding author(s). E-mail(s): [email protected]; Contributing authors: [email protected]; [email protected]; [email protected]; [email protected]; wdixon@{ufl.edu,vt.edu}; Abstract Modern science and engineering increasingly rely on time-varying data, yet the mathematical tools used to model temporal phenomena are often developed within separate disciplines, obscuring common principles and limiting the transfer of ideas across fields. This chapter presents the theory of narratives, an abstract framework for time-varying objects of any mathematical kind that supports both theoretical investigations and applications. To illustrate this perspective, the chapter develops three vignettes, each illustrating a different research direction. The first addresses a general concern: What information loss can occur when switching between different representations of temporal data? The second concerns structural and algorithmic approaches: How can we systematically decompose time-varying data into simple pieces and obtain invariants describing its structural complexity? The third is an application to control theory: How can we model multi-agent systems with switching communication topologies? More important than any individual vignette, the central message of this invitation is that a suitable abstract perspective can organize and guide research across remarkably diverse mathematical and scientific domains.

Keywords: Time-Varying Data, Temporal Networks, Categories of Narratives, Temporal Data Structures, Persistent and Cumulative Data, Structured Decompositions, Cellular Sheaves, Multi-Agent Systems, Control Theory MSC Classification: 18A40 , 18F20 , 18A25 , 05C90 , 37B55 , 93C85

Contents 1

Introduction

Background on Narratives: How to Model Time-Varying Data using Sheaves 2.1 Categories of temporal data . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Changing Perspectives on Temporal Data: The Persistence– Accumulation Adjunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Systematic Temporalization . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4

Three Vignettes on Time-Varying Data and the Ensuing Research Directions 3.1 Vignette 1: Narratives and the Fixed Points of the Persistence–Accumulation Adjunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Narratives encoding persistence and accumulation simultaneously . . 3.1.2 Factorizing the persistence–accumulation adjunction . . . . . . . . . 3.1.3 Classifying narratives by rigidity . . . . . . . . . . . . . . . . . . . . 3.2 Vignette 2: Decomposing Time-Varying Data into Simple Pieces: Structured Decompositions of Narratives . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Structured decompositions . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Temporalization of spined sd-categories . . . . . . . . . . . . . . . . 3.2.3 Temporalizing tree-width: examples . . . . . . . . . . . . . . . . . . 3.3 Vignette 3: Temporal Cellular Sheaves: Modelling Multi-agent Systems with Switching Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Cellular sheaves for multi-agent systems . . . . . . . . . . . . . . . . 3.3.2 Category of cellular sheaves . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Temporal cellular sheaves and switching topologies . . . . . . . . . .

Conclusion and future directions

6 7

9 11 13 19 22 22 24 29 31 31 33 35 36

1 Introduction Modern science and engineering are increasingly driven by the analysis of time-varying data. From social dynamics [1], environmental science [2], and public health [3, 4] to distributed control of multi-agent systems [5, 6], language evolution [7], and the computational history of science [8, 9], observations rarely describe static objects; rather, they capture the evolution of phenomena through time [10]. Despite the ubiquity of such data, the mathematical tools used to analyze them remain largely fragmented [11], with different communities developing specialized theories for temporal data mining, temporal databases, temporal networks, and related domains [11–14]. Many existing approaches represent temporal information as sequences of measurements or snapshots of evolving systems, often without a coherent mathematical structure describing how these observations relate across time. As a result, integrating different representations of temporal data, or reasoning systematically about their transformations, remains a significant challenge. The theory of narratives introduced in [15] addresses this problem by representing time-varying data as sheaves and cosheaves over categories of time intervals. A persistent narrative records information that remains valid throughout an interval, while a cumulative narrative records information that accumulates over it. Because narratives are categorical objects, the framework describes not only timevarying data but also maps between them, and it applies to data valued in categories of sets, graphs, topological spaces, cellular sheaves, and many other structured objects. This chapter is intended as an invitation to the theory of narratives. Through a survey of recent developments, we hope to illustrate how narratives provide a common framework in which ideas from many areas of mathematics can contribute to the study of time-varying data, through both abstract theory and concrete applications. The theory of narratives was designed to address five requirements that arise when one seeks a general mathematical language for time-varying data: (D1) (Categories of Temporal Data) Any theory of temporal data should define not only time-varying data, but also appropriate morphisms thereof. (D2) (Cumulative and Persistent Perspectives) In contrast to being a mere sequence, temporal data should explicitly record whether it is to be viewed cumulatively or persistently. Furthermore, there should be methods of conversion between these two viewpoints. (D3) (Systematic “Temporalization”) Any theory of temporal data should come equipped with systematic ways of obtaining temporal analogues of notions relating to static data. (D4) (Object Agnosticism) Theories of temporal data should be object agnostic and applicable to any kinds of data originating from given underlying dynamics. (D5) (Sampling) Since temporal data arises from an underlying dynamical system, any theory of temporal data should be interoperable with theories of dynamical systems. This chapter collects three recent developments in the theory of narratives. Each is presented as a vignette centered on a different question: (1) how much information is preserved when one changes between persistent and cumulative viewpoints, (2) how the structural complexity of time-varying data can be measured, and (3) how narratives can be used to model multi-agent systems whose interaction structure changes through time. Together, these examples illustrate the broader goals of our research program: by studying time-varying data 3

systematically and abstractly, we can use a unified language to describe many different kinds of questions concerning time-varying data. The first vignette concerns the adjunction between persistent and cumulative narratives. Since this adjunction is not, in general, an equivalence, converting a narrative from one viewpoint to the other and back may lose information. We introduce narratives valued in a cotwisted arrow category, which encode a persistent component, a cumulative component, and a comparison between them. We then use this category to factorize the persistence– accumulation adjunction and to classify narratives according to whether they can be recovered after either of the two possible round trips. The second vignette concerns decompositions of time-varying data. Complex objects are often studied by expressing them as composites of smaller pieces and recording how these pieces overlap. Such decompositions also give rise to measures of structural complexity. In the temporal setting, the pieces must themselves vary through time: decomposing each snapshot independently does not record how the pieces persist, merge, split, or disappear. Building on recent work [16], we explain how theories of structured decompositions for static objects can be lifted to persistent narratives. The resulting framework yields decompositions whose pieces are time-varying objects and yields temporal analogues of structural invariants such as tree-width. The third vignette applies narratives to multi-agent systems whose communication topology changes through time. By taking cellular sheaves as the category of values, a narrative can record both the changing interaction graph and the local state spaces, sensing maps, and compatibility constraints carried by its vertices and edges. The resulting model of a switching system contains substantially more information than a sequence of communication graphs. It also provides a setting in which the relationship between an underlying dynamical system and the temporal data sampled from it can be studied using the same categorical language.

2 Background on Narratives: How to Model Time-Varying Data using Sheaves 2.1 Categories of temporal data We begin by recalling background on narratives: objects introduced in [15] representing time-varying objects valued in any sufficiently nice category. Narratives are (co)sheaves over categories of time intervals—we call these time categories—which model temporal data by recording how temporal information relates across overlapping intervals of time. The thesis of [15] is that temporal data should be understood not merely as a sequence of observations, but as a structured system of relations connecting observations across time. For example, a time-varying graph may consist of a family of graphs Gt indexed by time together with morphisms describing how vertices and edges persist, merge, or disappear as time evolves. Narratives capture precisely these additional relations across time. Rather than representing time merely as a totally ordered set, the framework uses categories of intervals, which naturally encode the inclusion relations between time periods. Definition 1 (Time Categories) A time category is any sub-join-semilattice of I or IN , where I (resp. IN ) is the category of closed intervals in R (resp. N) with inclusions as morphisms.

Remark 1 (Alternative models of time) Although we focus on interval categories in this chapter, the categorical viewpoint naturally accommodates more general notions of time. For instance, one could replace intervals by a finite branching tree to model branching temporal evolutions, such as the history of a Git repository or the multiple futures envisioned in Borges’ The Garden of Forking Paths [17]. Developing such generalized notions of time is an interesting direction for future research. Example 1 (Finite time categories) If T is a time category and [a, b] ∈ T, then the slice category T/[a, b], consisting of the intervals contained in [a, b], is itself a time category, and the canonical inclusion T/[a, b] ,→ T restricts the temporal domain to the interval [a, b]. In particular, for every n ≥ 0, we write Tn := IN /[0, n]. Its objects are the intervals [i, j] ⊆ [0, n], ordered by inclusion, so Tn models temporal data consisting of n + 1 snapshots together with every interval determined by them. For example, T2 consists of the six intervals contained in [0, 2]: [0, 2] [0, 1] [0, 0]

[1, 2] [1, 1]

[2, 2]

Example 2 (Changing temporal resolution) Suppose that [a, b] is an interval in a time category T, and choose a partition a = r0 ≤ r1 ≤ · · · ≤ rn = b. This partition determines a unique functor R : Tn −→ T/[a, b],

R([i, j]) = [ri , r j ].

The finite time category Tn models the temporal resolution of [a, b] determined by the chosen snapshots r0 , . . . , rn : the objects [i, i] correspond to the snapshots, while the objects [i, j] correspond to the intervals from ri to r j .

To speak of sheaves, one must first have a site, that is, a category equipped with a coverage, where, intuitively, a coverage amounts to a systematic way of defining what it means for an object to be “covered” by opens. As shown in [15], time categories become sites when equipped with the Johnstone coverage [18]. Under this coverage, a cover of an interval [ℓ, ℓ′ ] is generated by a partition into two closed intervals ([ℓ, p], [p, ℓ′ ]). This reflects the idea that information about a time interval can be reconstructed from information on adjacent subintervals. Narratives As we alluded to earlier, narratives—our model for temporal data—consist of sheaves or cosheaves over time categories (viewed as sites, as above). The choice between sheaves and cosheaves is a modelling decision: should the model track data that persists over time (sheaves) or data that accumulates over time (cosheaves)? Definition 2 (T-sheaves and T-cosheaves) Let T be a time category equipped with the Johnstone coverage. If D has pullbacks, a D-valued sheaf on T is a presheaf F : Top → D such that F([a, b]) ∼ = F([a, p]) ×F([p,p]) F([p, b]).

Dually, if D has pushouts, a D-valued cosheaf on T is a copresheaf F̂ : T → D such that for any interval [a, b] and cover ([a, p], [p, b]), F̂([a, b]) ∼ F̂([p, b]). = F̂([a, p]) + F̂([p,p])

Definition 3 (Narratives) Let T be a time category and D a category with pullbacks (resp. pushouts). The category of persistent D-narratives, denoted Pe(T, D) (resp. cumulative D-narratives, denoted Cu(T, D)) consists of D-valued sheaves (resp. cosheaves) on T.

A persistent narrative models information that must remain valid throughout a time interval. The sheaf condition ensures that such information over a larger interval can be reconstructed from data that persist across overlapping sub-intervals. In contrast, a cumulative narrative models information that accumulates over time, with the cosheaf condition expressing that data associated with a longer interval arises from aggregating the data of its sub-intervals. In both cases, a narrative encodes not only observations made at individual moments in time but also the relations describing how these observations evolve and interact across time intervals. Remark 2 Since persistent narratives are sheaves, their categories can carry an internal intuitionistic logic. In particular, when the target category is Set, or more generally a presheaf category ([C, Set]), categories of discrete persistent narratives form Grothendieck topoi. In [4], this structure is used to define temporal truth values and a propositional language for reasoning about properties that hold at specific times or throughout intervals. The resulting logic is applied to public health models, where it can express temporal properties of individuals and conditions and support reasoning about possible routes of disease transmission in time-varying contact networks.

2.2 Changing Perspectives on Temporal Data: The Persistence– Accumulation Adjunction Cumulative and persistent narratives are related by the following adjunction [15], which describes how one may change perspective between persistent and cumulative descriptions of temporal data. Theorem 2.1 (Adjunction between cumulative and persistent narratives [15]) Let D be a category with limits and colimits and T a time category. There exist functors K : Pe(T, D) → Cu(T, D) and P : Cu(T, D) → Pe(T, D) forming an adjunction: K

⊣

Pe(T, D)

Cu(T, D).

The functor K sends a persistent narrative F : Top → D to its canonical cumulative counterpart K F. For each interval [a, b] ∈ T, its value is defined by F (K F)ba := colim (T /[a, b])op ,→ Top − →D . (1) 6

Thus, (K F)ba accumulates the persistent data assigned by F to the subintervals of [a, b]. An inclusion i : [a, b] ,→ [c, d] induces a morphism K F(i) : (K F)ba −→ (K F)dc

by the universal property of the corresponding colimits. Thus, K F(i) records how accumulated data over a smaller time window contribute to the accumulated data over a larger one. Dually, the functor P sends a cumulative narrative F̂ : T → D to its canonical persistent counterpart. For each interval [a, b] ∈ T, its value is defined by F̂ (P F̂)ba := lim T /[a, b] ,→ T − →D . (2) Thus, (P F̂)ba extracts the data compatible across the subintervals of [a, b]. An inclusion i : [a, b] ,→ [c, d] induces a morphism P F̂(i) : (P F̂)dc −→ (P F̂)ba

by the universal property of the corresponding limits. The adjunction is equipped with a unit and counit η : idPe(T,D) =⇒ P K and ε : K P =⇒ idCu(T,D) . For a persistent narrative F, the component ηF : F −→ P K F compares the prescribed persistent data with the persistent narrative reconstructed after passing through its cumulative completion. Dually, for a cumulative narrative F̂, the component εF̂ : K P F̂ −→ F̂ compares the cumulative narrative reconstructed from its persistent completion with the original cumulative data. The functors K and P do not, in general, form an equivalence of categories. Consequently, passing from one perspective to the other and back need not recover the original temporal structure. Instead, the adjunction replaces the original data by the canonical objects determined by the corresponding colimit and limit constructions. The unit and counit therefore measure the extent to which the persistent and cumulative descriptions agree with these canonical reconstructions. A natural problem is therefore to characterize those temporal structures for which no information is lost. Equivalently, one may ask when the unit or counit of the adjunction is an isomorphism, or, more generally, which narratives are fixed points of the persistence–accumulation adjunction. The first research direction developed in Section 3.1 is devoted to these questions.

2.3 Systematic Temporalization We now explain how [15] addresses Desideratum (D3), namely the requirement that a theory of temporal data provide systematic procedures for producing temporal analogues of familiar static notions. The guiding observation is that the static theories we care about (graphs, groups, spaces, etc.) are far more mature than their temporal counterparts, and that many static properties are most naturally expressed categorically: either as membership in a subcategory, or as the existence of morphisms from a class of “test objects” (paths, cliques, colorings, and so on). Once phrased categorically, these notions admit canonical lifts to narrative categories.

Changing data types functorially. A first ingredient is that narratives are functorial in the data category. If C and D are categories of static data and K : C → D is a data-conversion functor, then postcomposition transports C-valued narratives to D-valued narratives whenever K preserves the universal constructions that define the (co)sheaf conditions. Concretely, if K is continuous, then for any time category T the assignment F 7→ K ◦ F defines a functor (K ◦ −) : Pe(T, C) → Pe(T, D), and dually if K preserves colimits then (K ◦ −) sends cumulative C-narratives to cumulative D-narratives. There is also a contravariant form: if K : Cop → D takes limits to colimits (resp. colimits to limits), then composition with K switches perspectives, producing a functor from persistent to cumulative narratives (resp. cumulative to persistent). In this way, standard static constructions can be “temporalized” and transported across data types in a principled, functorial manner. Lifting static properties by change of base. The second ingredient is a systematic way to lift classes of static objects to classes of narratives. Suppose a static property is presented by a subcategory inclusion P : P ,→ C (one should think of P as the full subcategory of objects of C satisfying the property). If P is continuous, then the induced functor (P ◦ −) identifies those persistent C-narratives whose values lie in P in a way compatible with the sheaf condition; dually, if P preserves colimits, it specifies the corresponding class of cumulative narratives. This reproduces, in the temporal setting, the common pattern from static combinatorics and algebra: properties become subcategories, and temporal analogues become subcategories of narrative categories. Temporal analogues at a chosen resolution. While change of base yields a clean lift, it can be too strict in applications: one may only care that a property appears at a particular temporal granularity. The framework in [15] accounts for this by introducing a functorial method for changing temporal resolution. Given a subjoin-semilattice inclusion τ : S ,→ T, precomposition defines a restriction functor (− ◦ τ) sending T-narratives to S-narratives (persistent-to-persistent and cumulative-to-cumulative). By combining restriction with change of base, one obtains a general notion of a narrative satisfying a static property only on the intervals in S: rather than requiring the property at all intervals, one imposes it after restricting to S, and defines the resulting class of narratives by a pullback that expresses compatibility between “restriction to S” and “landing in P”. This produces a family of temporal analogues parametrized by resolution, reflecting the empirical reality that certain phenomena are only visible after aggregating over sufficiently large time windows. Example 3 (Temporal resolution) Recall from Example 2 that a partition a = r0 ≤ · · · ≤ rn = b determines a functor R : Tn −→ T/[a, b]. Consequently, every D-valued narrative F : (T/[a, b])op → D restricts along R to the narrative op F ◦ Rop : Tn −→ D . The resulting narrative is the restriction of F to the temporal resolution induced by the chosen partition.

Graph-theoretic case studies: paths, cliques, and dualities. To demonstrate the machinery recovers familiar temporal notions while adding conceptual clarity, [15] develops graph-theoretic case studies. Path-like behavior is obtained by lifting the subcategory of paths in Grph to a corresponding class of graph narratives; temporal paths in a graph narrative can then be expressed as subobjects of that narrative, recovering the static viewpoint in which many decision problems are homomorphism problems. Temporal cliques are treated similarly: by lifting the subcategory of complete graphs and combining it with a resolution restriction (e.g., requiring completeness only over intervals of length at least n), one recovers standard definitions of temporal k-cliques from the temporal-graph literature, but now characterized by morphisms of narratives. This categorical reformulation also exposes dualities: just as cliques and colorings are related by categorical duality in the static setting, temporal analogues inherit corresponding dual notions, and these dualities depend on whether one works cumulatively or persistently. A key conceptual payoff is that these temporalizations are not ad hoc: they arise from a small number of functorial principles (change of base, change of resolution, and categorical characterizations by morphisms). Moreover, the interaction with the persistent–cumulative adjunction highlights genuine temporal subtleties: for instance, properties defined by stability under pushouts may behave differently from those defined by stability under pullbacks, and changing perspective can therefore change which temporal analogues exist or are well behaved.

3 Three Vignettes on Time-Varying Data and the Ensuing Research Directions 3.1 Vignette 1: Narratives and the Fixed Points of the Persistence–Accumulation Adjunction The functor K sends a persistent narrative F : Top → D to its cumulative counterpart K F by forming pushouts that encode data accumulated over a given time window. Applying P then returns to the persistent viewpoint by computing pullbacks, producing P K F. In general, this pushout–pullback round trip does not recover the original persistent sheaf. More conceptually, because K and P form an adjunction rather than an equivalence, the composite P K need not act as the identity on persistent narratives. Equivalently, the unit ηF : F → P K F may fail to be an isomorphism. Thus, passing between these viewpoints may approximate the original temporal structure by its associated limit and colimit constructions. Figure 1 illustrates this phenomenon by exhibiting a persistent narrative for which the unit ηF : F → P K F is not an isomorphism. The significance of Figure 1 is not merely that the unit fails to be invertible, but why it fails. The span F00 ← − F01 → − F11 defining the persistent narrative is prescribed data and therefore need not satisfy any universal property. By contrast, the span F00 ← − F00 ×(K F)10 F11 → − 1 0 1 1 F1 is built by taking the pullback of the cospan F0 → (K F)0 ← F1 . The unit ηF01 : F01 −→ (P K F)10

0 1

f a

ι1

(a, b)

π1

ι2 ∗

(b)

(a)

π2 b

(c)

Fig. 1: An example showing that the adjunction K ⊣ P is not an equivalence. (a) Let T be the time category [0, 0] ,→ [0, 1] ←- [1, 1]. Consider the persistent narrative F : Top → Set shown in the figure. Its value at the interval [0, 1] is F01 = {0, 1}. (b) Applying K yields a cumulative narrative with (K F)10 = F00 +F01 F11 = {a} +{0,1} {b}, which in this case is the singleton {∗}. (c) Applying P produces a persistent narrative with (P K F)10 = F00 ×(K F)10 F11 ∼ = {(a, b)}. 1 1 ∼ Since {(a, b)} = ̸ {0, 1}, the component ηF01 : F0 → (P K F)0 is not an isomorphism. Hence P K F ̸∼ = F. is the canonical comparison between the prescribed persistent data and its canonical approximation via the pushout–pullback round trip. This observation leads to a natural characterization of the fixed points of the adjunction in the direction F → P K F. By a fixed point we mean a persistent narrative F for which the unit ηF : F → P K F is an isomorphism. Equivalently, as illustrated by the diagram below, this requires the span F00 ← − F01 → − F11 to coincide with the pullback of its pushout F00 → (K F)10 ← F11 . F01 ⌟

F11 ⌟

F00 (K F)10

This characterization immediately yields a broad class of fixed points whenever the ambient category D is adhesive. Recall that in an adhesive category, pushouts along monomorphisms are Van Kampen [19], and hence are stable under pullback. Consequently, if the span F00 ← − F01 → − F11 consists of monomorphisms, then the associated pushout square is also a pullback. Therefore, F is a fixed point of the adjunction in the direction F → P K F. The discussion above concerns the unit of the adjunction and the recovery of persistent data. Dually, one may study the counit and the recovery of cumulative data. Figure 1 already shows that these two behaviors need not agree: panel (b) is recovered after the pullback– pushout round trip, whereas panel (a) is not recovered after the pushout–pullback round trip. This asymmetry motivates the introduction of narratives, which encode persistent and cumulative descriptions simultaneously together with the comparison between them.

3.1.1 Narratives encoding persistence and accumulation simultaneously Definition 4 (Cotwisted Arrow Category) Let D be a small category. The cotwisted arrow category of D, denoted D▷◁ , is defined as follows. • Objects are morphisms f : x → y in D. f

f′

• Morphisms from (x − → y) to (x′ − → y′ ) are pairs of morphisms (u : x → x′ , v : y′ → y) in D such that the following diagram commutes: u

x′ that is, f = v ◦ f ′ ◦ u.

f′

y′

Thus, a morphism in D▷◁ encodes a factorization of f through f ′ . The notation D▷◁ is mnemonic for the defining commutative square: the superscript ▷ reminds the reader that the domain morphism points to the right, whereas the subscript ◁ indicates that the codomain morphism points to the left. • Composition is defined componentwise: (u′ , v′ ) ◦ (u, v) = (u′ ◦ u, v ◦ v′ ). Lemma 3.1 If D has pullbacks and pushouts, then the cotwisted arrow category D▷◁ has pullbacks.

Proof Consider two morphisms in D▷◁ with common codomain, fi

(ui , vi ) : (xi − → yi ) −→ (x0 −→ y0 ),

i = 1, 2,

satisfying fi = vi ◦ f0 ◦ ui . They are depicted in the following diagram. x1

x2 u1

x0 f1

= v1

y2 u

1 2 Form in D the pullback of the span x1 −→ x0 ←− x2 , namely x1 ←−− P −−→ x2 , and the pushout of the q1 q2 v1 v2 cospan y1 ←− y0 −→ y2 , namely y1 −→ Q ←− y2 . Since u1 ◦ p1 = u2 ◦ p2 and q1 ◦ v1 = q2 ◦ v2 , we obtain

q1 ◦ f1 ◦ p1 = q1 ◦ v1 ◦ f0 ◦ u1 ◦ p1 = q2 ◦ v2 ◦ f0 ◦ u2 ◦ p2 = q2 ◦ f2 ◦ p2 .

Hence, by the universal property of the pushout, there exists a unique morphism h : P → Q satisfying f1

h = q1 ◦ f1 ◦ p1 = q2 ◦ f2 ◦ p2 . Consequently, (p1 , q1 ) : (P → − Q) → (x1 −→ y1 ) and (p2 , q2 ) : (P → − Q) → f2

(x2 −→ y2 ) are morphisms in D▷◁ whose composites with (u1 , v1 ) and (u2 , v2 ) coincide. g

To verify the universal property, let (ai , bi ) : (z → − w) → (xi − → yi ), i = 1, 2, be morphisms in D▷◁ whose composites with (u1 , v1 ) and (u2 , v2 ) agree. Then u1 ◦ a1 = u2 ◦ a2 and b1 ◦ v1 = b2 ◦ v2 . By the universal property of the pullback, there exists a unique morphism a : z → P such that pi ◦ a = ai , i = 1, 2.

Similarly, by the universal property of the pushout, there exists a unique morphism b : Q → w such that b ◦ qi = bi , i = 1, 2. Moreover, g

b ◦ h ◦ a = b ◦ qi ◦ fi ◦ pi ◦ a = bi ◦ fi ◦ ai = g,

so (a, b) : (z → − w) → (P → − Q) is a morphism in D▷◁ . Its uniqueness follows from the uniqueness of a h

and b. Therefore, (P → − Q), together with the morphisms (p1 , q1 ) and (p2 , q2 ), is the pullback of (u1 , v1 ) and (u2 , v2 ) in D▷◁ . □

We can now define T-sheaves on D▷◁ as follows. Proposition 3.2 (T-sheaves on D▷◁ ) Let T be any time category equipped with the Johnstone coverage. Suppose that D has limits and colimits (and therefore D▷◁ has limits). Then a D▷◁ -valued sheaf is a presheaf X : Top → D▷◁ such that: for any interval [a, b] and any cover ([a, p], [p, b]) of this interval, X([a, b]) is the pullback X([a, p]) ×X([p,p]) X([p, b]). Proof Since the Johnstone coverage is generated by binary covers, the sheaf condition requires precisely the existence of the corresponding pullbacks in D▷◁ . By Lemma 3.1, D▷◁ has these pullbacks whenever D has pullbacks and pushouts. The result therefore follows directly from the definition of a sheaf. □ Definition 5 We denote by Nar(T, D▷◁ ) the category of D▷◁ -valued sheaves on T and we call it the category of D▷◁ -narratives with T-time. γb

a A narrative X ∈ Nar(T, D▷◁ ) assigns to every interval [a, b] a morphism Xab = (Pab − → Cab ) in b b D. The objects Pa form its persistent component, the objects Ca form its cumulative component, and the morphisms γba compare these two descriptions. Figure 2 illustrates this structure on the category IN /[0, 2], whose objects are the intervals contained in [0, 2] ⊆ N.

Remark 3 The comparison morphisms γba need not be isomorphisms, even when a = b. Thus the persistent and cumulative descriptions of the same interval generally contain different kinds of information. For example, in Set or Grph, one may interpret γtt : Ptt → Ctt as an attribute map assigning to each element or vertex of Ptt a color, label, weight, community, role, or other feature in Ctt . In this case, Ptt represents the collection of objects and Ctt represents the collection of possible attributes, with γtt recording the assignment of attributes to objects. The sheaf structure then encodes how both the objects and their attributes relate across overlapping intervals of time: restrictions on the persistent side track how objects change through time, while restrictions on the cumulative side track the compatibility and evolution of their attributes. The sheaf condition ensures that local descriptions on overlapping intervals can be uniquely assembled into a coherent global account of both the objects and their attributes.

We have constructed the category Nar(T, D▷◁ ), whose objects simultaneously encode both the persistent and cumulative descriptions of a temporal object together with the comparison between them. As illustrated in Figure 2, the persistent and cumulative components may each arise either from prescribed data (see Remark 3) or from their respective universal constructions. These independent possibilities will later give rise to the classification of narratives by rigidity (Section 3.1.3). 12

P02 ⌟

P01

P12

P00

P11

γ00

γ11

γ10

γ20

γ22

γ21

C22

C01

C12 ⌟

⌟

C11 ⌟

C00

P22

C02 Fig. 2: A D-narrative on the category IN /[0, 2], whose objects are the intervals contained in [0, 2] ⊆ N. The upper diagram is its persistent component, the lower diagram is its cumulative component, and the dashed morphisms γba : Pab → Cab compare the two. In the case shown, the persistent data P00 ← P01 → P11 ← P12 → P22 , is prescribed data, while P02 is determined by a pullback. On the cumulative side, C01 ,C12 , and C02 are determined by pushouts.

3.1.2 Factorizing the persistence–accumulation adjunction Having constructed the category of narratives, we now show that it naturally sits between persistent and cumulative narratives by factorizing the persistence–accumulation adjunction. Theorem 3.3 The adjunction K ⊣ P factorizes through the category Nar(T, D▷◁ ) via the functors P ▷◁ and K ▷◁ . That is, both the outer and inner triangles in the following diagram commute: K

Cu(T, D)

⊣

Pe(T, D)

P P ▷◁

dom▷◁ K ▷◁

cod▷◁

Nar(T, D▷◁ ) Equivalently,

cod▷◁ ◦ K ▷◁ = K ,

dom▷◁ ◦ P ▷◁ = P .

Moreover,

dom▷◁ ◦ K ▷◁ = idPe(T,D) ,

cod▷◁ ◦ P ▷◁ = idCu(T,D) .

The forgetful functors recover the persistent and cumulative components of a narrative by forgetting one side of the comparison morphism: dom▷◁ : Nar(T, D▷◁ ) −→ Pe(T, D),

cod▷◁ : Nar(T, D▷◁ ) −→ Cu(T, D) .

Conversely, the functors P ▷◁ : Cu(T, D) −→ Nar(T, D▷◁ ),

K ▷◁ : Pe(T, D) −→ Nar(T, D▷◁ ),

canonically complete persistent and cumulative narratives into D▷◁ -valued narratives by adjoining their cumulative and persistent counterparts, respectively. We now construct each of these four functors. Once these constructions are in place, the proof of Theorem 3.3 will follow by verifying that the four triangles commute by construction. The forgetful functors. We first construct the functors dom▷◁ : Nar(T, D▷◁ ) −→ Pe(T, D),

cod▷◁ : Nar(T, D▷◁ ) −→ Cu(T, D) .

These arise from the canonical domain and codomain projections of the cotwisted arrow category, dom cod D ←−−− D▷◁ −−→ Dop , f

where dom sends an arrow x → − y to its domain x, while cod sends it to its codomain y. On a f

f′

morphism (u, v) : (x → − y) → (x′ − → y′ ) in D▷◁ , they are given by x u

x′

dom

x′ f′

cod

y′

Thus dom is covariant, whereas cod is naturally viewed as taking values in Dop . Proposition 3.4 Composition with dom and cod defines functors dom▷◁ : Nar(T, D▷◁ ) −→ Pe(T, D),

given on objects by

cod▷◁ : Nar(T, D▷◁ ) −→ Cu(T, D)

dom▷◁ (X) = dom ◦X,

cod▷◁ (X) = cod ◦X.

Proof Let X : Top → D▷◁ be a narrative. For each interval [a, b], write γba Xab = Pab − → Cab . We define dom▷◁ (X) on objects by [a, b] 7→ Pab and cod▷◁ (X) by [a, b] 7→ Cab . Given a morphism i : [a, b] ,→ [c, d], if X(i) = (pi , ci ), we put dom▷◁ (X)(i) = pi and cod▷◁ (X)(i) = ci . Since composition in D▷◁ is defined componentwise, both assignments preserve identities and composition. Furthermore, because X is a sheaf valued in D▷◁ , applying dom to each pullback diagram recovers the sheaf condition defining persistent narratives, while applying cod recovers the corresponding pushout condition defining cumulative narratives. Thus, dom▷◁ (X) ∈ Pe(T, D) and cod▷◁ (X) ∈ Cu(T, D). Finally, a morphism of narratives is a natural transformation in D▷◁ , and composing it componentwise with dom or cod yields natural transformations between the corresponding persistent or cumulative narratives. Therefore, dom▷◁ and cod▷◁ define functors. □

The cumulative completion. Having constructed the forgetful functors, we now turn to the opposite direction. Our next goal is to show that every persistent narrative admits a canonical cumulative completion into a D▷◁ -valued narrative. Proposition 3.5 (Cumulative completion of a persistent narrative) There is a functor K ▷◁ : Pe(T, D) → Nar(T, D▷◁ )

that sends a persistent narrative F : Top → D to the narrative K ▷◁ F : Top → D▷◁ .

defined as follows. Given an interval [a, b] ∈ T, K ▷◁ F maps it to the object αb

a Fab −→ K Fab

of D▷◁ , where αba is the canonical cocone map into the colimit defining K Fab . Given an inclusion i : [a, b] ,→ [c, d], K ▷◁ F maps it to the morphism in D▷◁ F(i) K F(i) Fcd −−→ Fab , K Fab −−−−→ K Fcd , which satisfies the cotwisted commutativity condition: F(i)

Fcd

Fab αba

αdc

K Fab K F(i)

. Equivalently,

K Fcd

αdc = K F(i) ◦ αba ◦ F(i).

Proof For each interval [a, b], the object K Fab is defined by the colimit in Equation (1), and αba : Fab −→ K Fab

is the corresponding canonical cocone map. If i : [a, b] ,→ [c, d] ∈ T, then F(i) : Fcd → Fab is induced by the functoriality of F ∈ Pe(T, D). Moreover, i induces a restriction of the canonical cocone defining K Fcd to a cocone on the diagram defining K Fab . By the universal property of the colimit K Fab , there is a unique morphism K F(i) : K Fab −→ K Fcd such that

Hence,

αdc = K F(i) ◦ αba ◦ F(i). αdc αba F(i), K F(i) : Fcd −→ K Fcd −→ Fab −→ K Fab

is a morphism in D▷◁ . Functoriality of K ▷◁ F : Top → D▷◁ follows immediately from the functoriality of F, of K F, and from the uniqueness of the induced maps between the corresponding colimits. It remains to show that K ▷◁ F is a sheaf. Let [a, b] ∈ T, and consider the cover ([a, p], [p, b]). We must show that K ▷◁ Fab is the following pullback in D▷◁ .

(F( f ),K F( f )) p

K ▷◁ Fa

K ▷◁ Fab

K ▷◁ Fpb

(F(h),K F(h))

(F(g),K F(g))

(F(k),K F(k))

K ▷◁ Fp

p p This square is well defined in D▷◁ . Indeed, F is a persistent sheaf, so Fab is the pullback of Fa → Fp ← p p b b b Fp , whereas K F is a cumulative narrative, so K Fa is the pushout of K Fa ← K Fp → K Fp . Let u p u : x → y be an arbitrary object of D▷◁ , together with compatible morphisms (pl , cl ) : (x → − y) → K ▷◁ Fa u ▷ b and (pr , cr ) : (x → − y) → K ◁ Fp , as in the following diagram. (pl ,cl ) p

K ▷◁ Fa

(pr ,cr )

K ▷◁ Fpb

(F(h),K F(h))

K ▷◁ Fp

Equivalently, the following diagram in D commutes.

(F(k),K F(k))

x pr =

Fab ⌟

F( f ) p

F(g)

Fpb

= F(h)

F(k)

Fp u

αap

α pp

αbp

p K Fp K F(g)

K F( f ) p

K Fa

⌟

K F(h)

K Fpb

K Fab

K F(k)

= cr

y Since the upper square is a pullback, there is a unique morphism p : x → Fab such that F( f ) ◦ p = pl and F(g)◦ p = pr . Likewise, since the lower square is a pushout, there is a unique morphism c : K Fab → y such that c ◦ K F(h) = cl and c ◦ K F(k) = cr . Moreover, the commutativity of the outer diagrams αb

a implies that u = c ◦ αba ◦ p, so (p, c) : (x → − y) → (Fab −→ K Fab ) is a morphism in D▷◁ . Since p and c are uniquely determined by the pullback and pushout universal properties, respectively, (p, c) is the unique morphism making the required diagrams commute. Therefore, K ▷◁ Fab satisfies the universal property of the pullback in D▷◁ , and hence, K ▷◁ F is a sheaf. □

The persistent completion. Dually, every cumulative narrative admits a canonical persistent completion into a D▷◁ -valued narrative. Proposition 3.6 (Persistent completion of a cumulative narrative) There is a functor P ▷◁ : Cu(T, D) → Nar(T, D▷◁ )

that assigns to each cumulative narrative F̂ ∈ Cu(T, D) the D▷◁ -valued narrative P ▷◁ F̂ defined as follows. • On objects [a, b] ∈ T, the sheaf P ▷◁ F̂ assigns the morphism βb

a P F̂ab −→ F̂ab ,

viewed as an object in the cotwisted arrow category D▷◁ . The morphism βba is the limit cone morphism from P F̂ab to the object F̂ab .

• On morphisms [a, b] ,− → [c, d] in T, the sheaf P ▷◁ F̂ assigns the morphism in D▷◁ P F̂(i)

F̂(i)

(P F̂cd −−−−→ P F̂ab , F̂ab −−→ F̂cd ),

which satisfies the cotwisted commutativity condition

P F̂cd

P F̂(i)

P F̂ab βba

βdc

F̂ab F̂(i)

. Explicitly,

F̂cd

βdc = F̂(i) ◦ βba ◦ P F̂(i).

Proof The construction is the categorical dual of Proposition 3.5. For each interval [a, b], the object P F̂ab is defined by the limit in Equation (2), with canonical cone morphism βba : P F̂ab → F̂ab . Given an inclusion i : [a, b] ,→ [c, d], the universal property of the limit induces a unique morphism P F̂(i) : P F̂cd → P F̂ab satisfying βdc = F̂(i) ◦ βba ◦ P F̂(i). Hence (P F̂(i), F̂(i)) is a morphism in D▷◁ , and these assignments define the functor P ▷◁ F̂. To verify the sheaf axiom, let ([a, p], [p, b]) be a cover of [a, b]. Given an arbitrary object u : x → y p of D▷◁ together with compatible morphisms to P ▷◁ F̂a and P ▷◁ F̂pb , since F̂ is a cumulative narrative, p p b b F̂a is the pushout of F̂a ← F̂p → F̂p , while P F̂ is a persistent narrative, so P F̂ab is the pullback p p of P F̂a → P F̂p ← P F̂pb . The universal properties of the pushout F̂ab and the pullback P F̂ab yield unique morphisms p : x → P F̂ab and c : F̂ab → y, which satisfy the cotwisted compatibility condition and therefore determine the unique morphism (p, c) in D▷◁ . The verification of this compatibility is exactly dual to that in Proposition 3.5, and is therefore omitted. □ Proof of Theorem 3.3 The functors involved are well defined by Proposition 3.4, Proposition 3.5, and Proposition 3.6. It remains to verify the identities cod▷◁ ◦ K ▷◁ = K ,

dom▷◁ ◦ P ▷◁ = P,

dom▷◁ ◦ K ▷◁ = idPe(T,D) ,

αb

cod▷◁ ◦ P ▷◁ = idCu(T,D) .

a For F ∈ Pe(T, D), we have K ▷◁ Fab = (Fab −→ K Fab ) and, for every inclusion i : [a, b] ,→ [c, d], K ▷◁ F(i) = F(i), K F(i) . Hence,

cod▷◁ (K ▷◁ F) = K F, so cod▷◁ ◦ K ▷◁ = K and dom▷◁ ◦ K ▷◁ = idPe(T,D) .

dom▷◁ (K ▷◁ F) = F, βb

▷ b b a b Similarly, for F̂ ∈ Cu(T, D), we have P ◁ F̂a = (P F̂a −→ F̂a ) and, for every inclusion i : [a, b] ,→ ▷ [c, d], P ◁ F̂(i) = P F̂(i), F̂(i) . Hence,

dom▷◁ (P ▷◁ F̂) = P F̂, so dom▷◁ ◦ P ▷◁ = P and cod▷◁ ◦ P ▷◁ = idCu(T,D) .

cod▷◁ (P ▷◁ F̂) = F̂, □

3.1.3 Classifying narratives by rigidity Since X ∈ Nar(T, D▷◁ ) is valued in the cotwisted arrow category, it canonically determines, for every interval [a, b], a comparison morphism γba : Pab −→ Cab , where Xab =

b b γa b Pa − → Ca .

Applying the completion functors to the persistent and cumulative components of X produces the narratives and P ▷◁ (cod▷◁ (X)). K ▷◁ (dom▷◁ (X)) By construction of the functors K ▷◁ and P ▷◁ , the structure morphism of K ▷◁ (dom▷◁ (X)) at an interval [a, b] is the component b ηdom▷◁ (X) a : dom▷◁ (X)ba −→ (P K dom▷◁ (X))ba of the unit of the adjunction, while the structure morphism of P ▷◁ (cod▷◁ (X)) is the component b εcod▷◁ (X) a : (K P cod▷◁ (X))ba −→ cod▷◁ (X)ba of the counit. These assemble into natural transformations ηdom▷◁ (X) : dom▷◁ (X) =⇒ P K (dom▷◁ (X)) and

εcod▷◁ (X) : K P (cod▷◁ (X)) =⇒ cod▷◁ (X), which we call the canonical comparison morphisms associated to the narrative X. These comparison morphisms measure how closely the persistent and cumulative descriptions encoded by a narrative agree with the canonical ones determined by the persistence–accumulation adjunction. This observation motivates the following rigidity classification of narratives. Definition 6 (Left rigid narrative) A narrative X ∈ Nar(T, D▷◁ ) is called left rigid if the comparison morphism ηdom▷ (X) : dom▷◁ (X) −→ P K (dom▷◁ (X)) is an isomorphism.

◁

Equivalently, the persistent component of X is completely recovered after passing to its canonical cumulative completion and back. Example 4 (Spans of monomorphisms in adhesive categories) Assume that the ambient category D is adhesive, and let X ∈ Nar(T, D▷◁ ) be a narrative whose persistent component dom▷◁ (X)00 ← − dom▷◁ (X)10 → − dom▷◁ (X)11

consists of monomorphisms. Since pushouts along monomorphisms are Van Kampen [19], the associated pushout square is also a pullback. Hence, P K (dom▷◁ (X)) ∼ = dom▷◁ (X), and therefore, X is left rigid. This class of examples is particularly relevant in double-pushout graph rewriting, where rewriting rules are represented by spans of monomorphisms in adhesive categories [19, 20]. Consequently, for this broad class of graph transformations, the passage from persistent to cumulative descriptions and back preserves the original persistent description. Remark 4 It is worth emphasizing that the converse need not hold. Although adhesive categories guarantee that spans of monomorphisms are preserved by the pushout–pullback composite, they do not in general imply that cospans are preserved by the pullback–pushout composite. Thus, even in adhesive categories, left rigidity does not automatically imply right rigidity. Definition 7 (Right rigid narrative) A narrative X ∈ Nar(T, D▷◁ ) is called right rigid if the comparison morphism εcod▷ (X) : K P(cod▷◁ (X)) −→ cod▷◁ (X) is an isomorphism.

◁

Equivalently, the cumulative component of X is completely recovered after passing to its canonical persistent completion and back. Example 5 (A right rigid narrative) Consider the narrative X given by: {0, 1}

pℓ

{a}

{b} cℓ

{∗}. Applying P to the cumulative component cod▷◁ (X) computes the pullback {a} ×{∗} {b} ∼ = {(a, b)}. π

ℓ r Applying K to the persistent narrative {a} ←− {(a, b)} −→ {b} = P(cod▷◁ (X)) computes its pushout, which is again the singleton {∗}. Therefore, the counit εcod▷ (X) : K P(cod▷◁ (X)) −→ cod▷◁ (X) is an ◁ isomorphism. Hence, X is right rigid. Moreover, X is not left rigid. Indeed, P K (dom▷◁ (X)) has apex {(a, b)}, while dom▷◁ (X) has apex {0, 1}. Hence the unit ηdom▷ (X) : dom▷◁ (X) −→ P K (dom▷◁ (X)) is ◁ not an isomorphism.

Definition 8 (Rigid and loose narratives) A narrative is called • rigid if it is both left rigid and right rigid; • loose if it is neither left rigid nor right rigid. Example 6 (Rigid narratives) The simplest examples of rigid narratives are the constant ones. Let d ∈ D. id

d The constant narrative is the D▷◁ -valued sheaf X defined by Xab = (d −−→ d) for every interval [a, b] ∈ T,

with every restriction morphism equal to (idd , idd ). Since both the persistent and cumulative components are constant, one has dom▷◁ (X) = P(cod▷◁ (X))

and

cod▷◁ (X) = K (dom▷◁ (X)).

Hence X is rigid. More generally, the same conclusion holds whenever the morphisms of the narrative are isomorphisms. Indeed, replacing the identities above by arbitrary isomorphisms does not change either the pullback or pushout constructions up to canonical isomorphism, so both comparison morphisms remain isomorphisms. Consider, for instance: {(a, b)}

πℓ

πr

{a}

{b} cℓ

{∗}. π

ℓ r ℓ r The persistent component {a} ←− {(a, b)} −→ {b} is already the pullback of the cospan {a} − → {∗} ← − {b}, while the pushout of this pullback is again the singleton {∗}.

Example 7 (Loose narratives) Loose narratives already appear in very simple categories. Consider the poset category (N, ≤), whose objects are natural numbers and in which there exists a unique morphism m → n precisely when m ≤ n. In this category, pullbacks are given by meets m × p n = min{m, n}, while pushouts are given by joins m + p n = max{m, n}. Consider the narrative 0 1

2 3

Its domain is the span dom▷◁ (X) = (1 ← 0 → 2), and applying the completion functors yields K (dom▷◁ (X)) = (1 → 2 ← 2) and P K (dom▷◁ (X)) = (1 ← 1 → 2), which is not isomorphic to dom▷◁ (X). Thus, X is not left rigid. Likewise, its codomain is the cospan cod▷◁ (X) = (1 → 3 ← 2), and applying the completion functors gives P(cod▷◁ (X)) = (1 ← 1 → 2) and K P(cod▷◁ (X)) = (1 → 2 ← 2), which is not isomorphic to cod▷◁ (X). Hence, X is not right rigid, and therefore it is loose.

The central question explored in this vignette is when persistent and cumulative descriptions determine one another exactly. Investigating the fixed points of the persistence– accumulation adjunction naturally leads to the category of narratives, which simultaneously records both descriptions together with the comparison between them. This approach provides a specialized framework for systematically investigating the conditions—relating to data category and temporal data assignments—under which information is preserved as one transitions between persistent and cumulative representations.

3.2 Vignette 2: Decomposing Time-Varying Data into Simple Pieces: Structured Decompositions of Narratives Complex data, whether static or time-varying, is often easier to understand and analyze when it is represented as a composite of smaller or simpler pieces. Thus, in this section, we ask: how does one decompose complicated time-varying data into simpler pieces in a systematic way? A decomposition serves two roles: (1) it divides an object into component pieces, and (2) it records how these pieces overlap, so that the original object may be reconstructed by gluing them together. Thinking about this with a more topological slant, there is a sense in which this section is about seeking simple coverings of a temporal object by small, time-varying pieces, analogous to open sets, whose evolution and mutual compatibility are themselves tracked through time. Our goal is to obtain an invariant of the structural complexity of a time-varying object by measuring the complexity of the pieces in its decompositions and their overlaps. These pieces must themselves form time-varying objects, with structure maps recording how they persist, merge, split, or disappear. It is not enough to decompose each snapshot independently: the pieces of the decomposition must also capture the evolution of the global structure. We seek a method that reuses theories of decomposition for static data instead of defining a new notion for each temporal setting. This section is based on the recent paper by Bumpus and Nickel [16] whose main result provides such a method by lifting theories of decompositions from static objects to persistent narratives.

3.2.1 Structured decompositions In this section, we use narratives to construct a temporalized theory of structured decompositions, which were introduced in [21] and provide a category theoretical generalization of tree-decompositions. The goal of our approach is to split time-varying data systematically into smaller components, providing a formal framework for dealing with temporal systems. This is an instance of the broader principle of compositionality, which states that the meaning or behaviour of a complex system is completely determined by the meanings or behaviours of its constituent parts and the rules governing their connections. Breaking complicated data into simpler pieces has already proved useful in many areas of mathematics and computer science, particularly in graph theory, logic, algorithms, and complexity theory. Prominent examples include Robertson and Seymour’s graph structure theorem [22] and Courcelle’s theorem [23]. Here, a graph G means a diagram from the category V ⇒ E to the category Set of sets. Thus, a graph in this sense is the same as a quiver in representation theory and as a copresheaf on V ⇒ E in category theory. In particular, our graphs are directed and are allowed to possess loops and multiple edges. Given a graph G, we denote the set of its vertices by V (G) := G(V ) and the set of its edges by E(G) := G(E). We write Grph for the wide subcategory of the functor category [V ⇒ E, Set] whose objects are the graphs. Its morphisms are simply natural transformations between graphs, also called graph morphisms. Tree-decompositions. Originally introduced by Halin in 1976 [24], the notion of a tree-decomposition (see Definition 9) was rediscovered in 1984 by Robertson and Seymour [25] and has since played 22

an essential role in structural and extremal graph theory, as well as in various other areas of mathematics and computer science. For instance, tree-decompositions have proved to be a convenient tool in matrix decomposition [26], query optimization [27], and dynamic programming [28]. They are also frequently used to solve constraint satisfaction problems [29] and in junction tree algorithms for probabilistic inference [30]. Robertson and Seymour themselves used tree-decompositions as a crucial component of their celebrated graph structure theorem [22], which establishes a profound connection between graph minor theory and the theory of topological embeddings. Its significance is further illustrated by applications to the disjoint paths problem [31], Sachs’ linkless embedding conjecture [32], and Courcelle’s theorem [23]. Moreover, tree-decompositions have proved very useful for investigating compositional structures. They serve as an efficient topological tool for tackling algorithmic graph problems and have been used to improve the efficiency of dynamic programming. For example, with the aid of tree-decompositions, several algorithmic problems that are NP-hard on arbitrary graphs may be solved efficiently by dynamic programming on graphs of bounded tree-width. A concrete example is the problem of finding a maximum independent set in graphs of bounded tree-width. To acknowledge the benefit of structured decompositions (see Definition 12) we make the notion of ordinary tree-decompositions precise. Definition 9 A tree-decomposition of a graph G is a pair (T, (Vt )t∈Ob(T ) ) consisting of a tree T and a family of vertex sets Vt ⊆ V (G) indexed by the vertices t of T and satisfying the following two conditions: (T1) G =

t∈Ob(T ) G[Vt ] where G[Vt ] denotes the subgraph of G induced by Vt .

(T2) For each vertex v of G, the induced subgraph Tv := T [{t ∈ T | v ∈ Vt }] ⊆ T is connected.

We call T the decomposition tree or the model of the decomposition. The subsets Vt ⊆ V (G) are called the bags, and the induced subgraphs G[Vt ] ⊆ G are the corresponding parts.

Intuitively, a tree-decomposition reveals the global structure of a graph whenever that structure is tree-like. An example of a tree-decomposition is shown in Figure 3.

Fig. 3: A tree-decomposition of a graph (on the left-hand side) and its decomposition tree (on the right-hand side).

Tree-width. Tree-decompositions also provide a convenient tool for constructively computing the treewidth of a graph, as explained below. Originally introduced by Bertelè and Brioschi, the notion of tree-width has become indispensable in mathematics and computer science. For instance, [33] provides a revealing overview of major applications of tree-width and more general notions of graph width that have been developed from the classical tree-width parameter to capture a broader range of contexts. The tree-width of a graph G measures the extent to which the structure of G resembles that of a tree. Indeed, the tree-like structure of the graph is reflected in the parts of its decomposition: the smaller these parts are, the more tree-like G is. Definition 10 The width of a tree-decomposition (T, (Vt )t∈Ob(T ) ) is the maximum order of its bags minus one, maxt∈V (T ) |Vt | − 1. The tree-width tw(G) of a graph G is the minimum width of its treedecompositions, tw(G) := min max |Vt | − 1 (T,(Vt )t∈Ob(T ) ) t∈V (T )

where the minimum is taken over all tree-decompositions of G.

The reason for the “minus one” in the definition of the width of a tree-decomposition is to ensure that the tree-width of any tree is one, as expected from a reasonable measure of structural tree-likeness. Category theoretical generalization. To provide a general category-theoretical framework for tree-decompositions and extend their scope of application, the notion of structured decompositions and, more specifically, spined structured decomposition categories (or simply spined sd-categories) was introduced in [21]. These provide a unified axiomatic setting for studying tree-width and its generalizations. The framework recovers several notions of graph width, including ordinary tree-width, complemented tree-width, tree independence number, hypergraph tree-width, and layered tree-width. Thus, spined sd-categories capture the classical notion of tree-width together with many of its variants. We define them explicitly in Definition 12.

3.2.2 Temporalization of spined sd-categories Need for temporalization. Structured decompositions are concerned only with static graphs, meaning graphs in the traditional sense, consisting merely of a set of vertices together with a set of edges connecting them. When applying the existing concepts and results to time-varying data, however, this conventional notion of a graph is no longer sufficient. Many systems of interest evolve over time, and traditional graph-theoretical techniques ignore this temporal dimension. To capture such evolution, a variety of notions of temporal graphs have been introduced. These differ in how they represent temporal information and the evolution of the underlying graph. For an overview of the diversity of existing approaches, we refer to [34–39].

Motivated by the increasing use of temporal graphs to model time-dependent data, we develop a notion of spined sd-categories for time-varying graphs and, more generally, timevarying structures. This is the main objective of the remainder of this section, which is based on [16]. Combining spined sd-categories and narratives. To temporalize spined sd-categories, we reinterpret the theory of structured decompositions developed in [21] within the framework of persistent and cumulative narratives developed in [15]. This yields a time-dependent generalization of spined sd-categories. Structured decompositions. Definition 11 Let J be a graph. Its barycentric subdivision is the category J obtained from J by replacing each vertex with an object and each edge e, with endpoints v and w, by an object e together ev ew with morphisms ev : e → v and ew : e → w, that is, a span v ← − e −→ w. R

Example 8 The barycentric subdivision of the triangle K 3 depicted on the left is the category visualized on the right. v a

a b

cu av

cw bv

b bw

Definition 12 Let J be a graph, and let D be a category. A J-structured decomposition in D is a functor R R of shape d : J → D with the property that for every morphism k : x → y in J, its image d(k) : d(x) → d(y) under d is a monomorphism in D.

Relevance of structured decompositions and schematic visualizations. We illustrate the breadth of structured decompositions by discussing four examples from different mathematical domains, accompanied by schematic visualizations. (1) Tree-decompositions. As already mentioned, the development of structured decompositions was originally inspired by tree-decompositions in graph theory, making them perhaps the most prominent example. These combinatorial objects can be described as tree-shaped structured decompositions with values in the category Grph of graphs, that R is, functors of the form T → Grph for some tree T . Replacing T with an arbitrary graph leads to the more general notion of a graph-decomposition, studied, for example, in [40, 41]. The notion of graph-decompositions moreover gives rise to a wide variety of combinatorial width parameters measuring the structural resemblance of a graph to a given graph model, such as a tree, a path, or a cycle. Examples include the classical tree-width together with many of its variants, as discussed in [21, Chapter 3].

Fig. 4: The cycle C5 , the category C5 and a C5 -shaped structured decomposition of graphs. R

Figure 4 shows a structured decomposition in the category Grph of graphs shaped by the cycle C5 of length five, together with the Rcycle itself and its barycentric subdiviR 5 sion C . The functor d sends each object xi of C5 corresponding to a vertex xi of the graph C5 to a complete graph. (2) Hybrid dynamical systems. In his thesis [42], Ames establishes a category-theoretical framework for the study of hybrid dynamical systems, that is, dynamical systems with both continuous and discrete components. The thesis introduces the notion of a hybrid object in a category C, defined as a functor from a so-called D-category to C, which may be viewed as a special case of a structured decomposition. To illustrate this concept, consider a structured decomposition in the category Man of topological manifolds and continuous maps, shaped by the path P3 of length three, as shown in Figure 5. We observe that the map d( f1 ) : S1 → Σ1 , from the topological unit circle S1 to the torus Σ1 (the closed orientable surface of genus one), is homotopic to a constant map. Likewise, the map d( f2 ) : S1 → Σ2 , where Σ2 denotes the closed orientable d(g3 )

surface of genus two, is homotopic to the composite S1 −−−→ Σ1 ,→ Σ2 . (3) Graphs of groups. The fundamental objects of Bass–Serre theory, namely graphs of groups, are precisely structured decompositions valued in the category of groups and group homomorphisms [43–45]. Restricting to structured decompositions shaped by trees recovers the setting of Bass–Serre theory, in which such decompositions correspond to well-behaved group actions on trees. As an example, we consider the fundamental groups of the manifolds in the image of R the functor d : P3 → Man from the previous example, thereby obtaining a P3 -shaped structured decomposition in the category Grp of groups, shown in Figure 6. More precisely, this is the composition of the previous structured decomposition in Man with the fundamental group functor π1 : Man → Grp. In the upper part of the figure, we illustrate closed curves in S1 , Σ1 , and Σ2 generating the corresponding fundamental groups, while the lower part visualizes the resulting structured decomposition of fundamental groups.

Fig. 5: The path P3 , the category P3 and a P3 -shaped structured decomposition of manifolds. R

Fig. 6: A P3 -shaped structured decomposition of groups (lower part), obtained by computing the fundamental groups of the manifolds in Figure 5 with the chosen generators (upper part). As expected, the homotopic maps d( f1 ) ≃ const : S1 → Σ1 induce the same group homomorphism π1 (S1 ) → π1 (Σ1 ), namely the trivial homomorphism. Likewise, the homotopic maps d( f2 ) ≃ incl ◦ d(g3 ) : S1 → Σ2 induce the same homomorphism π1 (S1 ) → π1 (Σ2 ), namely x 7→ a1 . (4) Cellular sheaves. Cellular sheaves encode local-to-global interactions in systems built from graphs, simplicial complexes, and cell complexes [46]. Later in this chapter, we use them to model multi-agent systems with time-varying communication topologies, illustrating an application of narratives to control theory developed in [47]. From the perspective developed here, cellular sheaves arise naturally as the dual notion to structured decompositions: they are structured co-decompositions valued in the category Vect of real vector spaces and linear maps. We nevertheless retain the terminology of cellular sheaf theory in order to align with the existing literature on control theory and multi-agent systems.

Spined sd-categories. Definition 13 Let D be a category, and let G be a class of graphs including the trivial graph with exactly one vertex and no edge. The pair (D, G ) is said to beRa structured decomposition category, or simply, an sd-category, iff every structured decomposition d : J → D in D with J ∈ G admits a colimit. We call G the index class of (D, G ). Definition 14 A spine on a category D is a family Ω = (Ωn )n≥0 of increasing subcategories Ω0 ⊆ Ω1 ⊆ Ω2 ⊆ . . . with the following additional properties: S S • The union Ω := n≥0 Ωn is closed under isomorphic objects in D, and for any n ≥ 0, Ωn is S closed under isomorphic objects as a subcategory of Ω. • For every object X ∈ Ob(D), there exists an object W ∈ Ob(Ωn ) for some integer n ≥ 0 together with a monomorphism W ↣ X in D. e of Ωn−1 along with a monomorphism W ↣ W e • Given an integer n ≥ 1 and objects W of Ωn and W in D, then W is already contained in Ωn−1 . A spined sd-category is a triple (D, G , Ω) where (D, G ) is an sd-category and Ω is a spine on D.

Combining persistent narratives and spined sd-categories. We begin with the persistent perspective; the cumulative perspective and the relation between the two are discussed in Section 4. Let T be a finite discrete time category, let S ⊆ T be a subjoin-semilattice, and let τ : S ,→ T denote the inclusion functor. Furthermore, let (D, G , Ω) be a spined sd-category satisfying the following additional condition. (T1) The category D and its subcategories Ωn ⊆ D admit all pullbacks, the inclusion functors ιn : Ωn ,→ D preserve pullbacks, and each Ωn is full in D. In particular, post-composition with ιn provides a well-defined functor Pe(T, ιn ) : Pe(T, Ωn ) → Pe(T, D), which we call the covariant change-of-base functor. Similarly, we have a change-oftemporal-resolution functor defined by pre-composition with the opposite τop : Sop ,→ Top of τ: Pe(τ, D) : Pe(T, D) → Pe(S, D). The same holds when replacing the category T by S and D by Ωn , for n ≥ 0. For each n ≥ 0, we consider the following pullback square of categories and functors: Pe(T, D) ×Pe(S,D) Pe(S, Ωn ) πn

Pe(T, D)

Pe(S, Ωn ) Pe(S,ιn )

Pe(τ,D)

Pe(S, D).

b n to be the image of the pullback category under πn , so this is the subcategory We define Ω b n := πn (Pe(T, D) ×Pe(S,D) Pe(S, Ωn )) ⊆ Pe(T, D) . Ω 28

b n is the full subcategory of Pe(T, D) whose objects are those Lemma 3.7 For every integer n ≥ 0, Ω persistent narratives F : Top → D whose value F([a, b]) at any time interval [a, b] in S is contained in Ωn . Theorem 3.8 Let again T be a finite discrete time category, let τ : S ,→ T be the inclusion of a subjoin-semilattice S ⊆ T, and let (D, G , Ω) be a spined sd-category satisfying (T1). Furthermore, suppose that the following conditions hold. (T2) The category D is cocomplete, that is, it admits all small colimits. (T3) The inclusion functor Pe(T, D) ,→ [Top , D] admits a left adjoint S : [Top , D] → Pe(T, D) whose restriction to Pe(T, D) is the identity functor. Then the pair (Pe(T, D), G ) is an sd-category.

Since S is both a left adjoint and a retraction of the inclusion functor, it can be regarded as a sheafification functor. In Example 9, where D is the category Grph of graphs, S is induced by the usual sheafification functor for set-valued presheaves. By adding one final axiom, we arrive at the notion of a temporalized spined sd-category. Theorem 3.9 As before, let T be a finite discrete time category, and let τ : S ,→ T be the inclusion of a sub-join-semilattice S ⊆ T. Let (D, G , Ω) be a spined sd-category that satisfies the axioms (T1), (T2) and (T3) as well as (T4) The category D admits pushout squares along monomorphisms and these are also pullback squares. Moreover, monomorphisms are stable under pushouts. b n ⊆ Pe(T, D) with n ≥ 0 define a spine Ω b on Pe(T, D), thereby exhibiting the Then the subcategories Ω b sd-category (Pe(T, D), G ) of Theorem 3.8 as a spined sd-category (Pe(T, D), G , Ω).

Theorem 3.9 allows measures of complexity to be lifted from the static to the time-varying setting. A complete proof is given in [16].

3.2.3 Temporalizing tree-width: examples In ordinary graph theory, the notion of tree-width is typically defined by means of treedecompositions, as explained in Paragraph 3.2.1. The category-theoretical framework of spined sd-categories [21] extends this concept to arbitrary structured decompositions. More precisely, given a spined sd-category Γ = (D, G , Ω), each object of D is assigned a Γ-size [21, Definition 2.5.4]. We restrict attention to spined sd-categories in which the subcategories Ωn ⊆ D are full, in which case the definition simplifies as follows. Definition 15 The Γ-size of an object X ∈ Ob(D) is the minimum non-negative integer n for which there exists an object W ∈ Ob(Ωn ) together with a monomorphism X ↣ W in D. The resulting map sΓ : Ob(D) → N0 , is called the size function of Γ.

The size function allows the notions of tree-width for tree-decompositions and graphs to be extended to width notions for structured decompositions and objects of arbitrary spined sd-categories, respectively. 29

Definition 16 The width wΓ (d) of a structured decomposition d : Γ-size of its bags d(v) minus one:

J → D with J ∈ G is the maximum

wΓ (d) := max sΓ (d(v)) − 1. v∈V (J)

Now, the Γ-width wRΓ (X) of an object X of D is defined as the minimum Γ-widths of all structured decompositions d : J → D with J ∈ G whose colimit is isomorphic to X: wΓ (X) :=

R min

d : J→D with J∈G , colim d ∼ =X

wΓ (d).

Section 3 of [21] shows that many classical graph width parameters are recovered as instances of this general notion by choosing appropriate spined sd-categories. This justifies spined sd-categories as a unified framework for generalized tree-widths. To justify the temporalization of spined sd-categories and the resulting notions of timevarying structured decompositions and Γ-width, we consider three classical graph width parameters. For each, we exhibit a spined sd-category whose temporalization via Theorem 3.9 yields a natural time-varying analogue of the corresponding width notion. Specifically, we consider ordinary tree-width (Definition 10), complemented tree-width, and the tree independence number. Example 9 (Ordinary tree-width). Proposition 3.1.1 in [21] shows that the category Grph together with the class of all trees and the full subcategories Ωn ⊆ Grph containing the complete graphs of order at least n is a spined sd-category whose associated notion of width is the ordinary tree-width of a graph. To apply our temporalization method of Theorem 3.9, we need to replace Grph by the category of reflexive graphs, meaning those graphs with precisely one loop at each vertex. Proposition 3.10 For any finite discrete time category T and any sub-join-semilattice S ⊆ T, Γ induces b whose size function takes any b := (Pe(T, Grphrefl ), {trees}, Ω), a temporalized spined sd-category Γ persistent narrative X : Top → Grphrefl to the maximum order among the graphs X(s) with s ∈ Ob(S), sΓb (X) = max |X(s)|. s∈Ob(S)

b The Γ-size of a structured decomposition d :

J → Pe(T, Grphrefl ) for any tree J can be shown to be

wΓb (d) = max wΓ (ds ) s∈Ob(S)

where ds : J → Grphrefl is obtained from d by evaluation at s ∈ Ob(S). Since wΓ is the ordinary tree-width of a graph, we thus recover maximum tree-width, which is a well-known generalization of tree-width for temporal graphs. R

Example 10 (Complemented tree-width). The complemented tree-width of a graph G is the ordinary tree-width of its complement G, the graph with the same vertex set as G and with an edge between two vertices if and only if these vertices are non-adjacent in G. Let Grph be the category whose objects are the undirected graphs and whose morphisms from G to H are graph morphisms of complements G → H. By [21, Proposition 3.3.4], Γ := (Grph, {trees}, Ω) is a spined sd-category where Ωn is the full subcategory of Grph whose objects are all edgeless graphs of order at most n. Its associated width notion is complemented tree-width.

Proposition 3.11 For any sub-join-semilattice S of a finite discrete time category T, Γ induces a b Its width notion is given by the maximum time-varying spined sd-category (Pe(T, Grph), {trees}, Ω). complemented tree-width over S.

Modifying the spine Ω on Grph appropriately will give rise to the tree independence number of a graph, discussed in the next example. Example 11 (Tree independence number). The independence number of a graph is the maximum number of pairwise non-adjacent vertices. The tree independence number of a tree decomposition is the maximum independence number of its bags minus one, and the tree independence number of a graph is the minimum one among all its tree decompositions. For any n ≥ 0, let Ωαn denote the full subcategory of Grph whose objects are the graphs of independence number α(G) ≤ n. Then by [21, Proposition 3.4.5], they define a spine Ωα on Grph making the triple (Grph, {trees}, Ωα ) to a spined sd-category, whose width notion is the tree independence number. Proposition 3.12 Given T and S as usual, the above spined sd-category induces a temporalization b α ). Its size function is given by the maximum independence number of graphs, (Pe(T, Grph), {trees}, Ω so its associated width notion recovers the maximum tree independence number over S.

3.3 Vignette 3: Temporal Cellular Sheaves: Modelling Multi-agent Systems with Switching Topologies This vignette outlines an ongoing research program developing category-theoretic and sheaftheoretic methods for control, with current applications to control barrier functions and multiagent systems [47, 48]. Building on these ideas, we focus here on multi-agent systems with switching communication topologies [47]. Such systems arise in applications ranging from robotic swarms and autonomous vehicles to sensor networks and distributed optimization, where the communication graph changes over time due to mobility, communication failures, or environmental constraints [5, 6, 49, 50]. A common approach represents the communication topology by a graph whose vertices correspond to agents and whose edges represent communication links [5, 49]. This graph captures the connectivity of the network and provides the underlying structure for many distributed control algorithms. The communication graph, however, captures only who communicates with whom. The dynamics of the agents, the information they exchange, the sensing mechanisms, and the transformations performed along communication links must be modeled separately. Because these additional structures are usually introduced in an application-specific manner, it is difficult to develop a unified mathematical framework encompassing heterogeneous multi-agent systems.

3.3.1 Cellular sheaves for multi-agent systems Cellular sheaves offer a mathematical model for the additional structures required in heterogeneous multi-agent systems [51, 52]. They assign (potentially different) vector spaces to agents and communication links, together with linear maps describing how information is measured, communicated, or transformed locally. This construction naturally accommodates heterogeneous state spaces, sensing mechanisms, communication protocols, and local 31

information-processing rules. In this way, the communication graph specifies who communicates with whom, while the cellular sheaf specifies what information is associated with each agent and communication link, and how that information is transformed. Categorically, a cellular sheaf is simply a functor

G : inc(G) −→ Vect, where inc(G) denotes the incidence category of the communication (directed) graph G. Its objects are the faces of G (vertices and edges), and its morphisms are precisely the incidence he t → e. Figure 7 illustrates −e e and v − relations: for every edge e = (u, v), there are morphisms u → this construction.

G(inc(G)) G j e1 i

inc

G(he1 )

te2

he1

e2 e3

G(j)

inc(G) j e1 te1

e2 he2

he3

te3

G(te2 )

G(e1)

G(e2)

G(te1 ) G(i)

G(he2 ) G(he3 )

G(e3)

G(te3 )

G(z)

Fig. 7: From left to right: the directed communication graph G, whose vertices represent agents and whose edges e1 , e2 and e3 represent directed communication links; its incidence category inc(G), whose objects are the faces of G, namely its vertices and edges, and whose morphisms record the incidence relations; and the diagram determined by the cellular sheaf G : inc(G) → Vect. In this example, G assigns the vector space R2 to every object of inc(G), equivalently to every face of G, together with linear maps associated with the incidence morphisms. These maps encode the local sensing, communication, and information-processing relations of the network.

Remark 5 (Cellular sheaves as structured co-decompositions) Notice that cellular sheaves are instances of the structured co-decompositions considered in Section 3.2 since the incidence category inc(G) of a R op . Thus, a cellular sheaf G : inc(G) → Vect is equivalently a contravarigraph G is isomorphic to ( G) R ant functor from Ĝ : ( G)op → Vect, and hence a G-shaped structured co-decomposition of vector R spaces. Equivalently, after taking opposites, it may be regarded as a functor G op : G → Vectop . When the cellular sheaf maps are epimorphisms in Vect, they become monomorphisms in Vectop , so that G op is a structured decomposition in the sense used earlier in this chapter. To match the terminology of control theory, multi-agent systems, and the cellular-sheaf literature, we refer to these objects as cellular sheaves throughout this section.

The functorial viewpoint is essential because it guarantees that the local models assigned to agents and communication links are compatible with the communication topology. Rather than specifying local state spaces, sensing maps, and communication rules independently, functoriality requires them to respect the incidence relations of the graph. Consequently, the resulting cellular sheaf represents a globally consistent information-processing architecture for the multi-agent system.

3.3.2 Category of cellular sheaves To model systems whose communication topology changes over time, we must also specify how one cellular sheaf transforms into another. This requires a suitable notion of morphism between cellular sheaves, capturing both the evolution of the underlying communication graph and the induced transformation of the associated local state data. This leads naturally to the category of cellular sheaves. Definition 17 (Category of cellular sheaves) The category CellSh is defined as follows. • Its objects are cellular sheaves G : inc(G) −→ Vect, where G is a finite directed graph.

• A morphism (T , α) : G → H consists of a functor T : inc(G) → inc(H) and a natural transformation α : G ⇒ H ◦ T , as shown below. T

inc(G)

inc(H)

Vect

We first examine the functor T : inc(G) → inc(H) appearing in a morphism (T , α) : G → H . Recall that the objects of inc(G) are the agents and communication links of G, while its nonidentity morphisms encode incidences between them. Thus, T specifies how the communication topology G is represented inside, or transformed into, the communication topology H. Because T is functorial, it preserves incidence relations: whenever an agent is incident to a communication link in G, its image must be incident to the image of that link in H. The following examples illustrate increasingly sophisticated ways in which a functor between incidence categories may arise in applications, beginning with subsystem inclusions, progressing to a coarse-graining of agents into teams, and culminating in switching communication topologies.

Example 12 (A subsystem of a system) Let G be a subgraph of H. The inclusions of vertices and edges determine a functor I : inc(G) ,→ inc(H) that sends every agent and communication link of G to the corresponding cell of H. Functoriality follows because incidences in G remain incidences in H. Example 13 (Aggregation of agents into teams) Hierarchical control often requires reasoning simultaneously at different levels of abstraction [53–55]. At the lower level, individual agents communicate through a detailed network, while at the higher level, groups of agents are treated as teams interacting

through a coarser communication topology. A functor between the corresponding incidence categories relates these two descriptions. Consider the path graph G = P4 = 1−2−3−4, representing four communicating agents. Suppose that agents 1 and 2 form team A, while agents 3 and 4 form team B. The team-level communication graph H therefore consists of two vertices, A and B, connected by a single edge AB. The aggregation is described by a functor T : inc(G) −→ inc(H)

defined by

T (1) = T (2) = A,

T (3) = T (4) = B,

and

T (12) = A, 12 1

T (23) = AB,

23 2

T (34) = B.

34 3

−−→

The color coding displays the aggregation. The objects 1, 2, and 12 share the color of team A, while 3, 4, and 34 share the color of team B. Accordingly, the intra-team links 12 and 34 are mapped to the team objects A and B, respectively. Their incidence morphisms are therefore mapped to the corresponding identity morphisms, shown as loops in the team-level category. This expresses that communication within each team is black-boxed in the coarse description. By contrast, the link 23 and its incidence morphisms share the color of the edge AB and its incidence morphisms. Thus, the communication between the two teams remains visible as a nontrivial edge at the team level. Example 14 (Switching topologies) Consider a multi-agent system whose communication topology changes over time. Let Gti and Gtk denote the communication graphs at two time instants ti < tk . Both may be viewed as communication subgraphs of a larger graph G describing every communication link that appears during the entire time horizon. The corresponding inclusion functors admit a pullback

inc(Gti ) ,→ inc(G) ←- inc(Gtk ). inc(Gti ) ←- inc(Gti ) ×inc(G) inc(Gtk ) ,→ inc(Gtk ),

whose apex identifies precisely the agents and communication links common to both topologies. The resulting span therefore represents the communication subsystem that persists across the transition from Gti to Gtk .

The second component of a morphism of cellular sheaves is given by a natural transformation α : G ⇒ H ◦ T . For every incidence morphism m : x → y in inc(G), naturality requires the commutativity of

G (x)

G (m)

G (y) αy

αx

H (T (x)) H (T (m)) H (T (y)). 34

Thus, performing the local computation prescribed by G and then communicating the resulting information via α to H yields the same result as first communicating the local data from G to H and then perform the corresponding local computation in H . In this sense, a morphism (T , α) : G → H makes the local information-processing rules of the two systems compatible with the information processing protocol within each system. Example 15 (Persistent information across a topology change) Consider the switching-topology setting of Example 14. We use this situation to illustrate the form of morphisms in the category of cellular sheaves. Let inc(Gttki ) Ii

Ik t Gtik

inc(Gttii )

αi

inc(Gttkk ) αk

Gtii

Gtkk

Vect where Gttii , Gttik , and Gttkk are cellular sheaves on the communication topologies inc(Gti ), inc(Gttki ), and inc(Gtk ), respectively. Since the communication topologies and the functors Ii and Ik have already been specified, defining morphisms of cellular sheaves amounts to specifying natural transformations αk : Gttik ⇒ Gttkk ◦ Ik ,

αi : Gttik ⇒ Gttii ◦ Ii ,

together with these functors, define the morphisms of cellular sheaves (I ,α )

(I ,α )

k i Gttkk . Gttik −−k−−→ Gttii ←−i−−−

The natural transformations αi and αk assign compatible linear maps to every persistent agent and communication link. Consequently, the communication subsystem that survives the topology change is accompanied by a coherent identification of the local state spaces, sensing maps, and communication constraints at both time instants.

3.3.3 Temporal cellular sheaves and switching topologies To model multi-agent systems with switching communication topologies as temporal narratives, we need the category of cellular sheaves to have the required structure. The following lemma, proved in [47], establishes precisely this fact. Lemma 3.13 The category CellSh admits pullbacks and pushouts.

Consequently, all the constructions developed in Section 3.1 apply with D = CellSh. Definition 18 (Temporal cellular sheaf) A temporal cellular sheaf is a CellSh-valued narrative, that is, a sheaf F : Top −→ CellSh▷◁ .

γb

a Thus, each interval [a, b] ∈ T is assigned a morphism of cellular sheaves Pab − → Cab , where b b Pa and Ca model the persistent and cumulative aspects of the multi-agent system over the interval [a, b], respectively, while γba relates the two descriptions. The sheaf condition reconstructs the persistent component by pullbacks and the cumulative component by pushouts, so that both the communication topology and the associated sensing and interaction maps evolve coherently through time. The principal advantage of temporal cellular sheaves is that they model not only the communication topology at each time instant but also the structural relationships between communication topologies across time intervals. Thus, instead of viewing a switching multiagent system as a sequence of independent communication graphs, the narrative records how information persists and accumulates as the communication architecture evolves. Within this framework, distributed coordination problems such as consensus, formation control, and target tracking can be formulated categorically. The dynamics of the agents evolve on the vector spaces assigned by the cellular sheaves, while the temporal narrative specifies how these local dynamical models are related as the communication topology changes. Current work investigates the stability theory of temporal cellular sheaves, building on recent sheaf-theoretic approaches to distributed control together with classical Lyapunov methods for switching systems. The objective is to characterize how changes in the communication topology interact with the evolution of distributed state variables, and to establish sufficient conditions under which target-tracking errors remain bounded and converge despite topology switches. This research program is currently being developed in [47].

4 Conclusion and future directions One of the strengths of the narrative framework is that it is largely independent of the nature of the objects evolving through time. Once an appropriate target category has been identified, the same theory immediately yields a coherent framework for modeling temporal phenomena across a wide range of applications. The three research directions presented in this chapter illustrate this flexibility from complementary perspectives: the first investigates the categorical structure of the persistence–accumulation adjunction through the category of narratives and its induced factorization of the adjunction, the second explores temporal analogues of structured decompositions, and the third instantiates the framework in the category of cellular sheaves to model multi-agent systems with switching communication topologies. Towards a characterization of the fixed points of the adjunction The factorization of the persistence–accumulation adjunction through the category of narratives introduces a setting in which persistence and accumulation are no longer viewed as separate constructions, but as two complementary descriptions of the same temporal object. The resulting rigidity classification measures the extent to which these descriptions determine one another. Rigid narratives coincide with the canonical completions induced by the adjunction in both directions. Left-rigid narratives preserve their persistent description under the persistence–accumulation round trip, right-rigid narratives preserve their cumulative description, while loose narratives lose information in both directions.

The rigidity classification also opens several directions for future research. A first natural question is to determine which rigidity classes arise in a given ambient category and how they reflect its structural properties. More generally, one may seek intrinsic categorical characterizations of left, right, and rigid narratives, as well as investigate how rigidity behaves under products, limits, colimits, functorial changes of the ambient category, and other categorical constructions. Beyond their intrinsic categorical interest, these questions contribute to a broader understanding of information-preserving changes of perspective, including those arising in data science. Structured decompositions of cumulative narratives By virtue of the tight relation between persistent and cumulative narratives, as revealed in Section 2.2, it is desirable to temporalize structured decompositions and width also from the cumulative point of view. More specifically, under dual assumptions of Theorem 3.8, we may form a pullback square Cu(T, D) ×Cu(S,D) Cu(S, Ωn )

Cu(S, Ωn )

πn

Cu(S,ιn )

Cu(T, D)

Cu(τ,D)

Cu(S, D).

We define Ω̌n ⊆ Cu(T, D) to be the image category of the functor πn . If we dualize the assumptions of Theorem 3.9, do we again obtain a spined sd-category of the form (Cu(T, D), G , Ω̌)? How does the proof change? A second direction is to investigate the relationship between the persistent and cumulative temporalizations of spined sd-categories. As exposed in Theorem 2.1, given any time category T and a category D that is both complete and cocomplete, then there exists a pair of adjoint functors ⊣

Pe(T, D)

Cu(T, D) .

It would be interesting to investigate the following questions, assuming the setting of Theorem 3.9 together with the dual assumptions: • Are the above adjoint functors sd-functors in the sense of [21, Definition 2.7.1]? • Are they even width-preserving in the sense of [21, Definition 2.7.8]? • If not, can this be guaranteed by modifying the assumptions appropriately? It would be desirable to have an adjoint pair of width-preserving sd-functors between the persistent and cumulative temporalized spined sd-categories. This would not only reveal a fundamental relation between the persistent and cumulative perspectives but also allow a convenient transfer between concepts and results for persistent narratives to cumulative ones and vice versa.

Temporal cellular sheaves: modelling multi-agent systems with switching topology Temporal cellular sheaves demonstrate how the narrative framework applies naturally to heterogeneous multi-agent systems with switching communication topologies. Choosing cellular sheaves as the target category allows the framework to encode not only the evolution of the communication architecture but also the heterogeneous sensing, communication, and information-processing structures associated with it. This establishes a categorical foundation for studying distributed control problems on time-varying communication networks. A natural next step is to endow temporal cellular sheaves with dynamical systems evolving on the vector spaces assigned to their cells. This raises the problem of understanding how the dynamics interact with topology changes and with the persistent and cumulative structures encoded by the narrative. Of particular interest is the development of a stability theory for the sheaf-theoretic description of switching communication networks, leading to conditions under which distributed coordination objectives—such as consensus, formation maintenance, or target tracking—remain stable despite changes in the communication topology. This research program is currently under development in [47].

Declarations Funding Benjamin Merlin Bumpus was supported by the São Paulo Research Foundation (FAPESP), grant 2025/16921-5. Conflict of interest The authors declare that they have no competing interests. Data availability No datasets were generated or analyzed during the current study. Materials availability Not applicable. Code availability Not applicable. Author contributions The authors’ contributions are described according to the CRediT (Contributor Roles Taxonomy) as follows. Conceptualization: W.L., B.B. Methodology: W.L., B.B. Formal analysis: W.L., B.B., J.N., J.G. Investigation: W.L., B.B., J.N., J.G. Resources: All authors. Writing—original draft: W.L., B.B., J.N. Writing-review and editing: All authors. Supervision: W.L., B.B., J.F., W.D. Project administration: W.L., B.B. Funding acquisition: W.L., B.B., J.N., J.G., J.F., W.D.

References [1] Miritello, G.: Temporal Patterns of Communication in Social Networks. Springer Theses. Springer, Cham, Switzerland (2013). https://doi.org/10.1007/978-3-319-00110-4 [2] Choi, B., Bergés, M., Bou-Zeid, E., Pozzi, M.: Short-term probabilistic forecasting of meso-scale near-surface urban temperature fields. Environmental Modelling & Software 145, 105189 (2021) https://doi.org/10.1016/j.envsoft.2021.105189 [3] Meliker, J.R., Sloan, C.D.: Spatio-temporal epidemiology: Principles and opportunities. Spatial and Spatio-temporal Epidemiology 2(1), 1–9 (2011) https://doi.org/10.1016/j. sste.2010.10.001 [4] Niu, N., Osgood, N.D., Szelko, J.S., Srinivasan, P.V.: Temporal sheaf theory for reconciling temporal complexity within public health modelling. In: Proceedings of the Ninth International Conference on Applied Category Theory (2026). Accepted for publication. https://actconf2026.github.io/papers/ACT 2026 paper 51.pdf

[5] Mesbahi, M., Egerstedt, M.: Graph Theoretic Methods in Multiagent Networks. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ (2010) [6] Olfati-Saber, R., Fax, J.A., Murray, R.M.: Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE 95(1), 215–233 (2007) https://doi.org/10. 1109/JPROC.2006.887293 [7] Teich, M., Leal, W., Jost, J.: Diachronic data analysis supports and refines conceptual metaphor theory. PLOS Complex Systems 2(8), 0000058 (2025) https://doi.org/10. 1371/journal.pcsy.0000058 . Article e0000058 [8] Laubichler, M.D., Maienschein, J., Renn, J.: Computational perspectives in the history of science: To the memory of peter damerow. Isis 104(1), 119–130 (2013) https://doi. org/10.1086/669891 [9] Llanos, E.J., Leal, W., Luu, D.H., Jost, J., Stadler, P.F., Restrepo, G.: Exploration of the chemical space and its three historical regimes. Proceedings of the National Academy of Sciences 116(26), 12660–12665 (2019) https://doi.org/10.1073/pnas.1816039116 [10] Atluri, G., Karpatne, A., Kumar, V.: Spatio-temporal data mining: A survey of problems and methods. ACM Computing Surveys 51(4), 83–18341 (2018) https://doi.org/ 10.1145/3161602 [11] Laxman, S., Sastry, P.S.: A survey of temporal data mining. Sadhana 31(2), 173–198 (2006) https://doi.org/10.1007/BF02719780 [12] Habereder, I., Kneib, T., Echizen, I., Spinde, T.: A Systematic Review of SpatioTemporal Statistical Models: Theory, Structure, and Applications (2025). https://arxiv. org/abs/2511.00422

[13] Roddick, J.F., Spiliopoulou, M.: A survey of temporal knowledge discovery paradigms and methods. IEEE Transactions on Knowledge and Data Engineering 14(4), 750–767 (2002) https://doi.org/10.1109/TKDE.2002.1019212 [14] Roddick, J.F., Patrick, J.D.: Temporal semantics in information systems—a survey. Information Systems 17(3), 249–267 (1992) https://doi.org/10.1016/0306-4379(92) 90016-G [15] Bumpus, B.M., Leal, W., Fairbanks, J., Karvonen, M., Simard, F.: Towards a unified theory of time-varying data. Applied Categorical Structures 34(3), 23 (2026) https://doi. org/10.1007/s10485-026-09860-4 [16] Bumpus, B.M., Nickel, J.K.: Decomposing time-varying data into simple pieces: structured decompositions of narratives (2026). https://doi.org/10.48550/arXiv.2607.10442 [17] Borges, J.L.: El Jardı́n de Senderos Que Se Bifurcan. Editorial Sur, Buenos Aires (1941) [18] Johnstone, P.: A note on discrete Conduché fibrations. Theory and Applications of Categories 5(1), 1–11 (1999) [19] Lack, S., Sobocinski, P.: Adhesive categories. In: Walukiewicz, I. (ed.) Foundations of Software Science and Computation Structures, pp. 273–288. Springer, Berlin, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24727-2 20 [20] Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg (2006). https://doi.org/10.1007/3-540-31188-2 [21] Bumpus, B.M., Kocsis, Z.A., Master, J.E., Minichiello, E.: Structured Decompositions: Structural and Algorithmic Compositionality (2025). https://arxiv.org/abs/2207. 06091v7 [22] Robertson, N., Seymour, P.D.: Graph minors. xvii. taming a vortex. Journal of Combinatorial Theory, Series B 77(1), 162–210 (1999) [23] Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation 85(1), 12–75 (1990) [24] Halin, R.: S-functions for graphs. Journal of Geometry 8, 171–186 (1976) [25] Robertson, N., Seymour, P.D.: Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B 36(1), 49–64 (1984) [26] Liu, J.W.H.: A tree model for sparse symmetric indefinite matrix factorization. SIAM Journal on Matrix Analysis and Applications 9(1), 26–39 (1988) [27] Yannakakis, M.: Algorithms for acyclic database schemes. In: Proceedings of the Seventh International Conference on Very Large Data Bases (VLDB ’81), pp. 82–94. IEEE

Computer Society, Cannes, France (1981) [28] Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics 23(1), 11–24 (1989) [29] Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artificial Intelligence 38(3), 353–366 (1989) [30] Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society: Series B (Methodological) 50(2), 157–194 (1988) [31] Robertson, N., Seymour, P.D.: Graph minors. xiii. the disjoint path problem. Journal of Combinatorial Theory, Series B 63(1), 65–110 (1995) [32] Robertson, N., Seymour, P., Thomas, R.: Sachs’ linkless embedding conjecture. Journal of Combinatorial Theory, Series B 64(2), 185–227 (1995) [33] Fujita, T.: A brief overview of applications of tree-width and other graph width parameters. Applied Mathematics on Science and Engineering 2(1), 1–20 (2025) [34] Harary, F., Gupta, G.: Dynamic graph models. Mathematical and Computer Modelling 25(7), 79–87 (1997) [35] Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences 64(4), 820–842 (2002) [36] Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. In: Frey, H., Li, X., Ruehrup, S. (eds.) Ad-hoc, Mobile, and Wireless Networks, pp. 346–359. Springer, Berlin, Heidelberg (2011) [37] Holme, P., Saramäki, J.: Temporal networks. Physics Reports 519(3), 97–125 (2012) [38] Holme, P.: Modern temporal network theory: a colloquium. The European Physical Journal B 88(234) (2015) [39] Michail, O.: An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics 12 (2015) [40] Carmesin, J., Jacobs, R.W., Knappe, P., Kurkofka, J.: Canonical graph decompositions and local separations: From infinite coverings to a finite combinatorial theory (2025). https://arxiv.org/abs/2501.16170v1 [41] Diestel, R., Jacobs, R.W., Knappe, P., Kurkofka, J.: Canonical graph decompositions via coverings (2025). https://arxiv.org/abs/2207.04855v8 [42] Ames, A.D.: A categorical theory of hybrid systems. PhD thesis, University of California, Berkeley (2006). https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/ EECS-2006-165.pdf 41

[43] Serre, J.-P.: Arbres, amalgames, sl2 . Astérisque, Société Mathématique de France, Paris (46) (1977). Rédigé avec la collaboration de Hyman Bass [44] Serre, J.-P.: Trees. Springer Monographs in Mathematics. Springer, Berlin, Heidelberg (2003) [45] Bass, H.: Covering theory for graphs of groups. Journal of Pure and Applied Algebra (89), 3–47 (1993) [46] Hu, C.-S.: Cellular Sheaves on Higher-Dimensional Structures (2025). https://arxiv.org/ abs/2505.23993v3 [47] Copeland, A., Leal, W., Fallin, B., Bumpus, B.M., Fairbanks, J., Dixon, W.E.: A Temporal Cellular Sheaf Framework for Multi-Agent Systems with Switching Topologies. Work in progress (2026) [48] Currier, K., Leal, W., Fallin, B., Fairbanks, J., Dixon, W.E.: From local to global: Sheaf-theoretic control barrier functions on manifolds. In: Proceedings of the IEEE 65th Conference on Decision and Control (CDC). IEEE, Honolulu (2026) [49] Bullo, F., Cortés, J., Martı́nez, S.: Distributed Control of Robotic Networks. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, USA (2009) [50] Moreau, L.: Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control 50(2), 169–182 (2005) https://doi.org/10. 1109/TAC.2004.841888 [51] Hanks, T., Nino, C.F., Barcelo, J.B., Copeland, A., Dixon, W., Fairbanks, J.: Heterogeneous Multi-Agent Multi-Target Tracking using Cellular Sheaves (2025). https: //arxiv.org/abs/2512.24886 [52] Hanks, T., Riess, H., Cohen, S., Gross, T., Hale, M., Fairbanks, J.: Distributed multiagent coordination over cellular sheaves. In: 2025 IEEE 64th Conference on Decision and Control (CDC), pp. 3057–3064 (2025). https://doi.org/10.1109/CDC57313.2025. 11312066 [53] Scattolini, R.: Architectures for distributed and hierarchical model predictive control – a review. Journal of Process Control 19(5), 723–731 (2009) https://doi.org/10.1016/j. jprocont.2009.02.003 [54] Bai, H., George, J., Chakrabortty, A.: Hierarchical control of multi-agent systems using online reinforcement learning. In: Proceedings of the 2020 American Control Conference (ACC), pp. 340–345. IEEE, Denver, CO, USA (2020). https://doi.org/10.23919/ ACC45564.2020.9147797 [55] Zegers, F.M., Phillips, S., Dixon, W.E.: Consensus over clustered networks with asynchronous inter-cluster communication. In: 2021 American Control Conference (ACC), pp. 4249–4254 (2021). https://doi.org/10.23919/ACC50511.2021.9482931 42

Record · ID 668081 · SHA-256 be7c421c6d12d855
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.