Lyndon Word Transduction to Improve the Efficiency of Computing Chen–Fliess Series

W. Steven Gray, Fatima Raza, Lance Berlin, Luis A. Duffaut Espinosa · 2025

Read Lyndon Word Transduction to Improve the Efficiency of Computing Chen–Fliess Series by W. Steven Gray, Fatima Raza, Lance Berlin, Luis A. Duffaut Espinosa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19908.txt.

Introduction

Control systems written as Chen-Fliess series describe outputs through iterated integrals of the inputs. W. Steven Gray and three co-authors cut the cost of computing those series. The integrals are tied together by shuffle products, so naive evaluation repeats work. Lyndon words, a special family of letter strings, index a leaner basis that holds all needed information.

Transducing word bases converts the computation into that lean form. The shuffle algebra on polynomials is isomorphic to a polynomial algebra on Lyndon words, which is the mathematical hinge. Less redundancy means faster, larger simulations of nonlinear systems. Chen-Fliess series appear across control engineering, from robotics to circuits. A basis change is a quiet kind of progress: same answers, fraction of the effort.

Catalog record

CREATORW. Steven Gray, Fatima Raza, Lance Berlin, Luis A. Duffaut Espinosa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-19908

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lyndon Word Transduction to Improve the Efficiency of Computing Chen–Fliess Series W. Steven Gray, Fatima Raza, Lance Berlin, Luis A. Duffaut Espinosa Abstract . The class of input-output systems representable as Chen–Fliess series arises often in control theory. One well known drawback of this representation, however, is that the iterated integrals which appear in these series are algebraically related by the shuffle product. This becomes relevant when one wants to numerically evaluate these series in applications, as this redundancy leads to unnecessary computational expense. The general goal of this paper is to present a computationally efficient way to evaluate these series by introducing what amounts to a change of basis for the computation. The key idea is to use the fact that the shuffle algebra on (proper) polynomials over a finite alphabet is isomorphic to the polynomial algebra generated by the Lyndon words over this alphabet. The iterated integrals indexed by Lyndon words contain all the input information needed to compute the output. The change of basis is accomplished by applying a transduction, that is, a linear map between formal power series in different alphabets, to re-index the Chen–Fliess series in terms of Lyndon monomials. The method is illustrated using a simulation of a continuously stirred-tank reactor system under a cyber-physical attack. MSC2020 : 41A58, 68R15, 93-08 Keywords : computational methods, Chen–Fliess series, Lyndon words, control theory 1. Introduction The class of input-output systems representable as Chen–Fliess series arises often in control theory [ 13 , 14 , 26 ] . Their convergence properties are well understood [ 2 , 13 , 23 ] , and their structure as series of iterated integrals makes them amenable to many forms of algebraic analysis [ 10 , 11 , 13 , 14 , 18 , 16 ] . One well known drawback of this representation, however, is that iterated integrals are algebraically related, in the simplest instance by the integration by parts formula, and more generally in terms of a shuffle algebra over the rational field [ 13 , 43 ] . Therefore, such series representations contain redundant information. This fact becomes relevant when one wants to numerically evaluate these series in applications, as this redundancy leads to unnecessary computational expense. Therefore, the general goal of this paper is to present a computationally efficient way to evaluate these series by introducing what amounts to a change of basis for the computation. The closest related literature to the proposed problem is that for computing the signature of a path in {\mathbb{R}}^{m} [ 35 ] . Signatures have found wide application in finance [ 1 , 33 ] and machine learning [ 7 , 36 ] . Similar to Chen–Fliess series, they involve (formal) sums of iterated integrals, but there are some key differences: i) Signatures operate on paths, that is, parameterized curves that are normalized to have unit length and unit speed along the path. Chen–Fliess series are defined on control signals, which are usually not normalized in any way. ii) Signatures (and their close relative Chen series [ 45 ] ) are exponential Lie series. Chen–Fliess series are generally not of this type. iii) Chen–Fliess series involve a generating series, namely a formal power series that can be computed from an underlying state space model (if one exists [ 13 , 14 , 26 ] ) or identified from input-output data [ 22 , 17 ] . It can also be completely arbitrary. The coefficients of the generating series provide weights for the iterated integrals. Signatures have no such counterpart. There are a number of software packages available for efficiently computing signatures [ 15 , 31 , 37 , 41 , 42 , 46 ] . The key idea behind optimizing this computation is to use the fact that the logarithm of a signature is a Lie series in the free Lie algebra over an alphabet X containing m letters. There are known basis sets for this Lie algebra, for example, the Lyndon word basis [ 34 ] . In which case, the only iterated integrals that need to be computed are those corresponding to the Lyndon words L over X , which are considerably fewer than in the general case. In many machine learning applications, computing the log-signature is in fact the primary goal. In the context of Chen–Fliess series, however, the log signature is not so relevant an object. Nevertheless, Lyndon words are still useful in solving the proposed problem. The main idea behind a more efficient computation of the Chen–Fliess series is to use the fact that the (commutative) shuffle algebra on the linear space of (proper) polynomials in X is isomorphic to the commutative polynomial algebra generated by the Lyndon words L over X [ 24 , 25 , 34 , 40 , 43 ] . The shuffle algebra is the graded dual of the universal enveloping algebra of the free Lie algebra on X [ 34 ] . It turns out that the iterated integrals indexed by Lyndon words contain all the input information needed to compute the output. The objective therefore is to rewrite the Chen–Fliess series in terms of an expansion indexed solely by Lyndon word monomials. This is accomplished by applying a transduction from the finite alphabet X to the countably infinite alphabet L . A transduction is a linear map between formal power series in different alphabets [ 12 , 28 , 27 , 32 , 44 ] . In the current context, it is useful to first present a transduction as an action on the universal control systems of Kawski and Sussmann [ 30 ] . These behave in much the same way that linear transformations act on finite dimensional state space realizations, albeit universal control systems are not finite dimensional. This in turn induces a transduction on the Chen–Fliess representation of the input-output map. These Chen–Fliess transductions will initially be viewed as formal maps without regard to convergence. But for the particular transduction of interest from X to L , a matrix representation will be derived in order to perform convergence analysis. In particular, it will be shown that this transduction preserves the local convergence of the original series. It should also be noted that transductions were first used in the context of Chen–Fliess series by Ferfera in [ 10 ] to provide a sufficient condition under which the series interconnection of two rational (i.e., bilinear) systems remains rational. But the notion of a Chen–Fliess transduction as presented here is only implicit in this earlier work. Finally, the proposed solution is evaluated using the concept of computational efficiency . This is a relative measure of the reduction in the number of iterated integrals needed to represent a generic input-output map up to a given word length (level in the language of signatures) in the new series expansion in terms of L as compared to the original series in terms of X . An asymptotic approximation of this measure as a function of word length is given in order to easily assess a priori the potential benefits of applying a Chen–Fliess transduction in a given application. A number of examples are considered, including one involving a type of cyber-physical attack on a

Read the complete text