{'fraction_non_alphanumeric': 0.05724796229953596, 'fraction_numerical': 0.01125243442090837, 'mean_word_length': 3.473701193933527, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 66, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A combinatorial Hopf algebra for nonlinear output feedback control systems

In this work a combinatorial description is provided of a Faa di Bruno type Hopf algebra which naturally appears in the context of Fliess operators in nonlinear feedback control theory. It is a connected graded commutative and non-cocommutative Hopf algebra defined on rooted circle trees. A cancellation free forest formula for its antipode is given.


Introduction
Fliess operators [10,11], also known as Chen-Fliess functional expansions, play a crucial role in the theory of nonlinear control systems [23]. Most systems found in science and engineering can be viewed as a set of simpler interconnected subsystems. Ferfera was the first to describe some of the mathematical structures that result when these subsystems are modeled as Fliess operators [7,8]. Four basic system interconnections are found in most control systems. They are known as the parallel sum, parallel product, cascade and feedback connections. (See [15] for a review.) The first two are rather simple to describe mathematically. The third operation is equivalent to composing Fliess operators. Combining Fliess operators through a feedback connection as shown in Figure 1.1 is also based on composition. In short, the output of one system is fed into the input of another system, the output of which is then fed back into the input of the first. This feedback loop is, mathematically speaking, the most interesting interconnection. When one or both of the subsystems is nonlinear, the nature of the composite system can be remarkably complex. Despite this, it turns out that given two nonlinear inputoutput systems written in terms of such Chen-Fliess functional expansions, it is known that the feedback interconnected system is always well defined and in the same class. An explicit formula for the generating series of a single-input, single-output (SISO) closedloop system was provided by two of the authors, L. Duffaut Espinosa and W.S. Gray, in earlier work [14,15] in the context of a Faà di Bruno type Hopf algebra. L. Foissy [12] made a crucial contribution by showing that this Hopf algebra is connected. As a result, a simple standard recursive formula could be used to calculate the antipode [16], which plays an important role in the analysis and design of feedback systems [18,20]. In a more recent work, the full multivariable extension of the theory is presented [17]. Foissy's insight brought into focus the combinatorial nature of the Faà di Bruno type Hopf algebra found by L. Duffaut Espinosa and W.S. Gray. However, the central coproduct was presented in terms of two recursions, which made it difficult to understand its representation as a combinatorial algebra. M. Aguiar characterized the latter in terms of a connected graded vector space with homogeneous components spanned by finite sets of combinatorial objects, and the algebraic structures are given by particular constructions on those objects. In this work, a set of combinatorial objects is presented that allows one to realize the algebraic structures of the aforementioned multivariable Hopf algebra of L. Duffaut Espinosa and W.S. Gray in terms of combinatorial operations on those objects. This is based on the notion of rooted circle trees on which a connected graded bialgebra is defined in terms of extractions of rooted circle subtrees. The latter can be nested, disjoint or overlapping, which is similar to the situation found in Hopf algebras of Feynman graphs [5,13,25]. Motivated by this analogy, a Zimmermann type forest formula on rooted circle trees is given, which provides a solution of the standard recursions for the antipode. As a result, the antipode can be calculated in a way which is free of cancellations. This is of interest with respect to applications such as system inversion and output tracking, where the antipode needs to be computed explicitly to high order. Thus, combinatorial efficient methods are needed for its computation.
The paper is organized as follows. In Section 2 a few basics on Hopf algebras are collected mainly to fix the notation. Section 3 describes the Hopf algebra of decorated rooted circle trees. A cancellation free Zimmermann type forest formula is given for the antipode of this Hopf algebra. The pre-Lie algebra structure on rooted circle trees is presented in Subsection 3.2. In the last section the link to the multivariable Faà di Bruno type Hopf algebra of L. Duffaut Espinosa and W.S. Gray is described.
Acknowledgments. The second author was supported by a Ramón y Cajal research grant from the Spanish government. The third author was supported by a grant from the Severo Ochoa Excellence Program at the Instituto de Ciencias Matemáticas in Madrid, Spain.

Preliminaries
In this section, a few basics on Hopf algebras are collected to fix the notation. For details, in particular on combinatorial Hopf algebras, the reader is referred to [9,13,25], as well as the standard reference [29].
In general, k denotes the ground field of characteristic zero over which all algebraic structures are defined. A coalgebra over k consist of a triple (C, ∆, ε). The coproduct ∆ : C → C ⊗C is coassociative, that is, (∆⊗id)•∆ = (id⊗∆)•∆, and ε : C → k denotes the counit map. A bialgebra B is both a unital algebra and a coalgebra together with compatibility relations, such as both the algebra product, m, and unit map, e : k → B, are coalgebra morphisms [29]. The unit of B is denoted by For any x ∈ B (n) the coproduct is of the form Suppose A is a k-algebra with product m A and unit e A , e.g., A = k or A = B. The vector space L(B, A) of linear maps from the bialgebra B to A together with the convolution product Φ Ψ : , is an associative algebra with unit ι := e A • ε.
A Hopf algebra H is a bialgebra together with a particular k-linear map called an antipode S : H → H which satisfies the Hopf algebra axioms [29]. When A = H, the antipode S ∈ L(H, H) is characterized as the inverse of the identity map with respect to the convolution product, that is, A connected graded bialgebra is a connected graded Hopf algebra.
Let H = n≥0 H (n) be a connected graded Hopf algebra. Suppose A is a commutative unital algebra. The subset g 0 ⊂ L(H, A) of linear maps α that send the unit to zero, α(1) = 0, forms a Lie algebra in L(H, A). The exponential exp (α) = j≥0 1 j! α j is well defined and gives a bijection from g 0 onto the group G 0 = ι + g 0 of linear maps, γ, that send the unit of H to the algebra unit, γ(1) = 1 A . An infinitesimal character with values in A is a linear map ξ ∈ L(H, A) such that for x, y ∈ H, ξ(xy) = ξ(x)ι(y) + ι(x)ξ(y). The linear space of infinitesimal characters is denoted The set of characters is denoted by G A ⊂ G 0 . It forms a pro-unipotent group for the convolution product with (pro-nilpotent) Lie algebra g A [13,25]. The exponential map exp restricts to a bijection between g A and G A . The neutral element ι := e A • in G A is given by ι(1) = 1 A and ι(x) = 0 for x ∈ Ker(ε) = H + . The inverse of Φ ∈ G A is given by composition with the Hopf algebra antipode S, i.e., Φ −1 = Φ • S.

Hopf algebra of rooted circle trees
The presentation begins with a description of a class of rooted circle trees. The motivation for this setup will become clear once the theory of Fliess operators in nonlinear feedback control theory and the related Faà di Bruno type Hopf algebra are presented in the next section.
The vertices are strictly ordered and define a clockwise oriented closed edge e. The weight of c i is defined by the number of vertices, i.e., |c i | := |V (c i )|. The empty rct is denoted by 1, and |1| = |V (∅)| = 0. The set of internal vertices of c i is denoted V (c) and is defined by excluding the root vertex from V (c i ).
Here are the first few rcts with weights one up to four: The root has been colored green to distinguish it clearly from the internal vertices. The edge is oriented clockwise starting from the root. A decorated rooted circle tree is a rct c i together with a mapping Dec : V (c) → X from the set of its internal vertices V (c) to the alphabet X : The set (resp. the linear span) of rooted circle trees will be denoted by C • (resp. C • ). The set (resp. the linear span) of rooted circle trees decorated by an alphabet X will be denoted by C • X (resp. C • X ). Consider a particular grading on the set X: |x 0 | = 2 and |x i | = 1 for all i = 0. The degree of a decorated rooted circle tree c i ∈ C • X of weight |c i | = k + 1 is defined by Clearly this grading on X distinguishes internal vertices of a rct decorated by x 0 from the rest. They will play an important role in the Hopf algebraic structure to be defined further below. To this end, it is natural to suppress the decoration by letters x k in favor of using colored vertices f := { , } and to consider bicolored rcts, i.e., rcts with inner vertices being colored either red or black. The red vertices correspond to a decoration by the letter x 0 , whereas the black vertices represent decorations by any of the letters x k , k = 0. Note that the decoration of the root is fixed to be i, Here are a few bicolored rcts up to degree seven: It will also be useful to have the red vertices of a rct c i enumerated consecutively in increasing order. Denote by |c i | and |c i | the number of black and red vertices of c i , respectively. The weight of a colored rct c i is defined as before by the number of its internal vertices plus one. The degree of a bicolored rct c i is defined by: The set (resp. the linear span) of bicolored rooted circle trees will be denoted by C • f (resp. C • f ). The use of bicolored rcts with red vertices enumerated consecutively significantly simplifies the description of the combinatorial structure to be defined next on decorated rooted circle trees.
The set of internal vertices V (c) ⊂ V (c i ) of a rct c i is naturally ordered with the minimal element being the first vertex to the right of the root, and the maximal one being the vertex to the left of the root. Therefore, the elements in any subset J ⊆ V (c) can be written in strictly increasing order. Consider next the notion of admissible subsets The rct i has four admissible subsets: The rct i has five admissible subsets: Remark 3. The notion of admissible subsets of rcts is analogous to the admissible cuts on non-planar rooted trees in the context of the Butcher-Connes-Kreimer Hopf algebra. See [9,25] for reviews. For each admissible subset, J l , in an admissible extraction J , one can associate an oriented polygon inside c i by connecting the vertices of J l by oriented edges according to the total order implied by c i inside each admissible subset J l . For instance, returning to the previous example i the following are all admissible extractions: Pictorially these admissible extractions can be represented, respectively, by oriented polygons inscribed into the rct c i : Note that each polygon starts and ends at a particular red vertex, i.e., the minimal element in the corresponding admissible subset. Let J ∈ W(c i ) be an admissible extraction. Observe that the order of the red vertices implies an order of J = (J l 1 , . . . , J ls ), l 1 < · · · < l s , according to the minimal elements.
The indices indicate the corresponding minimal element of the admissible subsets, that is, 0 ≤ s ≤ |c i | . Let J l be an admissible subset of c i with the l-th red vertex of c i as minimal element. Define (c i /J l ) to be the rct with V (c i /J l ) := V (c i ) − J l , that is, the rct formed by eliminating in V (c) the vertices corresponding to the admissible subset J l . The rct c i n l := (c i /J l ) n l is defined by replacing in c i the l-th red vertex corresponding to the minimal element of J l by a black vertex decorated by x n l and eliminating in V (c) the vertices corresponding to the remaining elements in J l . The rct c n l |J l is defined in terms of the vertices of J l by making the minimal element in J l its root indexed by n l , and the remaining elements of the admissible subset J l are the internal vertices ordered according to the order in J l . Note that |V (c i n l )| = |V (c i )| − |J l | + 1 and |V (c n l |J l )| = |J l |. The rct c n l |J l may be considered a rooted circle subtree (sub-rct) of c i . Hence, to any admissible set J l there corresponds a unique pair of rcts (c i n l , c n l |J l ). This somewhat unwieldy notation becomes much clear when working directly with the diagrammatical notation of rcts. Hence, continuing the example above, the admissible subset In the following, admissible subsets of a rct are indexed by its minimal element. If several admissible subsets with the same minimal element are considered then pairs of indices are used, where the first index indicates the red vertex and the second index counts.
(1) Any admissible subset J l of a rct c i can be associated to a sub-rct of c i by identifying its minimal element as the root. See (3.2) for an example. The basic assumption is that two admissible subsets shall not have the same minimal element, i.e., roots. Apart from this, the following cases can occur when comparing two admissible subsets J k and J l , k = l. If k > l then the two sub-rcts are either strictly nested, The first case is illustrated in the rct where J 1 = { 1 , , , } and J 2 = { 2 , } share one black vertex. (2) The combinatorics described here are similar in flavor to those of Feynman graphs in physics. Those graphs can have subgraphs, and they can be disjoint, nested or overlapping. Feynman graphs appear in perturbative quantum field theory, and their combinatorics are crucial in the context of the solution of the so-called renormalization problem [3]. The analog of an admissible extraction is called a spinney in the context of Feynman graphs. The analog of the set of all admissible extractions is called a wood, which contains all spinneys [2,28].
Observe that for any admissible subset J l the weight |c i | = |c i n l | + |c n l |J l | − 1. Regarding the degrees of c i n l and c n l |J l , it follows that deg(c i n l ) = |c i |−2|J l | −|J l | +1, where |J l | and |J l | denote the number of red and black vertices in J l , respectively. For the extracted rct . Consider next the rct c n l |J l corresponding to the admissible subset J l as a sub-rct in c i . Since an admissible extraction J consists of strictly disjoint admissible subsets, one may extract several sub-rcts from a rct c i . Hence, to any admissible extraction J := {J l 1 , . . . , J l k }, there corresponds a unique rct c i n l 1 ···n l k := (c i /J l 1 ∪ · · · ∪ J l k ) n l 1 ···n l k with k red vertices replaced by black vertices decorated by x n l 1 , . . . , x n l k and a sequence of sub-rcts c The linear span of bicolored rooted circle trees C • f is extended to a commutative k-algebra H • f by using the disjoint union as a product, i.e., m H • C (c i , c j ) =: c i c j . This makes H • f a polynomial algebra with C • f as a generating set. A coproduct is defined on H • f in terms of admissible extractions. Let c i be a bicolored rct, the map ∆ : The coproduct is extended multiplicatively to H • f . The sum on the right-hand side is over all admissible extractions of the rct c i , including the empty set and the full rct. Note that it includes k internal summations, i.e., 1 ≤ n l 1 , · · · , n l k ≤ m. In other words, Einstein's summation convention applies so that pairs of indices are implying a summation from 1 to m. On the left-hand side of the tensor product there is always a single bicolored rct with root indexed by i, where several internal vertices have been eliminated, and k internal black vertices are indexed by n l 1 , · · · , n l k . The latter correspond to the minimal elements of the admissible subsets J l 1 , . . . , J l k , i.e., the red vertices enumerated l 1 , . . . , l k that have been turned into black vertices. On the right-hand side of the tensor product there is a monomial of k sub-rcts with roots indexed by n l 1 , · · · , n l k . Examples are in order to make this definition more transparent. First, note that the rct with no internal vertices is primitive, since there are no proper admissible subsets. That is, Similarly, the rcts with only black internal vertices also has no proper admissible subsets, therefore, Red vertices imply admissible subsets. Consider the following examples: Regarding the last example, the reader is referred to (3.2).
Theorem 6. H • f is a connected graded commutative unital Hopf algebra. Proof. The grading of H • f = n≥0 H • n is given in terms of the degree of rcts, namely, deg(c i c j ) = deg(c i ) + deg(c j ). Next coassociativity is shown, i.e., (∆ ⊗ id) • ∆ = (id ⊗ ∆) • ∆. Some notation is introduced to make the argument more transparent. Suppressing the internal summations, the coproduct is written as Here τ := c n l 1 |J l 1 · · · c n l k |J l k denotes the set of completely disjoint sub-rcts corresponding to an admissible extraction J = {J l 1 , . . . , J l k } ∈ W(c i ), and c n l |J l ⊂ c i is the sub-rct corresponding to the admissible subset J l of c i . The sum is taken over the set of sub-rct corresponding to J = {J l 1 , . . . , J l k }. Extracting the set of sub-rcts τ is denoted by c i /τ := c i n l 1 ···n l k . This notation follows the one used in the context of Hopf algebras of rooted trees or Feynman graphs [13]. Any sub-rct of c i may have itself sub-rcts. Indeed, for s > t and admissible subsets J s ⊂ J t , the two sub-rcts c ns |Js and c nt |Jt of a rct c i for which c ns |Js is a sub-rct of c nt |J l yield (3.4) (c i /c ns |Js )/(c nt |Jt /c ns |Js ) = c i /c nt |Jt . In this notation, the identity to be verified is the equality between Hence, what needs to be shown is that for each τ ⊂ c i The argument given here follows [13]. Let τ ⊂ c i such that τ ⊂ τ ⊂ c i . Then τ /τ ⊂ c i /τ . On the other hand, for τ ⊂ c i /τ there corresponds a τ such that τ ⊂ τ ⊂ c i and τ /τ = τ . Equality follows from (3.4).
Below another (indirect) proof will be presented by showing that the Hopf algebra H • X of decorated rcts is isomorphic to the output feedback Hopf algebra. The reduced coproduct ∆ is defined as Recall that W (c i ) is the set of proper admissible extractions, i.e., the empty admissible set J 0 := ∅ as well as the total admissible subset is a connected graded bialgebra, and therefore a Hopf algebra. The antipode S : is given in terms of the following recursive formulas starting with S(1) = 1 and A few examples are in order: In light of the last calculation and the cancellation appearing in it when using (3.5), one may wonder whether a cancellation free formula is available. The answer is yes, and it is known as Zimmermann's forest formula as discussed next [13].
3.1. Zimmermann forest type formula for the antipode of H • f . Zimmermann's celebrated forest formula first appeared in the context of the renormalization problem in perturbative quantum field theory [30]. It provides a closed form solution to Bogoliubov's so-called counterterm recursion for Feynman graphs [2,3]. The work of Connes-Kreimer unveiled the Hopf algebraic structure underlying the theory of renormalization [4,5]. As a result, a forest type formula, i.e., a closed form solution for the antipode, can be given in the context of the Butcher-Connes-Kreimer Hopf algebra of rooted trees. It is defined by extending the notion of admissible cuts on rooted trees to all cuts. See [9,25] for details. From a combinatorial point of view forest type formulas are interesting since they provide a way to calculate antipodes which is free of cancellations [6,13]. In control theory applications they have the potential to significantly reduce computation times [16,18,20].
In this section, a forest type formula for the antipode of the Hopf algebra of rooted circle trees is presented. It also provides a closed form solution for the recursions (3.6), which is moreover free of cancellations. It is defined by replacing admissible extractions by all extractions. However, the situation is somewhat involved due to the internal summations over the decorations n l 1 , · · · , n l k associated with extracting admissible subsets from a rct in the coproduct Recall that in the definition of an admissible extraction J ∈ W(c i ) of a rct c i all admissible subsets of J have to be strictly disjoint. This constraint is now relaxed by allowing for extractions I = {J l 1 , · · · , J l k }, l 1 < · · · < l k , which may contain admissible subsets that are either nested, The set of all extractions of a rct c i is denoted E(c i ). Note that W(c i ) ⊆ E(c i ). As an example, consider the rct i 1 2 and its admissible subsets: Then E(c i ) contains among others the extractions I 1 = {J 12 , J 2 } with J 2 ⊂ J 12 . Another example is the rct i 1 2 and its admissible subsets: Then E(c i ) contains among others the extractions: which are nested, i.e., J 2 ⊂ J 14 respectively J 2 ⊂ J 13 . In the rct one finds among others the extractions: Elements in an extraction I := {J l 1 , . . . , J l k } are either disjoint or strictly nested. This implies a natural poset structure on each extraction, which is represented in terms of a non-planar rooted tree. The tree reflects the resulting hierarchy of admissible subsets of a rct c i . Recall that by definition a non-planar rooted tree t is made out of vertices and nonintersecting oriented edges such that all but one vertex have exactly one outgoing line and an arbitrary number of incoming lines. The particular vertex with no outgoing line is called the root of the tree. It is drawn on top of the tree, whereas the leaves are the only vertices without any incoming lines. The weight of a rooted tree t is defined to be its number of vertices, (t) := |V (t)|. The following list contains rooted trees up to weight four: The root has been colored green. The empty rooted tree is denoted by 1. The set (resp. space) of rooted trees is denoted by T (resp. T ). (See [25] for details.) Recall the map B + defined on rooted trees. It maps rooted trees t 1 , . . . , t k to the rooted tree t := B + (t 1 , . . . , t k ) by connecting each of the roots of t 1 , . . . , t k via an edge to a new root. The tree with only one vertex, i.e., the root, and no edges is written = B + (1). The rest of the above trees can then be written B + (B + (1)), B + (B + (1), B + (1)), B + (B + (B + (1))), etc. Next, rooted trees are decorated in such a way that they represent the hierarchy of admissible subsets in an extraction of any rct. This hierarchy reflects the internal summations in the coproduct (3.8) on rcts. Let c i be a rct and I := {J l 1 , . . . , J l k } ∈ E(c i ) an extraction. Define a map h : T → {i, l 1 , . . . , l k } by decorating the root of t ∈ T by i. An edge in t goes out from a vertex decorated by l a to a vertex decorated by l b < l a if and only if J la ⊂ J l b . Regarding example (3.9), the following rooted trees are associated with the extractions I 1 , I 2 , I 3 , I 4 ,  (1)). Note that rooted trees corresponding to admissible extractions J := {J l 1 , . . . , J l k } are strictly of the form B i + (B l 1 + (1), B l 2 + (1), . . . , B l k + (1)). Using extractions, together with decorated rooted trees to encode the hierarchical structure of extractions of a rct, the antipode S of c i ∈ H • f is given in the following theorem. The decorated rooted tree corresponding to an extraction where t i I is the decorated rooted tree corresponding to the hierarchy of admissible subsets underlying the extraction I = {J l 1 , . . . , J l k }. The setẼ(c i ) ⊂ E(c i ) must not include J i = V (c i ). The map χ is defined on the decorated rooted tree t i I := B i + (t ls 1 , · · · , t ls b ) as The admissible subsets J i = V (c i ) and J 0 = ∅ correspond to c i = c i |J i and 1 = c 0 |J 0 , respectively. Note that the empty extraction I = {J 0 } corresponds to the rooted tree As another example, consider the rooted tree t i (3.9). Then Again, this gets much easier by working diagrammatically. Indeed, observe that I 3 corresponds to such that Note that the use of rooted trees solely reflects the need to keep track of the hierarchy of admissible subsets in an extraction, which is reflected in the extra summations in the coproduct (3.8). The antipode of the rct (3.9) consists of 26 terms corresponding to all possible extractions, including those mentioned above.

Proof. For any
where The goal is to show that the map S Z satisfies the recursion The uniqueness of the antipode then implies that S = S Z . Recall that W (c i ) is the set of proper admissible extractions of the rct c i , i.e., it contains neither J 0 nor J i . In addition, recall that the admissible extractions are a subset of all extractions, i.e., W(c i ) ⊆ E(c i ). This allows one to break the sum (3.12) into pieces such that The first term on the right-hand side corresponds to the admissible subset J 0 = ∅. The first sum on the right-hand side is over strictly pairwise disjoint subsets J := {J l 1 , . . . , J l k }, that is, proper admissible extractions. Recall that those extractions correspond to rooted trees of the form t i J = B i + (B l 1 + (1), . . . , B l k + (1)). Therefore, The second sum on the right-hand side of (3.13) is over extractions I := {J a 1 , . . . , J as }, which contain at least one pair of admissible subsets, J ap , J aq , a p = a q , such that either J ap ⊂ J aq or J aq ⊂ J ap . Assume that J s is an admissible subset of the rct c i with only one red vertex, i.e., its minimal element. This implies that the corresponding rct c ns |Js is primitive. Therefore, the rooted tree encoding the nesting is simply given by B i + (B s + (1)). Considering J s as an admissible extraction J := {J s } of c i yields a single term in S Z S Z (c i ) = −c i |J i + · · · + (c i |J i /J s ) ns c ns |Js + · · · , which can be written |Js is primitive. Assume now that J s contains more than one red vertex, which implies that the rct c ns |Js corresponding to the admissible subset J s has itself non-trivial sub-rcts. This means that there exist extractions I = {J s , J l 1 , . . . , J l k } ∈ E(c i )\W(c i ) such that J la ⊂ J s for all a = 1, . . . , k, i.e., I := {J l 1 , . . . , J l k } ∈ E (c ns |Js ), where E (c ns |Js ) are all proper extractions of c ns |Js . This yields ,...,J l k } J la ⊂Js,a=1,...,k which can be written Recall that Einstein's convention is in place, which implies a summation over pairs of indices. For an arbitrary proper admissible extraction I := {J l 1 , . . . , J l k } ∈ W (c i ) this generalizes to which then implies that Calculations of the antipode using formula (3.5) show non-trivial cancellations of terms (see Table 1). On the other hand, the forest formula in Theorem 7 is free of such cancellations. Indeed, this follows from the observation that each extraction I =

3.2.
Pre-Lie algebra of rooted circle trees. A right pre-Lie algebra is a k-vector space P with a bilinear composition : P × P → P that satisfies the right pre-Lie identity for a, b, c ∈ P . As a consequence, the bracket defined by [a, b] := a b − b a satisfies the Jacobi identity. Left pre-Lie algebras are defined via an analogous identity. (See [1,26] for details.) Restricting the coproduct (3.8) to extractions of single admissible subsets, i.e., linearizing it on both sides, leads to a map∆ : One can show that (3.15) satisfies the right co-pre-Lie relation The map π 23 operates on triple tensor products by exchanging the last two elements, i.e., π 23 (a ⊗ b ⊗ c) = a ⊗ c ⊗ b. The combinatorics of this right co-pre-Lie relation is best described by translating it to the dual side of the Hopf algebra of rcts. It will be seen that the corresponding pre-Lie algebra can be described in terms of insertions of rcts into rcts. However, the admissibility of such an insertion depends on the specific decoration of vertices and roots. Therefore, identity (3.16) translates to a right pre-Lie structure on the graded dual (H • X ) * of the Hopf algebra H • X of decorated rcts. Denote by z c i the normalized dual of the rct c i in the graded dual, that is, z c i , c j = z c i (c j ) = δ c i ,c j , and zero else. The linear map z c i is an infinitesimal character of H • f , hence a primitive element in the Hopf algebra (H • f ) * . Therefore, the convolution product The resulting Lie bracket on the Lie algebra g = Prim((H • f ) * ) spanned by the primitive elements z c i is given by The right pre-Lie product on rcts, c i c j , is obtained by inserting c j into c i . It can be described by writing the rct c i in terms of the operator Θ (x k ) for 0 ≤ k ≤ m. It is defined on rcts decorated by the alphabet X by inserting a vertex decorated by x k to the right of the root. Recall that the vertices of c i are strictly ordered, which implies that the decoration can be written as a word η = x k 1 · · · x k l =:ηx k l = x k 1η ∈ X * , where X * denotes the set of words over the alphabet X. Then where c i ∅ is the rct with no internal vertices. Equivalently, The right pre-Lie product is given as follows for rcts c i = Θ (x k 1 ) (c i ) = Θ (η) (c i ∅ ) and c j = Θ (η ) (c j ∅ ) with decorations η, η ∈ X * : (The definition of Θ has been linearly extended to R X .) This is the multivariable version of the pre-Lie product in [12]. Here the shuffle product of two words is defined by where x i , x j ∈ X,η,ξ ∈ X * and with η ∅ = η [27]. Hence, the pre-Lie product of two rcts c i , c j is the sum over all insertion of c j at vertices of c i decorated by x j The insertion itself is defined by changing the decoration of the insertion vertex from x j to x 0 and by shuffling the word decorating the vertices following the insertion vertex into the word decorating the inner vertices of c j . For example,

Fliess operators and their output feedback interconnection
The goal of this section is to show that the Hopf algebra H • f has a concrete application in the theory of nonlinear control systems. In particular, when two input-output systems represented in terms of Chen-Fliess series are interconnected to form a feedback system, the coordinate maps of the underlying group form an Hopf algebra which is isomorphic to the Hopf algebra H • f . Consider an alphabet X = {x 0 , x 1 , . . . , x m } and any finite sequence of letters from X, η = x i 1 · · · x i k , called words. The set of all words including the empty word, ∅, is designated by X * . It forms a monoid under catenation. Any mapping c : X * → R is called a formal power series. The value of c at η ∈ X * is written as (c, η) and called the coefficient of η in c. Typically, c is represented as the formal sum c = η∈X * (c, η)η. The collection of all formal power series over X is denoted by R X . It forms an associative R-algebra under the catenation product and an associative and commutative R-algebra under the shuffle product [10,27].
One can formally associate with any series c ∈ R X a causal m-input, -output operator, F c , in the following manner. Let p ≥ 1 and t 0 < t 1 be given.
where x i ∈ X,η ∈ X * , and u 0 = 1. The input-output operator corresponding to c is the Chen-Fliess series or Fliess operator [10, 11] Given Fliess operators F c and F d , where c, d ∈ R X , the parallel and product connections satisfy F c + F d = F c+d and F c F d = F c d , respectively [10]. When Fliess operators F c and F d with c ∈ R X and d ∈ R m X are interconnected in a cascade fashion, the composite system F c • F d has the Fliess operator representation F c•d , where the composition product of c and d is given by [7,8]. Here ψ d is the continuous (in the ultrametric sense) algebra homomorphism from R X to End(R X ) uniquely specified by ψ d ( i = 0, 1, . . . , m for any e ∈ R X , and where d i is the i-th component series of d, d 0 := 1, and ψ d (∅) is the identity map on R X . This composition product is associative and R-linear in its left argument. In the event that two Fliess operators are interconnected to form a feedback system as shown in Figure 1.1, it was shown in [21] that there always exists a unique generating series c@d such that y = F c@d [u] whenever c, d ∈ R m X . This so called feedback product of c and d can be viewed as the unique fixed point of a contractive iterated map on a complete ultrametric space, but this approach provides no machinery for computing the product.
Hopf algebraic tools are now employed to compute the feedback product [14,15,17]. Consider the set of operators F δ := {I +F c : c ∈ R m X }, where I denotes the identity operator. It is convenient to introduce the symbol δ as the (fictitious) generating series for the identity map. That is, F δ := I such that I + F c := F δ+c = F c δ with c δ := δ + c. The set of all such generating series for F δ will be denoted by R m X δ . The first theorem describes the multivariable output feedback group which is at the heart of the method. The group product is described in terms of the modified composition product of c ∈ R X and d ∈ R m X , where φ d is the continuous (in the ultrametric sense) algebra homomorphism from R X to End(R X ) uniquely specified by φ d ( i = 0, 1, . . . , m for any e ∈ R X , and where d 0 := 0, and φ d (∅) is the identity map on R X . It can be easily shown that for any x i ∈ X The following (non-associativity) identity was proved in [24] for all c ∈ R X and d, e ∈ R m X . The central idea is that (F δ , •, I) forms a group of operators under the composition where c δ • d δ := δ + d + c• d =: δ + c d. 1 Given the uniqueness of generating series of Fliess operators, this assertion is equivalent to the following theorem.
Theorem 8. [17] The triple (R m X δ , •, δ) is a group. 1 The same symbol will be used for composition on R m X and R m X δ . As elements in these two sets have a distinct notation, i.e., c versus c δ , respectively, it will always be clear which product is at play.

4.1.
Faà di Bruno type Hopf algebra. A Faà di Bruno type Hopf algebra is now defined for the coordinate maps of the feedback group. For any η ∈ X * , the corresponding coordinate map is the element of the dual space R m X * a i η : R m X → R : c → (c i , η) := a i η (c), where i = 1, 2, . . . , m. Let V denote the R-vector space spanned by these maps. Define |η| x i as the number of times the letter x i ∈ X appears in the word η. If the degree of a i η is defined as deg(a i η ) = 2 |η| x 0 + m j=1 |η| x j + 1, then V is a connected graded vector space, that is, and V (0) = R1. Consider next the free unital commutative R-algebra, H, with product m H (a i η ⊗ a j ξ ) = a i η a j ξ . This product is associative and unital with unit 1. The graduation on V induces a connected graduation on H with deg(a i η a j ξ ) = deg(a i η )+deg(a j ξ ) and deg(1) = 0. Specifically, H = n≥0 H (n) , where H (n) is the set of all elements of degree n and H (0) = R1.
Three coproducts are now introduced. The first coproduct is id is the identity map on V + , and θ k denotes the endomorphism on V + specified by θ k a i η = a i x k η for k = 0, 1, . . . , m and i, j = 1, 2, . . . , m. The first few terms of ∆ j are: The second coproduct is∆(H) ⊂ V ⊗ H, which is induced by the identity , η ∈ X * . This coproduct can be computed recursively as described in the following lemma, which is the multivariable version of Proposition 3 in [12].
. . , m, where id denotes the identity map on H.
The third coproduct is defined as ∆a i η :=∆a i η + 1 ⊗ a i η . The coassociativity of ∆ follows from the associativity of the product c d and the identity ∆a i η (c, d) = ((c d) i , η). This coproduct is used in the following central result.
The next theorem provides a fully recursive algorithm to compute the antipode for the feedback group.
Theorem 11. [16,17] The antipode, S, of any coordinate map a i η ∈ V + in the output feedback group can be computed by the following algorithm: 1: Recursively compute ∆ via (4.4). 2: Recursively compute∆ via Lemma 9. 3: Recursively compute S by where ε : H → R and e : R → H are the counit and unit maps of H, respectively. The reduced coproduct is defined as Applying the algorithm above gives the antipode of the first few coordinate maps: )a n 1 x 0 − S(a i xn 1 x 0 )a n 1 ∅ − S(a i x 0 xn 2 )a n 2 ∅ − (4.8) S(a i xn 1 xn 2 )a n 1 ∅ a n 2 )a n 1 ∅ a n 2 ∅ = −a i x 2 0 + a i xn 1 a n 1 x 0 + a i xn 1 x 0 a n 1 ∅ + a i x 0 xn 2 a n 2 ∅ − a i xn 1 a n 1 xn 2 a n 2 ∅ − a i xn 1 xn 2 a n 1 ∅ a n 2 ∅ , where i, j, k, l = 1, 2, . . . m. Recall that Einstein's summation convention is in place, so these expressions have implied summations. The explicit calculation for S(a i x 2 0 ) is shown above to demonstrate that this approach, not unexpectedly, involves some inter-term cancellations. This is consistent with what is known about the classical Faà di Bruno Hopf algebra and Zimmermann's forest formula. The latter can provide a cancellation free approach to computing the antipode [6,22]. Such a forest formula without cancellations will be given shortly using the results from subsection 3.1. But first the link between the Hopf algebra of decorated rct and the Faà di Bruno type Hopf algebra for the output feedback group is presented in the following theorem.
Theorem 12. The Hopf algebras H • X and H are isomorphic. Proof. Define the bijection ϕ : C • X → H, ϕ(c i ) := a i η , where the word η consist of the letters decorating the rct c i , and the order is implied by the order on c i . The map ϕ is extended multiplicatively to an algebra isomorphism. The main claim is that the coproduct (3.3) satisfies the set of recursions in Lemma 9. Note that this also implies coassociativity of (3.3). To this end, two operators Θ and Θ are defined on C • f . Both insert vertices to the right of the root The map Θ (n 1 ) is defined by inserting a black vertex indexed by n 1 to right of the root The sub-rct c n 1 |J 1 is defined by making the minimal element in J 1 its root indexed by n 1 , and the remaining elements of the admissible subset J 1 are the internal vertices ordered according to the order in J 1 . The sum in the second term on the right-hand side is over all admissible subsets that have the first red vertex of c i as its minimal element. This corresponds to extracting single sub-rcts. In fact, the last sum can be given a name The notation becomes clear when comparing it with the recursive definition of the coproduct in Lemma 9. Recall that black and red vertices of a rct c i ∈ C • X represent vertices which are decorated by x k , k = 0, and x 0 , respectively. The rct c i ∈ C • X with vertices decorated by x k 1 · · · x k l of weight l + 1 and degree deg(c i ) is mapped via ϕ to the coordinate function a i x k 1 ···x k l of degree deg(a i x k 1 ···x k l ). The map n 1 corresponds via ϕ to the classical deshuffling coproduct, i.e., (ϕ ⊗ ϕ) i (c i ) = ∆ i (ϕ(c i )), such that (ϕ ⊗ ϕ)∆(c i ) = ∆(ϕ(c i )).
On the right-hand side the coproduct is that of (H, m H , ∆) in Theorem 10.
In light of Theorem 12, the forest formula presented in Theorem 7 provides a cancellation free formula for the antipode in H. For example, recalling (3.7) and (4.8), Table 2. Composition products of formal power series induced by Fliess operator compositions operator composition generating series coproduct remarks a n 1 x 0 + a i xn 1 x 0 a n 1 ∅ + a i x 0 xn 2 a n 2 ∅ −a i xn 1 a n 1 xn 2 a n 2 ∅ − a i xn 1 xn 2 a n 1 ∅ a n 2 ∅ = S(a i Composition of Chen-Fliess series and the convolution product. In this subsection, the various composition products appearing in the previous sections are examined in more depth to reveal their relationship to each other as well as to the convolution product on the dual of H. The situation is summarized in Table 2. The product c•d is included here for completeness, but its role in the theory is relatively minor. Each composition induces a corresponding coproduct via identities like (4.5). These coproduct are easily shown to be related by adding specific terms of the primitive a i η ⊗ 1 + 1 ⊗ a i η as shown in Figure 4.1. With each c δ ∈ R m X δ , one can identify an element Φ c ∈ L(H, R) where by Φ c : a i η → a i η (c) = (c i , η), Φ c (1) = 1, and Φ c (a i η a j ξ ) = a i η (c)a j ξ (c) = Φ c (a i η )Φ c (a j ξ ). Given that L(H, R) ⊂ R X * * , there is clearly a canonical embedding of L(H, R) in R X so that characters of H can be identified with series in R X . In addition, . So in some sense an identification can also be made between convolution of characters and composition of series. In fact, this can be done for any of the four series compositions described above. This is not completely surprising from a system theory point of view given the fact that the composition of two linear time-invariant systems with respective impulse responses h c and h d has the impulse response h c h d , where in this case ' ' denotes function convolution. In the analytic case, function convolution is equivalent to the composition of the corresponding generating series, i.e., h c • h d = h c•d , which in turn reduces to a convolution sum over a one letter alphabet [19]. Put another way, the Hopf convolution product induced by c • d can be viewed as a nonlinear generalization of this classic convolution theorem in linear system theory. Continuing with the above development, since the composition inverse of c δ in Theorem 8 is c −1 δ = δ + c −1 with a i η (c −1 ) = (S(a i η ))(c), it follows that Φ −1 c = Φ c • S = Φ c −1 . Finally, the infinitesimal characters associated with H can be identified with elements ξ c ∈ L(H, R), where ξ c (a i η ) = k≥1 (−1) (k−1) (c i , η) k /k for any c ∈ R X and ξ c (1) = 0.