Tropical time series, iterated-sums signatures and quasisymmetric functions
Pith reviewed 2026-05-24 14:22 UTC · model grok-4.3
The pith
The iterated-sums signature over the tropical semiring extracts chronological features from real-valued time series unavailable from existing signature objects and computes them in linear time.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The iterated-sums signature is introduced over arbitrary commutative semirings; when the semiring is tropical, the resulting map on real-valued time series yields chronological features not easily obtained from prior signature-type objects, the map can be evaluated in linear time, and quasisymmetric expressions over semirings supply the correct algebraic framework for the semiring-valued case.
What carries the argument
The iterated-sums signature over the tropical semiring, which accumulates ordered sums under tropical addition and multiplication to produce sequence features.
If this is right
- Real-valued time series acquire new extractable features tied to chronological order.
- These features remain computable in time linear in the length of the input series.
- The same signature construction extends directly to time series taking values in any commutative semiring.
- Quasisymmetric expressions become the algebraic language for describing such signatures.
Where Pith is reading between the lines
- The linear-time property may allow the signature to serve as a drop-in feature map inside streaming or online algorithms.
- Other semirings could be substituted to target different notions of accumulation, such as probabilistic or fuzzy orderings.
- The connection to quasisymmetric functions suggests possible links to combinatorial enumeration problems that already use those functions.
Load-bearing premise
Quasisymmetric expressions over semirings form the appropriate framework for iterated-sums signatures on semiring-valued time series.
What would settle it
A concrete time series of length n for which the tropical iterated-sums signature either misses a clear chronological ordering present in the data or requires superlinear operations to compute.
Figures
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces the iterated-sums signature over arbitrary commutative semirings, taking the tropical semiring as its central motivating case. It asserts that the resulting features capture chronological aspects of real-valued time series unavailable from prior signature constructions, that the signature is computable in linear time, and that quasisymmetric expressions over semirings supply the correct algebraic framework for the semiring-valued setting.
Significance. If the definitional framework and the linear-time claim are made fully explicit with supporting algorithms and comparisons, the work would supply a new semiring-compatible extension of signature methods with potential utility in algebraic combinatorics and time-series feature extraction. The explicit link to quasisymmetric functions could unify existing approaches, provided concrete examples demonstrate features not recoverable from classical signatures.
major comments (2)
- [Abstract and §1] Abstract and §1: the linear-time computability claim is central to the practical contribution yet no explicit algorithm, recurrence, or complexity argument is supplied in the visible sections; without this the assertion remains unverified.
- [§3 or §4] §3 or §4 (whichever contains the comparison): the claim that tropical iterated-sums features are 'not easily available using existing signature-type objects' requires at least one concrete, side-by-side numerical example on a short real time series showing a chronological invariant absent from the classical signature; the current framing is purely definitional.
minor comments (2)
- Notation for the semiring operations and the iterated-sums product should be introduced once and used uniformly; several passages mix tropical and classical notation without explicit transition.
- [Abstract] The final sentence of the abstract identifies quasisymmetric expressions as 'the appropriate framework'; this identification should be justified by a short theorem or proposition rather than left as a concluding remark.
Simulated Author's Rebuttal
We thank the referee for the detailed review and constructive suggestions. We address each major comment below and will incorporate revisions accordingly.
read point-by-point responses
-
Referee: [Abstract and §1] Abstract and §1: the linear-time computability claim is central to the practical contribution yet no explicit algorithm, recurrence, or complexity argument is supplied in the visible sections; without this the assertion remains unverified.
Authors: We agree that providing an explicit algorithm and complexity argument will strengthen the manuscript. Although the linear-time claim is stated, the details of the recurrence are not fully expanded in the current version. In the revision, we will add an explicit description of the algorithm, including the recurrence relation and a proof of O(n) complexity for a time series of length n. revision: yes
-
Referee: [§3 or §4] §3 or §4 (whichever contains the comparison): the claim that tropical iterated-sums features are 'not easily available using existing signature-type objects' requires at least one concrete, side-by-side numerical example on a short real time series showing a chronological invariant absent from the classical signature; the current framing is purely definitional.
Authors: The manuscript aims to demonstrate the extraction of chronological aspects, but we recognize that a concrete numerical example would make the distinction clearer. We will include a short real-valued time series example with side-by-side computation of the tropical iterated-sums signature and the classical signature to show a specific chronological feature that is captured only by the former. revision: yes
Circularity Check
No significant circularity
full rationale
The paper introduces iterated-sums signatures as a new algebraic object over commutative semirings, with the tropical case as a motivating example. All central claims (feature extraction properties, linear-time computation, and identification of quasisymmetric expressions as the framework) are presented as definitional contributions rather than reductions of fitted parameters or prior results. No equations, self-citations, or ansatzes appear in the abstract that would reduce the claimed outputs to the inputs by construction. The work is self-contained as an algebraic definition and does not rely on load-bearing self-citations or uniqueness theorems imported from the authors' prior work.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Commutative semirings form a suitable algebraic base for defining iterated-sums signatures of time series.
- domain assumption Quasisymmetric expressions over semirings supply the correct bookkeeping for these signatures.
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
J. F. Allen,Maintaining knowledge about temporal intervals, Communications of the ACM 26 (1983), no. 11, 832–843
work page 1983
-
[4]
C. Amendola, P. Friz, and B. Sturmfels,Varieties of signature tensors, Forum of Mathematics, Sigma, vol. 7, Cambridge University Press, 2019. 38
work page 2019
-
[5]
D. Anderson and M. Roitman,A characterization of cancellation ideals, Proceedings of the American Mathematical Society125 (1997), no. 10, 2853–2854
work page 1997
-
[6]
R. Antoine, F. Perera, and H. Thiel,Tensor products and regularity properties of Cuntz semigroups, Mem. Amer. Math. Soc.251 (2018), no. 1199, viii+191
work page 2018
-
[7]
F. L. Baccelli, G. J. Olsder, J.-P. Quadrat, and G. Cohen,Synchronization and linearity. an algebra for discrete event systems, Chichester: Wiley, 1992
work page 1992
-
[8]
S. Bai, J. Z. Kolter, and V. Koltun,An empirical evaluation of generic convolutional and recurrent networks for sequence modeling, arXiv preprint arXiv:1803.01271 (2018)
work page internal anchor Pith review Pith/arXiv arXiv 2018
-
[9]
E. Baldwin and P. Klemperer,Tropical geometry to analyse demand, Unpublished paper.[281] (2013)
work page 2013
-
[10]
S. L. Bloom and Z. Ésik, Iteration theories, Iteration Theories, Springer, 1993, pp. 159–213
work page 1993
-
[11]
Tensor categorical foundations of algebraic geometry
M. Brandenburg, Tensor categorical foundations of algebraic geometry , 2014, arXiv:1410.1716
work page internal anchor Pith review Pith/arXiv arXiv 2014
-
[12]
M. Brandenburg,Einführung in die Kategorientheorie: Mit ausführlichen Erklärun- gen und zahlreichen Beispielen, Springer-Verlag, 2016
work page 2016
-
[13]
P.Butkovič, Max-linear systems: theory and algorithms, SpringerScience&Business Media, 2010
work page 2010
-
[14]
G. Carlsson and S. Kališnik Verovšek,Symmetric andr-symmetric tropical polyno- mials and rational functions, J. Pure Appl. Algebra220 (2016), no. 11, 3610–3627
work page 2016
-
[15]
C. G. Cassandras and S. Lafortune,Introduction to discrete event systems, second ed., Springer, New York, 2008
work page 2008
-
[16]
Chen, Integration of paths, geometric invariants and a generalized Baker- Hausdorff formula, Ann
K.-T. Chen, Integration of paths, geometric invariants and a generalized Baker- Hausdorff formula, Ann. of Math. (2)65 (1957), 163–178
work page 1957
- [17]
- [18]
- [19]
-
[20]
, Time-warping invariants of multidimensional time series, Acta Appl. Math. 170 (2020), 265–290. 39
work page 2020
-
[21]
M. Droste and W. Kuich,Chapter 1: Semirings and formal power series, Handbook ofweightedautomata, Monogr.Theoret.Comput.Sci.EATCSSer., Springer, Berlin, 2009, pp. 3–28
work page 2009
-
[22]
L. A. Duffaut Espinosa, W. S. Gray, and K. Ebrahimi-Fard,A combinatorial Hopf algebra for nonlinear output feedback control systems, J. Algebra453 (2016), 609– 643
work page 2016
-
[23]
,Discrete-time approximations of Fliess operators, Numer.Math.137(2017), 35–62
work page 2017
-
[24]
K. Ebrahimi-Fard, F. Fauvet, and D. Manchon,A comodule-bialgebra structure for word-series substitution and mould composition, J. Algebra489 (2017), 552–581
work page 2017
-
[25]
K. Ebrahimi-Fard, S. J. Malham, F. Patras, and A. Wiese,Flows and stochastic Taylor series in Itô calculus, Journal of Physics A: Mathematical and Theoretical 48 (2015), no. 49, 495202
work page 2015
-
[26]
J. Eisner, Parameter estimation for probabilistic finite-state transducers, Proceed- ings of the 40th Annual Meeting of the Association for Computational Linguistics (Philadelphia, Pennsylvania, USA), Association for Computational Linguistics, July 2002, pp. 1–8
work page 2002
-
[27]
H. I. Fawaz, G. Forestier, J. Weber, L. Idoumghar, and P.-A. Muller,Deep learning for time series classification: a review, Data Min. Knowl. Discov.33 (2019), no. 4, 917–963
work page 2019
-
[28]
J. G. Fletcher,A more general algorithm for computing closed semiring costs between vertices of a directed graph, Communications of the ACM23 (1980), no. 6, 350–351
work page 1980
-
[29]
M. Fliess,Fonctionnelles causales non linéaires et indéterminées non commutatives, Bulletin de la société mathématique de France109 (1981), 3–40
work page 1981
- [30]
-
[31]
P. K. Friz and N. B. Victoir,Multidimensional stochastic processes as rough paths, Cambridge Studies in Advanced Mathematics, no. 120, Cambridge University Press, 2010
work page 2010
-
[32]
J. G. Gaines, The algebra of iterated stochastic integrals, Stochastics Stochastics Rep. 49 (1994), no. 3-4, 169–179
work page 1994
-
[33]
I. M. Gessel,MultipartiteP-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983), Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289–317
work page 1983
-
[34]
Gilmer,Multiplicative ideal theory, Queen’s Papers in Pure and Appl
R. Gilmer,Multiplicative ideal theory, Queen’s Papers in Pure and Appl. Math.90 (1992). 40
work page 1992
-
[35]
K. Gimpel and N. A. Smith,Cube summing, approximate inference with non-local features, and dynamic programming without semirings, Proceedings of the 12th Con- ference of the European Chapter of the Association for Computational Linguistics (USA), EACL ’09, Association for Computational Linguistics, 2009, pp. 318–326
work page 2009
-
[36]
J. S. Golan,Semirings and affine equations over them: theory and applications, vol. 556, Springer Science & Business Media, 2013
work page 2013
-
[37]
M. Gondran and M. Minoux,Graphs, dioids and semirings: new models and algo- rithms, vol. 41, Springer Science & Business Media, 2008
work page 2008
-
[38]
Goodman,Semiring parsing, Comput
J. Goodman,Semiring parsing, Comput. Linguist.25 (1999), no. 4, 573–605
work page 1999
-
[39]
W. S. Gray, G. Venkatesh, and L. A. D. Espinosa,Nonlinear system identification for multivariable control via discrete-time Chen–Fliess series, Automatica119 (2020), 109085
work page 2020
-
[40]
B. Hambly and T. J. Lyons, Uniqueness for the signature of a path of bounded variation and the reduced path group, Ann. Math.171 (2010), no. 1, 109–167
work page 2010
-
[41]
B. Heidergott, G. J. Olsder, and J. Van Der Woude,Max plus at work: modeling and analysis of synchronized systems: a course on max-plus algebra and its applications, vol. 48, Princeton University Press, 2014
work page 2014
-
[42]
S. Kališnik and D. Lešnik,Symmetric polynomials in upper-bound semirings, Journal of Symbolic Computation (2020)
work page 2020
-
[43]
S. Kališnik and D. Lešnik,Symmetric polynomials in tropical algebra semirings, J. Symbolic Comput.93 (2019), 100–119
work page 2019
-
[44]
P. Kidger, P. Bonnier, I. Perez Arribas, C. Salvi, and T. Lyons,Deep signature transforms, Advances in Neural Information Processing Systems 32 (H. Wallach, H. Larochelle, A. Beygelzimer, F. d’ Alché-Buc, E. Fox, and R. Garnett, eds.), Curran Associates, Inc., 2019, pp. 3105–3115
work page 2019
-
[45]
F. J. Király and H. Oberhauser, Kernels for sequentially ordered data, J. Mach. Learn. Res.20 (2019), Paper No. 31, 45
work page 2019
-
[46]
J. Kohlas and N. Wilson,Semiring induced valuation algebras: exact and approxi- mate local computation algorithms, Artificial Intelligence172 (2008), no. 11, 1360– 1399
work page 2008
-
[47]
J. Komenda, S. Lahaye, J.-L. Boimond, and T. van den Boom,Max-plus algebra in the history of discrete event systemsr, Annual Reviews in Control 45 (2018), 240–249
work page 2018
-
[48]
A. Krizhevsky, I. Sutskever, and G. E. Hinton,Imagenet classification with deep convolutional neural networks, Advances in neural information processing systems, 2012, pp. 1097–1105. 41
work page 2012
-
[49]
W. Kuich and A. Salomaa,Semirings, automata, languages, EATCS Monographs on Theoretical Computer Science, vol. 5, Springer-Verlag, Berlin, 1986
work page 1986
- [50]
- [51]
-
[52]
T. J. Lyons,Differential equations driven by rough signals., Rev. Mat. Iberoam.14 (1998), no. 2, 215–310
work page 1998
-
[53]
D. Maclagan and B. Strumfels,Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015
work page 2015
-
[54]
S. MacLane,Categories for the working mathematician, Springer-Verlag, New York- Berlin, 1971, Graduate Texts in Mathematics, Vol. 5
work page 1971
-
[55]
C. Malvenuto and C. Reutenauer,Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra177 (1995), no. 3, 967–982
work page 1995
-
[56]
Marty,Des immersions ouvertes et des morphismes lisses en géométrie relative, Ph.D
F. Marty,Des immersions ouvertes et des morphismes lisses en géométrie relative, Ph.D. thesis, Université Toulouse III - Laboratoire Emile Picard, 2009
work page 2009
-
[57]
Mohri, Semiring frameworks and algorithms for shortest-distance problems, J
M. Mohri, Semiring frameworks and algorithms for shortest-distance problems, J. Autom. Lang. Comb.7 (2002), no. 3, 321–350
work page 2002
-
[58]
Myneni,The pricing of the american option, The Annals of Applied Probability (1992), 1–23
R. Myneni,The pricing of the american option, The Annals of Applied Probability (1992), 1–23
work page 1992
-
[59]
J. Norton and S. Spiroff,The tropical semiring in higher dimensions, Involve 11 (2018), no. 3, 477–488
work page 2018
-
[60]
L. Pachter and B. Sturmfels,Tropical geometry of statistical models, Proceedings of the National Academy of Sciences101 (2004), no. 46, 16132–16137
work page 2004
-
[61]
13, Cambridge university press, 2005
, Algebraic statistics for computational biology, vol. 13, Cambridge university press, 2005
work page 2005
-
[62]
A. Pnueli,The temporal logic of programs, 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), IEEE, 1977, pp. 46–57
work page 1977
-
[63]
Ree,Lie elements and an algebra associated with shuffles, Ann
R. Ree,Lie elements and an algebra associated with shuffles, Ann. of Math. (2)68 (1958), 210–220
work page 1958
-
[64]
Reutenauer, Free Lie algebras, Handbook of algebra, Vol
C. Reutenauer, Free Lie algebras, Handbook of algebra, Vol. 3, Handb. Algebr., vol. 3, Elsevier/North-Holland, Amsterdam, 2003, pp. 887–903. 42
work page 2003
-
[65]
Riehl,Category theory in context., Mineola, NY: Dover Publications, 2016
E. Riehl,Category theory in context., Mineola, NY: Dover Publications, 2016
work page 2016
-
[66]
M. Saers and D. Wu,Handling ties correctly and efficiently in Viterbi training us- ing the Viterbi semiring, Language and automata theory and applications, Lecture Notes in Comput. Sci., vol. 10792, Springer, Cham, 2018, pp. 284–295
work page 2018
-
[67]
Sakarovitch,Elements of automata theory, Cambridge University Press, 2009
J. Sakarovitch,Elements of automata theory, Cambridge University Press, 2009
work page 2009
-
[68]
P. Schultz, D. I. Spivak, and C. Vasilakopoulou,Dynamical systems and sheaves, Applied Categorical Structures28 (2020), no. 1, 1–57
work page 2020
- [69]
- [70]
-
[71]
J. Worthington, A bialgebraic approach to automata and formal language theory, Logical foundations of computer science, Lecture Notes in Comput. Sci., vol. 5407, Springer, Berlin, 2009, pp. 451–467. 43
work page 2009
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.