\section{Introduction}

Double-Pushout (DPO)~\cite{ehrig:2006aa} and more generally compositional categorical rewriting systems~\cite{nbSqPO2019, Behr2021compositionality} provide a versatile and mathematically sound framework for modeling complex transition systems, with a paradigmatic example the modeling of reaction systems in biochemistry~\cite{Boutillier:2018aa} and in organic chemistry~\cite{BK2020}. %
The specification of an individual rewriting operation (\emph{direct derivation}) in essence amounts to providing a rewrite rule, i.e., a span of monomorphisms, that acts as a sort of template for the operation, together with a \emph{match}, which permits to specify the location within a host object where the local replacement operation is to be performed. In practical applications, it is often the case that the rewriting rules themselves involve only comparatively small graph-like objects. In contrast, the host objects to which the rewrites are applied could easily be several orders of magnitude larger, so that an enormous number of matches may be possible for a given rule and a given host object.

A natural and powerful approach to overcome this fundamental problem consists in focusing on the combinatorial, statistical and structural properties of \emph{interactions} of rewriting rules within derivation traces, and to aim for a classification of traces in terms of ``interaction patterns''. %
Unlike in compositional diagrammatic calculi such as in particular the theory of string diagrams, the key obstacle for such a type of analysis in rewriting theories resides in the fact that two given rules may in general interact in a multitude of ways, i.e., there does not exist a notion of deterministic rule composition. %
Instead, as first demonstrated in~\cite{bdg2016} and further developed in~\cite{nbSqPO2019,bp2019-ext,BK2020, Behr2021compositionality}, it is necessary to define a notion of non-deterministic rule composition via a form of recursive application of the concurrency theorem, which then indeed permits to define tractable methods to reason statically about classes of rule compositions. %
Taking inspiration from the notion of \emph{pathways} in chemical reaction systems, this approach was then further refined in~\cite{behr2019tracelets} to the notion of \emph{tracelets}, which in essence act as the carriers of causal information in derivation sequences. %

The main objective of the present paper consists in establishing a principled mathematical approach to formalize the \emph{combinatorics} of tracelets. Generalizing results of~\cite{bdgh2016} on rewriting systems over directed multi-graphs to the categorical rewriting theory setting, we will demonstrate that it is indeed the notion of \emph{combinatorial Hopf algebras} that naturally captures the rich structure of tracelets. Apart from a rewriting-theoretic construction of the Hopf algebras (Section~\ref{sec:Hopf}), we report on our original discovery that this at first sight seemingly ad hoc construction is in fact interpretable in terms of the theory of \emph{decomposition spaces} (Sections~\ref{sec:DSRR} and~\ref{sec:DST}). Our motivation for this approach has been the analogy between the inductive definition of tracelets and the decomposition-space axioms in homotopy combinatorics. The benefit
of this `detour' is to situate the tracelet Hopf algebra in a
general framework covering most combinatorial Hopf algebras, thereby
exhibiting the constructions and proofs as general ideas.

Decomposition spaces were introduced in combinatorics by G\'alvez,
Kock and Tonks~\cite{Galvez-Kock-Tonks151207573}, \cite{Galvez-Kock-Tonks151207577} as a far-reaching homotopical generalization of posets for the purpose of incidence
algebras and M\"obius inversion, and independently by Dyckerhoff and
Kapranov~\cite{Dyckerhoff-Kapranov12123563} in homological algebra and representation theory, motivated mainly by the Waldhausen S-construction and Hall algebras.
Classically, since the work of Rota~\cite{RotaMoebius} in the 1960s, incidence algebras
were defined from posets through the process of decomposing
intervals. The construction can fruitfully be formulated in terms of
the nerve of a poset. However, a great many combinatorial co- and
Hopf algebras are not of incidence type, meaning that they are not
the incidence coalgebra of a poset. The basic observation of
\cite{Galvez-Kock-Tonks151207573} is that simplicial objects more general than nerves of
posets admit the incidence coalgebra construction, allowing most of
the basic features of the theory to carry over --- and that most
combinatorial Hopf algebras do arise as incidence Hopf algebras of
(monoidal) decomposition spaces.

\section{Double-Pushout rewriting and tracelet theory}

\begin{figure}
\centering
\subfigure[A direct derivation sequence of length $5$ (with edge creation/deletion rules, and where``wires'' indicate matches).\label{fig:ddExample}]{
$\vcenter{\hbox{\includegraphics[scale=0.1]{images/ddExStep1}}}$
$\vcenter{\hbox{\includegraphics[scale=0.1]{images/ddExStep2}}}$
$\vcenter{\hbox{\includegraphics[scale=0.1]{images/ddExStep3}}}$
$\vcenter{\hbox{\includegraphics[scale=0.1]{images/ddExStep4}}}$
$\vcenter{\hbox{\includegraphics[scale=0.1]{images/ddExStep5}}}$}\\
\subfigure[Tracelet and shift equivalence example.\label{fig:TAillustration}]{
$\vcenter{\hbox{\includegraphics[height=0.32\textwidth]{images/TAexampleIllustration}}}$}\;
\subfigure[Defining property of tracelets (here of length $3$).\label{fig:TA3definingProperty}]{$\vcenter{\hbox{\includegraphics[height=0.32\textwidth]{images/TLassocIllustration}}}$}
\caption{An illustration of graph rewriting sequences (top) and of the tracelet picture (bottom).}
\label{fig:TLP}
\end{figure}

Consider a rewriting system of undirected multi-graphs such as the one depicted in Figure~\ref{fig:ddExample}, with some elementary rules that link and unlink vertices with edges. Starting from some initial graph $X_0$, each rewriting step (\emph{direct derivation}) consists in choosing a rewriting rule together with an occurrence (\emph{match}) of the input motif (drawn at the bottom of the rule diagrams) within the graph that is rewritten. It is intuitively clear that sequences of rewrites (\emph{derivation traces}) have a rich intrinsic structure, since the graph-like nature of the input and output interfaces of the rules as well as the internal structure of the rules entail that the nature of \emph{interactions} between sequential rewriting steps is not easily encapsulated in any simple form of composition structure. %
To wit, consider the  diagram in Figure~\ref{fig:TAillustration}, which provides a sort of movie-script depiction of the five-step derivation trace depicted in the top part of the figure. For clarity, red wires are used to indicate inputs to rules that are present in the original configuration $X_0$, while blue wires indicate inputs to rules that have originated from outputs of preceding rules.

The main purpose of the theory of \emph{tracelets}~\cite{behr2019tracelets} then consists in rendering mathematically precise the meaning of this intuitive picture. In particular, according to the \emph{Tracelet Characterization Theorem}~\cite[Thm.~2]{behr2019tracelets}, each derivation trace of length $n$ is uniquely characterized by a \emph{tracelet} of length $n$ (cf.\ the sub-diagram consisting of the five rules and all blue wires in Figure~\ref{fig:TAillustration}) and a \emph{match} of the tracelet into the initial configuration $X_0$ (depicted as red ``wires'' in Figure~\ref{fig:TAillustration}). Crucially, the compositional structure of tracelets offers a form of statics causal analysis via algebraic relations such as commutator relations. This type of analysis takes advantage of algebraic relations such as \emph{shift equivalence}, which in the example of Figure~\ref{fig:TAillustration} amounts to the observation that the rules in the boxes highlighted in orange may be freely moved ``along the wires'' so as to exchange their order (i.e., without changing the overall effect of the rewriting sequence). Finally, as sketched via the highlighted triangle pattern that is produced via the rewriting sequence in the example, tracelets permit to statically reason about the combinatorics of pattern-counting problems in an efficient manner  (cf.\ \cite{Behr2021} for a prototype of such an analysis in the setting of counting patterns in planar rooted binary trees).

As depicted in Figure~\ref{fig:TA3definingProperty}, a tracelet of length $3$ exhibits already quite a non-trivial compositional structure, in that as sketched the internal structure of partial overlaps of rule inputs and outputs in such a tracelet is not inherently of a purely sequential nature; to wit, the diagram encodes a special kind of trace of length $3$, with the defining property that it may be equivalently (up to isomorphisms) be obtained via nested composition operations. It is in this particular sense that tracelets offer a \emph{minimal} causal presentation of the structure of rewriting sequences, since via the equivalences to nested pairwise composition operations, they permit to efficiently express $n$-step sequences as just a special type of derivation sequences.

\begin{blanko}{Categorical rewriting theory.} %
For simplicity, we will focus here on the variant of tracelet theory for so-called \emph{double-pushout (DPO) rewriting}, and for rewriting rules
without application conditions (referring to~\cite{behr2019tracelets} for
the general\footnote{Available generalizations include the type of
rewriting (with \emph{Sesqui-Pushout} semantics an alternative option), the
choice of base-categories (with \emph{$\cM$-adhesive
categories}~\cite{ehrig2014mathcal} a more general option) as well as the
inclusion of constraints and application conditions into the compositional
rewriting semantics (cf.\ also~\cite{Behr2021compositionality}).} theory).
Throughout this paper, let $\bfC$ denote an \emph{adhesive category}~\cite{ls2004adhesive} that is \emph{finitary} (in the sense of~\cite{Braatz:2010aa}, i.e., with only finitely many subobjects for each object up to isomorphisms), and that possesses
a strict initial object $\mathop{\varnothing}\in \obj{\bfC}$. \emph{Rewriting rules} are defined as spans of monomorphisms $r=(O\leftarrow o-K-i\rightarrow I)$, also denoted for brevity as $r=(O\leftharpoonup I)$. In the tradition of rewriting theory, we refer to such rules as \emph{linear rules} (with ``linear'' referring to the nature of the span as a span of monos), and denote the class of all such rules as $\Lin{\bfC}$. For every $r\in \Lin{\bfC}$ and object $X\in\obj{\bfC}$, let $\RMatchGT{}{r}{X}$ denote the \emph{set of (DPO-admissible) matches of $r$ into $X$}, where $m\in \RMatchGT{}{r}{X}$ iff $m$ is a monomorphism and the \emph{pushout complement} marked $\mathsf{POC}$ in the diagram below left exists:
\begin{equation}
\ti{DPOdd}
\end{equation}
Note that in an adhesive category, pushouts along monomorphisms (here marked $\mathsf{PO}$) are guaranteed to exist; in contrast, pushout complements (here marked $\mathsf{POC}$) may fail to exist, since not every composable pair of arrow can be completed into a pushout square. Moreover, $r_m$ as well as $Y=r_m(X)$ are evidently only defined up to universal isomorphisms. It is customary to refer to the data of the aforementioned diagram as a \emph{direct derivation}. For later convenience, taking advantage of the symmetry of the definition, we mark by $\mathsf{DPO}^{\dag}$ diagrams that arise as DPO-type direct derivations in the ``opposite direction'', i.e., ``against'' the direction of rules (here, from left to right; cf.\ the diagram above right).
\end{blanko}

\begin{blanko}{Tracelets.}\label{sec:maindefTracelets}
The class of \emph{tracelets} $\cT$ for DPO-type type rewriting over $\bfC$ is defined recursively:
\begin{itemize}
\item \emph{Tracelets of length $1$}: for every rule $r=(O\leftharpoonup I)\in \Lin{\bfC}$, define $T(r)\in \cT_1$ as a diagram
\begin{equation}
\ti{tlOne}\,.
\end{equation}
\item \emph{Tracelets of length $n+1$:} denoting by $\cT_n$ (for $n>1$) the class of trecelets of length $n$, the class $\cT_{n+1}$ is defined to consist of diagrams as below, where $r_k=(O_k\leftharpoonup I_k)\in \Lin{\bfC}$ are linear rules (for $k=1,\dotsc,n+1$), where the top right part of the diagram encodes a tracelet $T\in \cT_n$ of length $n$, where $\mu=(I_{n+1}\leftarrow M\rightarrow O_{n\cdots1})$ is a span of monos, with the cospan $I_{n+1}\rightarrow Y^{(n+1)}_{n+1,n}\leftarrow O_{n\cdots 1}$ its pushout, and such that the direct derivations marked $\mathsf{DPO}$ and $\mathsf{DPO}^{\dag}$ exist:
\begin{equation}
\ti{tlNpOneA}
\end{equation}
Then this data defines a tracelet $\TcompGT{T(r_{n+1})}{\mu}{T}{}$ of length $n+1$ (the \emph{tracelet composition} of $T(r_{n+1})$ with $T$ along $\mu$) uniquely up to universal isomorphisms (see comments below) as
\begin{equation}\label{eq:TnPone}
\TcompGT{T(r_{n+1})}{\mu}{T}{}:=\ti{tlNpOneB}\,.
\end{equation}
\end{itemize}
For later convenience, we will sometimes speak of the commutative square below rule $r_i$ in a tracelet as the \emph{$i$-th plaquette}. Let $\cT:=\cup_{n\geq1}\cT_n$ denote the class of all (finite length) tracelets. For later convenience, we also introduce the notations $\mathsf{in}(T):=I_{n\cdots1}$ (``input interface'' of $T\in \cT_n$), $\mathsf{out}(T):=O_{n\cdots1}$ (``output interface'' of $T\in \cT_n$), $\tMatchGT{T(r_{n+1})}{T}{}$ (for ``matches'', i.e., admissible partial overlaps $\mu$ of the length $1$ tracelet $T(r_{n+1})$ with the tracelet $T\in \cT_n$) and $[[T]]$ for the so-called \emph{evaluation} of the tracelet $T$, which for $T\in \cT_n$ is defined with notations as in the top right of~\eqref{eq:TnPone} as
\begin{equation}
[[T]]:=(O_{n\cdots1}\leftharpoonup I_{n\cdots 1})=(O_{n\cdots1}\leftharpoonup Y^{(n)}_{n,n-1})\circ \cdots\circ (Y^{(n)}_{2,1}\leftharpoonup I_{n\cdots 1})\,.
\end{equation}
Here, $\circ$ denotes the operation of \emph{span composition} (considered up to span-isomorphisms).
\end{blanko}

Up to this point, one might say that DPO-type tracelets are some form of data structure that encodes a certain form of \emph{sequential compositions} of rewriting rules. This point of view is augmented via the following definition, which finally reveals tracelets as a particular notion of compositional diagrams.

\begin{blanko}{Tracelet composition.} Let $T\in \cT_m$ and $T'\in \cT_n$ be two tracelets of length $m$ and $n$, respectively (for $m,n>0$). Let $\mu:=(I_{m\cdots1}\leftarrow M\rightarrow O'_{n\cdots 1})$ be a partial overlap (of the ``input interface'' $I_{m\cdots1}$ of $T$ with the ``output interface'' $O'_{n\cdots 1}$ of $T'$) whose pushout $I_{m\cdots1}\rightarrow Y^{(m+n)}_{n+1,n}\leftarrow O'_{n\cdots 1}$ satisfies that in the diagram below, all direct derivations marked $\mathsf{DPO}$ and $\mathsf{DPO}^{\dag}$, respectively, exist:
\begin{equation}
\ti{TmPnData}
\end{equation}
In this case, we write $\mu\in \tMatchGT{T}{T'}{}$ to say that $\mu$ is a(n DPO-admissible) \emph{match} of $T$ into $T'$, and we denote the \emph{composition} of $T$ with $T'$ along $\mu$ as
\begin{equation}
\TcompGT{T}{\mu}{T'}{}:=\ti{TcompMpN}\,.
\end{equation}
\end{blanko}

The definition of tracelets and their composition might appear somewhat ad
hoc at first sight, yet it is very natural if viewed in diagrammatic form.
To this end, consider the example of a tracelet of length $3$ such as in Figure~\ref{fig:TA3definingProperty}. The ``wires'' in the schematic
diagram that link individual length $1$ tracelets encode the partial
overlaps; as indicated, the tracelet of length $3$ may be realized
recursively via either determining the partial overlap of the first and the
second sub-tracelet, composing, and then determining the resulting overlap
of the composite tracelet of length $2$ with the third tracelet of length
$1$, or (equivalently as it will turn out) computing the composition of the
third and second tracelets of length $1$, and of that composite with the
first tracelet of length $1$. This so-called \emph{associativity property}
of tracelet compositions is at the heart of the algebraic properties of
tracelets. It will be further illustrated when we now pass to discuss tracelets
in the framework of decomposition spaces.

\section{The decomposition space of rewrite rules}\label{sec:DSRR}

In this section we describe a decomposition
space $\mathbf{X}_\bullet$ of rewrite rules (for a fixed rewrite system in a fixed
adhesive category $\bfC$ as above), whose incidence algebra is the rule algebra.

\begin{blanko}{Decomposition spaces.}
  A decomposition space~\cite{Dyckerhoff-Kapranov12123563},
  \cite{Galvez-Kock-Tonks151207573} is a simplicial groupoid $X_\bullet :
  \mathbbe{\Delta}^{\text{{\rm{op}}}}\to\kat{Grpd}$ satisfying a certain exactness property
  designed precisely to allow the incidence coalgebra construction,
  classically defined for posets. (The nerve of a poset or a category is an
  example of a decomposition space. Where categories encode composition,
  decomposition spaces owe their name to encoding decomposition.) Many
  situations where compositionality is hard to achieve can be dealt with
  instead with decompositions, as is often the case in combinatorics, where
  combinatorial structures can be split into smaller ones without the
  ability to compose~\cite{Galvez-Kock-Tonks170802570},
  \cite{Galvez-Kock-Tonks161209225}. Often non-deterministic composition
  structures can be turned around and constitute instead a decomposition.

  There are different ways to formulate the decomposition-space axioms. One
  (simplified) version states that for any endpoint-preserving monotone map
  $\alpha: [2] \rightarrow\Mapsfromchar [n]$, defining a decomposition of any $n$-simplex
  into an $n_1$-simplex and an $n_2$-simplex, the natural square
  \begin{equation}
  \ti{htpn1n2}
  \end{equation}
  is a pullback. It says that an $n$-simplex can be reconstructed from the
  two smaller simplices of the decomposition together with the information of
  a gluing of the the long edges of the two simplices onto the short edges
  of a base $2$-simplex.

  This condition is considerably weaker than the Segal condition (which
  characterizes categories, hence composition rather than just
  decomposition), which says that a single-vertex overlap between the two
  smaller simplices is enough to glue. In the decomposition-space case, the
  base $2$-simplex is required as a kind of context for the gluing.
\end{blanko}

\begin{blanko}{Groupoids of tracelets.}
  An {\em isomorphism} between two tracelets of length $n$ is by definition
  a family of object-wise isomorphisms between the involved objects in
  $\bfC$ making all squares commute. %
  We denote by $\mathbf{X}_n$ the groupoid of all tracelets of length $n$.
  (In particular,
  the only tracelet of length $0$ is the empty one (which
  evaluates to the trivial rule), so $\mathbf{X}_0 = \{*\}$.)
  %
\end{blanko}

\begin{theorem}
  The groupoids $\mathbf{X}_n$ assemble into a simplicial groupoid
  $\mathbf{X}_\bullet: \mathbbe{\Delta}^{\text{{\rm{op}}}}\to\kat{Grpd}$ (whose face and degeneracy maps we
  proceed to describe below).
\end{theorem}

To describe the simplicial structure, we give the standard presentation in
terms of face and degeneracy maps, so that the data is a diagram in the
category of groupoids of shape

\begin{equation}
\ti{rds}
\end{equation}

\begin{blanko}{Description of the face maps.}
The \emph{top face map} $d_n:\mathbf{X}_n\to\mathbf{X}_{n-1}$ (resp.~the \emph{bottom face
  map} $d_0:\mathbf{X}_n\to\mathbf{X}_{n-1}$) is defined via (1) performing \emph{tracelet surgery} (cf.\ Corollary~\ref{cor:TAbase}) to exhibit the tracelet as a composition of the first (the last) rule with an ($n-1$)-tracelet, followed by (2) extracting the ($n-1$)-length tracelet. This is illustrated in Figure~\ref{fig:TA3definingProperty} for the case of $n=3$, with $d_0$ ($d_3$) defined to return the tracelet shaded in light blue (in light yellow).

Recall from Section~\ref{sec:maindefTracelets} that a \emph{plaquette in position $i$} of a given tracelet is defined as the $i$-th direct derivation, i.e., the commutative subdiagram of the tracelet involving the $i$-th rule (read from the right). Then the \emph{inner face maps} $d_i : \mathbf{X}_n \to \mathbf{X}_{n-1}$ (for $0<i<n$) replace
  the two plaquettes $p_i$ and $p_{i+1}$ in the chain with a single new
  plaquette $p'$ with the same starting point as $p_i$ and the same endpoint
  as $p_{i+1}$, by applying the ``synthesis'' part of the concurrency theorem (cf.\ Theorem~\ref{thm:cct})
  to convert the sub-sequence of plaquettes $p_{i+1}$ after $p_i$ into a
  one-step direct derivation along the composite rule $p'_{i+1,i}$. The
  result of this operation is guaranteed to be a tracelet of length $n-1$. Referring once again Figure~\ref{fig:TA3definingProperty} for an illustration of the case $n=3$, $d_1$ ($d_2$) are defined to return the tracelet shaded in green (in pink).

  The \emph{degeneracy maps} $s_i : \mathbf{X}_n \to \mathbf{X}_{n+1}$ (for $0\leq i \leq n$)
  insert a copy of the trivial rule $\emptyset \leftarrow \emptyset \to
  \emptyset$ in the tracelet at position $i$.
\end{blanko}

In the form stated, $\mathbf{X}_\bullet$ is only a pseudo-simplicial groupoid.
This means that the simplicial identities only hold up to (specified)
isomorphism, and that there are coherence issues to deal with. The reason
for this pseudo-ness is that composition of rules and tracelets, as
involved in the face maps, is only well defined up to isomorphism, relying
as it does on pushouts and pullbacks. To actually get well-defined face maps, it is
necessary to make choices of these universal constructions, and these
choices screw up the strict simplicial identities. (A well-known example
of this phenomenon is
how composition of spans by means of pullbacks defines a bicategory, not an
ordinary category.)

This pseudo-ness is not at all a problem for the sake of decomposition-space
theory, designed to be up to homotopy, and it does not affect the incidence
algebra we construct from this decomposition space (which in any case is
spanned by iso-classes of rewrite rules). Nevertheless it is very fruitful
to provide also a strict model of $\mathbf{X}_\bullet$. The standard technique for
constructing this (which goes back to insight from algebraic topology from
the 1970s (notably Quillen,\footnote{Historical remark: B\'enabou (1963)
had described a bicategory spans. Quillen used the techniques of big
redundant $n$-simplices to exhibit the same structure as a {\em strict}
simplicial groupoid, now called Quillen's Q-construction. Instead of
having simply chains of $n$ composable spans
\raisebox{-0.5mm}{\ti{quillenA}}
in degree $n$, he defined it
to be diagrams of shape \raisebox{0.5mm}{%
\ti{quillenB}}, that is composable spans, {\em together} with all
the relevant pullbacks. Similar constructions were given in related
situation by Waldhausen and Segal, and today the technique is standard in
algebraic topology.} Waldhausen, and Segal)) is to beef up the
groupoid of $n$-simplices to something equivalent that contains all the
(redundant) data involved in the face maps.

Specifically, a $2$-simplex should not just be a $2$-tracelet, but rather
a $2$-tracelet {\em together} with a choice of composite rule. In this way
the middle face map $d_1 : \mathbf{X}_2 \to \mathbf{X}_1$ does not have to compute any composite by means of
choices; it can simply return the choice already built in. The fact that
these choices are unique up to universal isomorphisms say precisely that
this bigger groupoid is equivalent to the original, and hence that the
homotopy properties of the bigger simplicial groupoids are the same.
In Figure~\ref{fig:r2s} we see such a fully specified $2$-simplex.
The two short edges ($01$ and $12$) are the two rules in a $2$-tracelet,
and the squares marked PO and POC are the plaquettes constituting
altogether the $2$-tracelet. The pullback square (blue, marked as PB) is
not
part of the data of the tracelet, but it is included in the fully
specified notion of $2$-simplex.

In degree $3$ we arrive at the first point where there is an interesting
simplicial identity to establish, namely commutativity of the square
\begin{equation}
\ti{SPBI}
\end{equation}
which in essence states that a
sequential composition of three rules may be recovered equivalently from
two steps of pairwise rule compositions in either of the nesting orders.

For the groupoids of bare tracelets, this simplicial identity cannot be
strict, due to the choices of pushouts and pullbacks involved in
composition of rules and tracelets. That the equation holds up to natural
isomorphism is a nontrivial statement which involves the concurrency
theorem (in the particular form called associativity
theorem~\cite{bp2019-ext,bdg2016,bdgh2016}). We explain how the same
theorem implies the strict equation for the fully specified $3$-simplices.
This exhibits the beautiful geometry inherent in the associativity theorem.
As always, the idea is that a fully specified $3$-simplex should contain
all information about all choices. In particular (in order for the four
face maps to be forgetful) it should contain four $2$-simplices of the form
of Figure~\ref{fig:r2s}. A full picture of such a subdivided tetrahedron
is given in Figure~\ref{fig:r3s}.
One can chase through how this is built up from composition of tracelets,
over specified overlaps:
Consider the diagram
depicted in Figure~\ref{fig:rds3-prepA}, which is formed by (1) a
$2$-simplex encoding a composition of two rules $r_{21}$ and $r_{10}$ into
some rule $r_{20}$, and (2) another $2$-simplex of which one ``short edge''
is the rule $r_{20}$, and which contains another rule $r_{32}$ and the data
of the composition of $r_{32}$ with $r_{20}$ into some rule $r_{30}$. Upon
closer inspection, it is possible (via a number of somewhat intricate
steps) to construct from this data the interior and the other two faces of
a tetrahedron. To this end, one first invokes the ``analysis'' part of the
DPO-type concurrency theorem (cf.\ Theorem~\ref{thm:cct} in
Appendix~\ref{app:bg}) in order to obtain from the sub-diagram that
encodes the one-step direct derivation of the object $I_{03}$ along the
composite rule $O_{20}\leftarrow K_{20}\rightarrow K_{20}$ the data of a
sequence of two direct derivations along the ``constituent'' rules
$O_{21}\leftarrow K_{21}\rightarrow I_{21}$ after $O_{10}\leftarrow
K_{10}\rightarrow I_{10}$. This construction in particular delivers an
object $Z$ located in the interior of the tetrahedron. Over several
further steps (involving pushout and pullback operations), it is then
possible to fill the remaining two faces of the $3$-simplex with the
structure of two sequential rule compositions, ultimately resulting in the
diagram of Figure~\ref{fig:r3s}. The fact that all these constructions are
given by universal properties (pushouts and pullbacks, together with
the axioms of adhesive categories), ensures that the groupoid of such
fully specified $3$-simplices is equivalent to the groupoid of bare
$3$-tracelets.
The face maps are now obvious (or even tautological) and all the
simplicial identities are clearly strict for this reason: they merely
return data already contained in (the beefed-up version of) $\mathbf{X}_3$.

The higher simplices are
increasingly cumbersome to describe, due to our limited
vision of geometry in dimension higher than $3$, but the principle is easy to
follow: just include all information about all possible composites,
and the overall geometric shape is always a geometric $n$-simplex whose
edges are rules, whose $2$-dimensional faces are as in Figure~\ref{fig:r2s}
and whose $3$-dimensional faces are as in Figure~\ref{fig:r3s}.

The fact that in each dimension the bare tracelets contain information
necessary and sufficient to reconstruct the full specified simplex is an expression of the
the central result
of~\cite{behr2019tracelets} that it is indeed tracelets that provide the
minimal carriers of causal information in sequential rule compositions.

We proceed to establish that $\mathbf{X}_\bullet$ is a decomposition space. Since this is
a homotopy invariant property, we may work with the simple version of
groupoids of $n$-tracelets. Before the check, let us just note that
$\mathbf{X}_\bullet$ is
not a Segal space (a category), because of the non-deterministic nature of
composition. Specifically, a $2$-simplex
cannot be reconstructed from knowing its two short edges.

\begin{theorem}
  $\mathbf{X}_\bullet$ is a decomposition space. This means that
  for all $0<i<n$ the
  two squares
\begin{equation}
\ti{htpA}
	\qquad\qquad
\ti{htpB}
\end{equation}
are (homotopy) pullbacks.
\end{theorem}

To check this, it is enough to show that the fibers of the maps pictured
vertically are equivalent. We shall see that indeed all fibers of inner
face maps are canonically identified with the fiber of $d_1: \mathbf{X}_2 \to
\mathbf{X}_1$).

\begin{blanko}{Fiber calculations.}
Consider $d_1 : \mathbf{X}_2 \to \mathbf{X}_1$ which sends a pair of composable rules with
minimal gluing $(r_2,w,r_1)$ to the composite rule $r'$. The fiber over $r'\in
\mathbf{X}_1$ is thus the groupoid of all $(r_2,w,r_1)$ that compose to $r'$. We
denote this groupoid $(\mathbf{X}_2)_{r'}$. Notice that the objects of $\mathbf{X}_2$ are composable pairs of plaquettes with the property that the intermediate point between the two plaquettes is a minimal gluing (of the output of rule $r_1$ with the input of rule $r_2$; said otherwise, the middle cospan in the two-step direct derivation sequence is a pushout of its own pullback).

\end{blanko}

\begin{lemma}\label{lem:hf}
The (homotopy) fiber of $d_i : \mathbf{X}_n
\to \mathbf{X}_{n-1}$ (for $0<i<n$) over a tracelet which in position $i$ has a plaquette with rule $r'$ is equivalent to the groupoid
$(\mathbf{X}_2)_{r'}$. In particular, it does not depend on the whole plaquette $p'$
under $r'$, and it does not depend on the context in any way.
(\emph{Proof:} cf.\ Appendix~\ref{app:proof:lem:hf})
\end{lemma}

One can now unpack the general construction of incidence algebras of
decomposition spaces (cf.\ Appendix~\ref{app:incidencecoalg}) to establish:
\begin{proposition}
  The incidence algebra is the rule algebra of \cite{bp2019-ext}.
\end{proposition}
This algebra is not our main focus in this work. Rather do we regard the
decomposition space $\mathbf{X}_\bullet$ as a stepping stone towards more interesting
decomposition spaces and Hopf algebras, notably the tracelet Hopf algebra.

\section{Decomposition spaces of tracelets}\label{sec:DST}

So far we have defined the decomposition space $\mathbf{X}_\bullet$ of rules, whose
incidence algebra is the rule algebra of \cite{bp2019-ext}. We
now proceed towards Hopf algebras spanned by tracelets.

The Hopf algebra of tracelets should be spanned by iso-classes of
tracelets. Furthermore, we now impose one more restriction on tracelets,
namely that they should be {\em non-degenerate} as simplices of $\mathbf{X}_\bullet$. This means that the rules involved are not
allowed to be the trivial rule.\footnote{By imposing this condition, we account directly for an equivalence relation imposed in \cite{behr2019tracelets} called `equivalence up to trivial tracelets' (cf.\ Definition~\ref{def:nfe}).}
The non-degenerate simplices of $\mathbf{X}_\bullet$ do not form a simplicial object, since
inner faces of non-degenerate simplices are not always non-degenerate, but
the outer face maps survive (as a consequence of the decomposition-space
axioms), so as to define a presheaf
$$
\overarrow \mathbf{X}_\bullet: \mathbbe{\Delta}_{\text{inert}}^{\text{{\rm{op}}}}\to\kat{Grpd} .
$$
Left Kan extension along
the inclusion functor $j: \mathbbe{\Delta}_{\text{inert}} \to \mathbbe{\Delta}$
defines a new simplicial groupoid:
$$
\mathbf{Y}_\bullet := j_! \overarrow \mathbf{X}_\bullet \ : \ \mathbbe{\Delta}^{\text{{\rm{op}}}}\to\kat{Grpd} .
$$
This is a general construction that makes sense for any (complete)
decomposition space, and by a result of Hackney and
Kock~\cite{Hackney-Kock} it always produces a decomposition space again.
Furthermore, one can expand explicitly what its simplices are:
$$
\mathbf{Y}_k = \sum_{\alpha:[k] \rightarrow\Mapsfromchar [n]} \overarrow \mathbf{X}_n .
$$
(The sum is over active maps, cf.\ Appendix~\ref{app:actandinertmaps}.)
In particular
$$
\mathbf{Y}_0 = \mathbf{X}_0 \qquad \text{and} \qquad \mathbf{Y}_1 = \sum_{n\in \mathbb{N}} \overarrow \mathbf{X}_n .
$$
So the new $1$-simplices are the non-degenerate tracelets of any length.
The higher simplices are `subdivided tracelets'. To see this, recall that
the decomposition space axioms can be written  (cf.\ \cite[Prop. 6.9]{Galvez-Kock-Tonks151207573}) as saying that for any
active map $\alpha:[k] \rightarrow\Mapsfromchar [n]$ the canonical square
\begin{equation}
\ti{nkCanonical}
\end{equation}
is a pullback.
Here the vertical maps are active and the horizontal maps are combinations
of inert maps.  What the condition says is that it is possible to glue
together $k$ simplices (of different dimensions $n_i$) if just one has
available a `mould' to glue them together in, namely a $k$-simplex whose
$k$ principal edges match the long edges of the $k$ simplices.
(This is also the essence of the very definition of tracelet.)

An example of such a composition is depicted in Figure~\ref{fig:rds3-prepA}, in which a length $2$ tracelet (depicted as the $2$-simplex 012) is composed along the short edge 02 of the $2$-simplex 023 with a tracelet of length $1$ (here depicted as the edge 23). Figure~\ref{fig:rds3-prepB} then depicts the method for computing the resulting tracelet of length $3$, which itself is depicted in Figure~\ref{fig:rTot}.

Since non-degeneracy in a decomposition space can be measured on principal
edges (cf.\ \cite{Galvez-Kock-Tonks151207577}), we also have the pullback
\begin{equation}
\ti{nkCanonicalND}
\end{equation}
We see that a $k$-simplex in $\mathbf{Y}_\bullet$ is the data of a tracelet $\tau$ of length $k$
(not necessarily non-degenerate) together with a non-degenerate tracelet
$\sigma_i$
glued onto each of the principal edges of this base tracelet along their
evaluation. (That is, the rule given by evaluating the tracelet $\sigma_i$ must match
the rule corresponding to the $i$th principal edge of $\tau$.)

The corresponding algebra, given by the standard incidence algebra construction  (cf.\ Appendix~\ref{app:incidencecoalg}),  is spanned by isomorphism classes of non-degenerate
tracelets, and the product of two tracelets is given by summing over
all possible tracelet composites.

\bigskip

We now proceed to extend this structure into a Hopf algebra.
This is not straightforward, because it is easy to see that the decomposition space
$\mathbf{Y}_\bullet$ is not monoidal under sum.  A monoidal structure exists in degree $1$, by
declaring the product of two tracelets to be the composite along trivial
overlap:
$$
T \odot T' :=
\TcompGT{T}{\emptyset}{T'}{} .
$$
But this definition is not compatible with higher simplices.

Our task is now to explain how this is fixed in a canonical
way.
The solution amounts to imposing the so-called {\em shift equivalence}
relation on tracelets, an equivalence relation already important in the
theory. In the graphical
interpretation it is about saying that for tracelets that are not
connected, it should make no difference in which order they are applied.
After passing to this equivalence relation, the monoidal structure $\odot$
will be well defined in all simplicial degrees. This final symmetric
monoidal decomposition space of tracelets up to shift-equivalence will be
denoted $\mathbf{Z}_\bullet$. We shall go deeper into the notion of shift equivalence in
Section~\ref{sec:Hopf} (and interested reader are referred
to~\cite{bp2018,nbSqPO2019,Behr2021compositionality}
for the full background information and details).
Here we just state the following proposition, which gives an alternative
approach to shift equivalence.

A {\em splitting vertex} of a tracelet is an inner vertex for which the corresponding rule
overlap is trivial.
This property is invariant
under precomposition with active maps. (That is, if $\sigma' = g(\sigma)$
for $g$ an active map not eliminating vertex $v$, then $v$ is splitting for
$\sigma'$ if and only if it is splitting for $\sigma$.) Second, there are
expected transitive properties in connection with `stages' in the sense of
higher-order simplices of $\mathbf{Y}_\bullet$.
Note that this transitive property does {\em not} imply that
irreducibility is compatible with inert maps (outer face maps).

A non-degenerate tracelet $T \in \mathbf{Y}_1 = \sum_n \overarrow \mathbf{X}_n$ is {\em
primitive} if it does not admit any splitting. (A higher-dimensional
simplex $\sigma\in\mathbf{Y}_k$ (that is a subdivided tracelet) is primitive if its long edge is
primitive in $\mathbf{Y}_1 = \sum_n \overarrow \mathbf{X}_n$ (that is, its underlying tracelet
is primitive).)

\begin{lemma}
Every maximal splitting of a given simplex has, up to isomorphism and permutation, the
same primitive pieces.
\end{lemma}

\begin{proposition}
  Tracelets are shift-equivalent in the restricted sense of trivial overlaps if and only if they have the same factorization into primitives.
\end{proposition}

\begin{proposition}
  Shift-equivalence is compatible with the simplicial structure. This
  defines a simplicial groupoid $\mathbf{Z}_\bullet$ with $\mathbf{Z}_k = \mathbf{Y}_k/\sim$. This
  simplicial groupoid is a (locally finite) decomposition space.
\end{proposition}

Note that if $\widetilde \mathbf{Y}_n$ denotes the groupoid of shift-equivalence
classes, then we have
$$
\mathbf{Z}_k = \sum_{[k] \rightarrow\Mapsfromchar [n]} \mathbf{Y}_k \times_{\mathbf{X}_1^k} \big(\widetilde{\mathbf{Y}}_{n_1}
\times\cdots\times \widetilde{\mathbf{Y}}_{n_k}
\big)
$$
This makes sense: in the fiber product, the maps from the factors
$\widetilde{\mathbf{Y}}_{n_i}$ return the long edge, which is invariant under
shift-equivalence.

\begin{theorem} There is a level-wise equivalence of groupoids
$$
\mathbf{Z}_k \simeq \mathsf{S}(\mathbf{Y}_k^{\operatorname{irr}}) ,
$$
assembling into an equivalence of simplicial groupoids.
In particular, $\mathbf{Z}_\bullet$ is symmetric monoidal under $\odot$.
\end{theorem}

Note that the primitive tracelets themselves do not form a simplicial
groupoid. Only the active maps are well defined. The outer face maps
applied to an primitive tracelet is not necessarily primitive. (Said in
another way, a splitting vertex of a face might not be splitting for the
whole simplex.) But after we apply $\mathsf{S}$ (the
free-symmetric-monoidal-category monad), which is just a fancy way of
saying `monomials of' or `families of', it does work.\footnote{Note how
this is analogous to the decomposition space of
forests~\cite{Galvez-Kock-Tonks170802570}: every forest is of course a
disjoint union of trees, but the top face of a tree is not in general a
tree, only a forest.
}

The upshot is now that the standard incidence algebra construction (cf.\ Appendix~\ref{app:incidencecoalg}) yields a Hopf algebra $H$ of tracelets up
to shift equivalence. %
This is the Hopf algebra we are really interested in, and towards which
the previous ones were preliminary constructions. By
Poincar\'e--Birkhoff--Witt, $H$ is the enveloping algebra of the Lie
algebra of primitive tracelets. In the next section we spell out the structure maps of this Hopf algebra
in details.

\section{The Hopf algebra of tracelets}
\label{sec:Hopf}

Independently of the constructions of decomposition spaces presented in the
preceding sections, it is possible to construct the tracelet Hopf algebra
via an extension of the rule diagram Hopf algebra construction
of~\cite{bdgh2016} (which was based upon relational calculus) into the
category-theoretical setting provided by tracelet theory. The readers more
familiar with rewriting theory might appreciate however that the
constructions presented in this section, while perhaps somewhat ad hoc at
first sight, have a clear interpretation from decomposition space theory.
Throughout this section, we fix a field $\bK$ that will typically be chosen
as either $\bR$ or $\bC$ (or, possibly, $\bQ$). An essential prerequisite
for our Hopf algebra construction is given by the following notions of
equivalence relations.
\begin{blanko}{Shift equivalence (cf.\ \cite{behr2019tracelets}).}\label{def:se} %
Let $\equiv_S$ denote the equivalence relation on $\cT$ defined as the
  reflexive symmetric transitive closure of the relation on pairwise
  composition operations on tracelets: let $T= \TcompGT{T_B}{\mu}{T_A}{}$
  (for some admissible match $\mu=(I_B\leftarrow M\rightarrow O_A)$), and
  denote by $[[T_B]]=(O_B\leftarrow K_B\rightarrow I_B)$ and
  $[[T_A]]=(O_A\leftarrow K_A\rightarrow I_A)$ the evaluations of $T_B$ and
  $T_A$, respectively. Suppose $[[T_B]]$ and $[[T_A]]$ are
  \emph{sequentially independent} in the composition along $\mu$, which
  entails that $M$ is isomorphic to both the pullbacks of the cospans
  $K_B\rightarrow I_B\leftarrow M$ and $M\rightarrow O_A\leftarrow K_A$,
  respectively. In this situation we define the composite tracelet $\overline{T}=
  \TcompGT{T_A}{\overline{\mu}}{T_B}{}$ (for $\overline{\mu}=I_A\leftarrow
  M\rightarrow O_B$) to be \emph{shift equivalent} to the tracelet $T=
  \TcompGT{T_B}{\mu}{T_A}{}$.
\end{blanko}

\begin{blanko}{Normal form equivalence (cf.\ \cite{behr2019tracelets}).}\label{def:nfe} %
Let $\equiv_A$ denote an equivalence relation on $\cT$ (so-called
  \emph{abstraction equivalence}) whereby $T\equiv_A T'$ iff $T$ and $T'$
  are tracelets of the same length, and if moreover there exists an
  isomorphism $T\xrightarrow{\cong}T'$ (induced from isomorphisms on
  objects so that the resulting diagram commutes). Let $\equiv_T$ be
  defined as the reflexive symmetric transitive closure of a relation
  whereby for any $T\in \cT$, we let $T\equiv_T T\uplus T_{\mathop{\varnothing}}\equiv_T
  T_{\mathop{\varnothing}}\uplus T$ (with $T_{\mathop{\varnothing}}:=T(\mathop{\varnothing}\leftarrow\mathop{\varnothing}\rightarrow
  \mathop{\varnothing})\in \cT_1$, and where $\uplus:=\TcompGT{}{\mu_{\mathop{\varnothing}}}{}{}$ denotes tracelet composition along trivial overlap). Then we define the \emph{tracelet normal form}
  equivalence relation as
  $\equiv_N:=rst(\equiv_A\cup\equiv_T\cup\equiv_S)$, i.e., as the reflexive
  transitive closure of the union of the aforementioned three relations.
\end{blanko}

\begin{definition}[Primitive tracelets]
  Denote by $\mathfrak{Prim}(\cT_N)$ the set of \emph{primitive tracelets}, defined as
  \begin{equation}
    \mathfrak{Prim}(\cT_N):=\{ [T]_{\equiv_N}\vert T\neq T_{\mathop{\varnothing}}\land \not \exists T_A,T_B\neq T_{\mathop{\varnothing}}: T\equiv_N T_A\uplus T_B\}\,.
  \end{equation}
\end{definition}
Primitive tracelets play a central role in our construction, since they are in a certain sense the smallest ``indecomposable'' building blocks of tracelets with respect to (de-)composition (just as primitive \emph{rule diagrams} in~\cite{bdgh2016}).

\begin{proposition}[Tracelet normal form]\label{prop:TNF}
  Every tracelet $T\in\cT$ is $\equiv_N$-equivalent to a \emph{tracelet
  normal form} in the sense that $T_{\mathop{\varnothing}}\equiv_N T_{\mathop{\varnothing}}$, and\footnote{We chose to make the case distinction explicit in order to emphasize that the normal form of a non-trivial tracelet $T\neq T_{\mathop{\varnothing}}$ does itself not contain trivial sub-tracelets, such that manifestly $T_i\in \mathfrak{Prim}(\cT_N)$ in $T\equiv_N \uplus_{i\in I}T_i$. This is clearly the case, since invoking $\equiv_T$ on $\uplus_{i\in I}T_i$ would in effect remove any trivial constituent $T_i=T_{\mathop{\varnothing}}$.} $\forall T\neq T_{\mathop{\varnothing}}:\quad T\equiv_N \biguplus_{i\in I}T_i$, where $T_i\in \mathfrak{Prim}(\cT_N)$ for all $i\in I$, and with $I$ a (finite) index set. (\emph{Proof:} cf.\ Appendix~\ref{app:proof:prop:TNF})
\end{proposition}

\begin{definition}[Tracelet $\bK$-vector space $\hat{\cT}$]
  Let $\hat{\cT}$ be the $\bK$-vector space spanned by a basis indexed by
  $\equiv_N$-equivalence classes, in the sense that there exists an
  isomorphism $\delta:\cT_N \isopil basis(\hat{\cT})$ from the
  set\footnote{Here, we tacitly assume that the $\equiv_N$-equivalence
  classes indeed form a proper \emph{set}, which is in all known
  applications the case since abstraction equivalence $\equiv_A$ is part of
  the definition of $\equiv_N$. For example, it is well known that
  isomorphism classes of finite directed multigraphs indeed form a set.} of
  $\equiv_N$-equivalence classes of tracelets $\cT_N:=\cT\diagup_{\equiv_N}$
  to the set of basis vectors of $basis(\hat{\cT})$. We will use the
  notation $\hat{T}:=\delta(T)$ for the basis vector associated to some
  class $T\in \cT_N$. We denote by $Prim(\hat{\cT})\subset\hat{\cT}$ the sub-vector space of $\hat{\cT}$ spanned by basis vectors indexed by primitive tracelets.
\end{definition}

\begin{definition}[Tracelet algebra product and unit]
Let $\otimes\equiv \otimes_{\bK}$ be the tensor product operation on the $\bK$-vector space $\hat{\cT}$. Then the \emph{multiplication map} $\mu$ and the \emph{unit map} $\eta:\bK\rightarrow \hat{\cT}$ are defined via their action on basis vectors of $\hat{\cT}$ as follows:
  \begin{align}
  \begin{split}
  \mu&:\hat{\cT}\otimes \hat{\cT}\rightarrow \hat{\cT}: \hat{T}\otimes\hat{T}'\mapsto \tapGT{\hat{T}}{\hat{T}'}{}\,,\qquad
    \tapGT{\hat{T}}{\hat{T}'}{}
    :=\sum_{\mu\in \tMatchGT{T}{T'}{}}\delta\left(\left[
      \TcompGT{T}{\mu}{T'}{}
    \right]_{\equiv_N}
    \right)
  \end{split}\\
  \eta&:\bK\rightarrow \hat{\cT}: k\mapsto k\cdot \hat{T}_{\mathop{\varnothing}}\,.
  \end{align}
  Both definitions are suitably extended by (bi-)linearity to generic (pairs of) elements of $\hat{\cT}$.
\end{definition}

\begin{proposition}\label{prop:TraceletAlgebra}
  The morphisms $\mu$ and $\eta$ give rise to an \emph{associative, unital $\bK$-algebra} $(\hat{\cT},\mu,\eta)$, which we refer to as \emph{tracelet algebra}. (\emph{Proof:} cf.\ Appendix~\ref{app:proof:prop:TraceletAlgebra})
\end{proposition}

\begin{definition}[Tracelet coproduct and counit]
  Fixing the \emph{notational convention} $\uplus_{i\in\emptyset}T_i:=T_{\mathop{\varnothing}}$ for later convenience, let $T\equiv_N \uplus_{i\in I}T_i$ be the tracelet normal form for a given tracelet $T\in\cT$ (where $T_i\in \mathfrak{Prim}(\cT_N)$ for all $i\in I$ if $T\neq T_{\mathop{\varnothing}}$). Then the \emph{tracelet coproduct} $\Delta$ and \emph{tracelet counit} $\varepsilon$ are defined via their action on basis vectors $\hat{T}=\delta(T)$ of $\hat{\cT}$ as
  \begin{align}
    \Delta&: \hat{\cT}\rightarrow \hat{\cT}\otimes \hat{\cT}:\hat{T}\mapsto
    \Delta(\hat{T}):=\sum_{X\subset I}\delta\left(\left[\uplus_{x\in X}T_x\right]_{\equiv_N}\right)\otimes\delta\left(\left[\uplus_{y\in I\setminus X}T_x\right]_{\equiv_N}\right)
  \end{align}%
and $\varepsilon:\hat{\cT}\rightarrow \bK: \hat{T}\mapsto coeff_{\hat{T}_{\mathop{\varnothing}}}(\hat{T})$. Both definitions are extended by linearity to generic elements of $\hat{\cT}$.
\end{definition}

\begin{proposition}
    The data $(\hat{\cT},\Delta,\varepsilon)$ defines a \emph{coassociative, cocommutative and counital coalgebra}.
\end{proposition}
\begin{proof}
  Since the construction of $\Delta$ and $\varepsilon$ is the standard construction for a deconcatenation coalgebra (cf.\ e.g.\ \cite{manchon2008hopf}), the proof is omitted here for brevity.
\end{proof}

The algebra and coalgebra structures on $\hat{\cT}$ are compatible in the following sense:

\begin{theorem}[Bialgebra structure]\label{thm:Tbialg}
  The data $(\hat{\cT},\mu,\eta,\Delta,\varepsilon)$ defines a
  \emph{bialgebra}. (\emph{Proof:} cf.\
  Appendix~\ref{app:proof:thm:Tbialg})
\end{theorem}

By virtue of the definition of the tracelet normal form, it is evident that
both composition and decomposition of tracelets is compatible with a
filtration structure given by number of ``connected components''
in the following sense:
\begin{theorem}\label{thm:Tfiltration}
The tracelet bialgebra $(\hat{\cT},\mu,\eta,\Delta,\varepsilon)$ is \emph{connected and filtered}, with connected component $\hat{\cT}^{(0)}:=span_{\bK}\{\hat{T}_{\mathop{\varnothing}}\}$, and with the higher components of the filtration given by the subspaces
\begin{equation}
\forall n>0:\quad \hat{\cT}^{(n)}:=span_{\bK}\left.\left\{
\hat{T}_1\uplus\dotsc\uplus \hat{T}_n
\right\vert \hat{T}_1,\dotsc,\hat{T}_n\in Prim(\hat{\cT})
\right\}\,,
\end{equation}
where in a slight abuse of notations $\hat{T}_1\uplus\dotsc\uplus\hat{T}_n:=\delta(T_1\uplus\dotsc\uplus T_n)$ (\emph{Proof:} cf.\ Appendix~\ref{app:proof:thm:Tfiltration})
\end{theorem}

Utilizing results from the general theory of Hopf algebras (cf.\ e.g.\
\cite{manchon2008hopf} for an excellent review), we finally obtain
one of the central results of the present paper:

\begin{theorem}[Compare~\cite{bdgh2016}, Sec.~3.4 and Thm.~3.2]
The tracelet bialgebra $(\hat{\cT},\mu,\eta,\Delta,\varepsilon)$ admits the structure of a \emph{Hopf algebra}, where the \emph{antipode} $S$, which is to say the endomorphism of $\hat{\cT}$ that makes the diagram below commute,
\begin{equation}
\ti{antipode}
\end{equation}
is given by $S:=Id^{\star^{-1}}$. The latter denotes the inverse of the identity morphism $Id:\hat{\cT}\rightarrow \hat{\cT}$ under the \emph{convolution product} $\star$ of linear endomorphisms on $\hat{\cT}$. More concretely, letting $e:=\eta\circ \varepsilon$ denote the unit for the convolution product $\star$,
\begin{equation}
S(\hat{T})=Id^{\star^{-1}}(\hat{T})=(e-(e-Id))^{\star^{-1}}=e(\hat{T})+\sum_{k\geq 1}(e-Id)^{\star\:k}(\hat{T}).
\end{equation}
\end{theorem}
It might be instructive to compute the action of the coproduct and of the
antipode on tracelets of low filtration degree. To this end, in the
equations below let $\hat{T}_i\in Prim(\hat{\cT})$ denote primitive elements of $\hat{\cT}$.
\begin{equation}
\begin{aligned}
\Delta(\hat{T}_{\mathop{\varnothing}})&=\hat{T}_{\mathop{\varnothing}}\otimes \hat{T}_{\mathop{\varnothing}}
&\qquad
S(\hat{T}_{\mathop{\varnothing}})&=\hat{T}_{\mathop{\varnothing}}\\
\Delta(\hat{T}_1)&=\hat{T}_{\mathop{\varnothing}}\otimes \hat{T}_1+\hat{T}_1\otimes\hat{T}_{\mathop{\varnothing}}
&
S(\hat{T}_1)&=-\hat{T}_1\\
\Delta(\hat{T}=\hat{T}_1\uplus \hat{T}_2)&=\hat{T}_{\mathop{\varnothing}}\otimes \hat{T}+\hat{T}\otimes\hat{T}_{\mathop{\varnothing}} +\hat{T}_1\otimes \hat{T}_2+\hat{T}_2\otimes \hat{T}_1
&
S(\hat{T}_1\uplus \hat{T}_2)&=\tapGT{\hat{T}_1}{\hat{T}_2}{}+\tapGT{\hat{T}_2}{\hat{T}_1}{}-\hat{T}_1\uplus \hat{T}_2
\end{aligned}
\end{equation}

Finally, yet again taking inspiration from~\cite{bdgh2016}, one may demonstrate that the tracelet Hopf algebra is isomorphic to a Hopf algebra that is well-known in the setting of the Heisenberg-Weyl diagram Hopf algebra and the Poincar\'{e}-Birkhoff-Witt theorem for ``normal-ordering'' of elements of the Hopf algebra:
\begin{theorem}
Let $\cL_{\cT}:=(Prim(\hat{\cT}),[.,.]_{\diamond})$ denote the \emph{tracelet Lie algebra}, where $[\hat{T},\hat{T}']_{\diamond}:=\hat{T}\diamond\hat{T}'-\hat{T}'\diamond\hat{T}$ is the \emph{commutator operation} (w.r.t.\ $\diamond$). Then the tracelet Hopf algebra is isomorphic (in the sense of Hopf algebra isomorphisms) to the \emph{universal enveloping algebra} of $\cL_{\cT}$.
\end{theorem}

\begin{figure}
\centering
\subfigure[1-simplices\label{fig:r1s}]{
\href{http://nicolasbehr.com/files/asymptote3d/RDS1simplex.html}{%
\includegraphics[scale =0.75]{images/RDS-1simplex}}
}$\qquad\qquad$ \subfigure[2-simplices\label{fig:r2s}]{
\href{http://nicolasbehr.com/files/asymptote3d/RDS2simplex.html}{%
\includegraphics[scale =0.75]{images/RDS-2simplex}}
}\\
\subfigure[From adjacent 2-simplices\ldots \label{fig:rds3-prepA}]{
\href{http://nicolasbehr.com/files/asymptote3d/RDS2to3simplexA.html}{%
\includegraphics[scale =0.75]{images/RDS-2-to-3simplex-A}}
}$\qquad\qquad$ \subfigure[\ldots via the Concurrency Theorem\ldots\label{fig:rds3-prepB}]{
\href{http://nicolasbehr.com/files/asymptote3d/RDS2to3simplexB.html}{%
\includegraphics[scale =0.75]{images/RDS-2-to-3simplex-B}}
}\\
\subfigure[\ldots to 3-simplices.\label{fig:r3s}]{
\href{http://nicolasbehr.com/files/asymptote3d/RDS3simplex.html}{%
\includegraphics[scale =0.75]{images/RDS-3simplex}}
}$\qquad\qquad$ \subfigure[Tracelets of length 3 and evaluation\label{fig:rTot}]{
\href{http://nicolasbehr.com/files/asymptote3d/Tracelet-3simplex-and-evaluation.html}{%
\includegraphics[scale =0.75]{images/Tracelet-3simplex-and-evaluation}}
}
\caption{Elements of Tracelet Decomposition Space theory (\emph{Note:} in order to allow for a more in-detail inspection, the figures are hyperlinked to on-line interactive 3D views of the respective diagrams).}
\end{figure}


\section*{Introduction}
\label{sec1}
To date (May 2021),  more than one hundred millions of individuals have been reported as affected by COVID-19. More than two millions deaths have been ascribed to the infection. All over the world, the sheer numbers of the pandemic pose a heavy burden on emergency departments, hospitals, intensive care units and local medical assistance. From the beginning of the infection, it was apparent that COVID-19 encompasses a wide spectrum of both clinical presentations and consequent prognosis, with cases of sudden, unexpected evolution (and worsening) of the clinical and radiological picture \cite{struyf2020signs}. Such elements of variability and instability are still not fully explained, with an important role advocated for a multiplicity of pathophysiological processes  \cite{gupta2020extrapulmonary,li2020sars,wiersinga2020pathophysiology}. In this context, it would be natural to try to exploit techniques of artificial intelligence, fueled by the availability of large data amounts, to support clinicians. Indeed, a large number of efforts in this sense has
already been done, headed on different tasks, in particular diagnosis and
prognosis \cite{tayarani2020applications}. We focused on the latter, taking into account in particular
clinical usability.
We defined as our goal to build an hybrid machine learning/deep learning severity predictive model that can act as an auxiliary tool for patient risk assessing in clinical practice.
In order to accomplish the objective, we considered essential the combination of
imaging and non-imaging data. We chose to exploit a Convolutional Neural Network (CNN) as feature extractor, and CatBoost, a last generation gradient boosting model, as classifier of tabular
data \cite{prokhorenkova2018catboost,dorogush2018catboost}.
The proposed model is represented graphically in Fig. \ref{fig:graphabs}.
The output of the model is both the percentage
score of the outcome and the SHAP (SHapley Additive exPlanations)
evaluation of feature
importance in the individual
prediction \cite{lundberg2017unified, lundberg2018explainable}.
In this way, both synthetic and analytic information are provided to the
judgement of the clinician.
\begin{figure*}
\centering
\includegraphics[width=5 in]{figure1.pdf}
\caption{A graphical representation of the proposed model.}
\label{fig:graphabs}
\end{figure*}
\section*{Methods}
\label{sec2}
\subsection*{Patients and dataset}
\label{subsec2.1}
The dataset for this retrospective study consists of patients admitted to Fondazione Poliambulanza Istituto\\Ospedaliero (Brescia, Italy) between February 20, 2020 and May 6,
2020 with confirmed diagnosis of COVID-19. The hospital was at the forefront of fighting the disease outbreak in northern Italy in the first months of 2020. Diagnosis was made via nasopharyngeal swab analyzed through
 the Reverse Transcriptase-Polymerase Chain Reaction, RT-PCR.
Patients with baseline thoracic CT images,
 arterial blood gas analysis data, total blood counts and
 Lactate Dehydrogenase test (LDH) were considered for this study. This last has been  chosen as inclusion criterion due to his  effectivess as inflammatory biomarker for COVID-19 \cite{aloisio2020comprehensive,chen2020lactate}.
We chose a binary outcome in two severity classes, evaluated at dimission,
 defined as follows:
\begin{enumerate}
    \item ICU class: death or intensive care unit admission;
    \item Non-ICU class: patients discharged as healed or transferred to non-COVID
      wards for further care.
\end{enumerate}
We excluded patients for which outcome reconstruction was uncertain (e.g. due to early transferral to other hospitals or care structures).
 A total of 558 patients met these criteria. Fig. \ref{fig:flowchart} shows the flowchart of patients selection.
 Variables missing in more than 20\% of cases were excluded, even if their predictive efficacy has been advocated,
e.g. D-dimer \cite{lippi2020d}, Interleuchin-6 \cite{mcelvaney2020characterization}. Variables obviously redundant were merged (e.g. differential white cells count in
percent and absolute values). The 40
variables selected are shown in Table \ref{table:nonimagingdata}. Fig. \ref{fig:distributionplots} shows the respective
distribution of LDH and  $\rm {PaO_2/FiO_2}$  for both outcome classes. Deviations from normality are apparent for both classes.\\ The study has been approved by the ethical committee of Brescia (protocol number NP 4274 STUDIO GBDLCovid, session of 06/04/2021).
All methods were carried out in accordance with relevant guidelines and regulations. Informed consent collection or its waiving where not possible were conducted in agreement with the aforementioned protocol.

\begin{figure}[htb]
\centering
\includegraphics[scale=.3]{figure2.jpg}
\caption{Flowchart of patients inclusion/exclusion.}
\label{fig:flowchart}
\end{figure}
\begin{figure*}
\centering
\includegraphics[scale=0.3]{figure3a.pdf}\quad\includegraphics[scale=0.3]{figure3b.pdf}
\caption{Distributions of Lactic Acid Dehydrogenase and $ \rm{PaO_2/FiO_2}$ for patients in Non-ICU (gray) and ICU (red) severity classes. Yellow area is normal value range. Mean and median values are also indicated.}
\label{fig:distributionplots}
\end{figure*}
\begin{table*}

\caption{\label{table:nonimagingdata}Summary of clinical and laboratory variables used.}

\centering
\footnotesize
\resizebox{\textwidth}{!}{%

\begin{tabular}{|l|ccccc|}
\hline

\multicolumn{6}{|l|}{\bf{Binary}}\\
\hline

\hline

\multicolumn{2}{|l}{Variable}&   Total & Non-ICU &
ICU &\\
\hline

\hline
Sex &&
F=166 M=392 &
F=121\ M=259 &
F=45\ M=133 &\\

Diabetes &&
Y=131\ N=427 &
Y=80\ N=300 &
Y=51\ N=127 &\\

Hypertension &&
Y=255\ N=303 &
Y=165\ N=215 &
Y=90\ N=88 &\\

Cardiovascular Disease &&
Y=263\ N=295 &
Y=164\ N=216 &
Y=99\ N=79 &\\

Oncological (last 5 yrs) &&
Y=41\ N=517 &
Y=33\ N=347 &
Y=8\ N=170 &\\

\hline
\multicolumn{6}{|l|}{}\\
\hline
\multicolumn{6}{|l|}{\bf{Numerical}}\\
\hline

\hline

Variable& Measure Unit&  Median & Median: Non-ICU &
Median: ICU & Reference range\\
\hline

\hline
Age & yrs &
66 &
64 &
69 &\\
Body Mass Index (BMI) & &
26 &
25.9 &
26 &\\

Body Temperature & \degree C&
37.5 &
37.4 &
37.7 &
$<$ 37\\

Heart Rate (HR) & bpm &
92&
92 &
90 &
60-100\\

Diastolic Blood Pressure (DBP) & mmHg &
76 &
77 &
75 &
60-80\\

Systolic Blood Pressure (SBP) & mmHg &
127 &
127 &
127 &
90-120\\

\hline
\multicolumn{6}{|l|}{\it{Arterial Blood Gas Analysis}}\\
\hline
$\rm pCO_2$  & mmHg &
36 &
35 &
39 &
35-48\\

$\rm HCO_3$  & mmol/L &
25.4 &
25.4 &
25.4 &
21-28\\

$\rm PaO_2/FiO_2$  & mmHg &
255 &
277 &
134 &
$\geq$ 300\\

Lactate (LAC)  & mmol/L &
1.1 &
1.0 &
1.3 &
0.5-1.6\\

SO$_{2}$  & \% &
94 &
94.5 &
91.8 &
95-99\\

\hline
\multicolumn{6}{|l|}{\it{Complete Blood Count}}\\
\hline

White Blood Cell Count (WBC) & $\cdot 10^{9}/L$ &
7 &
6.6  &
8.3 &
4.5-10\\

Red Blood Cell Count (RBC) & $\cdot 10^{12}/L$ &
4.3 &
4.4 &
4.3 &
4.2-6.3\\

Hemoglobin (Hb) & g/dL &
13.1 &
13.2 &
13 &
14-18\\

Hematocrit (HCT) & \% &
39.8 &
39.8 &
39.6 &
40-52\\

Red Blood Cell Distribution Width (RDW) & \% &
12.3 &
12.1 &
12.6 &
10.6-13.8\\

Granulocyte Neutrophils \% & \% &
78 &
75 &
84.7 &
41-70\\

Granulocyte Eosinophils \% & \% &
0.2 &
0.2 &
0.2 &
1-5\\

Granulocyte Basophils \% & \% &
0.2 &
0.3 &
0.2 &
0.1-2\\

Monocytes \% & \% &
6.5 &
7.4 &
5 &
1-12\\

Lymphocytes \% & \% &
14.2 &
16.6 &
9.4 &
20-50\\

Platelets (PLT) & $ \cdot 10^{9}/L$ &
189 &
198 &
176 &
130-450 \\

\hline
\multicolumn{6}{|l|}{\it{Additional Blood / Laboratory Analysis}}\\
\hline

Erythrocyte Sedimentation Rate (ESR) & mm/hour &
5.5 &
5.4 &
5.6 &
\it{variable}\\

C-reactive Protein (CRP)  & mg/L &
92 &
71 &
151 &
$<$ 5 \\

Albumin  & g/dL &
3.2 &
3.3 &
3.2 &
3.1-5.2\\

Prothrombin Time International Normalized Ratio (PT INR)  & &
1 &
1 &
1.1 &
0.8-1.2\\

Aspartate Aminotransferase (AST)  & U/L &
46 &
43 &
55 &
$<$ 60\\

Alanine Aminotransferase (ALT)  & U/L &
34 &
33 &
35 &
$<$ 35\\

Total Bilirubin  & mg/dL &
0.7 &
0.6 &
0.7 & $<$ 1.2 \\

Creatine kinase (CK) & U/L &
102 &
86 &
163 &
30-200\\

Lactic Acid Dehydrogenase (LDH)  & U/L &
388 &
343 &
505 &
125-220\\

Sodium & mmol/L &
140 &
140 &
140 &
136-145\\

Potassium  & mmol/L &
4.1 &
4.1 &
4.1 &
3.3-5.1\\

Creatinine  & mg/dL &
0.84 &
0.8 &
0.96 &
0.72-1.18 \\

Urea  & mg/dL &
38 &
34 &
47 &
18-55\\

\hline
\end{tabular}%
}

\end{table*}

\subsection*{CT acquisition protocols}
\label{subsec2.2}
Chest CT were acquired using two 64 slices scanners Optima
CT 660 (GE Medical Systems, Milwaukee, USA). All patients were
examined in supine position. Four different acquisition protocols were used (see Table \ref{table:CTprot}). For all protocols, tube voltage was 120 kVp and automatic current modulation was used. The reconstruction algorithm were mixed filtered back projections-iterative (ASIR), usually with different proportions for the same acquisition (e.g. lung, bone and parenchyma optimized).

\begin{table}[ht!]
\caption{\label{table:CTprot} CT acquisition protocols}
\begin{tabular}{|l|cccc|}
\hline
Protocol & \#1&\#2&\#3&\#4 \\

\hline

\hline
 \% of cases  &  70 \%& 20 \%& 7 \%& 3 \% \\

 Transverse resolution (mm) & 0.765& 0.765& 0.765& 0.765\\

 Slice width (mm) &2.5&1.25&2.5&2.5\\

 Slice spacing (mm) &2.5&1.25&0.625&1.1\\

 Pitch &1.375&0.969&1.375&0.984\\
\hline
\end{tabular}
\end{table}

\subsection*{Image preprocessing}
\label{subsec2.3}
All CT scans were transformed with bicubic interpolation to a common spatial resolution of 1.625 mm $\times$ 1.625 mm $\times$ 2.5 mm. A rigid registration to a single CT picked as representative was performed in order to minimize small patient positioning differences.
A lung mask was created on the basis of non-rigid method registration of a known CT with lung mask to the target CT \cite{sluimer2005toward,liauchuk2017imageclef}.
Once masked images were produced, a volume of size
160$\times$160$\times$240 was obtained with zero-padding. At this point,
different reconstructions for the same CT scans were merged (mean values were
used), obtaining
one single baseline volumetric image for each patient. The images were then z-normalized (subtracting means and dividing by standard deviation).

\subsection*{Tabular missing data}
\label{subsec2.4}
Non-imaging missing data have been replaced with median imputation. In order to avoid knowledge leakage, median imputation was always performed after test/ validation/ training split.

\subsection*{Model overview}
\label{subsec2.5}
The proposed model is composed as follows:
\begin{itemize}
    \item a fully 3D CNN patient-level classifier on CT images;
    \item feature extraction from the last Fully Connected Layer of the CNN;
    \item  a dimensionality reduction procedure including Principal Component Analysis (PCA) on extracted image features, a preliminary CatBoost model and the Boruta algorithm with the SHAP feature importance as metric (BorutaSHAP, \cite{ekeany_2020_4247618});
    \item  a CatBoost classifier on the reduced feature space.
\end{itemize}
The dataset was split in train/validation and test (holdout) subsets, in a 0.8:0.2 proportion (N$\rm{_{train/valid}}$=451, ICU=147, non-ICU=304 and N$\rm {_{test}}$=107, ICU=31, non-ICU=76, respectively; see Supplementary Table S1 for demographic data of the split). Ten fold stratified cross validation was applied in the train/validation set. The best model was then retrained on the joined training and validation sets and applied to the test
 set. Overall validation strategy is not trivial, due to feature extraction and feature selection steps. In brief, for each fold the validation set is first used for CNN hyperparameters choice and PCA analysis. Once image feature are extracted, we step back to the training set for the BorutaShap feature selection and a reduction of the CatBoost hyperparameter space to be searched. Validation set is again used to pick the best hyperparameter choice for the fold.
 The output of the model is the percentage score of the classification and the SHAP feature importance values at patient level (see Fig. \ref{fig:CrossValidation}).\\
\subsection*{Volumetric convolutional neural network}
\label{subsec2.6}
The first block of the proposed model is a patient-level 3D CNN classifier, with six convolutional layers with ReLU activation followed by max pooling, and three fully connected layers with  a 0.25 dropout, plus a final classification layer. Group normalization is used, due to its better efficacy with small batches \cite{wu2018group}. The loss function is CrossEntropy.
The CNN block is shown in Figure \ref{fig:CNN}.

\begin{figure*}
\centering
\includegraphics[width=\linewidth]{figure4.pdf}
\caption{A representation of the CNN architecture used. Actual model is volumetric, i.e. three spatial dimensions plus  a channels dimension. Green arrows represent convolution operations with stride of 1. A ReLU nonlinear activation is applied after convolutions, and then a 2x2x2 max pooling in order to reduce spatial dimensions. Red arrow represents flattening. Blue arrows are full connections (with a 0.25  dropout), purple arrow stands for the final classifier with Log SoftMax and Cross Entropy loss function.}
\label{fig:CNN}
\end{figure*}
\subsection*{CNN training and data augmentation}
\label{subsec2.7}
Data augmentation was performed in each fold on the fly, only for each training set, in the ten cross validation folds.
Data augmentation techniques used were:
\begin{itemize}
    \item Affine deformation. During every epoch, there was a 50\% of probability to apply a random affine deformation with rotation between 0 to 10 degrees and a size variation up to 10\%.
    \item Elastic deformation. A random displacement was attributed to a grid of
      7$\times$7$\times$7 control points assigned to every images, with a
      maximum displacement equals to 10 voxels in each direction along
      cartesian axes. The displacement at every voxel was interpolated using a
      cubic B-spline function.
 \end{itemize}
All the techniques were implemented using the framework Torchio \cite{perez2020torchio}. Training was performed with the Stochastic Gradient Descent (SGD) optimizer and a fixed learning rate of $3\times 10^{-5}$. The number of epochs was chosen for each training/validation fold on the basis of AUC result on the validation set (the best in a fixed number of 50). For each fold, features at the input of the final classification layer were extracted (40 features).

\subsection*{Dimensionality reduction}
\label{subsec2.8}
 A dimensionality reduction procedure was applied, articulated as follows:
\begin{itemize}
    \item Principal Component Analysis (PCA) of image extracted features (reduction of 40 extracted features to 5 principal components).
    \item Training and hyperparameter optimization of a preliminary CatBoost classifier, with 40 non-imaging features and the 5 imaging features from PCA.
    \item A majority voting multi BorutaSHAP feature selection procedure.
\end{itemize}
All these steps were learned by the training subset, and then applied to validation (and test) subsets.
The usage of PCA to provide an out of the box, unsupervised, dimensionality reduction for CNN extracted features has been already proven effective in hybrid approaches \cite{lin2018convolutional}.  In this work we applied PCA only to CNN extracted image features, that can be considered natively agnostic, while the subsequent feature selection preserves interpretability.
The Boruta algorithm is an all relevant feature selection method, i.e. it tries to select all the features relevant for a given ensemble model. Relevance is evaluated against shadow features, that is dummy features created from real ones with random reordering of values \cite{kursa2010boruta}.
 In the BorutaSHAP Python implementation, features and shadow features are compared by means of their SHAP importance values, producing therefore a result more consistent than other metrics \cite{lundberg2018consistent,hooker2019please}.
The level of feature elimination can be tuned via a (percentile based) multiplicative factor on maximum shadow feature.
The ensemble model used was a preliminary CatBoost classifier, in which we fixed number of trees at 700 and learning rate at double of automatic CatBoost suggestion (so to to reach a quicker convergence).
For other hyperparameters, Bayesian optimization was performed with the automatic optimization framework Optuna 2.3.0 \cite{akiba2019optuna}, with 300 trials (0.8:0.2 calculation/evaluation split).\\
In our dataset, SHAP feature importance tends to have a slowly degrading distribution, except for the two most important features (CT first principal component and PaO$_{2}$/FiO$_{2}$; see Figure \ref{fig:borutashap}). Such a feature importance distribution can show some dependence on random picking of data sample.
 Therefore, in order to increase the robustness of feature selection,  we implemented a nested majority voting feature elimination strategy.\\
 The training subsample was divided in a 7:1 inner training and inner validation sets (with shuffling). A weak BorutaSHAP (85 percentile) feature selector with the preliminary CatBoost model was applied in each fold. Each time, feature importance was evaluated in the inner validation subset. Eight feature choices resulted.
A feature absent in six over eight choices was eliminated.
This procedure was applied to each of the ten training/validation folds (Figure \ref{fig:CrossValidation}).

\begin{figure}[htb]
\centering
\includegraphics[width=4 in]{figure5.pdf}
\caption{A representative BorutaSHAP importance plot. Green are features to keep in the model for this fold. Blue are maximum, mean, median and minimum shadow features.}
\label{fig:borutashap}
\end{figure}

\subsection*{CatBoost model}
\label{subsec2.9}
We built a CatBoost classifier on the reduced feature set, using a two steps procedure for hyperparameters optimization:
\begin{itemize}
    \item Selection of a reduced number of hyperparameter combinations (the
best performing on the training set), with the aid of Bayesian optimization, at fixed learning rate and number of trees.
    \item The selected combinations were compared on the validation set, with a fixed learning rate and a number of trees optimized by the overfitting detector.
    \end{itemize}
The best model was chosen by AUC on its validation subset. It was then retrained on the joined training and validation subset, with a 120\% number of trees in order to keep in account the larger training size. Such final model was evaluated on the test/holdout dataset. A graphical resume of the cross validation and testing procedure is shown in Fig. \ref{fig:CrossValidation}.
The rationale of the procedure is to control the computational burden of hyperparameter search, and at the same time to fully exploit the potential of the overfitting detector for number of trees selection by means of early stopping. In the first step, Bayesian optimization in the training set was performed with the Optuna optimizer, with parameters as in the previous subsection. For the first step, learning rate was fixed at the values automatically calculated by CatBoost on the basis of the number of instances and features.
Models with AUC $\geq$ 0.96 were selected for validation testing (an empirically chosen threshold value).
 In the second step, learning rate was fixed at a constant value of 0.008 (at the lower end of the range of values for the first step). The number of trees was picked with the CatBoost overfitting detector as the best performing on the validation subset, starting with a very large value, 20000. In this way, almost complete freedom is left to the overfitting detector to stop at the best iteration. In practice the final model has fixed learning rate, a Bayesian-optimized combination of hyperparameters, and a number of trees found by the overfitting detector.
 Hyperparameters of the final CatBoost model are reported in Supplementary Table S2.

\begin{figure}[htb]
\centering
\includegraphics[width=4.3 in]{figure6.pdf}
\caption{A sketch of the cross validation procedure with dimensionality reduction. Both Optuna hyperparameter optimization and BorutaSHAP feature selection were computed with inner cross validation in the training set, not represented here.}
\label{fig:CrossValidation}
\end{figure}

\subsection*{Implementation and code availability}
\label{subsec2.10}
The overall model implementation has been made in \\Python 3.7 with open source libraries. In particular the framework PyTorch 1.7 \cite{paszke2019pytorch} has been used for the CNN block. The PC utilized for the training is equipped with a Intel\textsuperscript{\tiny\textregistered} Core\textsuperscript{\tiny TM} i7-8700 CPU (6 cores, 12 threads, 3.2 GHz) and a NVIDIA\textsuperscript{\tiny\textregistered} GeForce\textsuperscript{\tiny\textregistered} RTX 2080 Ti GPU (11 GB memory).
The code is available at\\
 https://github.com/matteochieregato/GradientboostingCovid19.
\section*{Results}
\label{sec3}
\subsection*{CNN results}
\label{subsec3.1}
Results of the CNN classifier in terms of AUC is shown in Figure \ref{fig:CB_CrossVal} for the ten validation subsets. The third validation fold has the best AUC score, 0.889 (mean AUC in the ten folds is 0.806). Non-imaging feature selected by our procedure were consistent between folds. Variation in CNN results are likely to be imputed to the number of patients used for the training, not so large for deep learning.
\begin{figure}[htb]
\centering
\includegraphics[width=3.5 in]{figure7.pdf}
\caption{Cross validation of the CatBoost and CNN classifiers. A roughly common trend can be discerned, however the highest score is reached at different folds (3rd for the CNN and 10th for the CatBoost classifier).}
\label{fig:CB_CrossVal}
\end{figure}
\subsection*{CatBoost predictive power}
\label{subsec3.2}
Classification results of CatBoost in terms of AUC is shown in Fig. \ref{fig:CB_CrossVal} for each of the ten validation subsets (mean AUC = 0.915). The final best model reaches AUC = 0.949 in the test set, with a 95\% confidence interval of 0.899-0.986. The confidence  interval is calculated with the bootstrap method with 10000 folds resampling of the test set. Fig. \ref{fig:ConfMatrix} shows the confusion matrix for the test set (Sensitivity = 83.9\%, Specificity = 93.4\%). Since the model is intended as probabilistic classifier, it is optimized on probabilistic AUC, not on sensitivity and specificity. Setting the threshold for ICU prediction at 0.25 instead of 0.5, sensitivity becomes 90.3\% with a specificity of 89.5\%.

\begin{figure}[htb]
\centering
\includegraphics[width=3.5 in]{figure8.pdf}
\caption{Confusion matrix obtained with the best model on the test set (0 : non-ICU patients and 1 : ICU patients).}
\label{fig:ConfMatrix}
\end{figure}

\subsection*{Feature selection and global level feature importance}
\label{subsec3.3}
Figure \ref{fig:GlobalImportance} shows the 22 features selected by our procedure in the best model, along with SHAP global feature importance in prediction over the test set.
The first CT principal component and the $\rm PaO_{2}/FiO_{2}$ stand out.
\begin{figure}[htb]
\centering
 \includegraphics[width=3.7 in]{figure9.pdf}\par
 \caption{Mean absolute value of the SHAP values for each feature in the test set.}
 \label{fig:GlobalImportance}
\end{figure}

\subsection*{Patient level feature importance}
\label{subsec3.4}
Figure \ref{fig:SinglePatientImportance} shows the SHAP output in terms of feature importance for a single prediction \cite{lundberg2018explainable}. Features are divided in colors and sides corresponding to the outcome to which they pull the prediction to (ICU is red and non-ICU is blue), bar size is which percentage score corresponds to the respective feature.
The case shown is correctly predicted as ICU with an 83\% score.
From the plot it is possible to see that  CT features (1 and 4) and most of parameters contribute to the ICU outcome prediction, despite a $\rm PaO_{2}/FiO_{2}$ ratio higher than most ICU cases (corresponding to mild Acute Respiratory Distress Syndrome, \cite{force2012acute}).

\begin{figure*}
\centering
\includegraphics[width=\textwidth]{figure10.pdf}
\caption{Force plot of SHAP values for single patient. Less important features are omitted for the sake of visualization. 0.83 is the probability of ICU outcome. Features in red contribute positively to such probability, features in blue contribute negatively. More details are in Subsection Model introspection.}
\label{fig:SinglePatientImportance}
\end{figure*}

\subsection*{Model introspection}
\label{subsec3.5}
We analyzed on a case-by-case basis the patients for which the final model gave a wrong prediction, in particular ICU outcomes misclassified as non-ICU. It turned out that for 2 out of such 5 patients in the test set, there were meaningful additional information not taken in account by the model. In one case, there was a full scale D-dimer value (well known as indicator of poor outcome \cite{lippi2020d}). In the other, the patient is insulin-dependent type 1 diabetic. Diabetes comorbidity was eliminated by the feature selection procedure. Indeed, in our dataset a specific type 1 effect could have been hidden by the overwhelming majority of type 2 diabetic patients.
Such cases highlight the supporting role for which the proposed model is rightly intended for. Note that if these two cases were  to be excluded, sensitivity would be 89.7\%.
\section*{Discussion}
\label{sec4}
\subsection*{Imaging and non-imaging data combination}
\label{subsec4.1}
Complex tasks in clinic need
integration of radiological information with laboratory and clinical
information. Machine learning
methods are starting to be employed for such a purpose.
Besides COVID-19 prognosis, examples can be Alzheimer disease classification and progress \cite{altaf2018multi} or the individuation of immunotherapy responders \cite{tunali2019novel}.\\
Radiological information is native as imaging data, while laboratory and
clinical information comes in
tabular form.
Up to now, there is still no consensus on the best way to
combine these two types of data in machine learning models.
In particular,
CNN are showing "unreasonable effectiveness" in image
related task \cite{LeCun,he2016deep} in the last years. However, the same is simply not
true for tabular data \cite{chui2018notes}, where ensemble models, and especially gradient
boosting variations (XGBoost, \cite{chen2016xgboost}, LightGBM, \cite{ke2017lightgbm}, CatBoost, \cite{prokhorenkova2018catboost}),  have the edge (\cite{kaggle2019}).\\
In principle, an integration of imaging and non-imaging information that harnesses the power of neural network in a combined model can be reached in a number of ways. Leaving apart simple CNN usage for segmentation \cite{zhang2020clinically}, they essentially boil down to three methods. First, combination of results of fully separated models \cite{ning2020open}. Second,
injection of non-imaging data, either as they are or after one or more fully connected layer, at some point of the CNN architecture, with a fully connected layer being the obvious choice \cite{meng2020deep, spasov2019parameter, gessert2020skin, liu2018joint}. Third, CNN as image feature extractor and a different machine learning model on the top to operate on both image extracted and non image features on equal footing (e.g. \cite{xu2020accurately}).\\
The first method is somewhat hampered by the fact that it can not keep in account any interaction between imaging and non imaging features.
The second method has the advantage of being end-to-end differentiable, and therefore trainable. As such, it is also more elegant to validate.
The third method can exploit a state-of-art model for heterogeneous data (e.g. gradient boosting, \cite{pang2019novel}, \cite{ren2017novel}, \cite{carvalho2020diagnosis} for extracted CNN features in XGBoost classifiers). The underlying machine learning architecture is less prone to data-starving, it is naturally integrable with advanced feature selection algorithms, and more readily explainable once agnostic features for images are accepted as such, since its symmetrical elaboration of non-imaging and image extracted features. \\
Our dataset consists of few hundred of patients,  a small number for CNN applications. Prognosis is a patient-level task, and as such we believe that number of patients, not of CT slices, is the fundamental number of instances. Furthermore, there is a perceived need for explainability of artificial intelligence applications, especially in the clinics (see below).
Therefore, we chose to sacrifice full differentiability and opted for the third method. As far as we know, this the first time that such a method to combine  CNN-extracted and non imaging data in a gradient boosting machine is used in a medical application.

\subsection*{Model building and training}
\label{subsec4.2}
For COVID-19 prognosis, global features are likely to be more effective than spatially localized features
(that could be more useful for diagnosis in initial phases). Therefore a fully 3D
patient-level architecture is the more appropriate choice for the task. A CNN classifier allows to pick the high level representation features relevant to the task.
At the end of the network, a multiple fully connected layer structure allowed us a gradual reduction of the number of features before their extraction, so to balance it with non-imaging features.
CatBoost was used as the machine learning classifier for the final model. CatBoost is becoming increasingly applied in complex datasets \cite{hancock2020catboost}. It implements Ordered Boosting,
a permutation driven version of boosting algorithm, and Oblivious Decision
Trees, a particular type of decision trees (as well as other features we do
not treat here). Both should be especially effective in avoiding
overfitting. Hancock  and Khoshgoftaar \cite{hancock2020catboost} pointed out that CatBoost performance is likely
sensitive to hyperparameters choice. We especially picked by hand some
hyperparameters (Ordered Boosting as boosting type and Bayesian
bootstrap type) so to select the solution less prone to overfitting, using
Bayesian optimization for most of the others. The most influential
hyperparameters are the learning rate and the number of trees. For these,
CatBoost provides very powerful tuning methods, respectively with the
automatic learning rate estimate and the overfitting detector, and we made use
of both.
The feature selection in our model is based on the combination of the Boruta algorithm with the SHAP metric, as implemented by Keany et al.  \cite{ekeany_2020_4247618}.
The Boruta algorithm tries to find all relevant features for the task (and the model), not a compact subset that
minimize information loss for the classifier \cite{kursa2010boruta}. The use of the SHAP metric naturally keeps in account feature interactions and cooperative effects.
We implemented a majority voting procedure in order to exploit the strengths of BorutaSHAP, at the same time minimizing the risk of information loss and the dependence of subsampling randomness (Subsection CatBoost model).
Since validation set is used as such both for CNN feature extractor and CatBoost hyperparameter choice, we can not completely exclude that some knowledge leaks from the feature extraction along our dimensionality reduction procedure up to the hyperparameter choice.
We believe that our selected procedure, in particular the restriction of feature selection and Bayesian hyperparameter optimization on the training set should minimize the impact
of knowledge leakage (and therefore the risk of overfitting). In any case no leakage on the test set was possible, due to holdout from the start.

 \subsection*{Model interpretability}
\label{subsec4.3}
There is a general debate about the need
of interpretability of machine learning models for decision making \cite{bostrom2014ethics}. Notably, European Union legislation assesses the right to have an explanation of a decision made after automated data processing (GDPR16,
\cite{GDPR16}). We believe that an
even stronger push for model explainability comes from clinical needs. In
particular, an explainable model is not only more acceptable for doctors and patients, but becomes much more integrable with additional, out-of-the-model information (see Subsection Model introspection). In the proposed model, interpretability at global level and especially as single prediction level is given by the SHAP analysis. CT features, being extracted from the CNN classifier and the PCA reduction, are agnostic. However, one can still use them to appraise the overall weight of CT both in general and single case predictions. In particular, the first principal component is much more significant than the others, so it can be used as a proxy.

\subsection*{Limitations}
\label{subsec4.4}
There are limitations to the proposed model. First, the dataset comes from a
single center, in a localized period of time, with consequent trade-off
between data homogeneity and generalization power.
Second, the number of
our patients is limited in comparison to the usual numbers in deep
learning classification tasks. Larger datasets naturally tend to reduce model
variance. To reduce the influence of these  two limitations, we took
particular care in trying to avoid overfitting.\\
Finally, any endpoint for COVID-19 related task can be potentially
influenced by the pressure posed to hospitals by the large numbers of patients
e.g. mortality rate and/or choice of admission to intensive care units can
change. We considered an ICU admission severity outcome to be
more applicable in clinical context than a mortality prediction.
However, we are aware that such an outcome definition is
calibrated on our center (i.e. a different center can have different admission
criteria to intensive care unit). We believe that the choice of an interpretable,
probabilistic output can reduce the bias due to outcome choice.

\section*{Conclusion}
\label{sec5}

We built a COVID-19 prognostic hybrid machine-learning/deep learning model intended to be
usable as a tool that can support clinical decision making.
The proposed model fully integrates imaging and non-imaging data. A 3D CNN classifier extracts patient level features from  baseline CT scans. A CatBoost classifier is applied on extracted features and laboratory and clinical data. Feature selection in the model is performed via the Boruta algorithm combined with the SHAP feature importance. Such architecture blends state-of-art machine learning for tabular data with the efficacy of a 3D CNN in building and selecting patient-level complex image features.
The tool is interpretable at global and at single
patient level, with the SHAP importance of features in obtaining the  percentage score of classification. Such analytical result is susceptible to be integrated by ulterior information that the clinician may have. We think that at the present state of things, this is the correct clinical usage of machine learning for COVID-19 prognostic tasks.
There are a handful of COVID-19 prognostic models that make use of radiological and clinical data with deep learning techniques, most of them either using deep learning only for segmentation \cite{zhang2020clinically,chao2020integrative, chassagnon2021ai} or keeping as a variable the resulting classification \cite{ning2020open}.
At odds with them, and more in line with \cite{meng2020deep} and \cite{xu2020accurately} (despite a much different architecture), the proposed method joins heterogeneous data at a lower representation level. As such, it allows models to take into account feature interactions. In particular an high degree of interaction between heterogeneous features is expected for COVID-19 prognosis task, due to complex relations between anatomical and functional lung involvement and systemic inflammatory response.\\
The proposed model was trained on a limited size dataset, without image segmentation from the radiologists. It would be therefore easily retrainable from scratch in order to adapt it to the mutable landscape of the pandemic, due to different variants of the virus, differences in the affected population demographics and effects of vaccine campaigns. Efforts in artificial intelligence triggered by the pandemic are likely to pave the way to future applications in different clinical contexts.  We believe that the integration of heterogeneous data and the interpretability of models will be keypoints for any clinical application involving complex tasks.

\section*{Data availability}
\label{sec6}
The dataset analyzed during the current study can be made available from the corresponding author on reasonable requests upon ethical comittee approval.


\section*{ABSTRACT}
    The proposed Circular Electron Positron Collider (CEPC), with a center-of-mass energy $\sqrt{s} = 240$ GeV, will primarily serve as a Higgs factory.
    At the same time, it can offer good opportunities to search for new physics phenomena at low energy, which can be challenging to discover at hadron colliders, but well motivated by some theoretical models developed to explain, e.g., the relic abundance of dark matter.
    This paper presents sensitivity studies of chargino pair production, considering scenarios for both a Bino-like and a Higgsino-like neutralino as the lightest supersymmetric particle, using full Monte Carlo (MC) simulation.
    With the assumption of systematic uncertainties at the level of 5\%, the CEPC has the ability to discover chargino pair production up to the kinematic limit of $\sqrt{s}/2$ for both scenarios.
    The results have a minor dependence on the reconstruction model and detector geometry.
    These results can also be considered as a reference and benchmark for similar searches at other proposed electron-positron colliders, such as the Future Circular Collider ee (FCC-ee) or the International Linear Collider (ILC), particularly given the similar nature of the facilities, detectors, center-of-mass energies, and target luminosities.
    \par\textbf{Keywords: }CEPC; chargino; Bino; Higgsino

\let\thefootnote\relax\footnotetext{* This study was supported by the National Key Programme (Grant NO.: 2018YFA0404000).}
\tableofcontents
\clearpage

 \section{Introduction}
 \label{sec:intro}
 \input{introduction.tex}

 \section{Detector, Software and Samples}
 \label{sec:samples}
 \input{samples.tex}

 \section{Search for chargino pair production at CEPC}
 \label{sec:searchew}
 \input{searchew.tex}

 \pagebreak
 \clearpage

 \section{Conclusion}
 \label{sec:conclusion}
 \input{conclusion.tex}

 \section{Acknowledgements}
 \label{sec:acknowledgements}
 \input{acknowledge.tex}

\bibliographystyle{spphys}

\subsection{Search for chargino pair production with Bino LSP}
\label{subsec:searchcb}
\input{searchcb.tex}
\subsection{Search for chargino pair production with Higgsino LSP}
\label{subsec:searchch}
\input{searchch.tex}
\subsection{Chargino pair production search summary}
\label{subsec:searchsum}
The studies presented in this paper demonstrate that the discovery sensitivity for electroweakinos with both a Bino-like LSP and a Higgsino-like LSP can reach masses up to $\sqrt{s}/2$ at CEPC. The sensitivity can be further improved if considering additional final states (i.e. electron and tau), alternate signal scenarios such as disappearing track or chargino pair production with photon initial-state radiation (ISR), or more complicate analysis techniques (i.e. machine learning etc).

The prospective limits at CEPC compared with LEP and LHC results are shown in Figure \ref{fig:searchsum}.
In general, the sensitivity at CEPC is mainly constrained by the center-of-mass energy and is not strongly dependent on the mass splitting between NLSP and LSP, allowing CEPC to cover very compressed electroweakinos that are very difficult to search for at the LHC due to the reduced acceptance and reconstruction efficiency of the soft leptons.
\begin{figure}[!htp]
  \centering
    \subfigure [] {\includegraphics[width=.48\textwidth]{Figure6a.pdf}}
    \subfigure [] {\includegraphics[width=.48\textwidth]{Figure6b.pdf}}
    \caption{Observed and expected exclusion limits on SUSY simplified models for chargino-pair production with (a) Bino-like LSP and (b) Higgsino-like LSP obtained by ATLAS. The observed limits obtained by LEP are also shown for Higgsino LSP case in Figure \ref{fig:searchsum} (b), while not shown in Figure \ref{fig:searchsum} (a) since the limit of chargino mass is below 100 GeV. The prospected limits at CEPC are also shown in the dotted purple line for rough comparison. }
    \label{fig:searchsum}
  \end{figure}