2.1 Discrete models of conservative programs

The notion of a conservative program (Haucourt Reference Haucourt2018, §4.1) is based on a virtual machine allowing parallel execution of multi-instructions, that is, partial maps $\mu$ on $\{{1},\ldots ,{n}\}$ assigning to the $i^{th}$ process of the machine the instruction it has to execute (the $i^{th}$ process is inactive during the execution of $\mu$ if the latter is not defined at $i$ ). Every instruction executed by $\mu$ is supposed to be atomic in the sense that «its execution should appear to take effect instantaneously at some moment between its invocation and response» (Herlihy et al. Reference Herlihy, Shavit, Luchangco and Spear2020, Principle 3.4.1, p. 58).

With the notation from Def. 2.2, the vertices of $G$ are possible positions of the instruction pointer $p$ . At each step, $p$ moves from the source $v$ to the target $v'$ of the arrow $a$ carrying the next instruction to execute. However, our setting does not allow $p$ to jump from $v$ to $v'$ without going through an intermediate stage, namely the arrow $a$ itself. The arrows of $G$ are thus legit positions of the instruction pointer; we are in a setting where instruction executions, or more abstractly “events,” have duration (Pratt Reference Pratt2000, §4, §5).

The virtual machine on which $P$ is executed comes with a pool of resources shared by the processes of $P$ . These resources are renewable in the sense that they can be restored after use: each process can take and release them by means of atomic instructions.

A program $P$ is conservative if, and only if, so are its processes (Haucourt Reference Haucourt2018, Lem. 4.1). Whether a sequential process is conservative is decided by a breadth-first traversal of its underlying graph (Haucourt Reference Haucourt2018, p. 1734–1735).

In other words, the amount of resources required to execute a conservative program $P$ is known at compile time. Moreover, according to the second point of Def. 2.5, the discrete model of $P$ induces an overapproximation of all its possible behaviors (i.e. all the sequences of multi-instructions associated with the execution traces of $P$ ); the subtlety is that multiple directed paths on $({{G}}_{{1},\,\ldots ,\, {{G}}_{n}})$ may induce the same sequence of multi-instructions.

2.2 Continuum of states

We have already mentioned that the arrows of the graph of a sequential process are intermediate positions of the instruction pointer (Def. 2.2). Pushing this principle further, we specify where the pointer stands on a given arrow of $G$ . Suppose that the map

\begin{equation*} \ell \::\:{{G}}^{{({1})}}\:\to \:\:[{{R}},{{\infty }}[ \end{equation*}

assigns to each arrow a length which is meant to be the execution time of the atomic instruction it carries (§6). The real number $R$ is supposed to be positive because execution times should not be arbitrarily small. This constraint has important consequences for the mathematical properties of the models that will be defined later. We end up with a continuum of states:

Definition 2.6. The underlying set of the metric graph of $G$ is the set

\begin{equation*} |{G}| = {{G}}^{{({0})}} \:\: \cup \:\: \bigcup \big \{\:\:\{a\} \times ]{{0}},{{\ell (a)}}[\:\:\ \big |\ \:\:a\in {{G}}^{{({1})}}\:\:\big \} . \end{equation*}

The quotient map ${{\pi }}_G:|{G}|\to G$ is defined by ${{\pi }}_G(v)=v$ on ${{G}}^{{({0})}}$ and by ${{\pi }}_G(a,t)=a$ elsewhere. The local order on $|{G}|$ (Def. 5.11) encodes the constraints that force the pointer $p$ to move continuously with respect to the direction imposed by the arrows. The source and the target of an arrow $a$ play the role of $(a,0)$ and $(a,\ell (a))$ which are intentionally omitted. An arrow of $|{G}|$ is a subset of the form $\{a\} \times ]{{0}},{{\ell (a)}}[$ for some $a\in {{G}}^{{({1})}}$ ; by extension its source and its target are those of $a$ .

Definition 2.7. Subsets of the form $\{a\} \times J$ are said to be initial (resp. final) when $J$ is an initial (resp. final) subinterval of $]{{0}},{{\ell (a)}}[$ . A subset $S$ of $|{G}|$ is said to be a star when it is of the form

\begin{equation*} S(v,i,f) = \bigcup _{\textrm {tgt}\; a=v}\{a\} \times ]{{\ell (a)-f(a)}},{{\ell (a)}}[ \quad \cup \quad \{v\} \quad \cup \:\:\bigcup _{\textrm {src}\ a=v}\{a\} \times ]{{0}},{{i(a)}}[ \end{equation*}

with the functions $i:{{\textrm {src}}}^{{-1}}\{v\}\to \mathbb{R}_{{+}}\setminus \{0\}$ , $f:{{\textrm {tgt}}}^{{-1}}\{v\}\to \mathbb{R}_{{+}}\setminus \{0\}$ satisfying $i(a)$ , $f(a)\leqslant \ell (a)$ whenever it makes sense. The vertex $v$ is called the center of the star. Moreover:

1. – we write $S(v)$ when $i(a)=\ell (a)$ and $f(a)=\ell (a)$ whenever it makes sense.

2. – if both $i$ and $f$ are constant and equal to $r\lt \tfrac R2$ , we write $S(v,r)$ instead of $S(v,i,f)$ , and call $S(v,r)$ the star centered at $v$ of radius $r$ .

3. – the canonical star centered at $v$ is the set $S(v,\tfrac \ell 2,\tfrac \ell 2)$ , that is, $i(a)={\ell (a)}/2$ for every $a\in {{\textrm {src}}}^{{-1}}\{v\}$ and $f(a)={\ell (a)}/2$ for every $a\in {{\textrm {tgt}}}^{{-1}}\{v\}$ .

A path on a topological space $X$ is a continuous map $\gamma :[{{a}},{{b}}]\to X$ with $a\leqslant b$ . The endpoints of $\gamma$ are $\gamma (a)$ and $\gamma (b)$ , more precisely its starting and finishing points. The opposite of $\gamma$ is the path $\bar {\gamma }:[{{a}},{{b}}]\to X$ with $\bar {\gamma }(t)=\gamma (a+b-t)$ . Given a path $\delta :[{{b}},{{c}}]\to X$ with $\gamma (b)=\delta (b)$ , the concatenation $\gamma \cdot \delta$ is the path defined on $[{{a}},{{c}}]$ by $\gamma \cdot \delta (t)=\gamma (t)$ if $t\leqslant b$ , and by $\gamma \cdot \delta (t)=\delta (t)$ if $b\leqslant t$ . If $\textit {dom}\:(\delta )=[{{b'}},{{c}}]$ , then we still write $\gamma \cdot \delta$ to mean $\gamma \cdot (\delta \circ \tau )$ with $\tau$ denoting the translation $t\mapsto t+b'-b$ from $[{{b}},{{c-b'+b}}]$ to $[{{b'}},{{c}}]$ .

Definition 2.11. The tile over $p\in {{G}}_{1}{ \times }\cdots { \times }{{G}}_{n}$ is the set ${{({{\pi }}_{G_1}{ \times }\cdots { \times }{{\pi }}_{G_n})}}^{{-1}}\{p\}$ , that is, ${{\tau }}_{1}{ \times }\cdots { \times }{{\tau }}_{n}$ with ${{\tau }}_i=\{{{p}}_{{{i}}}\}$ if ${{p}}_{{{i}}}$ is a vertex, and ${{\tau }}_i=\{{{p}}_{{{i}}}\} \times ]{{0}},{{\ell ({{p}}_{{{i}}})}}[$ if ${{p}}_{{{i}}}$ is an arrow. Each ${{\tau }}_i$ admits a canonical (total) order; the product of these total orders is the canonical partial order of the tile over $p$ . A path $\gamma$ on $|{{{G}}_{{{1}}}}| \times \cdots \times |{{{G}}_{{{n}}}}|$ is said to be directed when for every tile $\tau$ and every interval $J\subseteq {{\gamma }}^{{-1}}(\tau )$ , the restriction of $\gamma$ to $J$ is order preserving; we say that $\gamma$ crosses a tile $\tau$ if there exists $[{{a}},{{b}}]\subseteq \textit {dom}\:(\gamma )$ such that $\gamma ([{{a}},{{b}}])\subseteq \bar {\tau }$ (the closure of $\tau$ ) and $\gamma ([{{a}},{{b}}])\setminus \tau =\{\gamma (a),\gamma (b)\}$ . A subset of $|{{{G}}_{{{1}}}}| \times \cdots \times |{{{G}}_{{{n}}}}|$ is said to be tile compatible when it can be written as a (necessarily disjoint) union of tiles. The middle of the tile over $p$ is the point $({{x}}_{{1},\ldots ,{{x}}_{n}})$ defined by

\begin{equation*} {{x}}_{{{i}}} = \left \{\begin{array}{ll} {{p}}_{{{i}}} & \text{ if } {{p}}_{{{i}}} \text{ is a vertex,} \\ \big ({{p}}_{{{i}}},\tfrac 12\ell ({{p}}_{{{i}}})\big ) & \text{ if } {{p}}_{{{i}}} \text{ is an arrow,} \\ \end{array} \right . \end{equation*}

for $i\in \{{1},\ldots ,{n}\}$ . The lower corner and the upper corner of the tile over $p$ are the points $({{x}}_{{1},\ldots ,{{x}}_{n}})$ and $({{y}}_{{1},\ldots ,{{y}}_{n}})$ defined, for $i\in \{{1},\ldots ,{n}\}$ , by

\begin{equation*} {{x}}_{{{i}}} = \left \{ \begin{array}{ll} {{p}}_{{{i}}} & \text{ if } {{p}}_{{{i}}} \text{ is a vertex,} \\ \textrm {src}({{p}}_{{{i}}}) & \text{ if } {{p}}_{{{i}}} \text{ is an arrow} \\ \end{array} \right . \qquad \text{and}\qquad {{y}}_{{y}{{i}}} = \left \{ \begin{array}{ll} {{p}}_{{{i}}} & \text{ if } {{p}}_{{{i}}} \text{ is a vertex,} \\ \textrm {tgt}({{p}}_{{{i}}}) & \text{ if } {{p}}_{{{i}}} \text{ is an arrow.} \\ \end{array} \right . \end{equation*}

Note that if one of the components of $p$ is an arrow, then the source and the target of $p$ do not belong to the tile over $p$ .

The progress graphs shown in Figure 1 are tile compatible, and more generally:

The notion of tile compatibility deserves some explanation. Every $p\in {{[[{{P}}]]}}_{{{d}}}$ is (tacitly) labeled by the multi-instruction $\mu$ that is defined at $i$ when ${{p}}_{{{i}}}$ is an arrow of ${{G}}_{{{i}}}$ (the underlying graph of the $i^{th}$ process of $P$ ), in which case the (atomic) instruction ${{\mu }}_i$ is the label of ${{p}}_{{{i}}}$ – see Def. 2.2. Denote by ${{\tau }}_p$ the tile over $p$ , and let $\gamma$ be a directed path (Def. 2.11) from the lower corner to the upper corner of ${{\tau }}_p$ which only visits ${{\tau }}_p$ and its corners. Then, $\gamma$ represents an execution of the multi-instruction $\mu$ in which the speeds of the processes may vary independently of each other, with the only restriction that all the processes start and finish at the same time. From this point of view, the tile over $p$ represents all the possible continuous schedules for the execution of $\mu$ (by contrast, there is only one discrete schedule for the execution of $\mu$ ). A more elaborate discussion should take into account all the directed paths $\gamma$ that cross ${{\tau }}_p$ (Def. 2.11). Suppose that $[{{a}},{{b}}]\subseteq \textit {dom}\:(\gamma )$ with $\gamma ([{{a}},{{b}}])\subseteq {{\bar {\tau }}}_{{{p}}}$ and $\gamma ([{{a}},{{b}}])\setminus {{\tau }}_p=\{\gamma (a),\gamma (b)\}$ . Also suppose that $\gamma$ is written as the concatenation ${{\gamma }}_{{{1}}}{{\gamma }}_{{{2}}}{{\gamma }}_{{{3}}}$ with ${{\gamma }}_{{{2}}}$ the restriction of $\gamma$ to $[{{a}},{{b}}]$ . As long as one is only concerned with the execution trace associated with $\gamma$ , one can “replace” $\gamma$ by $\delta ={{\gamma }}_{{{1}}}{{\tilde \gamma }}_{{{2}}}{{\gamma }}_{{{3}}}$ provided that ${{\tilde \gamma }}_{{{2}}}$ is a directed path defined on $[{{a}},{{b}}]$ with ${{\tilde \gamma }}_{{{2}}}(a)=\gamma (a)$ , ${{\tilde \gamma }}_{{{2}}}(b)=\gamma (b)$ , and ${{\tilde \gamma }}_{{{2}}}(]{{a}},{{b}}[)\subseteq {{\tau }}_p$ – see (Haucourt, Reference Haucourt2018, Thm. 6.1 and Cor. 6.2) for a formal statement. It may be that $\delta$ is smooth while $\gamma$ is not, and the path $\delta$ may be of lesser length – see Figure 2. If $X$ is a tile-compatible subset of $|{{{G}}_{{{1}}}}| \times \cdots \times |{{{G}}_{{{n}}}}|$ , then we have $\textit {img}\:(\gamma )\subseteq X\Leftrightarrow \textit {img}\:(\delta )\subseteq X$ . Consequently, in a tile-compatible set, one can choose the directed path representing a given execution trace in order to optimize certain parameters: the cases of smoothness and execution time are discussed in §6, and more specifically in Thm. 6.5 and Cor. 6.6. Tile-compatible subsets also play an crucial role in the preamble of §5.

2.3 Blowing up vertices

For every arrow $a$ of $G$ , the canonical bijection $\{a\} \times ]{{0}},{{\ell (a)}}[\to ]{{0}},{{\ell (a)}}[$ induces a dihomeomorphism (i.e. a homeomorphism i.e., also an order isomorphism, see p. 21).

From the topological and order-theoretic points of view, the set $|{G}|$ is “almost everywhere” like $\mathbb{R}$ . The only possible exceptions are the singular vertices of $G$ . As for curves in Algebraic Geometry,Footnote ¹ we “resolve singularities” by “blowing them up,” that is, we replace each vertex $v$ by the traversals at $v$ :

Definition 2.15. The underlying set of the blowup of $G$ , which we denote by $\|{G}\|$ , is the union of $|{G}|\setminus {{{G}}^{{({0})}}}$ and the set of traversals of $G$ , that is to say

\begin{equation*} \|{G}\| = \bigcup \big \{\{a\} \times ]{{0}},{{\ell (a)}}[\ \big |\ {a\in {{G}}^{{({1})}}}\big \} \:\cup \: \big \{(a,b)\in {{G}}^{{({1})}} \times {{G}}^{{({1})}}\ \big |\ \textrm {tgt}\; a=\textrm {src}\; b\big \}. \end{equation*}

The blowup of $G$ is the map ${\beta }_G:\|{G}\|\to |{G}|$ defined by ${\beta }_G(a,b)=\textrm {tgt}\; a$ (or $\textrm {src}\; b$ ) for every traversal $(a,b)$ of $G$ , and by ${\beta }_G(a,t)=(a,t)$ for every $a\in {{G}}^{{({1})}}$ and $t\in \:]{{0}},{{\ell (a)}}[$ . A subset of $\|{{{G}}_{{{1}}}}\| \times \cdots \times \|{{{G}}_{{{n}}}}\|$ is said to be tile compatible when it is the inverse image under ${{\beta }}_{{{G_1}}} \times \cdots \times {{\beta }}_{{{G_n}}}$ of some tile-compatible set (Def. 2.11). From now on, we write ${{\beta }}_i$ instead of ${{\beta }}_{{{G_i}}}$ .

Remark 2.17. The constructions $|{\_}|$ and $\|{\_}\|$ readily extend to functors from $\mathbf{Grph}$ to $\mathbf{Set}$ : given a graph morphism $f:G\to G'$ , the maps $|{f}|$ and $\|{f}\|$ are defined by

\begin{equation*} |{f}|(v)={{f}}^{{({0})}}(v), \quad \|{f}\|(a,b)=({{f}}^{{({1})}}(a),{{f}}^{{({1})}}(b)), \quad \text{and}\quad |{f}|(a,t)=\|{f}\|(a,t)=({{f}}^{{({1})}}(a),t) \end{equation*}

where $v\in {{G}}^{{({0})}}$ , $a\in {{G}}^{{({1})}}$ , $t\in \:]{{0}},{{\ell (a)}}[$ , $(a,b)$ is a traversal of $G$ , and ${{f}}^{{({0})}}$ , ${{f}}^{{({1})}}$ denote the vertex and the arrow parts of $f$ . Moreover, the collection of blowups ${\beta }_G:\|{G}\|\to |{G}|$ , for $G$ running through the class of graphs, forms a natural transformation from $\|{\_}\|$ to $|{\_}|$ . If $|{G}|$ and $|{G'}|$ are equipped with the topologies from Rem. 2.9 , then $|{f}|$ is continuous.

Remark 2.18. It is natural to define the topology of $\|{G}\|$ as the initial topology of the blowup ${\beta }_G$ : a base of this topology is given by the inverse images under ${\beta }_G$ of the stars and segments (Rem. 2.9). By observing that ${{{\beta }_G}}^{{-1}}(S(v,i,f))$ is the set

\begin{equation*} \bigcup _{\textrm {tgt}\; a=v=\textrm {src}\; b}\{a\} \times ]{{\ell (a)-f(a)}},{{\ell (a)}}[ \:\:\cup \:\: \{(a,b)\} \:\cup \: \{b\} \times ]{{0}},{{i(b)}}[ \end{equation*}

we conclude that if the graph $G$ has a singular traversal $\tau$ (Def. 2.14), then the topology of $\|{G}\|$ is not ${{T}}_{{{1}}}$ ; indeed, the set $\{\tau \}$ is not closed. Conversely, if $G$ has no singular traversal, then the topology of $\|{G}\|$ is Hausdorff ( ${{T}}_{{{2}}}$ ).

Example 2.20. We denote by $Z$ the connected graph whose arrows (all of length $1$ ) are $(n,n+1)$ with $n\in \mathbb{Z}$ , the source and the target being $n$ and $n+1$ , respectively.

Every vertex of $Z$ has a unique traversal so the blowup of $Z$ is a bijection. We obtain a canonical bijection from $\|{Z}\|$ to $\mathbb{R}$ by composing the blowup of $Z$ with the following bijection:

\begin{equation*} \begin{array}{ccl} |{Z}| & \to & {\mathbb{R}} \\ n & \mapsto & n \\ ((n,n+1),t) &\mapsto & n+t \end{array} \end{equation*}

Figure 3.

The blowup of a graph containing a branching point.

We will see that every set $\|{G}\|$ carries a “canonical” atlas (Def. 3.3). Connectedness and non-Hausdorffness of (the topology of) this atlas (Def. A.8) derive from the fact that any neighborhood of a traversal $(a,b)$ meets any neighborhood of another traversal $(a',b')$ precisely when $a=a'$ or $b=b'$ (see the proof of Lem. 3.2).

We have already observed that the endpoints of $G$ are “forgotten” by $\|{G}\|$ . One may think of this as an issue since the starting point of the automaton associated with a process is an endpoint. We circumvent the difficulty taking advantage of the following control flow graph feature: the starting point has a unique outgoing arrow $a$ (Def. 2.2). So we can harmlessly declare any point on $\{a\} \times ]{{0}},{{\ell (a)}}[$ to be the starting point instead of the source of $a$ . Another (and more canonical) way to solve the problem consists of adding a fresh arrow ending at the starting point we wish to save. The same remarks hold (and the same tricks work) for the final points of the graph.

3.1 Standard atlases

Given a graph $G$ with $\ell :{{G}}^{{({1})}}\to ]{{0}},{{\infty }}[$ , the set $\|{G}\|$ (Def. 2.15) admits a “natural” atlas that we now describe. Given $x\in {{G}}^{{({1})}}$ we define

(2) \begin{equation} {{I}}_{{{x}}}=\:\:]{{0}},{{\tfrac {\ell (x)}2}}[,\qquad {{J}}_{{{x}}}=\:\:]{{\tfrac {\ell (x)}2}},{{\ell (x)}}[, \end{equation}

and keep in mind the bijection $t \mapsto t-\ell (x)$ from ${{J}}_{{{x}}}$ to $-{{I}}_{{{x}}}$ .

Definition 3.1. The standard charts of $G$ are the bijections

\begin{equation*} \begin{gathered} {{\phi }}_{a\phantom {b}}\quad :\quad \{a\} \times ]{{0}},{{\ell (a)}}[\quad \to \quad ]{{0}},{{\ell (a)}}[\quad \text{and}\quad \\[1mm] {{\phi }}_{{{ab}}}\quad :\quad \{a\} \times {{J}}_{{{a}}}\:\:\cup \:\:\{(a,b)\}\:\:\cup \:\:\{b\} \times {{I}}_{{{b}}} \quad \to \quad -{{I}}_{{{a}}}\:\cup \:\{0\}\:\cup \:{{I}}_{{{b}}}\\[1mm] \quad \text{ with }\quad (a,t)\mapsto t-\ell (a), \quad (a,b)\mapsto 0, \quad (b,t)\mapsto t \end{gathered} \end{equation*}

for all arrows $a$ and all traversals $(a,b)$ of $G$ . The standard charts of $({{G}}_{{1},\ldots ,{{G}}_{n}})$ are the products ${{\phi }}_{1}{ \times }\cdots { \times }{{\phi }}_{n}$ with ${{\phi }}_i$ a standard chart of ${{G}}_{{{i}}}$ for $i\in \{{1},\ldots ,{n}\}$ .

Proof. The domains of the standard charts cover $\|{G}\|$ . Given two arrows $a$ and $a'$ with $a\not =a'$ , the domains of ${{\phi }}_a$ and ${{\phi }}_{{{a'}}}$ are disjoint. By applying the distributivity of $\cap$ over $\cup$ , and the fact that ${{I}}_{{{x}}}\cap {{J}}_{{{x}}}=\emptyset$ – see (2), the intersection of $\textit {dom}\:{{\phi }}_{{{ab}}}$ and $\textit {dom}\:{{\phi }}_{{{a'b'}}}$ is the disjoint union

\begin{equation*} (\{a\}\cap \{a'\}) \times ({{J}}_{{{a}}}\cap {{J}}_{{{a'}}}) \:\: \cup \:\: \big (\{(a,b)\}\cap \{(a',b')\}\big ) \:\: \cup \:\: (\{b\}\cap \{b'\}) \times ({{I}}_{{{b}}}\cap {{I}}_{{{b'}}}). \end{equation*}

The transition map ${{\phi }}_{{{a'b'}}}\circ {{{{\phi }}_{{{ab}}}}}^{{-1}}$ is an identity whose domain is $\textit {cod}\,({{\phi }}_{{{ab}}})$ if $(a,b)=(a',b')$ , the interval ${{J}}_{{{a}}}$ if $a=a'$ and $b\not =b'$ , the interval ${{I}}_{{{b}}}$ if $a\not =a'$ and $b=b'$ , and empty otherwise. If $c\not \in \{a,b\}$ , then the domains of the charts ${{\phi }}_{{{ab}}}$ and ${{\phi }}_{{{c}}}$ are disjoint. So the only nontrivial case is when $c\in \{a,b\}$ . We take $\{a\} \times {{J}}_{{{a}}}$ as witness of compatibility of ${{\phi }}_{{{ab}}}$ and ${{\phi }}_{{{a}}}$ since we have

\begin{equation*} {{\phi }}_{{{ab}}}\circ {{{{\phi }}_a}}^{{-1}}\quad :\quad t\:\in \:{{J}}_{{{a}}} \quad \mapsto \quad t-\ell (a)\:\in \:-{{I}}_{{{a}}}, \end{equation*}

and ${{J}}_{{{b}}}$ as witness of compatibility of ${{\phi }}_{{{ab}}}$ and ${{\phi }}_{{{b}}}$ since ${{\phi }}_{{{ab}}}\circ {{{{\phi }}_b}}^{{-1}}$ is just the identity map on ${{J}}_{{{b}}}$ . Hence the transition maps are translations. We readily deduce the higher dimensional case from the description of the transition maps between the charts of a product of atlases (Def. A.5); in particular, the transition maps are translations as products of such maps.

3.2 Tangent vectors

For any standard charts $\phi$ and $\psi$ of $({{G}}_{{1},\ldots ,{{G}}_{n}})$ , the derivative of $\psi \circ {{\phi }}^{{-1}}$ at any point of $\textit {cod}\,\phi \cap \textit {cod}\,\psi$ is the identity map ${id}_{{\mathbb{R}}^n}:{\mathbb{R}}^n\to {\mathbb{R}}^n$ (Lem. 3.2). It follows from §A.3 (24) that for all $v\in T_{p}(\mathcal{A}_{{G_1}} \times \cdots \times \mathcal{A}_{{G_n}})$ , the representation ${{[[{{v}}]]}}_{{{p}}}^{{{\phi }}}$ does not depend on the standard chart $\phi$ . So we may as well decide that the tangent space of $\mathcal{A}_{{G_1}} \times \cdots \times \mathcal{A}_{{G_n}}$ at $p$ is

(3) \begin{equation} T_{p}(\mathcal{A}_{{G_1}} \times \cdots \times \mathcal{A}_{{G_n}}) = \{p\} \times {\mathbb{R}}^n \end{equation}

with the obvious topological vector space structure.

Definition 3.6. A standard tangent chart of $({{G}}_{{1},\ldots ,{{G}}_{n}})$ is a product $\phi \times {id}_{{\mathbb{R}}^n}$ with $\phi$ a standard chart of $({{G}}_{{1},\ldots ,{{G}}_{n}})$ ; it corresponds to the chart $T\phi$ from § A.3 ( 25 ) provided that following ( 3 ) we adopt $\|{{{G}}_{{{n}}}}\|\: \times \:{\mathbb{R}}^n$ as the underlying set of the tangent bundle $\mathcal{A}_{{G_{1}}} \times \cdots \times \mathcal{A}_{{G_{n}}}$ : $\mathcal{A}_{{G_{1}}} \times \cdots \times \mathcal{A}_{{G_{n}}}$ :

\begin{equation*} \begin{array}{rclcl} T\phi &:&\textit {dom}\:\phi \times {\mathbb{R}}^n&\to &\textit {cod}\,\phi \times {\mathbb{R}}^n \\ & & (p,t) & \mapsto & (\phi p,t). \end{array} \end{equation*}

The standard tangent atlas of $({{G}}_{{1},\ldots ,{{G}}_{n}})$ is the collection of its standard tangent charts. The standard representation of the tangent bundle of $\mathcal{A}_{{G_{1}}} \times \cdots \times \mathcal{A}_{{G_{n}}}$ is the set $\|{{{G}}_{{{1}}}}\| \times \cdots \times \|{{{G}}_{{{n}}}}\|\: \times \:{\mathbb{R}}^n$ equipped with the standard tangent atlas. The standard parallelization of $({{G}}_{{1},\ldots ,{{G}}_{n}})$ is the tuple of vector fields $({{f}}_{,\ldots ,{{f}}_{1}}n)$ with

\begin{equation*} \begin{array}{lcccr} {{f}}_i&:&\|{{{G}}_{{{1}}}}\| \times \cdots \times \|{{{G}}_{{{n}}}}\|&\to &(\|{{{G}}_{{{1}}}}\| \times \cdots \times \|{{{G}}_{{{n}}}}\|)\: \times \:{\mathbb{R}}^n \\ & & p&\mapsto &p,{{e}}_{{{i}}} \end{array} \end{equation*}

for $i\in \{{1},\ldots ,{n}\}$ and ${{e}}_{{{i}}}$ the $i^{th}$ vector of the canonical basis of ${\mathbb{R}}^n$ . The standard basis of the tangent space at $p$ is $({f}_{p}(){n}\ldots {n}{f}_{{1}}(),)$ ; its positive cone is the set of vectors whose coordinates in the standard basis are non-negative.

Remark 3.7. Strictly speaking, even if $({{f}}_{{1},\ldots ,{{f}}_{n}})$ and $({{g}}_{{1},\ldots ,{{g}}_{m}})$ are standard parallelizations (Def. 3.6), the tuple of vector fields $({{f}}_{{1},\ldots ,{{f}}_{n}},{{g}}_{{1},\ldots ,{{g}}_{m}})$ is not. Yet, the latter is related to a standard parallelization by the obvious smooth diffeomorphism (Def. A.5)

\begin{equation*} (\mathcal{A}_{{G_{1}}} \times {\mathbb{R}}) \times \cdots \times (\mathcal{A}_{{G_{n}}} \times {\mathbb{R}}){} \quad \cong \quad (\mathcal{A}_{{G_{1}}} \times \cdots \times \mathcal{A}_{{G_{n}}})\: \times \:{\mathbb{R}}^n. \end{equation*}

3.3 Derivatives

Let $f:\mathcal{A}_{{G_{1}}} \times \cdots \times \mathcal{A}_{{G_{n}}}\to \mathcal{A}_{{G'_{1}}} \times \cdots \times \mathcal{A}_{{G'_{m}}}$ be a smooth map (Def. A.5) between standard atlases (Def. 3.3). The transition maps between standard charts are translations (Lem. 3.2) so we have ${D{({{\phi }}_{{{0}}}\circ {{{{\phi }}_{{{1}}}}}^{{-1}})}}_{{\phi _1(p)}}={id}_{{\mathbb{R}}^n}$ and ${D{({{\psi }}_{{{1}}}\circ {{\psi }_{{0}}^{{-1}}})}}_{{{{\psi }}_0(f{p})}}={id}_{{\mathbb{R}}^m}$ for all ${{\phi }}_0$ , ${{\phi }}_{{{1}}}\in \mathcal{A}_{{G_{1}}} \times \cdots \times \mathcal{A}_{{G_{n}}}$ and ${{\psi }}_0$ , ${{\psi }}_{{{1}}}\in \mathcal{A}_{{G'_{1}}} \times \cdots \times \mathcal{A}_{{G'_{m}}}$ , with $p\in \textit {dom}\:({{\phi }}_{{{0}}})\cap \textit {dom}\:({{\phi }}_{{{1}}})$ — see §A.1, p. 49. From Lem. A.6, we deduce that the representation of ${D{f}}_{{p}}$ (Def. A.14) does not depend on the standard charts in which it is represented, so it can be identified with an $n \times m$ matrix with entries in $\mathbb{R}$ which we just denote by $f'p$ without mentioning any chart:

Definition 3.8. The matrix $f'p$ is called the standard representation of ${D{f}}_{{p}}$ and we have

\begin{equation*} {D{f}}_{{p}}(p,t) = Tf(p,t) = \big (\:fp,\:f'p\cdot t\:\big ) \end{equation*}

with $f'p\cdot t$ being the product of the standard representation of ${D{f}}_{{p}}$ and the vector $t\in {\mathbb{R}}^n$ .

3.4 Functoriality

We denote by $\mathbf{Grph}_\ell$ the category whose objects are graphs equipped with a map $\ell :{{G}}^{{({1})}}\to ]{{0}},{{\infty }}[$ such that $\inf (\ell )\not =0$ , and whose morphisms are $2$ -tuples $(g,{{r}}_{{r}{{g}}})$ with $g:G\to G'$ a graph morphism such that $\ell '({{g}}_{{{1}}}(a))={{r}}_{{r}{{g}}}\cdot \ell (a)$ for every arrow $a$ . We would like to extend the construction $G\mapsto \mathcal{A}_{{G}}$ (Def. 3.3) to a functor $ \mathcal{A}_{{\ast }}:\mathbf{Grph}_\ell \to \mathbf{Atl}$ . To every morphism $(g,{{r}}_{{r}{{g}}})$ of $\mathbf{Grph}_\ell$ , we associate the map $f:\|{G}\|\to \|{G'}\|$ defined by $f(a,t)=({{g}}_{{{1}}}a,{{r}}_{{r}{{g}}}t)$ for every arrow $a$ of $G$ and $t\in \:]{{0}},{{\ell (a)}}[$ , and by $f(a,b)=({{g}}_{{{1}}}a,{{g}}_{{{1}}}b)$ for every traversal $(a,b)$ of $G$ . Such a map $f$ is called a dilation. Denoting by ${{\psi }}_{{{a'}}}$ and ${{\psi }}_{{{a'b'}}}$ the charts of the standard atlas of $\mathcal{A}_{{G'}}$ associated with $a'={{g}}_{{{1}}}a$ and $(a',b')=f(a,b)=({{g}}_{{{1}}}a,{{g}}_{{{1}}}b)$ , we have

\begin{equation*} \begin{array}{lcrclcrcl} {{\psi }}_{{{a'}}}\circ f\circ {{{{\phi }}_{{{a}}}}}^{{-1}} & \quad :\quad \ & t & \in & ]{{0}},{{\ell (a)}}[ & \quad \mapsto \quad \ & {{r}}_{{r}{{g}}}t & \in & ]{{0}},{{\ell (a')}}[\\ {{\psi }}_{{{a'b'}}}\circ f\circ {{{{\phi }}_{{{ab}}}}}^{{-1}} & : & t & \in & ]{{\tfrac {-\ell (a)}2}},{{\tfrac {\ell (b)}2}}[ & \mapsto & {{r}}_{{r}{{g}}}t & \in & ]{{\tfrac {-\ell (a')}2}},{{\tfrac {\ell (b')}2}}[ \end{array} \end{equation*}

so the map $f$ is smooth, and with the notation from Def. 3.8 we have $f'p={{r}}_{{r}{{g}}}\in {\mathbb{R}}$ for all $p\in \|{G}\|$ .