{'fraction_non_alphanumeric': 0.056355085481299076, 'fraction_numerical': 0.014108955856528672, 'mean_word_length': 3.887442043997238, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 64, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tropical time series, iterated-sums signatures and quasisymmetric functions

Aiming for a systematic feature-extraction from time series, we introduce the iterated-sums signature over arbitrary commutative semirings. The case of the tropical semiring is a central, and our motivating example. It leads to features of (real-valued) time series that are not easily available using existing signature-type objects. We demonstrate how the signature extracts chronological aspects of a time series, and that its calculation is possible in linear time. We identify quasisymmetric expressions over semirings as the appropriate framework for iterated-sums signatures over semiring-valued time series.


Introduction
Recent developments [20,44,45,50,70] have shown that various forms of iterated-sum and iterated-integral operations can form a useful component in machine learning pipelines for sequential data. Originating from the study of (discretized) controlled ordinary differential equations (ODEs) [29,52], they are particularly apt to model input-output relations that are well-approximated by dynamical systems [22,23]. In fact, the iterated-integrals signature IIS(x) 1 of a (smooth enough) multidimensional curve x = (x (1) , . . . , x (d) ) : [0, T ] → R d , is the solution to a certain universal controlled ODE [31,Proposition 7.8]. It is universal in the sense that the solution to any other controlled ODE can be well-approximated by a linear expression of the iterated-integrals signature. On a more concrete level, the entries of the "classical" iterated-integrals signature are real numbers, indexed by words w = w 1 · · · w k in the alphabet A = {1, . . . , d}, and given as follows Here and throughout the rest of the article, we use subscript notation to denote the value at (continuous or discrete) time t.
Not all input-output relations are well-modeled by controlled ODEs, though. As an extreme example, we mention that a controlled ODE does not care about so-called "treelike" excursions of the driving signal [40]. The iterated-integrals signature can therefore, for example, not distinguish the following two one-dimensional curves, t ∈ [0, 1], t → 0 and t → sin(2πt).
There are several ways to circumvent this particular problem, e.g. "lifting" a onedimensional curve to a two-dimensional curve [30]. The iterated-sums signature (ISS) introduced in [20] (see also [45,70]) forgoes this particular problem altogether and brings the added benefit of working directly with discrete time series (in order to apply the theory of iterated integrals to discrete-time sequential data, it has to be interpolated to a, say, piecewise linear curve). But even the ISS cannot "see" all aspects of a time series. Indeed, the ISS is invariant to time warping and hence cannot distinguish time series run at different speeds (see Lemma 4.2 for a proper definition). It turns out that such invariance is often desirable. The search for such invariants was in fact the starting point of [20], where it is shown that the ISS contains all polynomial expressions in the time series entries that are invariant to time warping. There are, however, non-polynomial time-warping invariant functionals as the following example shows (this is well-defined for any time series z that is eventually constant): Such expressions are ubiquitous in financial mathematics, in particular the pricing of American options [58]. Moreover, it is folklore knowledge that such expressions are poorly approximated by polynomials. This is related to the fact that this functional is not well-approximated by (discretized) ODEs.
The aim of the work at hand is to introduce a systematic feature-extraction method for time series that encompasses functionals as the one in eq. (2).
The entry point for our investigation is the observation that (2) can be considered as a polynomial expression if one changes the underlying field of the reals to the tropical (or min-plus) semiring. This, as well as other semirings, have (a subset of) the reals as the underlying set, and only the operations of "addition" and "multiplication" have a different meaning. As a result, this opens ways to consider real-valued time series under many different lenses. In particular, it allows us to consider (2) as part of an iterated-sums signature. Moreover, semirings whose underlying sets are not given by subsets of the real line enable one to look at time series with values in more general spaces.
After this general motivation, we now present two ways to naturally arrive at the signature we introduce in this work, where the first one makes the remarks above, in particular those concerning the invariant in (2), more concrete.
1. Invariants of a time series. Accommodating the discrete nature of the time series x = (x 1 , x 2 , . . . , x N ), x i ∈ R d , one may consider the discrete analog of (1), i.e., the so-called iterated-sums signature ISS over the reals is defined in terms of the increments Here w = w 1 · · · w k is a word over a certain alphabet -larger than A from above -which is adapted to the discrete nature of the summation operation. It was shown in [20] that the map ISS(x) stores all polynomial invariants to time warping (and translation).
Alternatively, the ISS can be defined as ISS(z) p,q , w = p<i 1 <i 2 <···<i k ≤q (z i 1 ) w 1 · · · (z i k ) w k , and the former definition is obtained by evaluating at increments, z i = δx i . The latter definition yields an object that is invariant to insertion of 0 ∈ R into the time series z = (z 1 , z 2 , . . .), and it is this viewpoint that generalizes to arbitrary semirings. More precisely, in Section 2 we construct a signature over commutative semirings that is invariant to the insertion of zeros of the semiring. The underlying mathematical object are quasisymmetric expressions over commutative semirings, which, to the best of our knowledge, we introduce for the first time in Section 3. The way back from invariants to inserting zeros to time-warping invariants is not as straightforward as in the case when considering computations over a field, and we investigate it in Section 4. As we will see, expressions like (2) will be covered by the resulting theory.

Cheap chronological information of a time series.
The importance of convolutional neural networks (CNNs) is hard to overestimate [48]. Their success, in particular in image recognition, is usually attributed to two ingredients: a) weight sharing which reduces, in comparison to fully connected networks, the amount of parameters and hence allows for deeper architectures, and b) convolution and its particular structure (usually combined with maxpooling) leads to desirable properties with respect to image recognition (modeling of receptive fields, approximate translation invariance, etc.).
Although CNNs have been successfully applied in the context of time series data (see [8,27] for recent surveys), this does not seem to be based on the inherent properties of sequential data. In particular, the structure of time series is very different from that of images. It is not clear why the receptive-field structure of CNNs captures intrinsically meaningful information of sequential data. Moreover, time series possess a characteristic that images do not: a chronology, that is, the values of the series are ordered according to the time index. We explain this using an example.
where a 1 , a 2 ∈ R are the parameters of the convolutional kernel. This network can learn to answer questions of the following type.
• Is there a 16 in the sequence somewhere? (Just as a full-blown CNN on image data can answer the question: Is there a dog somewhere in the picture?) • Is there a 2 directly followed by a 16 somewhere in the sequence? (indeed, with a 1 = −1, a 2 = 1 one gets output 14 if and only if the statement is true) However, it can not answer the question • Is there a 2 somewhere and then, sometime after, a 16 in the sequence?
We believe that chronological questions of this type are the relevant questions for time series. Note that the following architecture allows us to answer this question Indeed, again with a 1 = −1, a 2 = 1, the output is 14 if and only if the question is answered positively.
Example 1.2. The preceeding example was strictly for illustrative purposes and the chronological question posed there can be answered by other means (for example a simple inite state automaton). To see how its conceptual idea can be applied in a deep learning pipeline though, we have set up the github repository https: // github. com/ diehlj/ tropical-time-series , which implements the following binary classification problem.
One sample x is generated as follows (we have chosen the 'pattern' [2, −3, 16] of length three now).
• Set Here τ ∈ S 3 is the identity for samples of Class A, and it is drawn randomly from S 3 \ {id S 3 } for samples of Class B. The task is to learn distinguishing the two classes. This is again a "chronological question", as in the preceeding example. We test two different architectures • FCN: a fully connected network of depth with linear readout. Trainable parameters: 5762 (for T = 100).
• ISS: a layer inspired by the current work, given by where f θ j are learnable functions (neural networks themselves, in our implementation), followed by a linear "readout" layer. Trainable parameters: 342 (for any T ).
The results in Example 1.2 show that the FCN (wth a much larger number of parameters), does consistently worse than the ISS. The inductive bias of "chronological question", in this simple example, seems to help our architecture, for small noise, to achieve perfect classification.
Abstractly we can describe functions that extract such chronological features of sequences x ∈ R N in the following form where Now, in this generality, such features are computationally intractable, even for modest values of N and k, since K has to be evaluated N k times. The iteratedsums signature presented in this work represents a special case of the functions K and pool that is tractable. The application of this structure in deep learning pipelines will be addressed in subsequent work.
The central object of this work, the iterated-sums signature ISS S will be properly defined in (17) below. To get there, we need to work through some algebraic background in Section 2 first. We therefore now give a preview in the setting of the tropical semiring S = R min+ with addition ⊕ min+ given by the minimum, and multiplication min+ given by the sum of real numbers. Let (z 1 , z 2 , z 3 , . . . ), z i ∈ R, be an infinite time series. Define ISS Rmin+ , indexed by words w = w 1 · · · w k in the alphabet A = {1, 2, 3, . . .} 2 and 1 ≤ s ≤ t < +∞, as For example (see also Figure 2) We remark two, maybe, non-obvious properties of this object. Firstly, in order to calculate ISS Rmin+ over large intervals, it suffices to calculate it over small intervals: This is also the reason why expressions that seem to have polynomial complexity (after all, the third-order iterated sum in (4) takes the maximum of O(|t − s| 3 )-terms), are in fact calculable in linear time, as we will see in Section 5.
Secondly, we note that the product (in the semiring) of any iterated sums (which are iterated minima in the current example) can be written as the sum (in the semiring) of (different) iterated sums: Both of these facts might come as no surprise to people familiar with iterated integrals or iterated sums over fields. Indeed, the first property is a version of Chen's identity. It just says that the computation of iterated integrals and iterated sums can be split into calculations on subintervals. This property is usually encoded algebraically by the noncocommutative deconcatenation coproduct on the unital tensor algebra over an alphabet. The general form of Chen's identity in our setting is stated in Lemma 2.10.
Integration by parts implies that linear combinations of iterated integrals are closed under multiplication. This finds its abstract algebraic formulation in terms of the commutative shuffle product on the unital tensor algebra over an alphabet [16,63]. Analogously, its discrete counterpart, i.e., summation by parts, permits to define an algebra on iterated sums, leading to the notion of commutative quasi-shuffle algebra [32]. The general form of the quasi-shuffle identity in our setting is found in Lemma 2.13.
Maybe more interestingly, new phenomena appear when working over general semirings. As we will see in Section 4, over an idempotent semiring, non-strict iterated sums satisfy a shuffle identity and in this sense behave like iterated integrals. These non-strict iterated sums also give a nice way to get certain time-warping invariants of a real-valued time series, covering expression (2).
The paper is organized as follows. In Section 2 we define the iterated-sums signature over a commutative semiring. In Section 3 we take a closer look at quasisymmetric functions, which are underlying the iterated-sums signature and are of independent interest. In Section 4 we return to the question of time warping invariants in the context of iterated-sums signature over a commutative semiring. Section 5 exposes an algorithm for efficient calculation of iterated sums. It is based on Chen's identity, but alternatively can be considered as a dynamic programming principle in play here. We finish with conclusions and an outlook in Section 6. In Appendix A we present a categorical view on semirings, semimodules, and semialgebras. Such a categorical view is useful in highlighting the similarities to the theory of rings, modules, and algebras.

Related works
We finish this introduction by mentioning related literature. We already indicated how iterated sums and integrals have, in the last decade, been successfully applied as a feature extraction method in machine learning. The relation of iterated sums to the Hopf algebra of quasisymmetric functions [55] was established in [20].
Symmetric functions form an important subspace and the generalization of this subspace to the setting of semirings has been investigated in [14,42,43].

Iterated-sums signatures over a semiring
We start by introducing basic concepts from semiring theory. Relevant references are [49,53,71]. The definitions and constructions recalled here are in some sense "hands-on". For a more abstract, i.e. categorical, view see Appendix A. For example, starting from an alphabet A = {a 1 , . . . , a n }, the set of (finite) words over A forms, under concatenation, the free non-commutative monoid, denoted by A * . The empty word, e, is the neutral element. The length of a word w = a i 1 · · · a i k ∈ A * is denoted (w) = k. A monoid morphism is a map between monoids which is compatible with the products and takes the neutral element to the neutral element. Note that for an alphabet A and any monoid (M, , 1 M ), every map φ : A → M can be uniquely extended to a monoid morphismφ : A * → M by definingφ(e) = 1 M and for any word w = a i 1 · · · a i k ∈ A * ,φ(a i 1 · · · a i k ) := φ(a i 1 ) · · · φ(a i k ). In other words, A * is the free monoid over A.
The notion of semiring combines two monoids in a compatible, i.e. distributive, way. However, contrary to rings, the invertibility under addition is not part of the requirements.
• 0 S S s = s S 0 S = 0 S for all s ∈ S, and • multiplication distributes over addition Note that the parentheses on the right-hand sides of the identities in (5) can be omitted when assuming the common precedence of multiplication over addition. A semiring S is called idempotent, if for all elements a ∈ S we have that a ⊕ S a = a.
Semirings form an essential part of the modern theory of automata and languages. We refer the reader to the introductory references [15,49]. Example 2.3. Any commutative ring, in particular the field of reals (R, +, ·, 0, 1), forms a commutative semiring.
There are also examples of semirings whose underlying sets are not given by (subsets of ) the real line. We note that summation by parts holds in a semiring. Indeed, multiplying two sums 4 over semiring elements one can show that, like in the usual ring-setting, (6) implies that the product of two iterated sums of depths k 1 and k 2 can be expressed in terms of a linear combination of iterated sums of depths k, with max(k 1 , k 2 ) ≤ k ≤ k 1 + k 2 . The reduction of the lengths of the iterated sums is due to the diagonal terms (, e.g., the third summand on the right-hand side of (6)). The algebraic formulation of this leads to the quasi-shuffle identity (see below).
Regarding (6), we remark on a peculiarity in the semiring setting. The lack of inverses with respect to addition makes summation-by-parts for non-strict iterated sums less appealing since the space of such sums is not closed under multiplication. Indeed, replacing in (7) the strict inequalities of the indices by non-strict inequalities and multiplying two such expressions one arrives at the sum of expressions that do contain strict inequalities 4 In order to not clutter the notation, for the moment we do not specify bounds for the summation indices. To have a well-defined sum it suffices to assume that the sequences a1, a2, . . . and b1, b2, . . . are eventually equal to 0S. 5 Here, depth of an iterated sum refers to the number of indices in the summation. as well. For example However, if we consider (8) in an idempotent semiring, one observes an interesting phenomenon. The fact that a ⊕ S a = a for all elements a in such a semiring implies the somewhat surprising identity where we used that The example (8) then becomes Hence, in the idempotent case, products of non-strict iterated sums satisfy the shuffle relation. We return to this in Section 4.
Note that if the underlying semiring S is idempotent, then the semimodule M is idempotent as well.
Example 2.5. An incarnation of the free S-semimodule F on a set D is given by functions f : D → S with finite support, i.e., f (d) = 0 S for all but finitely many elements d ∈ D. The action of S as well as the addition are defined pointwise.
Definition 2.6. An associative semialgebra over a commutative semiring S consists of a semiring (A, is a semimodule over S and such that the semimodule structure is compatible with A in the following way Remark 2.7. Motivated by summation by parts (6) and the particular property of iterated non-strict sums (9), one can introduce the notion of a Rota-Baxter S-semialgebra. Let Note that if the semiring S, and therefore also the semialgebra A, is idempotent the map R := λ id A ⊕ A R satisfies the particular relation (11) as well. In fact, we have the more surprising (weight zero) identity 6 (compare also (10)) We now consider formal series over the (possibly infinite) alphabet A with coefficients in a commutative semiring S of the form The set of all such series is denoted by S A . For a series F ∈ S A , the support, supp(F ), consists of all words in w ∈ A * with coefficient c w different from 0 S . We denote 6 Indeed, we see that by expanding the right-hand side of (12) we obtaiñ with S A the subset of series with finite support. We may view a series (13) as a map F : Each map F : A * → S can be uniquely extended to a linear map F : S A → S, and we denote this pairing by ., We can equip S A with a linear and multiplicative structure by defining For instance, let F = s 1 a 1 a 2 + s 2 a 1 and G = t 1 a 3 + t 2 a 2 a 3 be elements in S A then This turns S A , as well as S A , into S-semialgebras. The constant series are given by defining for any element s ∈ S the series F s := se, which include in particular the constant series 1 and 0. 7 As is the case over rings, S A is the free associative S-semialgebra over the alphabet A. This manifests in the following universal property: Proposition 2.8. For any S-semialgebra U and map φ : A → U there exists a unique S-semialgebra morphism extendingφ : S A → U extending φ. In other words, every map φ : A → U admits a unique mutiplicative and S-linear extension to S A .
The proof of Proposition 2.8 is standard, and therefore we omit it. For an indirect proof, we refer the reader to Appendix A.
We shall now equip the S-semimodule S A with another product. This product is a natural extension of the well-known shuffle (or Hurwitz) product commonly defined in automata theory [49]. For this we assume that the alphabet A carries a commutative semigroup product denoted by the binary bracket operation [− −] : A × A → A. Observe that commutativity and associativity permit to express iterations [a i 1 [· · · [a i n−1 a in ] · · · ] =: [a i 1 · · · a in ]. The commutative quasi-shuffle product on S A is defined first on words and then extended bilinearly. For words ua i and va j , where a i , a j ∈ A, u, v ∈ A * , we define ua i e = ua i = e ua i and inductively For instance, a i a j = a i a j + a j a i + [a i a j ]. It is easy to observe that for a trivial bracket product on A, the quasi-shuffle product (14) reduces to the shuffle product on A * . The latter will be denoted with ¡ and satisfies the recursion [64] It is known that an explicit expression can be defined for the shuffle product in terms of so-called shuffle permutations (bijections). In the case of the quasi-shuffle product (14), an analogous non-recursive formula can be given in terms of certain surjections [24,25]. We refer the reader to Appendix B for details.
For the remainder of the paper, we specialize to a specific alphabet A. Let A = {1, 2, . . . , d} and let A be the -extended -alphabet containing all formal brackets in elements of A , i.e., all formal monomials in those letters, Here, for consistency of notation, we write of S d -valued time series of infinite length that are eventually equal to 0 d S , whose elements are sequences , for S the tropical semiring R min+ = (R ∪ {+∞}, min, +, +∞, 0).
, by defining the coefficient We also write ISS S (z) := ISS S 0,∞ (z). As an example, we compute Our first results concern the verification that ISS S is a proper iterated-sums signature. By this we mean that it carries the two main properties mentioned in the introduction, i.e., it satisfies Chen's identity and is compatible with the quasi-shuffle product (14). Lemma 2.10 (Chen's identity). For p < r < q, w ∈ S A and z ∈ S or, equivalently, using the non-commutative concatenation product on S A , Remark 2.11. This allows, for p < r < q, to calculate ISS S p,q (z) from ISS S p,r (z) and ISS S r,q (z). However, in contrast to the situation over a ring, we cannot calculate ISS S r,q (z) from ISS S p,q (z) and ISS S p,r (z). This is due to the fact that semiring addition, ⊕ S , is not invertible. We return to this point in Section 5.
Example 2.12. One example was already given in Example 1.3. Consider now again the min-plus semiring S = R min+ (here d = 1 corresponding to the single letter alphabet A = {1}). Then From summation by parts (6) extended to iterated S-sums we deduce the multiplicativity of ISS S (z) over the quasi-shuffle product (14) on S A .
Proof. We first note that for a word x ∈ A * and a letter a ∈ A, which follows directly from the definition of ISS S . We prove the Lemma by induction on the sum q = (w) + (v) of the lengths of the words. It is trivially true for q = 0, 1. Suppose that q ≥ 2. Let it be true up to arbitrary q − 1 and assume (w) + (v) = q. Without loss of generality, we assume that both w = w 1 · · · w and v = v 1 · · · v k are nonempty since otherwise there is nothing to prove. For i = s + 1, . . . , t, define Note that for a fixed j one has Then where the last equality follows from summation-by-parts, (6). Now, the first term in the last equality is equal to where we used (20) and the induction hypothesis (since (v) + (w 1 · · · w −1 ) = q − 1). Analogously, for the second term, we obtain The last term is equal to where we used (20) and the induction hypothesis.
Combining those terms, we get, via (14), that

Quasisymmetric expressions over a semiring
The aim of this section is to study the coefficients, i.e. the iterated sums used to define the ISS S in (17), as formal power series expressions. 8 Analogous to the classical case, this results in the definition of the notion of quasisymmetric expressions defined over a semiring. These are formal series with coefficients in S which have a particular symmetry property defined below. When considered over a commutative ring, their siblings form the well-studied Hopf algebra of quasisymmetric functions with the monomial quasisymmetric functions as one of many bases [33,51,55]. As we shall see, working over a semiring leads to rather minor changes compared to the classical theory of quasisymmetric functions. This stems from the fact that most properties only rely on the index set (i.e., the totally ordered set of integers). However, it turns out that the monomial basis is the only reasonable one, see Remark 3.8.
In the following, we denote by the commutative S-semialgebra of formal power series expressions in commuting ordered indeterminates X := {X 1 , X 2 , X 3 , . . .} with coefficients in S. We write monomials in these variables in the usual form X α 1 s 1 · · · X αn sn , n ≥ 0, α 1 , . . . , α n ≥ 1, but note that this is -of course -just a formal expression, so that we might as well have written X S α 1 s 1 S · · · s X S αn sn .Which, although more consistent with previous notation, we abstain from to reduce notational clutter. The degree of such a monomial is defined by the sum of the exponents, |X α 1 s 1 · · · · · X αn sn | := α 1 + · · · + α n . Similar to the power series semialgebra in noncommuting variables of the previous section, elements P ∈ where c m ∈ S and the sum is over formal commutative monomials in the indeterminates X 1 , X 2 , . . . . The linear structure follows as for the case of noncommutative variables and the multiplicative structure is induced from the product of formal monomials (Cauchy product). We shall write P (m) := c m . By small abuse of notation, we let S[[X 1 , X 2 , X 3 , . . .]] contain only power series of bounded degree, i.e., for P ∈ S[[X 1 , X 2 , X 3 , . . .]] there is N ≥ 0 such that for all monomials m with |m| ≥ N , P (m) = 0 S . The subset with power series of finite support is denoted S[X 1 , X 2 , . . . ] and forms the space of formal polynomial expressions. Definition 3.1. An element P ∈ S[[X 1 , X 2 , X 3 , . . .]] is a quasisymmetric expression if for all n ≥ 1, α 1 , . . . , α n ≥ 1, 0 < s 1 < · · · < s n and 0 < t 1 < · · · < t n the coefficients of the monomials X α 1 s 1 · · · · · X αn sn and X α 1 t 1 · · · · · X αn tn ,

Remark 3.3.
1. We can naturally evaluate a formal monomial at values in a commutative semiring, e.g. for semiring elements z 1 , z 2 ∈ S, The iterated sums in the definition of the ISS S , (17), then amount, in the onedimensional case, to evaluation of specific monomial quasisymmetric expression, 2. See [20, Remark 3.5] for a straightforward extension to "multidimensional" quasisymmetric expressions.
Example 3.4. The simplest, non-trivial quasisymmetric expression is or, written as formal sum, Another example is given by Definition 3.5. We say that a family v i , i ∈ I, of vectors in a S-semimodule M is a basis if for every w ∈ M there exist unique coefficients λ i ∈ S, i ∈ I, all but finitely many equal to zero, with Remark 3.6. There exist different concepts of linear independence in semimodules. The reader is referred to [2] for an overview. 9 We then have, as expected, that the monomial quasisymmetric expressions are a basis for QSym S . Proposition 3.7. The family M α of monomial quasisymmetric expressions a basis for QSym S . Proof. To show that every element of QSym S can be written as a linear combination of monomial quasisymmetric expressions, let Q ∈ QSym S . If Q is the zero power series, we are done. Otherwise, take a monomial m = X α 1 t 1 · · · · · X α k t k in Q with non-zero coefficient c ∈ S (i.e., considering Q as a function on monomials, Q(m) = c). Then Since Q has finite degree we can repeat this finitely many times to see that Q is a linear combination of monomial quasisymmetric expressions.
The uniqueness of coefficients follows from the fact that for α = β the supports of M α and M β are disjoint. Regarding the latter, in the semiring setting, the corresponding fundamental quasisymmetric expressions, F β ∈ QSym S , can be defined as linear combinations of monomial quasisymmetric expressions where ≤ is the following "refinement" partial order: (β 1 , . . . , β m ) ≤ (α 1 , . . . , α n ) if and only if there is a sequence of integers k 1 , . . . , k m with k j ≥ 1 and k 1 + · · · + k m = n, and such that β i = α j + α j+1 + · · · + α j+k i −1 for all i = 1, . . . , m. For example, (4, 4) ≤ (3, 1, 2, 2). It turns out that those expressions are closed under multiplication, i.e., they form a sub-semialgebra of QSym S . This subalgebra is strictly smaller (and might be interesting to investigate further). Indeed, the classical inversion formula (between the M α and F β ) implies, for instance, that M (2) can not be expressed in terms of fundamental quasisymmetric expressions in the semiring setting (having no minus operation available) 10 .
In fact, more holds, as the following statement shows.
Lemma 3.9. Let S be a semiring without additive inverses, that is a ⊕ b = 0 implies a = b = 0, and zero-divisor free. Then: the monomial basis is the only basis of QSym S . Proof. Let G i , i ∈ I, be another basis and let M α be some monomial basis element. Then we can write with c j ∈ S min+ \ {0 min+ }. Let m be any monomial not appearing in M α . Then By assumption, this implies c j min+ G i j (m) = 0 min+ , j = 1, . . . , n. Since S is zero-divisor free and the c j are not equal to 0, m does not appear in any of the G i j . Hence n = 1 and c 1 G i 1 = M α . Hence the basis (G i ) i contains, up to multiplicative factors, the monomial basis. Since this subset already forms a basis, the basis (G i ) i is equal, up to multiplicative factors, to the monomial basis.

Invariance to inserting zeros
We will now show that QSym S can be characterized by invariance to "inserting zeros". For n ≥ 1 define the commutative S-semialgebra morphism induced multiplicatively from the following map on X 1 , X 2 , . . .
Proof. ⇒: Immediate, since the morphism zero preserves the exponents and the order of the variables involved.
From Theorem 3.11 we get the following consequence. be the map that inserts 0 S at position n into a time series, that is, With this notation, Corollary 3.13 means that if z = τ n 1 • · · · • τ n k (z) for some set of integers 0 ≤ n 1 ≤ · · · ≤ n k then In fact, under some restrictions, a converse statement is also true. Recall that a semiring S • has the cancellation property if a c = b c and c = 0 imply a = b, We remark that if S is a ring then both notions coincide and S is then also called an integral domain. For semirings, the cancellation property is the strictly stronger notion of the two as the following examples show.
Example 3.14. The bottleneck semiring (R ∪ {±∞}, max, min, −∞, +∞) does not satisfy the cancellation property, as for example 3 7 = 7 = 4 7, but it is zero-divisor free: As another example consider the semiring of ideals of a commutative ring R Its multiplicative semigroup has been extensively studied, see for example [34].
If R is an integral domain, then S is clearly zero-divisor free. It does, in general, not have the cancellation property. Indeed in R = Z[2i] we have It turns out that S has the cancellation property if and only if every ideal in R is locally a regular principal ideal, [5].
In the following, given z ∈ S d,N ≥1 0S we denote byž its compression, obtained by deleting all the zero entries in z before it is eventually constant.  Proof. Suppose S has the cancellation property and let z, z ∈ S d,N ≥1 0S be such that ISS S (z) 0,∞ = ISS S (z ) 0,∞ . Without loss of generality, we assume that d = 1. In the general case, the conclusion follows after applying the following argument along each dimension.
Let N ∈ N ≥1 be the largest integer such that ISS S (z) 0,∞ , [1] N = 0. Then there exists an increasing sequence 1 ≤ i 1 < · · · < i N of integers such that z i j = 0 S , and z n = 0 S for all n > i N . In particular, we must have We call the integer N the effective length of z, and we note that it must be the stay the same for z , although the exact sequence of timestamps might differ. Now, by assumption, we have that Moreover, by picking out the coefficient of the word [11][1] N −1 we see that Since S is has the cancellation property and z i 1 = 0 S , this implies that z i 1 = z j 1 . Inserting this equality into eq. (23) and using again the fact that S has the cancellation property, we conclude that Testing now against the word [1] [11][1] N −2 implies, by a similar argument, that z i 2 = z j 2 . The argument then continues by replacing this new identity into eq. (23) to obtain an equality similar to eq. (24) but with fewer terms, and then picking out words of the form This procedure clearly terminates after N steps, and the output is that z i k = z j k for all k = 1, . . . , N , i.e.,ž =ž . Assume now that S is not zero-divisor free. Then, there exist a, b ∈ S \ {0 S } such that a b = 0. If a = 0 the time series z = (a, b, 0 S , . . . ) and z = (b, a, 0 S , . . . ) are such thatž =ž but with ISS S (z) 0,∞ = ISS S (z ) 0,∞ . Indeed, it is easy to check that for the words [1], [11] and [1][1] both coefficients coincide. The only other potentially non-zero coefficients in both signatures are those associated with words of the form In any case, we have that the coefficients are either a k b or b k a which all vanish.
Assume now a = b, i.e. a 2 = 0 S . If a + a = 0 and a + a = a we can repeat the argument with z = (a, a + a, 0 S , . . . ) and z = (a + a, a, 0 S , . . . ). If a + a = 0, then the signature of z = (a, a + a, 0 S , . . . ) is trivial, althoughž is not trivial.

Time warping invariants in an idempotent semiring
Example 2.9 together with Corollary 3.13 shows one way to obtain time warping invariants of a real-valued time series. This does not cover the invariant (2) though.
Since R ⊂ R ∪ {+∞}, and since the tropical semiring is idempotent we can also calculate ISS S (z) on a real-valued time series that is eventually constant. Recall that ISS S (z) = ISS S 0,∞ (z). Since this includes the invariant (2). But, as is quickly seen, most coefficients are not invariant to time warping. To wit, gives, for, the values −2 and −6 respectively. It turns out that if we change the strict inequality over points in time in (25) into a weak or non-strict inequality, namely then we do get a time warping invariant. In this section we would like to spell out how this works in general.
where the possibly infinite sum is well-defined, since S is idempotent and z is eventually constant. As before, we write ISS S,idem (z) = ISS S,idem 0,+∞ (z). The following lemma is immediate.
Then, for all n ≥ 1:  Example 4.4. Using, for example, the computation in (10), we see that where we used idempotency of ⊕ S .
Proof. The proof follows analogously to the one of Lemma 2.13. Owing to idempotency, for f i , g i ∈ S, i = s + 1, . . . , t, (6) becomes This leads to the last term in (21) not being present and hence to a shuffle product instead of a quasi-shuffle product.
We note that, in the tropical semiring, ISS Rmin+,idem is very degenerate, in the sense that, in the one-dimensional case, To get a more interesting object we can allow powers in Z \ {0} (instead of just N ≥1 ), e.g.  Proof. The shuffle property follows as in Lemma 4.3. The time-warping invariance is immediate, as in Lemma 4.2. Chen's identity follows from the partition of the time interval Remark 4.6. The iterated-sums signature over a field of characteristic 0 is, via the Hoffman exponential, in bijection to a certain iterated-integrals signature, [20,Theorem 5.3]. The iterated-sums signature satisfies a quasi-shuffle identity, whereas the iteratedintegrals signature is a shuffle character. In fact, there is a whole family of signature-like maps, indexed by θ ∈ (−1, 1) obtained by composing the iterated sums signature with some linear transformation A θ→1 which generalize Hoffman's exponential (it being the case θ = 0), see [19,Remark 2.3].
When working over an idempotent semiring, however, only the cases θ = −1 and θ = 0 are well defined, and both maps coincide.
Over a field K, owing to the group-likness of ISS K implying the identity one obtains, with computational preparation cost O(T · k) and storage cost O(T · k) (i.e. the cost of computing respectively storing (27), for S = K), the values for arbitrary s, t = 1, . . . , T , i = 1, . . . , k, at query cost O(k). 11 Such a cheap access to iterated sums over arbitrary sub-intervals is key to some applications in machine learning. Over a general semiring, ISS S 0,s (z) −1 is not defined. But, a slightly less efficient calculation for all subintervals simultaneously is still possible: There is an algorithm that, for given a word w of length k and time horizon T , obtains for all s, t = 1, . . . , T , i = 1, . . . , k at "query" cost O(log(T ) k ).
The computational "preparation" cost (explained in the proof ) for this algorithm is O(k log(T )T ) and the storage cost is O(kT ).

(Preparation) Calculate
involves O(k) many queries to ISS K 0,s (z) and ISS K 0,t (z). and such that q is minimal. This can, for example, be done by the exploration of a corresponding binary tree, with cost O(N ) = O(log(T )). Note that q ≤ 2N = 2 log(T ). Then, for v ∈ W , The q-th iterated "deconcatenation" v 1 ···vq=v · · · contains O( k+q−1 q−1 ) terms. The latter expression is monotonically increasing in q and hence bounded by yielding a "query" cost of

Conclusion
In (17) we introduced the iterated-sums signature, ISS S (z), over a commutative semiring S. It stores all iterated sums (taken in the semiring) of a multidimensional time series z = (z 1 , z 2 , . . .) with entries z i ∈ S d . As in the case over commutative rings, this object satisfies Chen's identity (Lemma 2.10) which here as well allows for efficient computation. It also satisfies the quasi-shuffle identity (Lemma 2.13) that is, it behaves like a grouplike element. Unlike for the usual ISS there is no proper Hopf algebra structure available here and it is in general not possible to take the logarithm of the signature.
In the one-dimensional case over commutative rings, the entries of the iterated-sums signature correspond to the evaluation of certain formal power series, namely quasisymmetric functions. Here, this is also true (Section 3), though it is more appropriate to speak of quasisymmetric expressions, since polynomial expressions over a semiring are not in one-to-one correspondence with polynomial functions.
In order to explicitly cover the expression (2) from the Introduction, we looked at the special case of idempotent semirings in Section 4.
Calculation of ISS S 0,t (z) with a fixed starting time 0, can be done at the same (linear) cost as in the case over commutative rings. Owing to the lack of additive inverses, the calculation of ISS S (z) over arbitrary subintervals is more intricate. In Section 5 we provided an algorithm, that incurrs an additional logarithmic cost factor.

Open questions
• The iterated-sums signature over the reals has a close connection to discrete control theory as explored in reference [39]. In the setting of the max-plus semiring: Is there a relation to discrete control theory in that semiring [15,17,47]? 12 • The ISS over a commutative ring contains, owing to the quasi-shuffle identity, many redundant entries. Working with the log-signature removes these redundancies. Over a general commutative semiring, we cannot take the logarithm of the signature, so an open question is How to extract the "minimal" information contained in the signature?
• As seen in Remark 2.11, owing to the lack of additive inverses, Chen's identity only works in "one direction".
Is there a way (with maybe a larger object) of obtaining a general Chen's identity?
• Multidimensional time series are explicitly covered by the present work. Just as over the reals, this amounts to projecting the time series to coordinates before calculating the iterated-sums.
In the semiring setting, a more interesting approach seems possible. Indeed, one can turn a multidimensional real-valued time series into a one-dimensional semiring-valued time series. One example is via the map • Chen's identity, Lemma 2.10, applied to time points 0, t, t + 1 reads as where we use the notation of (17). This allows for an iterative calculation of this value, with total cost O(n · t). This can be seen as a special case of dynamic programming.
Is there a deeper connection to the dynamic programming literature?
• The iterated-integrals signature has been investigated from the perspective of algebraic geometry in [4].
Is there interesting tropical algebraic geometry, that can be done on the objects introduced in this work?
• In Appendix A we recall how category theory provides an organized view on semirings and their modules. In a push for further generality, Is it possible to categorify the iterated-sums signature?
The category of polynomial functors [69] and the abstract view on time series in [68] might prove useful in this regard.
• What connection can be drawn to the literature on temporal logic [62] and Allen's temporal logic [3]?

A. Categorial view on semirings
The aim of this section is to give a brief overview of the categorical setting for semirings, semimodules, etc. Good references on category theory are [54,65] (see also [12] (in German)). For the particularities of monoidal categories, we refer to [11,Section 4.1] and [56].
Recall that a monoidal category is a category C with a bifunctor ⊗ : C × C → C, and an object 1 ∈ C called the unit such that there exist natural isomorphisms and satisfy some consistency relations. Essentially, this means that there is a notion of "tensor product" internal to the category. A monoidal category is symmetric if furthermore it is endowed with a "braiding" or "twisting" natural isomorphism τ X,Y : X ⊗ Y → Y ⊗ X such that τ Y,X • τ X,Y = id X⊗Y . Examples of symmetric monoidal categories include Vect k for any field k and Mod R for any commutative ring R. In both cases, ⊗ corresponds to the internal tensor product.
In any monoidal category, the notion of monoid makes sense. A monoid on a monoidal category C is an object M in C together with two arrows µ : M ⊗ M → M and u : 1 → M satisfying an associativity and unitality condition [54,Section VII.3]. Additionally, in a symmetric monoidal category, one can also impose a commutativity constraint and obtain commutative monoids. As an example, monoids in Vect k correspond to algebras over vector spaces. Dually, a comonoid in C is a monoid in the dual (or opposite) category C op . 13 As monoids on the category of vector spaces correspond to algebras, comonoids in Vect k correspond to coalgebras. The category of monoids in C is denoted by Mon(C). 14 Likewise, the category of commutative monoids in C is denoted by CMon(C).
Proposition A.1 (Theorem VII.3.2 in [54]). Let C be a monoidal category with countable coproducts and assume that for each A ∈ C the functors − ⊗ A, A ⊗ − preserve countable coproducts. Then the forgetful functor U : Mon(C) → C has a left adjoint F : C → Mon(C). On an object X in C, the underlying object of F (X) is X ⊗n in C, with the monoidal structure given by the tensor product.
Example A.2. In the category Set, coproducts correspond to disjoint unions, i.e., for any countable sequence (A n ) of sets, A n . 13 One may also consider bimonoids and Hopf monoids. 14 The arrows are given by arrows in C that respect the monoid structure, [56, Definition 1.2.9].
The category Set also possesses a monoidal structure given by the cartesian product, that is, A ⊗ B := A × B. Hence, can be identified with the free monoid over the set X, since monoids over Set are classical monoids.
Example A.3. In the category Vect k , coproducts correspond to direct sums, i.e., for any countable sequence (V n ) of vector spaces over k, In particular is the tensor algebra over X since monoids over Vect k correspond to unital k-algebras.
Suppose that C is a symmetric monoidal category and let R be a commutative monoid object in C. A left R-module is an object M in C with an arrow µ M : R ⊗ M → M defining an action of R on M . One can also define right R-modules in an obvious way, but since R is commutative both notions coincide and we just call them R-modules. The category of R-modules is denoted by Mod R . 15 A nice example of symmetric monoidal category is Ab, the category of abelian groups. The tensor product on Ab is obtained form the cartesian (or direct) product of abelian groups by modding out the relations (a 1 , b) + (a 2 , b) − (a 1 + a 2 , b) and (a, b 1 ) + (a, b 2 ) − (a, b 1 + b 2 ). We denote it by ⊗ as usual. The unit for this tensor product is the group of integers with addition. Monoid objects over this category correspond to rings, that is, Mon(Ab) = Ring. Given an object R in CMon(Ab), that is, a commutative ring, the notion of R-module corresponds to the usual notion of a module over a ring.
For any given commutative monoid object R in a symmetric monoidal category (C, ⊗, 1), the category of modules Mod R is also a symmetric monoidal category when endowed with the tensor product M ⊗ R N defined as the coequalizer of the two maps M ⊗ R ⊗ N ⇒ M ⊗ N given by the action of R on M and N . The unit for this tensor product is R seen as a module over itself. Hence, the complete data is (Mod R , ⊗ R , R). Now, we consider the category of monoids Mon(Mod R ). We call objects in this category algebras over R. Likewise, comonoids in Mod R are called coalgebras.
Theorem A.4 (Proposition 1.2.14 in [56]). Let C be a symmetric monoidal category. If C is either complete or cocomplete, then so are CMon(C) and Mod R for any commutative monoid R in C.

A.1. The category of semirings
We apply the above construction to the category CMon := CMon(Set) of commutative monoids. This is a symmetric monoidal category, with product given by the tensor product of commutative monoids [6, Appendix B].
1. The category CMon is complete and cocomplete.
2. For R an object in CMon(CMon), the category Mod R is complete and cocomplete.
Proof. 1. A commutative monoid is nothing else than a commutative monoid object in the symmetric monoidal category (Set, ×, { * }) which is known to be complete and cocomplete [65, Theorem 3.2.6, Proposition 3.5.1]. Therefore, CMon is also complete and cocomplete by Theorem A.4.
2. This follows from point 1. and Theorem A.4.
1. In CMon, for each A ∈ CMon the functors − ⊗ A and A ⊗ − preserve countable coproducts.
2. For R an object in CMon(CMon), the tensor product in Mod R preserves countable coproducts.
Proof. 1. By [6,Appendix B], CMon is closed. In particular, this means that − ⊗ A is left adjoint to Hom(A, −). Therefore, − ⊗ A preserves colimits [65,Theorem 4.5.3], and in particular coproducts. By symmetry of the tensor product, the same is true for A ⊗ −. 2. By proposition A.5, CMon is complete. Therefore, by [11, Theorem 4.1.10], for any commutative monoid R in CMon, Mod R is a cocomplete symmetric monoidal category with unit R and tensor product ⊗ R .
The category of commutative monoids CMon(CMon) corresponds to commutative semirings, i.e., commutative rings without negative elements. 16 For a fixed commutative semiring R, objects in the category Mod R are known as semimodules. The notions of semialgebra, semi-coalgebra and Hopf semialgebra follow (as monoid, comonoid, and Hopf monoid in Mod R ).
Theorem A.7. Let R be a commutative semiring.
1. There exists a left adjoint F : Set → Mod R to the forgetful functor. F (D) is the free R-module over D.
2. There exists a left adjoint F : Mod R → Mon(Mod R ) to the forgetful functor. F (X) is the free semialgebra over X. 16 Also called rigs, rings without negative elements.
Proof. Using Proposition A.5 and Proposition A.6 we can apply Proposition A.1.
F (D) corresponds to the free S-semimodule over a set D indicated in Section 2. It is free in the following sense. For every map φ from D into an S-semimodule M there exists a unique S-semimodule morphism Φ : F → M such that the following diagram commutes.

. Symmetric powers
Let C be a symmetric monoidal category and R a commutative monoid object. Recall that the category Mod R is itself a symmetric monoidal category with R as the unit. Given an object M in Mod R , the symmetric group S n acts naturally on M ⊗ R n . In fact, the action is induced by the braiding map corresponding to ⊗ R . Suppose that C has finite colimits. The symmetric power S n M is then defined to be the coequalizer of the action of S n on M ⊗ R n . By definition, this means that S n M has the following universal property: every symmetric morphism 17 f : M ⊗ R n → N extends uniquely to a morphismf : S n M → N . In particular, there are canonical epimorphisms S n M ⊗ S m M S n+m M . If C is furthermore cocomplete, the previous construction endows the coproduct S(M ) := ∞ n=0 S n M with a commutative algebra structure. This object is the free commutative monoid object over M . The required universality property follows by gluing together the universality of each symmetric power.
In the particular case where the underlying category is CMon, for a semimodule M , S(M ) is the free commutative semialgebra over M .