\documentclass[12pt,fleqn]{article}
% \pagestyle{empty}

\input cyracc.def
\usepackage{graphicx,color}
\font\tencyr=wncyss10
\def\cyr{\tencyr\cyracc}
%
\newcommand{\aaa}{\fbox{$a$\rule{0mm}{5mm}}\,}
\newcommand{\bb}{\fbox{$b$\rule{0mm}{5mm}}\,}
\newcommand{\IIFX}{{\cal IIF}({\cal X})}
\newcommand{\dirprod}{\stackrel{\leftarrow}{\prod}^{\mbox{\tiny \raisebox{-1mm}{$\infty$}}}}
\newcommand{\Dirprod}{\stackrel{\leftarrow}{\Prod}^{\mbox{\tiny \raisebox{-1mm}{$\infty$}}}}
\newcommand{\printout}[1]{\begin{center}\framebox{
            \begin{minipage}{120mm}\bf #1\end{minipage}}\end{center}}
\newcommand{\rref}[1]{(\ref{#1})}
\newcommand{\UUpsilon}{\Upsilon\!\!\Upsilon}
\newcommand{\Shu}{\mbox{{\cyr Sh}}}
\newcommand{\shu}{\,\mbox{{\cyr sh}}\,}
\newcommand{\noi}{\noindent}
\newcommand{\vv}{\vspace{2mm}}
\newcommand{\vvv}{\vspace{7mm}}
\newcommand{\leftbrack}{\,<\!}
\newcommand{\ritebrack}{\!>\,}
\newcommand{\X}{{\mbox{${\cal X}$}}}
\newcommand{\Ren}{\mbox{${\bf R}^n$}}
\newcommand{\ren}{{\bf R}^n}
\newcommand{\R}{{\rm I}\hspace{-.2em}{\rm R}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\kk}{{\bf k}}
\newcommand{\PBW}{Poincar\'{e}-Birkhoff-Witt}
\newcommand{\Ser}{\mbox{\rm Ser}}
\newcommand{\veps}{\mbox{$\varepsilon$}}
\newcommand{\vphi}{\mbox{$\varphi$}}
\newcommand{\ddt}{{d\,\over dt}}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bd}{\begin{displaymath}}
\newcommand{\ed}{\end{displaymath}}
\newcommand{\bea}{\begin{equation}\begin{array}{ccl}}
\newcommand{\eea}{\end{array}\end{equation}}
\newcommand{\beqn}{\begin{eqnarray}}
\newcommand{\eeqn}{\end{eqnarray}}
\newcommand{\bda}{\begin{displaymath}\begin{array}{ccl}}
\newcommand{\eda}{\end{array}\end{displaymath}}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}{Definition}
\newcommand{\pf}{\vspace{1mm}\rule{0mm}{3mm}\\{\bf Proof. }}
\renewcommand{\baselinestretch}{1.2}
\topmargin=-10mm
\textheight=240mm
\textwidth=165mm
\evensidemargin=-9mm
\oddsidemargin=-9mm
\parindent=0mm

\begin{document}
\def\eps{\varepsilon}
\def\equaldef{\,{\buildrel \rm def \over =}\,}
\definecolor{darkgreen}{rgb}{0,.5,0.2}
\definecolor{purple}{rgb}{0.7,0,0.6}
\definecolor{brown}{rgb}{0.6,0.3,0.3}

\rule{11mm}{0mm}\hfill {\Large \bf \color{darkgreen}{Harvey Mudd
  College, March 1999}}
%{\large Harvey Mudd College, March 1999}
\vvv

\begin{center}
{\color{purple} {\Huge \bf Nonlinear Control:}
\\
{\LARGE \bf
From parallel parking \rule{43mm}{0mm}
\vv
\vv
\\
\rule{43mm}{0mm} to chronological algebras}
}% end color
\vvv \vvv

{\color{blue}
{\LARGE \bf Matthias Kawski }
\\
{\Large Department of Mathematics
\\
Arizona State University
\\
Tempe, Arizona 85287}}

{\color{red}\large \tt kawski@asu.edu}

{\color{darkgreen}{\large \tt
http://math.la.asu.edu/}$\tilde{\;\;}${\tt kawski}} \vvv \vvv \vvv

\begin{minipage}{150mm}
{\large {\bf Abstract.}
We know from personal experience that it is possible to
parallel park a car, even though one cannot directly move a
car side-ways. The key trick is to concatenate simple forward
and backward motions with suitable changes of the steering
angle.
\\
On a more abstract level, the side-ways motion is a consequence
of the lack of commutativity of the flows of the dynamical
systems that correspond to the simple forward and backward
motions with different steering angles.
\\
Geometric nonlinear control is the analysis of such noncommuting
flows in a general setting. Two key issues are controllability
-- in the example: Is it at all possible to move the car
side-ways? -- and automated path generation for controlled
dynamical systems.
\\
Motivated by the example, this talk will give a brief
introduction into the geometric and algebraic foundations
of noncommuting flows.
}
\end{minipage}
\end{center}
\vspace{78mm}

\pagebreak

\begin{center}
{\Huge \bf Parallel parking a car}
\end{center}
\vspace{78mm}

\hspace{-25mm}
\resizebox{0.60\textwidth}{!}{\includegraphics[-20mm,0mm][100mm,100mm]{stillplot.ps}}
\vspace{-99mm}
\\
\begin{picture}(100,100)
\put(0,32){\framebox(65,38){}}
\put(250,32){\framebox(65,38){}}
\put(340,32){\framebox(65,38){}}
\put(-20,28){\line(1,0){450}}
\end{picture}

{\LARGE
A simple problem to motivate the basic concepts
\\
of geometric nonlinear control theory.
\vvv
\vvv

The car cannot directly move side-ways,
\vvv

but practical experience tells us that
\begin{itemize}
\item {\em it is possible} to parallel park a car.
\item {\em it is not completely trivial}
to generate \\
the necessary maneuvers.
\end{itemize}
}
\pagebreak


\begin{center}
{\Huge \bf Parallel parking a car}
\end{center}
\vspace{78mm}

\hspace{-55mm}
\resizebox{0.60\textwidth}{!}{\includegraphics[-20mm,0mm][100mm,100mm]{stillplot.ps}}
\vspace{-59mm}

{\Large
\begin{itemize}
\item
How to mathematically model the system?
\item
Possible practical objectives:
\begin{itemize}
\item
Automate parallel-parking and similar maneuvers of a car
\item
Automate control of general mechanical systems
\end{itemize}
\item
Mathematical objectives:
\begin{itemize}
\item
Abstract the characteristic structures
\item
Formulate desired properties in a mathematical language
\item
Establish necessary and sufficient conditions
\item
Develop algorithms for solving general problems
\end{itemize}
\end{itemize}}
\pagebreak

\begin{center}
{\Huge \bf \rule{28mm}{0mm}Parallel parking a car}
\end{center}
\vspace{18mm}

\hspace{-35mm}
\resizebox{0.30\textwidth}{!}{\includegraphics[-20mm,0mm][100mm,100mm]{stillplot.ps}}
\vspace{-25mm}

\raisebox{16mm}{
\begin{minipage}{82mm}
{\Large \bf The states of the system}
\\
(simplified model -- correct for bicycle)
\end{minipage}
}
\hspace{-5mm}
\begin{picture}(100,0)
\put(30,90){\line(1,0){170}}
\put(122,30){\line(0,1){60}}
\put(122,90){\line(2,1){70}}
\put(30,30){\vector(1,0){150}}
\put(30,30){\vector(0,1){110}}
\put(118,22){$x$}
\put(22,88){$y$}
\put(165,94){$\Theta$}
\put(172,135){$\Phi$}
\put(138,110.5){\line(1,1){50}}
\put(138,109.5){\line(2,1){60}}
\thicklines
\put(100,60){\line(2,1){60}}
\put(85,90){\line(2,1){60}}
\put(85,90){\line(1,-2){15}}
\put(145,120){\line(1,-2){15}}
\put(102,67){\line(2,1){12}}
\put(92,87){\line(2,1){12}}
\put(101.5,68){\line(2,1){12}}
\put(91.5,88){\line(2,1){12}}
\put(102.5,66){\line(2,1){12}}
\put(92.5,86){\line(2,1){12}}
\put(143,85.5){\line(1,1){10}}
\put(133,105.5){\line(1,1){10}}
\put(142.3,86.2){\line(1,1){10}}
\put(132.3,106.2){\line(1,1){10}}
\put(143.7,84.8){\line(1,1){10}}
\put(133.7,104.8){\line(1,1){10}}
\end{picture}
\vspace{-5mm}

{\Large
\bd
\left.
\begin{array}{cl}
x,\;y & \mbox{coordinates of center of car}\\
v & \mbox{speed}\\
\Theta & \mbox{orientation of the car}\\
\Phi & \mbox{steering angle}
\end{array}
\rule{32mm}{0mm}
\right\}
\rule{8mm}{0mm}
\mbox{states}
\rule{27mm}{0mm}
\ed
\rule{7mm}{0mm}
\hrulefill
\rule{22mm}{0mm}
\bd
\left.
\begin{array}{cl}
a\;\;& \mbox{acceleration}\\
\omega\;\; & \mbox{angular velocity of steering wheel}
\\ &\mbox{\rule{25mm}{0mm}
    \raisebox{2mm}{(about a vertical axis)}}
\end{array}
\rule{18mm}{0mm}
\right\}
\mbox{\hspace{-3mm}
\begin{tabular}{l}
inputs\\
\rule{7mm}{0mm}({\em ``controls''})
\end{tabular}
}
\ed
}

{\Large
\bd
\begin{tabular}{l}
Equations\\
of motion
\end{tabular}
\rule{9mm}{0mm}
\left\{
\begin{array}{ccll}
\dot{x}&=& v\cos \Theta \\
\dot{y}&=& v\sin \Theta \\
\dot{v}&=& a &(=u_1) \\
\dot{\Theta}&=& v\sin \Phi \\
\dot{\Phi}&=& \omega &(=u_2) \\
\end{array}
\right.
\ed
This is not a standard dynamical system.
\\
\rule{22mm}{0mm}
Instead:
This is a {\em controlled dynamical system}.
\pagebreak

\begin{center}
{\Huge \bf \rule{28mm}{0mm}Parallel parking a car}
\end{center}
\vspace{49mm}

\hspace{-20mm}
\resizebox{0.30\textwidth}{!}{
\includegraphics[-20mm,0mm][100mm,100mm]{stillplot.ps}}
\vspace{-86mm}
{\LARGE
\bd
\rule{55mm}{0mm}
\left\{
\begin{array}{ccll}
\dot{x}&=& v\cos \Theta \\
\dot{y}&=& v\sin \Theta \\
\dot{v}&=& a &(=u_1) \\
\dot{\Theta}&=& v\sin \Phi \\
\dot{\Phi}&=& \omega &(=u_2) \\
\end{array}
\right.
\ed
\vvv


Written in standard as a multi-input
control system
%on a manifold:
\vv

\bd
\left\{
\begin{array}{ccl}
\dot{z} &=& f_0(z)+\sum_{j=1}^2u_jf_j(z)
\\
z &\in& M^5 = {\bf R^3}\times S^1 \times S^1
\\
u & \in & [-a_{\rm max},a_{\rm max}]\times
          [-\omega_{\rm max},\omega_{\rm max}]
\end{array}
\right.
\ed
\vv
\vv

with {\em drift vector field}
\bd
f_0=
z_3\cos z_4{\partial \over \partial z_1}+
z_3\sin z_4{\partial \over \partial z_2}+
z_3\sin z_5{\partial \over \partial z_4},
\ed
and {\em controlled fields}
\bd
f_1={\partial \over \partial z_3},
\;\;\mbox{ and }\;\;
f_2={\partial \over \partial z_5}.
\ed
\vvv
\vvv

For every choice of controls $u_1(t),\;u_2(t)$
(that are locally integrable) one obtains an
ordinary dynamical system.
}
\pagebreak

{\LARGE \bf Easiest example:
{\em Piecewise constant controls}}
\rule{61mm}{0mm}\hfill
{\Large in this simple {\em cascade system}
}
\vspace{-10mm}
\\
\begin{minipage}{45mm}
\rule{0mm}{19mm}

\resizebox{60mm}{25mm}{\includegraphics{cntrls.ps}}
\vspace{13mm}

\resizebox{60mm}{25mm}{\includegraphics{speedplot.ps}}
\vspace{13mm}

\resizebox{60mm}{25mm}{\includegraphics{angleplot.ps}}
\vspace{13mm}

\resizebox{60mm}{25mm}{\includegraphics{velplot.ps}}
\end{minipage}
\begin{minipage}{115mm}
{\Large
{\bf Control inputs}:
\\
Blue: For/backward acceleration $u_1$
\\
Red: Angular velocity of steering wheel $u_2$
\vvv

{\bf States}:
\\
Black: For/backward speed $v=\int u_1$
\\
Magenta: Steering angle $\Phi=\int u_2$.
\\
Brown: Orientation of the car $\Theta=\int v\sin\Phi$.
\\
Green: $x$-component of velocity $v_x=v\cos \Theta$
\\
Cyan: $y$-component of velocity $v_y=v\sin \Theta$
}
\vspace{71mm}

\hspace{-20mm}
\resizebox{0.70\textwidth}{!}{\includegraphics[-20mm,0mm][100mm,100mm]{stillplot.ps}}
\vspace{-75mm}
\end{minipage}
\vspace{2mm}

\bd
v(0)=\Phi(0)=\Theta(0)=x(0)=y(0)=0=v(t)=\Phi(t)=\Theta(t)=x(t)
\ed
\bd
y(t)=
\int_0^t
  \underbrace{\int_0^{t_1}\!\!u_1(t_2)\,dt_2}_{v(t_1)}
  \cdot\sin
  \overbrace{(\int_0^{t_1}\!\!
      \underbrace{\int_0^{t_2}\!\!u_1(t_2)\,dt_2}_{v(t_2)}\cdot
      \sin(
      \underbrace{\int_0^{t_2}\!\!u_2(t_3)\,dt_3)}_{\Phi(t_2)}
      \,dt_2)}^{\Theta(t_1)}
\,dt_1\
\ed
\pagebreak

\begin{center}
{\Huge \bf Noncommuting flows}
\end{center}
\vvv
\vvv
\vvv


\raisebox{-19mm}{
\resizebox{0.66\textwidth}{33mm}{\includegraphics{cntrls.ps}}
}
\hspace{-38mm}
\begin{minipage}{97mm}
Concatenate the solutions of the
\\
(standard) dynamical systems
\\
(controls normalized to $\pm 1$)
\end{minipage}
\begin{displaymath}
\begin{array}{cccccccccrl}
0&\leq&t&<&T_1&\rule{12mm}{0mm}
                 &\dot{z}&=&f_0(z)&+f_1(x)&+f_2(z)\\
T_1&\leq&t&<&T_2&&\dot{z}&=&f_0(z)&+f_1(x)&-f_2(z)\\
T_2&\leq&t&<&T_3&&\dot{z}&=&f_0(z)&&-f_2(z)\\
T_3&\leq&t&<&T_4&&\dot{z}&=&f_0(z)&-f_1(x)&-f_2(z)\\
T_4&\leq&t&<&T_5&&\dot{z}&=&f_0(z)&-f_1(x)&+f_2(z)\\
T_5&\leq&t&<&T_6&&\dot{z}&=&f_0(z)&-f_1(x)&-f_2(z)\\
T_6&\leq&t&<&T_7&&\dot{z}&=&f_0(z)&&-f_2(z)\\
T_7&\leq&t&<&T_8&&\dot{z}&=&f_0(z)&+f_1(x)&-f_2(z)\\
T_8&\leq&t&<&T_9&&\dot{z}&=&f_0(z)&+f_1(x)&+f_2(z)
\end{array}
\end{displaymath}
\vspace{23mm}

\begin{minipage}{85mm}
\begin{center}
The flows do not commute.
\\
Most simple picture for:
\end{center}
{\large
\bd
f_1(x)=\left(\begin{array}{c}1\\0\\-y\end{array}\right)
\rule{12mm}{0mm}
f_2(x)=\left(\begin{array}{c}0\\1\\x\end{array}\right)
\ed
}
\end{minipage}
\rule{22mm}{0mm}
\begin{minipage}{25mm}
\rule{44mm}{0mm}
\resizebox{55mm}{55mm}{\includegraphics{bracket.ps}}
\end{minipage}
\pagebreak


\raisebox{41mm}{
{\Huge \bf The Lie bracket}
}
\rule{24mm}{0mm}
\resizebox{55mm}{55mm}{\includegraphics{bracket.ps}}
\vspace{-18mm}

{\bf Geometric definition}
\\
The Lie bracket of two vector fields
$f$ and $g$ at $p$ is defined
as the limit (provided it exists):
For all smooth functions $\varphi$
\bd
([f,g]\varphi)(p)=\lim_{t\rightarrow 0}
{1\over t^2}
\left(
\varphi(e^{-tg}e^{-tf}e^{tg}e^{tf}(p))-\varphi (p)\right)
\ed
\vvv
\vvv

{\bf In local coordinates}
\\
%(Let $Du$ denote the Jacobian matrix
%of a column vector field $u$.)
If $v$ and $w$ are (column) vector fields, then

\bd
[v,w]=(Dw)v-(Dv)w
\ed
\vvv
\vvv
\vvv

{\large
Recall the basic example
\begin{minipage}{85mm}
{\large
\bd
f_1(x)=\left(\begin{array}{c}1\\0\\-y\end{array}\right)
\rule{12mm}{0mm}
f_2(x)=\left(\begin{array}{c}0\\1\\x\end{array}\right)
\ed
}
\end{minipage}
\vvv

\bd
[f_1,f_2](x)=
\left(\begin{array}{ccc}0&0&0\\0&0&0\\1&0&0\end{array}\right)
\left(\begin{array}{c}1\\0\\-y\end{array}\right)
-
\left(\begin{array}{ccc}0&0&0\\0&0&0\\0&-1&0\end{array}\right)
\left(\begin{array}{c}0\\1\\x\end{array}\right)
=
\left(\begin{array}{c}0\\0\\2\end{array}\right)
\ed
}
\pagebreak


\begin{center}
{\Huge \bf Lie algebra rank condition}
\end{center}
\vvv
\vvv

Controllability is the {\em opposite} of integrability.
Loosely speaking, a control system is globally controllable.
if it is possible to reach any point in the state space
from any other point in the state space along a solution
curve of the control system.
\vvv
\vvv


Accessibility is a weak form of controllability:
A system is accessible from a point $p$ if it is
possible to reach an open set of states by solution
curves of the system starting at $p$.
\vvv
\vvv

A {\em sufficient condition} for accessibility of
a smooth control system
$\dot{x}=f_0(x)+\sum_{k=1}^m u_k f_k(x)$
from a point $p$ is that the Lie algebra
generated by the vector fields $f_0,\ldots f_m$
spans the tangent space at the point $p$.
\pagebreak

\begin{center}
{\Huge \bf \rule{28mm}{0mm}
Parking model is controllable}
\end{center}
\vspace{23mm}

\hspace{-35mm}
\resizebox{0.30\textwidth}{!}{\includegraphics[-20mm,0mm][100mm,100mm]{stillplot.ps}}
\vspace{-45mm}

\raisebox{26mm}{
\begin{minipage}{22mm}
{\Large \bf Recall:}
\end{minipage}
}
\hspace{-2mm}
\raisebox{26mm}{
\begin{minipage}{142mm}
{\large
\bd
f_0(z)=\left(\begin{array}{c}
z_3\cos z_4\\z_3\sin z_4\\0\\z_3\sin z_5\\0
\end{array}\right)
\rule{12mm}{0mm}
f_1(z)=\left(\begin{array}{c}
0\\0\\\fbox{1}\\0\\0
\end{array}\right)
\rule{12mm}{0mm}
f_2(z)=\left(\begin{array}{c}
0\\0\\0\\0\\\fbox{1}
\end{array}\right)
\ed
}
\end{minipage}
}
\vvv

{\large
\bd
[f_1,f_0](x)=\left(\begin{array}{c}
\fbox{$\cos z_4$}\\\sin z_4\\0\\\sin z_5\\0
\end{array}\right)
\rule{8mm}{0mm}
[f_2,f_0](x)=\left(\begin{array}{c}
0\\0\\0\\z_3\cos z_5\\0
\end{array}\right)
\rule{8mm}{0mm}
[f_2,f_1](x)=\left(\begin{array}{c}
0\\0\\0\\0\\0
\end{array}\right)
\ed
\vvv
\bd
[f_1,[f_2,f_0]](x)=\left(\begin{array}{c}
0\\0\\0\\\fbox{$\cos z_5$}\\0
\end{array}\right)
\rule{8mm}{0mm}
[[f_1,[f_2,f_0]],[f_1,f_2]](x)=\left(\begin{array}{c}
\sin z_4\\\fbox{$\cos z_4$}\\0\\0\\0
\end{array}\right)
\ed
}

These iterated Lie brackets span the tangent space
of ${\bf R}^5$ at the origin -- hence the system is
accessible from $0$.
\pagebreak


\begin{center}
{\Huge \bf  Manipulating exponential products}
\end{center}
\vvv

Instead of working with complicated concatenations of flows like
 {\color{purple}
 \bd \rule{0mm}{1mm} \mbox{\hspace{-5mm}} z(t)=
e^{\int^{t_9}_{t_8}(f_0+f_1+f_2)\,dt}\circ \ldots
% e^{\int^{t_3}_{t_2}(f_0-f_2)\,dt}\circ
e^{\int^{t_2}_{t_1}(f_0+f_1-f_2)\,dt}\circ
e^{\int^{t_1}_0(f_0+f_1+f_2)\,dt}
(p)
\ed
 }%end purple
\vv

it is desirable to rewrite the
solution curve using a minimal
number of vector fields $f_{\pi_k}$
that span the tangent space
(typically using iterated Lie brackets of
the system fields $f_0,f_1,\ldots f_m$)
\vv

 {\color{purple}
{\em Coordinates of the first kind}
 {\color{blue}
\bd \rule{0mm}{1mm} \mbox{\hspace{-0mm}} z(t)=
e^{b_1(t,u)f_{\pi_1}
  +b_2(t,u)f_{\pi_1}
  +b_3(t,u)f_{\pi_3}
  + \ldots
  +b_n(t,u)f_{\pi_n}}
(p)
\ed
 }%end blue

{\em Coordinates of the second kind}
 }%end purple
 {\color{blue}
\bd \rule{0mm}{1mm} \mbox{\hspace{-0mm}} z(t)=
e^{c_1(t,u)f_{\pi_1}} \circ e^{c_2(t,u)f_{\pi_1}} \circ
e^{c_3(t,u)f_{\pi_3}} \circ \ldots \circ e^{c_n(t,u)f_{\pi_n}} (p)
\ed \vvv
 }%end blue

{\color{darkgreen}
 Using the {\em Campbell-Baker-Hausdorff formula},
this is possible, but a book-keeping nightmare. \vv
 }%end darkgreen

{\color{brown}
 Moreover, the CBH formula does
 {\color{purple}not} use a {\color{purple}basis},
but uses linear combinations of all possible iterated Lie
brackets. Yet, by the Jacobi identity (and anticommutativity), in
ever Lie algebra e.g.

{\color{blue} \bd [X,[Y,{\color{red}[X,Y]}]]+
[Y,\underbrace{[{\color{red}[X,Y]},X]}]+
[{\color{red}[X,Y]},[X,Y]]]=0 \ed
 }%end blue
and hence
 {\color{blue}
 \bd [X,[Y,{\color{red}[X,Y]}]]=
 [Y,\overbrace{[X,{\color{red}[X,Y]}]}] \ed
 }%end blue
 }%end brown

{\color{darkgreen}
 {\bf Plan}:
\begin{itemize}
\item Work with bases for (free) Lie algebras.
\item Find useful formulae for the coefficients
      $b_k(t,u)$ or $c_k(t,u)$.
\end{itemize}
 }%end darkgreen
\pagebreak

\begin{center}
{\Huge \bf The Chen Fliess series}
\end{center}
\vvv

{\large
{\color{darkgreen}
K.~T.~Chen, 1957:
Geometric invariants of curves in ${\bf R}^n$
\\
M.~Fliess, 1970s: adaptation to control
}% end of color dark green
\vvv


The formal control system
 {\color{blue}
\bd \label{formal}
\dot{S}=S\left( \sum_{i=1}^m u^iX_i\right), \;\;\;\; S(0)=I \ed
 }% end of color blue
\vvv

on the associative algebra
$\hat{A}(X_1\ldots X_m)$
{\color{brown}
of formal power series %(with real coefficients)
in the
\\
noncommuting indeterminates (letters)
$X_1,\ldots X_m$
}%end brown
has the unique solution
\vvv

 {\color{blue}
\bd
\rule{0mm}{1mm}\hspace{-6mm}
S_{CF}(T,u)=\sum_I
\underbrace{
\int_0^T\!\!\int_0^{t_1}\!\!\cdots \int_0^{t_{p-1}}\!\!
u^{i_p}(t_p)\ldots u^{i_1}(t_1)
\, dt_1\ldots dt_p
}_{\Upsilon^I(T,u)}
\;\underbrace{
X_{i_1}\ldots X_{i_p}
}_{X_I}
\ed
}% end of color blue
\vvv
\vvv

{\bf What is the CF-series good for?}
\vv

For any given control system
 {\color{blue}
\bd \dot{x}=\sum_{i=1}^mu_i(x)f_i(x),\;\;\; x(0)=p,\;\;
 \mbox{\color{black}with ``output'' }\;\; y=\varphi(x) \ed
 }% end of color blue

 {\color{red}
\bd \rule{0mm}{1mm}\hspace{-6mm} \phi(x(T,u))=\sum_I
 \underbrace{
 {\color{blue}
 \int_0^T\!\!\int_0^{t_1}\!\!\cdots\int_0^{t_{p-1}}\!\!
 u^{i_p}(t_p)\ldots u^{i_1}(t_1) \, dt_1\ldots dt_p }
 }_{\Upsilon^I(T,u)} \; (f_{i_1}\circ\ldots \circ
f_{i_p}\varphi )(p) \ed
}% end of color red

{\color{brown}
(uniform convergence for small $T$
and IC's on compacta
[Sussmann, 1983])
}%end brown
\vvv

{\color{darkgreen}
The CF-series was basic tool for deriving many
high-order conditions for controllability and
optimality.
[Hermes, Stefani, Sussmann, Kawski, ...]
} %end color darkgreen
\pagebreak

\begin{center}
{\Huge \bf Inadequacies of the CF-series}
\end{center}
\vvv
\vvv

{\Large
{\color{darkgreen}
The Chen Fliess series is a good starting point, BUT
\begin{itemize}
\item It has too many terms
      (``$2^\infty$ when only $\infty$ should do'')
\item Lots of duplication:
      Repetition in the iterated integrals
      \\
      High-order partial diff operators
      \\
      \rule{12mm}{0mm}
      where only
      $1^{\rm st}$ or low order PDO's should occur
\item It is not geometric:
      \\
      Its character as exponential Lie series is
      not obvious
\item It is not geometric:
      \\
      Truncations do not correspond to any systems at all
      \\
      \rule{12mm}{0mm}
      (not directly useful for obtaining
      approximating systems)
\end{itemize}
}%end of darkgreen
\vvv \vvv More desirable alternatives: Expand the series in either
of the forms \bd \rule{0mm}{1mm}\hspace{-6mm}
S_{CF}(T,u)=\exp\left( \sum_{B\in {\cal B}} \alpha_B(t,u)\;B
\right) \ed or \bd S_{CF}(T,u)= \stackrel{\leftarrow}{\prod_{B\in
{\cal B}}} \exp\left( \beta_B(T,u)\;B\right) \ed for suitable
bases ${\cal B}$ of the free Lie algebra $L(X_1,\ldots X_m)$.
\\
\rule{1mm}{0mm}\hfill
{\color{purple} {\bf Question:} Existence? }%end purple
}%end of Large
\pagebreak

\begin{center}
{\LARGE \bf Ree's theorem and exponential Lie series}
\end{center}
\vvv

{\Large
{\color{red}
{\bf Theorem} [Ree, 1957]:
A formal power-series $\sum_I c_I X_I$ is an
exponential Lie series iff the coefficients
satisfy the {\em shuffle relations}
\bd
c_{I\,\shu\,J}=c_I \cdot c_J \;\;\;\mbox{ for all }\;I,J
\ed
}%end of red
\vvv
\vvv

{\color{purple}
{\bf Exercise}:
\\
The coefficients $\Upsilon_I(T,u)$
of the CF-series satisfy the
shuffle relations.
}%end of blue
\vv

{\color{brown}
(Simple induction.
Shuffles correspond to pointwise multiplication
of integrated integral functionals.
Recursive definition of shuffle product
corresponds to repeated integration by parts.)
}%end of brown
\vvv
\vvv

{\color{red}
{\bf Corollary}:
Either expansion of the CF-series
(exp of sum, or product of exp)
is possible.
}%end of red
\vvv

{\color{blue}
{\bf Issues/questions}:
\begin{itemize}
\item Need explicit basis for the free Lie algebra
\item Want explicit formulae for the iterated integral
      coefficients
      \\
      $\alpha_B(T,u)$ and/or $\beta_B(T,u)$.
\end{itemize}
}%end of blue
}% end of Large
\pagebreak

\begin{center}
{\Huge \bf Shuffle product}
\end{center}
\vvv
\vvv

{\Large
{\bf Combinatorial definition}
(for words $w,z$ and letters $a,b$):
\bd
(\,w\,a\,)\;\Shu\;(\,z\,b\,)= ((\,w\,a\,)\;\Shu\;z\,)\,b
                              +(\,w\;\Shu\;(\,z\,b\,))\,a
\ed
\vvv
\vvv

{\bf Example}: The shuffle product of two words

\bda

({\color{red}ab})\;\Shu\;({\color{blue}cd})&=&

{\color{red}a\,b}\,{\color{blue}c\,d}\, + \,{\color{red}
a}\,{\color{blue}c\,}{\color{red}b}\,{\color{blue}d}\,+\,
{\color{blue}c}\,{\color{red}a\,b\,}{\color{blue}d}\,+\,
\\&&
{\color{red}a}\,{\color{blue}c\,d\,}{\color{red}b}\,+\,{\color{blue}c\,}{\color{red}
a}\,{\color{blue}d\,}{\color{red}b}\,+\,{\color{blue}c\,d\,}{\color{red}a\,b\,}

\eda \vvv \vvv \vvv \vvv

{\bf Algebraic definition}:
\\
On the free associative algebra $A=A_{\bf k}({\cal X})$
{\color{brown}
(algebra of polynomials, or {\em ``words''})
}%end brown
over a set ${\cal X}$
{\color{brown}
(of noncommuting indeterminates, or{\em ``letters''})
}%end brown
define a {\em co-product}
\bd
\Delta \colon A \times A \mapsto A
\;\;\;\mbox{ by }\;\;\;
\Delta (a) = 1 \otimes a + a \otimes 1
\;\;\mbox{ for }a\in {\cal X}
\ed
\vvv

Define the {\em shuffle product} $\Shu$  as
the transpose of $\Delta$
\\
{\color{brown}
(on the algebra $\hat{A}=\hat{A}_{\bf k}({\cal X})$
of formal power series)
}%end brown
\bd
\leftbrack \;v\;\Shu \;w\;,\;z\;\ritebrack =
\leftbrack \;v\otimes w\;,\;\Delta (z)\;\ritebrack
\ed
}%end of Large
\pagebreak

\begin{center}
{\Huge \bf Shuffles and simplices}
\end{center}
\vvv

On permutations algebras Duchamp and Agrachev consider
\\
{\em partially commutative} and noncommutative shuffles.
Illustration:

\begin{center}
\begin{picture}(300,100)(-10,-10)
\multiput(0,0)(120,0){3}{\vector(1,0){70}}
\multiput(0,0)(120,0){3}{\vector(0,1){70}}
\thicklines
\multiput(0,0)(120,0){2}{\line(1,0){50}}
\put(0,50){\line(1,0){50}}
\put(240,50){\line(1,0){50}}
\put(0,0){\line(0,1){50}}
\put(240,0){\line(0,1){50}}
\multiput(50,0)(120,0){2}{\line(0,1){50}}
\multiput(1,1)(120,0){2}{\line(1,0){48}}
\put(1,49){\line(1,0){48}}
\put(241,49){\line(1,0){48}}
\put(1,1){\line(0,1){48}}
\put(241,1){\line(0,1){48}}
\multiput(49,1)(120,0){2}{\line(0,1){48}}
\put(120,0){\line(1,1){49}}
\put(121,0){\line(1,1){49}}
\put(240,1){\line(1,1){49}}
\put(240,0){\line(1,1){49}}
\put(14,22){$\sigma_{1\shu 2}$}
\put(22,-8){$\sigma_{1}$}
\put(-15,22){$\sigma_{2}$}
\put(87,20){$=$}
\put(147,14){$\sigma_{21}$}
\put(207,20){$\cup$}
\put(244,30){$\sigma_{12}$}
\end{picture}
\end{center}
\vspace{-3mm}

In the case of three letters $\{1,2,3\}$
\vspace{9mm}

\rule{9mm}{0mm}
\resizebox{0.19\textwidth}{!}{\includegraphics{a1.ps}}
\hspace{-7mm}\raisebox{16mm}{\scalebox{1.5}{$=$}}\hspace{9mm}
\resizebox{0.19\textwidth}{!}{\includegraphics{a2.ps}}
\hspace{-7mm}\raisebox{16mm}{\scalebox{1.5}{$\cup$}}\hspace{9mm}
\resizebox{0.19\textwidth}{!}{\includegraphics{a3.ps}}
\hspace{-7mm}\raisebox{16mm}{\scalebox{1.5}{$\cup$}}\hspace{9mm}
\resizebox{0.19\textwidth}{!}{\includegraphics{a4.ps}}
\vspace{-9mm}


\bd
\sigma_{(12)\shu 3}
\rule{13mm}{0mm}=\rule{13mm}{0mm}
\sigma_{312}
\rule{13mm}{0mm}\cup\rule{13mm}{0mm}
\sigma_{132}
\rule{13mm}{0mm}\cup\rule{13mm}{0mm}
\sigma_{123}\ed

{\large
E.g.
$\sigma_{(12)\shu 3}
=\{t\colon 0\leq t_1\leq t_2\leq 1,\;\;0\leq t_3\leq 1\}
$
}
\vvv

For multiplicative integrands
$f(x,y,z)=f_1(x)\cdot f_2(y)\cdot f_3(z)$
\\
(using $x,y,z$, instead of $t_1,t_2,t_3$
for better readability):
\begin{eqnarray*}
\lefteqn{
\left(\int_0^1\!\!\!\int_0^y\!(\;\cdot\;)dx\,dy\right)
    \cdot \int_0^1 (\cdot)dz
=}\\&&\!\!
\int_0^1\!\!\!\int_0^y\!\!\!\int_0^x\!(\;\cdot \;)\,dz\,dx\,dy
+\!\int_0^1\!\!\!\int_0^y\!\!\!\int_0^z\!(\;\cdot \;)\,dx\,dz\,dy
+\!\int_0^1\!\!\!\int_0^z\!\!\!\int_0^y\!(\;\cdot \;)\,dx\,dy\,dz
\end{eqnarray*}

\pagebreak

\begin{center}
{\LARGE \bf CF-coefficients satisfy shuffle-relations}
\end{center}
\vvv

{\Large
Sketch of proof of exercise
(by induction on the
combined lengths of the coefficients)
}
\vvv

{\color{blue}
\bd
\Upsilon^1(t,u)\equiv 1
\ed
\vvv

\bda
\Upsilon^{a\shu 1}(t,u)
&=&\Upsilon^a(t,u)
\rule{0mm}{9mm}
\\&=&\Upsilon^a(t,u)\cdot 1
\rule{0mm}{9mm}
\\&=&\Upsilon^a(t,u)\cdot \Upsilon^1(t,u)
\rule{0mm}{9mm}
\;\;\;\mbox{ for any letter }\;\;a\in {\cal X}
\eda
\vvv

\be
\label{byparts}
\begin{array}{ccl}
\lefteqn{\hspace{-11mm}
\Upsilon_{(wa)\shu (zb)}(T,u)=}
\\
\rule{0mm}{9mm}\rule{22mm}{0mm}&=&
\Upsilon_{((wa)\shu z)b+(w\shu (zb))a}(T,u)
\\
\rule{0mm}{9mm}&=&
\Upsilon_{((wa)\shu z)b}(T,u)+\Upsilon_{(w\shu (zb))a}(T,u)
\\
\rule{0mm}{9mm}&=&
\int_0^T \Upsilon_{(wa)\shu z}(t,u)\cdot u_b(t)dt+
\int_0^T \Upsilon_{w\shu (zb)}(t,u)\cdot u_a(t)dt
\\
\rule{0mm}{9mm}&=&
\int_0^T \left(
 \Upsilon_{wa}(t,u)\cdot\Upsilon_z(t,u)\cdot u_b(t)+
 \Upsilon_w(t,u)\cdot\Upsilon_{zb}(t,u)\cdot u_a(t)
 \right)dt
\\
\rule{0mm}{9mm}&=&
\int_0^T \left( \Upsilon_{wa}(t,u)\cdot
         {d\over dt}\Upsilon_{zb}(t,u)+
{d\over dt}\left(\Upsilon_{wa}(t,u)\right)\cdot
         \Upsilon_{zb}(t,u)\right)dt
\\
\rule{0mm}{9mm}&=&
\Upsilon_{wa}(T,u)\cdot \Upsilon_{zb}(T,u)
\end{array}
\ee
}%end blue
\vvv

{\color{brown}
{\Large
{\bf Morale}:
When working with repeated integrations by parts,
omit {\em ``integrals and similar notational ballast''}.
Instead work purely combinatorially in shuffle algebra.
}
}%end brown
\pagebreak

\begin{center}
{\Huge \bf Product expansion of CF-series}
\end{center}
\vvv

{\Large
{\color{brown}
Using Ree's theorem the existence of
exponential product expansions of the
CF-series is assured.
for suitable bases ${\cal B}$ of $L(X_1,\ldots X_m)$.

\bd
S_{CF}(T,u)=
\stackrel{\leftarrow}{\prod_{B\in {\cal B}}}
\exp\left( \beta_B(T,u)\;B\right)
\ed
}%end brown
\vvv

{\color{brown}
{\bf Recall remaining issues/questions}:
\begin{itemize}
\item Need explicit basis for the free Lie algebra
\item Want explicit formulae for the iterated integral
      coefficients
      \\
      $\alpha_B(T,u)$ and/or $\beta_B(T,u)$.
\end{itemize}
}%end brown
\vvv

Using different bases for the free Lie algebra
explicit formulae for the dual bases
(iterated integral functionals $\beta_B(T,u)$
have been rediscovered several times in
different contexts:
{\color{red}
\begin{itemize}
\item Sch\"utzenberger (1958), S\'eminaire Dubreil
\item Sussmann (1986), Nonlinear control
\item Melan\c{c}on and Reutenauer (1989), Combinatorics
\item Grayson and Grossman (1991),
      \\\rule{31mm}{0mm}
      Realizations of free nilpotent Lie algebras
\end{itemize}
}%end of red
\vvv

\rule{1mm}{0mm}\hfill
{\color{darkgreen}
$\Longrightarrow$ See historical slide
}%end of darkgreen
}%end of Large
\pagebreak




\begin{center}
{\Huge \bf  Lazard elimination}
\end{center}
\vvv
\vvv

{\LARGE
\begin{center}
\begin{minipage}{145mm}
{\color{red}
{\bf Theorem} [Lazard elimination]:
\\
Suppose  $\kk$ a field of scalars, $\X$ is a set and
$c\in \X$.
\\
Then the free Lie algebra $L_{\kk}(\X)$
over $\kk$ generated by $\X$ is the direct sum of the
one-dimensional subspace
$\{\lambda c\colon \lambda\in \kk\}$ and
of a Lie-subalgebra of $L_{\kk}(\X)$ that is
freely generated by the set
$\{({\rm ad}^j c,b)\colon
b\in \X\setminus\{c\},\,j\geq 0\}$.
}%end{red}
\end{minipage}
\end{center}
}%end of Large
\vvv
\vvv
\vvv

{\Large
{\color{darkgreen}
This principle is at the heart of constructions
involving Hall bases for free Lie algebras, for
Sussmann's derivation of the exponential product
expansion by solving DEs by iteration, and thereby
it is closely connected to chronological structures.
}%end darkgreen
}%end of Large
\pagebreak

\begin{center}
{\Huge \bf  Hall and Lyndon bases}
\end{center}
\vvv
{\Large

 {\color{darkgreen}
 Ph.~Hall, 1930s, calculus of commutator groups
 \\
 M.~Hall, 1950s, first bases for free Lie algebras
 \\
 Lyndon, 1950s, different (?) bases
 \\
 S\v{i}rsov, 1950s, different (?) bases
 \\
 Viennot, 1970s, only one kind of practical basis
 }%end darkgreen
\vvv
\vvv

 {\color{blue}
 A Hall set
 {\color{brown} over a set $\X$
 }%end brown
  is any strictly ordered subset $\tilde{\cal H}$
 {\color{brown} of the free magma
 }%end brown
 ${\cal M}(\X)$
  {\color{brown} (i.e. the set of all
  {\em parenthesized} words, or labelled binary trees)
 }%end brown
  that satisfies
\begin{itemize}
\item $\X\subseteq \tilde{\cal H}$

\item Suppose $a\in \X$.
      Then $(w,a)\in \tilde{\cal H}$ iff
      $w\in {\cal H}$, $w<a$ and $a<(w,a)$.
\item Suppose $u,v,w,(u,v)\in \tilde{\cal H}$.
      \\
      Then $(u,(v,w))\in \tilde{\cal H}$
      iff $v\leq u \leq (v,w)$ and $u<(u,(v,w))$.
\end{itemize}
 }%end blue
\vvv

 {\color{brown}
 Original Hall bases as in Bourbaki require that
 ordering be compatible with the length.
 Viennot showed that is not necessary.
 }%end brown
\vvv

 {\color{red}
 The image of a Hall set under the canonical map
 $\varphi \colon {\cal M}(\X) \mapsto L_{\kk}(\X)$
 from the free magma into the free Lie algebra is
 a basis for $L_{\kk}(\X)$.
 }%end red
 }%end of Large
 \pagebreak

 \begin{center}
 {\Huge \bf  Lie brackets and formal brackets}
 \end{center}
 \vvv
 {\Large

 {\color{purple}
 Need to distinguish formal brackets and
 elements of a Lie algebra.
 }%end purple
 \\
 E.g., consider
 %{\color{blue}
 $\{x,y,(x,y),(y,(x,(x,y)))\}\subseteq
 \tilde{\cal H}\subseteq {\cal M}(\{x,y\})$.
 %}%end blue
 Then
 {\color{blue}
 \bda
 \varphi((x,y))&=&[x,y]=-[y,x]
 \mbox{\color{black}\rule{15mm}{0mm}, and }\\
 \varphi((y,(x,(x,y))))&=&[y,[x,[x,y]]]=[x,[y,[x,y]]]
 \eda
 }%end blue
 {\color{brown}
 (due to anti-commutativity and
 Jacobi-identity in $L_k(\X)$).
 }%end brown
\vvv

 Consequently,
 {\color{blue}
 \bda
 \varphi^{-1}([x,[y,[x,y]]])&=&
 \varphi^{-1}([y,[x,[x,y]]])
 \\&=&
 (y,(x,(x,y)))
 \\&\neq&(x,(y,(x,y)))
 \mbox{\color{black}\rule{15mm}{0mm} in }{\cal M}(\X)
 \eda
 }%end blue
 \vvv

 Similarly,
 {\color{blue}
 \bda
 \varphi^{-1}([-y,x])&=&
 \varphi^{-1}([x,y])
 \\&=&
 (x,y)
 \\&\neq&-(y,x)
 \mbox{\color{black}\rule{15mm}{0mm} in the algebra over }
 {\cal M}(\X)
 \eda
 }%end blue
 \vvv

 {\color{darkgreen}
 But coding of iterated integrals depends critically
 on the factorization of the Hall words, requiring
 }%end darkgreen
 {\color{purple}
  well-defined left and right factors.
 }%end purple
 }%end blue
}%end of Large
\pagebreak

\begin{center}
{\Huge \bf  Hall and Lyndon bases, examples}
\end{center}
\vvv {\Large

 \begin{minipage}{50mm}
 \begin{center}
 {\color{darkgreen}
 Lyndon basis
 }%end darkgreen
 \vv

 ${\color{black}b}
 $\\
 ${\color{black}(
 {\color{blue}
 ((((ab)b)b)b)
 }{\color{red}
 b
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (((ab)b)b)
 }{\color{red}
 b
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 ((((ab)b)b)b)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 ((ab)b)
 }{\color{red}
 b
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 (((ab)b)b)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (((ab)b)b)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a(((ab)b)b))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 b
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 ((ab)b)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 ((ab)((ab)b))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 ((ab)b)
 }%end red
 )}%end black
 $\\
 \framebox{
 ${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 (a((ab)b))
 }%end red
 )}%end black
 $
 }
 \\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a((ab)b))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a(a((ab)b)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 b
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (a(ab))
 }{\color{red}
 (ab)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 ((a(ab))(ab))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (ab)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a(ab))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a(a(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a(a(a(ab))))
 }%end red
 )}%end black
 $\\
 ${\color{black}b}$
 \end{center}
 \end{minipage}
 \hfill
 \begin{minipage}{60mm}
 \begin{center}
 {\color{darkgreen}
 {\bf Lyndon words}
 }%end darkgreen
 \\
 ${\color{blue}L}
 {\color{black}<[}
 {\color{blue}L}
 {\color{red}R}
 {\color{black}]<}
 {\color{red}R}$
 \\
 {\color{brown}
 Read backwards,
 \\
 a word is Lyndon if
 \\
 it is strictly larger
 \\
 in lexicographical
 \\
 order than any of its
 \\
 cyclic rearrangements
 }%end brown
 \vvv
 \vvv

  {\color{darkgreen}
 {\bf Hall words}
 \\
 (in narrow sense)
 }%end darkgreen
 \\
 \begin{itemize}
 \item $a\in {\cal X}\Rightarrow a\in {\cal H}$
 \item
 \framebox{
 \begin{minipage}{40mm}
 $w,z\in {\cal H}, u<v$
 \\$\Rightarrow |u|<|v|$
 \end{minipage}
 }%end framebox
 \item
 If $a\in {\cal X}$, then
 \\
 $(ua)\in {\cal H}\Leftrightarrow$
 \\
 $u<a$ and $u<(ua)$
 \item
 $(u,(vw))\in {\cal H}\Leftrightarrow$
 \\
 $u,(vw)\in {\cal H}$ and
 \\
 $v\leq u<(vw)$, $u<(u(vw))$
 \end{itemize}
 \end{center}
 \end{minipage}
 \hfill
 \begin{minipage}{50mm}
 \begin{center}
{\color{darkgreen}
 Hall basis \\
 (as in Bourbaki)
 }%end darkgreen
${\color{black}(
 {\color{blue}
 (a(ab))
 }{\color{red}
 (b(ab))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 (b(b(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 (b(a(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 (a(a(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (b(b(b(ab))))
 }%end red
 )}%end black
 $\\
${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (b(b(a(ab))))
 }%end red
 )}%end black
 $\\
${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (b(a(a(ab))))
 }%end red
 )}%end black
 $\\
${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (a(a(a(ab))))
 }%end red
 )}%end black
 $\\
${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 (b(ab))
 }%end red
 )}%end black
 $\\
${\color{black}(
 {\color{blue}
 (ab)
 }{\color{red}
 (a(ab))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (b(b(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (b(a(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (a(a(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a(a(ab)))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (b(ab))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (a(ab))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (a(ab))
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 b
 }{\color{red}
 (ab)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 (ab)
 }%end red
 )}%end black
 $\\
 ${\color{black}(
 {\color{blue}
 a
 }{\color{red}
 b
 }%end red
 )}%end black
 $\\
 ${\color{black}b}$
 \\
 ${\color{black}a}$
 \end{center}
 \end{minipage}
}%end of Large
\pagebreak

\begin{center}
{\LARGE \bf  Hall-Viennot bases: unique factorization}
\end{center}
\vvv {\Large

 {\color{darkgreen}
  Bases for free Lie algebras proposed by M.~Hall,
  Lyndon, and Sir\v{s}ov  were originally considered
  to be distinct, until Viennot  showed that they
  all arise from a fundamental
  {\color{purple}\em unique factorization principle}.
 %leading to a common constructive formula.
 }%end darkgreen
 \vvv
 \vvv

 {\color{red}
 {\bf By construction}:
 The restriction of the map $\varphi$
 {\color{blue}
 \bda
 \varphi (a)&=&a\;\;\mbox{\color{black} for };\;a\in \X
          \;\;\mbox{\color{black}, and }
          \\
 \varphi ((w,z))&=&[\varphi(w),\varphi(z)]
 \;\;\;\mbox{\color{black} for }\;\;w,\;z \in {\cal M}(\X).
 \eda
 }%end blue

 to any Hall-set $\tilde{\cal H}\subseteq {\cal M}(\X)$
 is one-to-one by construction [Viennot].
 }%end red
 \vv

 {\color{purple}
 Hence the inverse image
 $\varphi^{-1}(H)\in \tilde{\cal H}\subseteq {\cal M}(\X)$
 of an element
 $H\in \varphi (\tilde{\cal H})\subseteq L_{\kk}(\X)$
 is well-defined
 }%end purple
 \vv

 {\color{darkgreen}
 {\bf Practically speaking}:
 When working with a fixed Hall set there is no need to
 write down any parentheses!
 }% end darkgreen
 \vvv
 \vvv

 {\color{red}
 {\bf Consequence}:
 Every word $w\in W(\X)$ factors uniquely into
 a nonincreasing product of Hall words, i.e.
 there exist unique $H_j\in {\cal H}$, such that
 }%end red
 {\color{blue}
 \bd
 \label{UFP}
 w=H_1H_2\ldots H_s\;\;\mbox{ and }\;\;
 H_1\geq H_2\geq \ldots \geq H_s
 \ed
 }%end blue
}%end of Large
\pagebreak

\begin{center}
{\Huge \bf  Chronological products}
\end{center}
\vvv
{\Large

{\color{darkgreen}
In the most simple basic control system
{\color{blue}
\bd
\label{brock2}
\begin{array}{cclll}
\dot{y}_1&=&u_1&\rule{15mm}{0mm}&|u_1|\leq 1\\
\dot{y}_2&=&u_2&\rule{15mm}{0mm}&|u_2|\leq 1\\
\dot{y}_3&=&y_1u_2\\
\end{array}.
\ed
}%end blue
many consider
as a {\color{red}virtual} third control
the function
{\color{blue}
\bd
u_3 (t)=
{\color{red}
(u_1\star u_2)(t)\stackrel{\rm def}{=}
\left( \int_0^t u_1(s)\,ds\right) \cdot u_2(t)
}%end red
\ed
}%end blue
\vvv

The ubiquitous occurrence of this product
justifies to call it
}%end darkgreen
\begin{center}
{\bf \color{red} ``THE PRODUCT of control theory''}
\end{center}
\vvv
\vvv
\vvv

{\color{purple}
{\bf Exercise}:
Verify that this product satisfies:
\bd
(u_1\star u_2+u_2\star u_1)(t)
=
{d\over dt}\left(
\left( \int_0^t u_1(s)\,ds\right)
\left( \int_0^t u_2(s)\,ds\right)
\right)
\ed
and also the three term
}%end purple
{\color{red}
right chronological identity
}%end red
\vvv

{\color{blue}
\bda
{\color{red}
\left(u_1\star (u_2\star u_3)\right)(t)
}%end red
&=&
\left( \int_0^t u_1(s),ds\right)\cdot
\left(\left( \int_0^t u_2(s)ds\right)\cdot u_3(t)\right)
\\&=&\rule{0mm}{8mm}
\left( \int_0^t\left(
       \int_0^s u_1(\sigma)\,d\sigma\right)\cdot \,
        u_2(s)ds\right)
\cdot u_3(t)
\\&&\rule{0mm}{8mm}\rule{6mm}{0mm}+
\left( \int_0^t\left(
       \int_0^s u_2(\sigma)\,d\sigma\right)\cdot \,
        u_1(s)ds\right)
\cdot u_3(t)
\\&=&\rule{0mm}{8mm}
{\color{red}
\left((u_1\star u_2)\star u_3\right)(t)+
\left((u_2\star u_1)\star u_3\right)(t)
}%end red
\eda
}%end blue



}%end of Large
\pagebreak

\begin{center}
{\Huge \bf  Chronological algebras}
\end{center}
\vvv
{\Large

{\color{blue}
A (right) {\em chronological algebra}
is a linear space $C$ (over a field $\kk$) that is
endowed with a bilinear product
$\ast\colon C\times C \mapsto C$ which satisfies the
(right) {\em chronological identity}
\be
\label{rci}
v\ast (w\ast z) = (v\ast w)\ast z+(w\ast v)\ast z
\;\;\mbox{ for all }\;v,w,z \in C
\ee
}% end blue
\vvv

{\color{darkgreen}
{\bf Example 1}:(repeated)
\\
${\cal L}_{\rm loc}([0,\infty))$
with
$(u_1\star u_2)(t)\stackrel{\rm def}{=}
\left( \int_0^t u_1(s)\,ds\right) \cdot u_2(t)$
\vvv

{\bf Example 2}:
\\
${\cal AC}_{\rm loc}([0,\infty))$
with
$(U_1\ast U_2)(t)\stackrel{\rm def}{=}
\left(\int_0^tU_1(s)U'_2(s)\,ds\right)$
}%end darkgreen
\vvv

{\color{blue}
{\bf Easy exercise}:
\bda
{\color{red}(F\ast(G\ast H))(t)}&=&
\int_0^t F(s)\cdot \left(
{d\over ds}\int_0^s
G(\sigma) H'(\sigma)\,d\sigma
\right)\, ds
\\\rule{0mm}{8mm}&=&
\int_0^t F(s) G(s)\cdot H'(s)\,ds
\\\rule{0mm}{8mm}&=&
\int_0^t
\left(\int_0^sF(\sigma)G'(\sigma)\,d\sigma+
\int_0^s G(\sigma)F'(\sigma)\,d\sigma\right)
\cdot H'(s)\,ds
\\\rule{0mm}{8mm}&=&
{\color{red}((F\ast G)\ast H)(t)+((F\ast G)\ast H)(t)}
\eda
\vvv

Also the symmetrized product is pointwise multiplication
\bd
{\color{red}(U_1\ast U_2)+(U_2\ast U_1)=(U_1\cdot U_2)}
\;\mbox{ for }\;U_1,U_2\in {\cal AC}_{{\rm loc},0}
\ed
}%end blue
}%end of Large
\pagebreak

\begin{center}
{\Huge \bf  Chronological algebras, examples}
\end{center}
\vvv
{\Large

There are many familiar chronological subalgebras
of the chronological algebras
${\cal AC}_{{\rm loc},0}$ and
${\cal AC}_{{\rm loc},0}$,
most notably those of polynomial and of
(real, or complex) exponential functions.
\\
Typical multiplication rules are
\vvv
\vvv

{\LARGE
{\color{blue} \bd
\begin{array}{cclcccl}
 x^n\star x^m &=& {1\over n+1}x^{n+m+1}
 &&e^{nt}\star e^{mt}&=&{1\over n}e^{(n+m)t}
 \\
 \rule{0mm}{15mm}
 \\
 x^n\ast x^m &=& {m\over n+m}x^{n+m}
 &\rule{12mm}{0mm}& e^{nt}\ast
 e^{mt}&=&{m\over n+m}e^{(n+m)t}
\end{array}
\ed
}%end blue
}%end LARGE
\vvv \vvv


{\color{purple}
{\bf Exercise}:
In each case verify directly that the
right chronological identity is satisfied.
}% end purple
 For example:
 \vv

 \rule{12mm}{0mm}
 {\color{blue}
 \begin{tabular}{ccrl}
 \rule{0mm}{12mm}
 $(x^m\star x^n)\star x^k$ &$=$&
     ${\color{red}{1\over m+n+2}\cdot{1\over m+1}}$&$x^{m+n+k+2}$\\
 \raisebox{-7mm}{\rule{0mm}{19mm}}
 $(x^n\star x^m)\star x^k$ &$=$&
     ${\color{red}{1\over m+n+2}\cdot{1\over n+1}}$&$x^{m+n+k+2}$
  \\ \hline
  \rule{0mm}{12mm}
  $x^m\star (x^n \star x^k)$ &$=$&
     ${\color{red}{1\over m+1}\cdot
     {1\over n+1}}$&$x^{m+n+k+2}$\\
 \end{tabular}
 }%end blue
}%end of Large
\pagebreak

\begin{center}
{\Huge \bf  Chron. products and solving DEs}
\end{center}
\vvv
{\Large
Chronological products efficiently encode
the solution of time-varying linear
differential equations by iteration:
\vvv

The integrated form of the universal control system
 {\color{blue}}
 \bd
 \dot{S}=S\cdot \Phi,\;\;\;\Phi(0)=1
 \;\;\mbox{\color{black} with}\;\;
 \Phi=\sum_{i=1}^m u^iX_i \ed
 }%end blue
 is compactly rewritten using
 chronological products
 {\color{red}
 \bd S=1+S\ast \Phi \ed
 }%end red
 Iteration yields the explicit series expansion
 \\
\rule{1mm}{0mm}\hspace{-23mm}
\begin{minipage}{170mm}
 {\color{blue}
 \bda S&=&{\color{red}1}+(1+S\ast \Phi)\ast \Phi
   %=1+\Phi+(S\ast \Phi)\ast\Phi
\\&=&
{\color{red}1+\Phi}+((1+S\ast \Phi)\ast \Phi)\ast\Phi
\\&=&
{\color{red}1+\Phi+(\Phi\ast\Phi)}+
   (((1+S\ast \Phi)\ast \Phi)\ast\Phi)\ast\Phi
\\ &=&{\color{red}1+\Phi+(\Phi\ast\Phi)+
((\Phi\ast\Phi)\ast \Phi)}+
((((1+S\ast \Phi)\ast\Phi)\ast\Phi)\ast\Phi)\ast\Phi
\\&\vdots
\\ &=&{\color{red}1+\Phi+(\Phi\ast\Phi)+
((\Phi\ast\Phi)\ast \Phi)+
(((\Phi\ast\Phi)\ast\Phi)\ast\Phi)}\ldots
 \eda
 }%end blue
 \end{minipage}
\vvv
\vvv

{\color{purple}
{\bf Corollaries}:
Coefficients of the CF-series
and in the exp.prod.expansion:
\\
For a word $w\in W(\X)$ and a letter $a\in \X$
\bd
 {\color{red}
 \Upsilon^{wa}(t,u)=
 {\color{blue}
 \int_0^T \Upsilon^w(s,u)\cdot
 \left( \mbox{$d\over ds$}\Upsilon^a(s,u)\right)\,ds
 =}%end blue
 \left(\Upsilon^w(\cdot,u)\ast
      \Upsilon^a(\cdot,u)\right)(t)
 }%end red
 \ed
 \bd
 {\color{red}
 C^{HK}(t,u)=C^H(t,u)\ast C^K(t,u)
 }%end red
\;\;
\mbox{ if }
H,K,HK\in {\cal H}
\ed
}%end purple
}%end of Large
\pagebreak

\begin{center}
{\Huge \bf  Normal forms for nilpotent systems}
\end{center}
\vvv
{\large
Chronological products provide the most compact
way for specifying a normal form for {\em free
nilpotent control systems of rank $r$}.
The key is to index the coordinates by Hall words
$H\in {\cal H}^{(r)}\stackrel{\rm def}{=}
\{H\in {\cal H}\colon |h|\leq r\}$
(rather than by the integers):
\vvv

{\Large
{\color{red}
{\bf Normal form} for a {\em free system}
(maximally free Lie algebra)
\bd
\begin{array}{cclll}
\dot{x}_a & = & u_a & \rule{12mm}{0mm} &
    \mbox{ if }a\in \X\\
x_{HK} & = & x_H\ast x_K &&
    \mbox{ if }
    H,K,HK\in {\cal H}^{(r)}(\X)\\
\end{array}
\ed
}%end red
}%end Large
\vvv
\vvv
\vvv

{\color{blue}
{\bf Example}:
Normal from for a free nilpotent system
(of rank $r=5$) using
a typical Hall set on the alphabet $\X=\{0,1\}$
\bd
\begin{array}{cclcllrcl}
\dot{x}_0  &=& u_0 \\
\dot{x}_1  &=& u_1 \\
\dot{x}_{01} &=& x_0\cdot\dot{x}_1&=&x_0\,u_1 \\
\dot{x}_{001} &=& x_0\cdot\dot{x}_{01}&=&x_0^2\,u_1
&\mbox{ using }&\psi^{-1}(001)&=&(0(01)) \\
\dot{x}_{101} &=& x_1\cdot\dot{x}_{01}&=&x_1x_0\,u_1
&\mbox{ using }&\psi^{-1}(101)&=&(1(01)) \\
\dot{x}_{0001} &=& x_0\cdot\dot{x}_{001}&=&x_0^3\,u_1
&\mbox{ using }&\psi^{-1}(0001)&=&(0(0(01))) \\
\dot{x}_{1001} &=& x_{1}\cdot\dot{x}_{001}&=&x_1x_0^2\,u_1
&\mbox{ using }&\psi^{-1}(1001)&=&(1(0(01))) \\
\dot{x}_{1101} &=& x_{1}\cdot\dot{x}_{101}&=&x_1^2x_0\,u_1
&\mbox{ using }&\psi^{-1}(1101)&=&(1(1(01))) \\
\dot{x}_{00001} &=& x_0\cdot\dot{x}_{001}&=&x_0^4\,u_1
&\mbox{ using }&\psi^{-1}(00001)&=&(0(0(0(01)))) \\
\dot{x}_{10001} &=& x_{1}\cdot\dot{x}_{0001}&=&x_1x_0^3\,u_1
&\mbox{ using }&\psi^{-1}(10001)&=&(1(0(0(01)))) \\
\dot{x}_{11001} &=& x_{1}\cdot\dot{x}_{1001}&=&x_1^2x_0^2\,u_1
&\mbox{ using }&\psi^{-1}(11001)&=&(1(1(0(01)))) \\
\dot{x}_{01001} &=& x_{01}\cdot\dot{x}_{001}&=&x_{01}x_0^3\,u_1
&\mbox{ using }&\psi^{-1}(01001)&=&((01)(0(01))) \\
\dot{x}_{01101} &=& x_{01}\cdot\dot{x}_{101}&=&x_{01}x_1^2x_0\,u_1
&\mbox{ using }&\psi^{-1}(01101)&=&((01)(1(01)))
\end{array}
\ed
}%end blue
}%end of large
\pagebreak

\begin{center}
{\Huge \bf  Free chronological algebra}
\end{center}
 \vvv

 {\large {\color{darkgreen}
 On $A_{\kk,0}(\X)$ and
 $\hat{A}_{\kk,0}(\X)$ {\color{brown} noncommutative polynomials
 and power series with zero constant term,
 }%end brown
 define a
 {\color{brown}
 (bilinear, noncommutative, nonassociative)
 }%end brown
 product by
 $w\ast a = wa$
 {\color{brown}
 for any nonempty word
 $w\in W_0(\X)$
 and $a\in \X$,
 and
 }%end brown
 {\Large
 {\color{blue}\bd
 w\ast (z\ast a) = (w\ast z)\ast a+(z\ast w)\ast a
 {\color{brown}
 \;\;\mbox{ for }\;a\in \X,\;w,z \in W_0(\X)
 }%end brown
 \ed
 }%end blue
 }%end Large
 }%end darkgreen
 \vvv

 {\color{purple} {\bf Exercise:}
\\
With this product
${\cal C}_{\kk}(\X)\stackrel{{\rm def}}{=}
\left(A_{\kk,0}(\X),\ast\right)$ is
a chronological algebra that is {\em free}
in the usual sense: If $C$ is any chronological
algebra then any $\gamma \colon \X \mapsto C$
extends uniquely to a  chronological
algebra homomorphism
$\hat{\gamma}:{\cal C}_{\kk}(\X)\mapsto C$.
}%end purple
\vvv

 {\color{darkgreen}
 Observe: The shuffle product is (the extension
 to $A_{\kk}(\X)$ of) the symmetrization of the
 chronological product (and $1\ast 1$ cannot be
 defined meaningfully)
 {\Large
 \bd
 {\color{red}w\ast z+ z\ast w = w \;\Shu\; z}
 \;\;\mbox{ for }\;w,z \in W_0(\X)
 \ed
 }%end Large
 \vvv

 Lots of useful identities
 ({\color{brown} e.g. to hide unwanted factorials})
 \\
 For $w\in A_{\kk,0}(\X)$ define
 {\color{blue}
 $w^{\ast 1}=\lambda^1(w)=w^{\shu 1}=w$,
 }%end blue
 % $w^{\ast 2}=\lambda^2(w)=w\ast w$,
 % $w^{\shu 2}=w\Shu w$,
 and inductively for $n\geq 1$
 {\color{blue}
 \bda
 \lambda^{n+1}(w)&=&w\ast \lambda^n(w)
 \\
 w^{\ast(n+1)}&=&w^{\ast n}\ast w
 \\
 w^{\shu (n+1)}&=&w\;\Shu\;w^{\shu n}=w^{\shu n}\;\Shu\;w
 \eda
 }%end blue

 {\Large \color{red} \raisebox{9mm}{{\bf Theorem}:}
 \rule{1mm}{0mm}
 \begin{minipage}{120mm}
 \bda
 w\ast w^{\ast (n-1)}&=&(n-1)\cdot w^{\ast n}
 \\
 \lambda^n(w)&=&(n-1)!\cdot w^{\ast n}
 \\
 w^{\shu n}&=&n! \cdot w^{\ast n}
 \rule{12mm}{0mm}\left( =n\lambda^n(w) \right)
 \eda
 \end{minipage}
 }%end red
 }%end of large
 \pagebreak

\begin{center}
{\Huge \bf  Chron. products and dual PBW bases}
\end{center}
\vvv {\Large


 Every Hall-word
 $H\in %\psi(\tilde{\cal H}\setminus \X) \subseteq
 W(\X)\setminus \X$, factors uniquely in the form
 \vvv
 \vvv
 \vvv

 \rule{1mm}{0mm}\hspace{-0mm}
 {\color{blue}
 \begin{picture}(220,120)(-20,-20)
 \setlength{\unitlength}{2pt}
 \put(0,0){\line(3,2){100}}
 \put(30,0){\line(3,2){85}} \put(60,0){\line(3,2){70}}
 \put(110,0){\line(3,2){45}} \put(140,0){\line(3,2){30}}
 \put(170,0){\line(3,2){15}} \put(100,67){\line(3,-2){100}}
 \put(-8,-12){$H_1$} \put(10,-12){$\geq$} \put(24,-12){$H_2$}
 \put(47,-12){$\geq$} \put(56,-12){$H_3$} \put(78,-12){$\ldots$}
 \put(100,-12){$H_{s-2}$} \put(126,-12){$\geq$}
 \put(136,-12){$H_{s-1}$} \put(159,-12){$\geq$}
 \put(169,-12){$H_s$} \put(185,-12){\bf \color{red}$<$}
 \put(202,-12){$a$}
 \end{picture}
 }%end blue
 \vvv

 {\color{darkgreen}
 This factorization
 {\color{brown} (due to the connection with
                 Lazard factorization)}
 perfectly matches
 {\color{purple}Sussmann's variation of parameters}
 approach to obtaining the iterated integrals
 $\beta_H(T,u)$ in the exponential product expansion
 of the CF-series
 }% end darkgreen
 {\color{blue}
 \bd
 \beta_H = \;\;{1\over (\ldots)!}\;\;
           (\beta_{H_1}\ast(\beta_{H_2}\ast \ldots
           (\beta_{H_{s-1}}\ast
           (\beta_{H_s}{\color{red}\ast \beta_a}))...))
 \ed
 }% end blue

 {\color{darkgreen}
 Compare to the mix of products from different algebras
 in Reutenauer's and Melan\c{c}on's formula for the
 dual-PBW bases.
 }% end darkgreen

 In the shuffle algebra $(A({\cal X}),\;\Shu\;)$ the
 transposes of both the left and right translation by
 a letter
 {\color{blue}$\lambda_a\colon w\mapsto aw$}, and
 {\color{blue}$\varrho_a\colon w\mapsto wa$} are derivations.
 However:
 \\
 {\color{red}
      On the chronological algebra, only
      $\lambda^\dagger_a$ is a derivation,
      $\varrho_a^\dagger$ is not.
 }%end red
 {\color{blue}
 \bd
 \begin{array}{ccccl}
 \lambda^\dagger_a (w\ast z)&=&
  (\lambda^\dagger_a w)\ast z &+&
   w\ast(\lambda^\dagger_a z)\\
  {\color{red} \varrho^\dagger_a (w\ast z)}
  &{\color{red}=}&&&
  {\color{red} w\ast (\varrho^\dagger_a  z)}\\
 \end{array}\ed
 }%end blue
}%end of Large
\pagebreak

\begin{center} {\Huge \bf  Realization of free chron.
algebra}
\end{center}
\vvv
{\Large
\rule{12mm}{0mm}
\framebox{
\begin{minipage}{143mm}
{\color{brown}
Compare the standard realization of polynomial algebras:
\vvv

\begin{tabular}{cl}
${\bf k}[X_1,\ldots X_n]$ &
      polynomials w/ coeff's in ${\bf k}$
      \\
\Huge $\downarrow$\\
${\bf k}[x_1,\ldots x_n]$ &
      polynomial functions ${\bf k}^n\mapsto {\bf k}$
      \\
&$=$ the subalgebra of ${\rm Map}({\bf k}^n,{\bf k})=
     {\bf k}^{{\bf k}^n}$
     \\&
     generated by the
     projections
     \\&
     $x_k=\pi_k\colon (p_1,\ldots,p_n)\mapsto p_k$
     \end{tabular}
}%end brown
\end{minipage}
}%end framebox
\vvv

{\color{blue}
Similarly realize the free chronological algebra as a
chronological algebra of {\em time-varying scalars}.
E.g for an index set ${\cal X}$ of letters
\bd
{\cal U}={\rm AC}_{\rm loc}([0,\infty),{\bf R})
\ed
\bd
\pi_a\colon {\cal U}^{\cal X} \mapsto {\cal U},\;\;
\pi_a(\{u_b\colon b\in {\cal X}\})=u_a
\ed
\bda
{\cal IIF}({\cal X}) &\subseteq&
{\rm Map}({\cal U}^{\cal X},{\cal U})
\\&&
\mbox{ subalgebra generated by projections}
\;\;\pi_a,\;a\in {\cal X}
\eda
}%end blue

{\color{red}
{\bf Theorem}[Kawski and Sussmann]:
The map $\UUpsilon( \colon C({\cal X})\mapsto {\cal IIF}({\cal X})$
defined by $\UUpsilon( \colon a \mapsto \pi_a$
is a chronological algebra {\bf iso}morphism.
}% end{red}
\vv

{\color{brown}
Chronological algebra surjective
{\em homo}morphism is rather clear by now.
The one-to-one-ness requires a sufficiently
rich coefficient ring and some analysis
(Nagano's theorem \ldots).
}%end brown

}%end of Large
\pagebreak

\begin{center}
{\Huge \bf CF series as identity map}
\end{center}
\vvv
{\LARGE
The Chen Fliess series of iterated integral
functionals corresponds to the identity map
% on the free chronological algebra
under the chronological algebra isomorphism
$\UUpsilon$, i.e. it is {\em natural object}.
}%end LARGE
\vvv

{\LARGE
{\color{blue}
\bd
\begin{array}{ccccc}
{\rm id}_A &\cong&
\sum_w w\otimes w &
\stackrel{
\color{purple}{\rm id}_{\hat{A}}\otimes \UUpsilon
}{\longleftarrow \!\!\!\longrightarrow}&
\sum_w w\otimes \UUpsilon(w)
\\
&& \mbox{\color{red} {\Huge$\parallel$}}
&& \mbox{\color{red} {\Huge$\parallel$}}
\\
&& \mbox{\color{red} Sch\"utzenberger,}
&& \mbox{\color{red} Sussmann}
\\
&& \mbox{\color{red} Melan\c{c}on \& R.}
&&
\\
&& \mbox{\color{brown} Combinatorics}
&& \mbox{\color{brown} Diff Equns proof}
\\
&& \mbox{\color{red} {\Huge$\parallel$}}
&& \mbox{\color{red} {\Huge$\parallel$}}
\\
&& \stackrel{\leftarrow}{\prod_H}
    \exp\left([H]\otimes S_H\right)&
\stackrel{
\color{purple}{\rm id}_{\hat{A}}\otimes \UUpsilon
}{\longleftarrow \!\!\!\longrightarrow}&
\stackrel{\leftarrow}{\prod_H}
\exp\left([H]\otimes \beta_H\right)
\end{array}
\ed
}%end blue
\vvv
\vvv

{\color{blue}
\bd
\begin{array}{ccccl}
{\rm Hom}(A,A)&\cong&
\hat{A}\tilde\otimes A&
\stackrel{
\color{purple}{\rm id}_{\hat{A}}\otimes \UUpsilon
}{\longleftarrow \!\!\!\longrightarrow}&
\hat{A}\tilde\otimes A \mbox{\em IIF}
\\
& & \mbox{free chron}&\mbox{\color{red}chron.algebra}&
\mbox{iterated integral}
\\
& & \mbox{algebra}&\mbox{\color{red}isomorphism}&
\mbox{functionals}
\end{array}
\ed
}%end blue
}%end LARGE
\pagebreak

\begin{center}
{\Huge \bf  Koszul duality and Leibniz operad}
\end{center}
\vvv
{\Large

{\color{blue}
{\em ``Dual''} to the chronological {\em ``operad''}
is the Leibniz {\em ``operad''}.
\\
{\color{brown} ({\em ``pre-Lie algebra structure'', or
``noncommutative Lie algebra''})
}%end brown
\\
{\color{brown} (this is originally called {\em chronological''} by
Gamkrelidze and Agrachev)
}%end brown
characterized by the 3-term Leibniz-identity

\bda \rule{27mm}{0mm}[x,[y,z]]&=&[[x,y],z]+[y,[x,z]]\\
\Leftrightarrow\rule{23mm}{0mm} [[x,y],z]&=&[[x,[y,z]]-[y,[x,z]]\\
\Leftrightarrow\rule{32mm}{0mm} L_{[x,y]}&=&[L_x,L_y] \eda
}%end blue
\vvv
\vvv

{\color{red} {\bf Puzzle}:
 The anti-commutativity of the
Lie-brackets appears so natural in control -- yet algebraically it
appears to be only a coincidence. \\ What in control corresponds
geometrically to the chronological algebra -- it must be {\em
connections}; but they are not much used in controllability and
optimality -- should they? What do they add?
}%end red
\vvv
\vvv
\vvv

{\color{brown}
For details on {\em Leibniz algebras}, and their
role in cyclic homology,
see numerous articles by Loday.
}%end brown
\vvv

{\color{brown}
For details on {\em Koszul duality of operads}
see Ginzburg and Kapranov, Duke. J. Math, 1997.
}%end brown
\vvv
\vvv

}%end of Large
\pagebreak


\begin{thebibliography}{99}


\bibitem{mkhjs}
   M.~Kawski and H.~J.~Sussmann
   {\em Noncommutative power series and formal Lie-algebraic techniques
        in nonlinear control theory},
   in: Operators, Systems, and Linear Algebra,
   U.~Helmke, D.~Pr\"atzel-Wolters and E.~Zerz, eds.,
   Teubner (1997), pp.~111--128.

\bibitem{moscow99}
   M.~Kawski,
   {\em Chronological algebras in nonlinear control},
   to appear in Proc. Conf. in honor of Pontryagin's
   90's birthday, Moscow, 1998.
\end{thebibliography}
\end{document}