\documentclass[12pt,twoside]{amsart}

\usepackage{amssymb}
\usepackage{pst-node,pstricks,multido,pst-plot,pst-text,pst-3d}%
\usepackage{graphicx}
\usepackage{amsfonts}
%\usepackage{ams}
\newtheorem{example}{Example}[section]
\newtheorem{note}[example]{Note}
\newtheorem{theorem}[example]{Theorem}
\newtheorem{exercise}{Exercise}[section]
\newtheorem{corollary}[example]{Corollary}
\newtheorem{conjecture}[example]{Conjecture}
\newtheorem{definition}[example]{Definition}
\newtheorem{proposition}[example]{Proposition}
\newtheorem{algorithm}[example]{Algorithm}
\newtheorem{lemma}[example]{Lemma}

\def\Proof{\noindent \it Proof -- \rm}
\def\Prod{\rm prod}
%\def\qed{\hspace{3.5mm} \hfill \vbox{\hrule height 3pt depth 2 pt width 2mm}
%\bigskip}



\def\bo{{\small \,\Box}}
\def\DD{{\sf D}}
\def\EE{{\sf E}}
\def\<{\langle}
\def\>{\rangle}
\def\R{{\mathbb R}}
\def\Q{{\mathbb Q}}
\def\C{{\mathbb C}}
\def\Z{{\mathbb Z}}
\def\N{{\mathbb N}}
\def\M{{\mathbb M}}
\def\F{{\mathbb F}}
\def\tr{{\rm tr\,}}
\def\gl{{\mathfrak gl}}
\def\glchap{\widehat\gl}
\def\diag{{\rm diag\,}}
\def\Hf{{\rm Hf\,}}
\def\SG{{\mathfrak S}}
\def\H{{\sf H}}
\def\t{{\bf t}}
\def\A{{\sf A}}
\def\aa{{\sf a}}
\def\ch{{\rm ch\,}}
\def\CC{{\cal C}}
\def\Card{\operatorname{Card}}
\def\cqfd{$\ \ \ \blacksquare$\\ \\}
\def\Alph{\mbox{\rm Alph}}
\def\alph{\mbox{\rm Alph}}
\font\twelvegoth=eufb10 at 12pt \font\tengoth=eufb10
\font\sevengoth=eufb7 \font\fivegoth=eufb5

\newfam\gothfam
\textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
\scriptscriptfont\gothfam=\fivegoth
\def\goth{\fam\gothfam\tengoth}

\def\shuff#1#2{\mathbin{
\hbox{\vbox{ \hbox{\vrule \hskip#2 \vrule height#1 width 0pt
}%
\hrule}%
\vbox{ \hbox{\vrule \hskip#2 \vrule height#1 width 0pt
\vrule }%
\hrule}%
}}}

\def\shuf{{\mathchoice{\shuff{7pt}{3.5pt}}%
{\shuff{6pt}{3pt}}%
{\shuff{4pt}{2pt}}%
{\shuff{3pt}{1.5pt}}}}%
\def\shuffle{\,\shuf\,}


\def\ashuff#1#2#3{
\kern 1pt \vrule height#1 \overline{\vrule height#3 width 0pt
\hskip#2} \rule{.3pt}{#1}\overline{\vrule height#3 width 0pt
\hskip#2} \rule{.3pt}{#1} \kern 1pt }

\def\ashuf{{\mathchoice{\ashuff{7pt}{3.5pt}{6pt}}%
{\ashuff{6pt}{3pt}{5pt}}%
{\ashuff{4pt}{2pt}{3.5pt}}%
{\ashuff{3pt}{1.5pt}{2.5pt}}}}%
\def\ashuffle{\,\ashuf\,}


\newcommand{\Pfa}{\displaystyle\mathop{{\rm Pf}}}

\newcommand{\Haff}{\displaystyle\mathop{{\rm Hf}}}

\def\ov#1{\overline{#1}}

\title{Transitive Hall sets}

\author{G\'erard {\sc Duchamp}, Marianne {\sc Flouret} and Jean-Gabriel
{\sc Luque}}

\date{}


\dedicatory{Dedicated to Xavier Viennot}
\begin{document}
 \begin{abstract}
We give the definition of Lazard and Hall sets in the context of
transitive factorizations of free monoids. The equivalence of the
two properties is proved. This allows to build new effective bases
of free partially commutative Lie algebras. The commutation graphs
for which such sets exist are completely characterized and we
explicit, in this context, the classical PBW rewriting process.
\end{abstract}
 \maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54 \rms (2006), Article~B54k\hfill}
\def\thepage{}
%
%

\section{Introduction}
Since the pioneering works of Sch\"utzenberger \cite{onfact,Sc} and
Viennot \cite{Vi2} it has been believed (and hoped) that the correct
dictionary between (discrete) monoids and (discrete) Lie algebras
could be obtained through the correspondence between multiplicative
factorizations of monoids and additive factorizations of Lie algebras.
%
%******%
%
%
%
%The correspondence with Lie algebras  is not so clear  for monoids
%as it is  in the case of groups (Lie groups and, after the work of
%Magnus \cite{Cha} and Lazard \cite{Laz} combinatorial groups). In
%fact, the first connection between the two realms was done by means
%the notion of factorization \cite{Vi2}.

On the other hand, one observes that elimination processes in
discrete Lie algebras give free factors as for the
Knizhnik-Zamolodchikov Lie algebra (see \cite{C1} eq. 4.9 and \cite{K1}) and
partially commutative Lie algebras through a scheme ($LA$ = Lie
Algebra)
\begin{center}
$LA_1$ in the class C=Free $LA \oplus LA_2$ in the class C
\end{center}
with increasing degree indices so that the process could be applied
to obtain bases (and, indeed in the case of Free Lie algebras,
all homogeneous ones, including Hall). This observation has led to
believe that the free factors could be the right way to generalize
Hall processes.


One must mention here that the contribution of Viennot himself
to the subject is twofold. First to the factorizations of monoids,
the subject of Viennot's ``Th\`ese d'\'Etat'' \cite{Vi1}. In this impressive
memoir, Viennot proposes a classification of the factorizations of the free
monoid and constructs a very interesting category, the {\it bascules}
(a reconstrution of the effect of the factorization ``from outside''), endowed
with two functors $L$ and $K\langle?\rangle$, respectively toward the category of $K$-Lie algebras
and to the category of $K$-associative algebras with unit. The second, and not least,
contribution is the model of heaps \cite{Vi3} which provides a geometric insight
for the partially commutative monoid \cite{CF}. This model allows also to introduce a thickness
parameter for the pieces \cite{GM,MV}.

In this paper, we want to show that the framework of factorization with free factors
can be broaden, following the track of the ``transitive factorizations''. We
show that the category of partially commutative structures
\cite{DK1,DK2,DL} can be used for getting a correct generalization
of Hall rewriting techniques as they appear in the works of
Reutenauer and M\'elan\c con \cite{Re,Me1,Me2,Me3}. Our construction here,
although it works for a wider category of algebras is valid for only some types of graphs.

The insight of heaps, by means of the ``pyramids'' which are the exact counterpart of
the elements of the Lazard code obtained by eliminating some variables (letters of the alphabet)
has been worked out by Lalonde and Krob. They can be found in \cite{Lal,Lal1,Lal2}.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL G. DUCHAMP, M. FLOURET AND J.-G. LUQUE}{\SMALL
TRANSITIVE HALL SETS}
%
%

The structure of the paper is the following. In section
(\ref{fact}), we give a partially commutative version of
Sch\"utzenberger 's factorization theorem. We introduce in Section
(\ref{TLS}) the notions of transitive Lazard and transitive Hall
sets in the free algebras of trees. Transitive Lazard sets are
defined by means of iterations of transitive bisections \cite{DL}.
Transitive Hall sets classically use a description of the total order
of the factorization which, here, must be compatible with the
commutations.  We prove that the two notions coincide and allow the
construction of bases of the free partially commutative Lie algebra
$L(A,\theta)$ as well as a natural Poincar\'e-Birkhoff-Witt
rewriting process (PBW).

\section{Factorizations of a trace monoid\label{fact}}

 Let $A$ be an alphabet and $\theta\in A\times A-\{(a,a)|a\in A\}$
be a symmetric relation. We will denote by $\M(A,\theta)$ a trace
monoid (or a free partially commutative monoid) over the alphabet
$A$ and whose commutations are defined by $ab=ba$ when
$(a,b)\in\theta$.\\ The only way to get the equality
\begin{equation}
\underline{\M(A,\theta)}=\underline{a^*}.\underline{\M(X,\theta_X)}
\end{equation}
where  $X$ is a subset of $\M(A,\theta)$, $a^*$ is the free monoid
of the alphabet $\{a\}$ and $\underline E=\sum_{e\in E}e$, is to
impose for each pair of letters $(z_1,z_2)\in\theta\cap(A-a)^2$ the
commutation $(z_1,a)\in\theta$ or $(z_2,a)\in\theta$. It is a direct
consequence of the transitive factorization theorem (see Section
(\ref{TypeH}) \cite{DL}).

More generally, an ordered family $(M_i)_{i\in I}$ of submonoids of $M$
is said to be a factorization if the product mapping $\coprod_{i\in
I}M_i\rightarrow M$ is one to one. For $|I|=2$, one gets the notion
of a bisection related to the flip-flop\footnote{In french
"bascule".} Lie-algebra by Viennot \cite{Vi2}. At the other end, when
all the $M_i$ have a single generator, one obtains a complete
factorization whose generating series is equal to the Hilbert series
of the Free Lie algebra. It has been shown in \cite{DK1} that this
property stills holds in the case of partial commutations and the link
between the Lyndon basis and Lazard elimination in this context has
been elucidated \cite{KL}. In this paper, we use this property to
define transitive Lazard sets for a family of trace monoids. Let us
first show some properties about conjugacy.

\subsection{Roots of conjugacy classes}
Let $m\in \M(A,\theta)$. It is shown  in \cite{DK3} (see also
\cite{Dub}) that the equation $u=t^p$ ($p\geq 1$) has at most one
solution. When it exists, this solution will be denoted by $^p\sqrt
u$. In the same paper \cite{DK3}, it is shown that if $g$, $r$, and
$t$ are three traces such that $g=r^q=t^p$ with $q$, $p\in\N$ then
there exists a trace $g'$ and $m\in {\rm lcm}(p,q)\N$ such that
$g=g'^m$. Hence, one defines the {\bf  root} $\sqrt g$ of a trace
$g$ as the smallest trace $g'$ satisfying $g=g'^m$ (the integer $m$
will be called the {\bf exponent} of $g$, we denote $m={\rm
ex}(g)$).

\begin{example}
Let us consider the commutation graph
\[(A,\theta)=a-c-b\]
we have $\sqrt{babcac}=bac$ and ${\rm ex}(babcac)=2$
\end{example}
We recall here the definition of conjugacy due to Duboc and
Choffrut  \cite{CH}. Two traces $t$ and $t'$ are said conjugate if
there exists a trace $u$ such that $tu=ut'$. Conjugacy is an
equivalence relation which, in turn, is no more that the
restriction to $\M(A,\theta)$ of the  conjugacy relation for the
group $\F(A,\theta)$. Exponent and  root are invariant under
conjugacy in the following sense.

\begin{proposition}\label{conjug}
Let $C$ be a conjugacy class,  $f\in C$, $g\in\M(A,\theta)$ and
$p\in\N$ be such that $f=g^p$. For each $f'\in C$, there exists
$g'\in\M(A,\theta)$ such that $f'=g'^p$. Furthermore $g$ and $g'$
are conjugate.
\end{proposition}

As a consequence of Proposition (\ref{conjug}) the root $\sqrt C$ of a
conjugacy class $C$ is uniquely defined as the set $\sqrt
C=\{\sqrt g\}_{g\in C}$.

\subsection{Sch\"utzenberger's factorization theorem for traces}
\label{schutz}

%Let $(M_i)_{i\in J}$ be a family of monoids. The restricted
%product $\coprod_{i\in J} M_i$ is the submonoid of $\prod_{i\in J}
%M_i$ of the families with finite support (all but a finite number
%of indices are $1_{M_i}$). Now, if the $(M_i)_{i\in J}$ are
%submonoids of a given monoid $M$ and if $J$ is totally ordered,
%the product $\Prod : M\times M\rightarrow M$ extends to an arrow
%$\Prod : \coprod_{i\in J} M_i\rightarrow M$ by means of the
%ordered product.\\ A factorization of a monoid $\M$ is an ordered
%family of submonoids $(M_i)_{i\in J}$ such that $\Prod :
%\coprod_{i\in J} M_i\rightarrow M$ is one to one.
 It is classical
that a submonoid $\M$ of $\M(A,\theta)$ has a unique minimal
generating set. Hence, a factorization will be characterized by
the family of the generating sets of its components and will be
denoted by $\F=(Y_i)_{i\in I}$ instead of $\F=(\M_i)_{i\in I}$ if
$Y_i=\M_i-\M_i^2$.

\medskip
The existence of the root of conjugacy classes allows us to extend
Sch\"utzen\-berger's factorization theorem \cite{onfact} to trace
monoids.
\begin{theorem}
Let $\F=(Y_i)_{i\in J}$ be an ordered family of noncommutative
subsets (i.e., for each i and each pair $(x,y)\in Y_i^2$, $x\neq y$
implies $xy\neq yx$) of $\M(A,\theta)$ and $\langle Y_i\rangle$ the
submonoid generated by $Y_i$.

\noindent We consider the following assertions:
\begin{enumerate}
\item\label{it1} The mapping {\Prod}  is into.
\item\label{it2} The mapping {\Prod  } is onto.
\item\label{it3} Each monoid  $\langle Y_i\rangle$ is free.
For each conjugacy class $C$ in $\M(A,\theta)$, if $C$ is connected
(i.e., if the restriction of the noncommutation graph to the
alphabet $\Alph(C)=\{a\in A|uav\in C\mbox{ with
}u,v\in\M(A,\theta)\}$ is a connected graph) then there exists a unique
$i\in J$ such that $C\cap\langle Y_i\rangle\neq\emptyset$ and in
this case $C\cap\langle Y_i\rangle$ is a conjugacy class of
 $\langle Y_i\rangle$. If $C$
is not connected, for each $i\in J$, $C\cap\langle
Y_i\rangle=\emptyset$.
\end{enumerate}
Two of the previous assertions imply the third.
\end{theorem}
\begin{proof} The structure of the proof is, in the broad outline, the
same as in \cite{onfact}. Nevertheless, due to the specificity
of the partially commutative context, numerous technical
arguments are more sophisticated.

Without restriction, one supposes that each $Y_i$ is a
minimal generating set of $\langle Y_i\rangle$. 

We prove
\ref{it1}) and \ref{it2}) imply \ref{it3}) by
examining the series
\begin{equation}\label{log}
\log\underline{\M(A,\theta)}-\sum\log\underline{\langle
Y_i\rangle}.
\end{equation}
Observing that \ref{it1}) and \ref{it2}) force the set $\F$ to be
a factorization, it is easy to show that (\ref{log}) is a Lie
series whose valuation is strictly greater than 1. Hence, if $C$
is a conjugacy class of $\M(A,\theta)$, one has
\begin{equation}\label{lyndon}
\left(\underline C,\sum\log\underline{\langle
Y_i\rangle}\right)=\left(\underline C,\sum_{l\in Ly(A,\theta)
}\log{\frac 1{1-l}}\right)
\end{equation}
where $Ly(A,\theta)$ denotes the set of Lyndon traces (which is a
complete factorization of $\M(A,\theta)$ for the standard order
\cite{Lal1,Lal2,Lal}) and $(\ ,\ )$ is the  scalar product  for
which the monomials are orthonormal. Lalonde has proved \cite{Lal1}
that $Ly(A,\theta)$
is a representative set of the strongly connected conjugacy classes.

If $C$ is not connected (\ref{lyndon}) implies
\[
\left(\underline
C,\sum_i\sum_m\frac1m\underline{Y_i^m}\right)=\left(\underline
C,\sum_l\sum_m\frac1ml^m\right)=0\nonumber
\]
and, the series  $\sum_i\sum_m\frac1m\underline{Y_i^m}$ being
positive, one gets $\langle Y_i\rangle\cap C=\emptyset$.

 If $C$
is strongly primitive (i.e., $C$ is connected and $\sqrt
C=C$), equality (\ref{lyndon}) implies
\[
\left(\underline
C,\sum_i\sum_m\frac1m\underline{Y_i^m}\right)=1.\nonumber
\]
Let $i$ and $m$ be such that $C\cap Y_i^m\neq\emptyset$. The
strong primitivity of $\underline C$ implies
\[
\left(\underline C,\sum_i\sum_m\frac1m\underline{Y_i^m}\right)\geq
1\nonumber
\]
and the uniqueness of $Y_i$ follows. Furthermore, by $\Card C\cap
Y_i^m=m$, we show that $C\cap Y_i^m$ is a conjugacy class in
$\langle Y_i\rangle$.

 Now, suppose  that $C$ is connected but
not primitive and let $p>1$ such that $C=\{g^p/g\in\sqrt C\}$. Let
$Y_i$ such that $\sqrt C\cap\langle Y_i\rangle\neq\emptyset$ is a
conjugacy class in $\langle Y_i\rangle$ (from the previous case,
$Y_i$ exists and is unique). One has $C\cap \langle
Y_i\rangle=C_j$ where each $C_j$ is a conjugacy class in $\langle
Y_i\rangle$. But for each $j$,
\[
\left(\underline{C_j},\sum_m\frac1m\underline{Y_i}^m\right)=\frac1p\nonumber
\]
and from (\ref{lyndon}) one has
\[
\left(\underline
C,\sum_m\frac1m\underline{Y_i}^m\right)=\frac1p.\nonumber
\]
The uniqueness of  $Y_i$ and $C_j$ follows.

\medskip
In order to prove that 1) (resp. 2)) and 3) imply 2) (resp. 1)),
one considers a conjugacy class $C$ of $\M(A,\theta)$. We need to
examine two cases. If $C$ is connected, assertion 3) implies 
that there
exists a unique $i$ and a unique conjugacy class $C_i$ of the monoid
$\langle Y_i\rangle$ verifying $C_i=C\cap\langle Y_i\rangle$. Let
$p$ be the exponent of $C$ and $p_i$ the exponent of $C_i$ in
$\langle Y_i\rangle$. The monoid $\langle Y_i\rangle$ being a
submonoid of $\M(A,\theta)$, one has immediately $p\geq p_i$. On the
other hand, let $j$ such that $\sqrt C\cap\langle Y_j\rangle=C_j\neq
0$ where $C_j$ is a conjugacy class of the monoid $\langle
Y_j\rangle$. Hence, for each $w\in C_j$, $w^p\in C$. This implies
$C\cap \langle Y_j\rangle\neq 0$ and, by assertion 3), $i=j$. It
follows $p\leq p_i$ and then $p=p_i$.

Now, each $\langle Y_j\rangle$ being free with generator $Y_j$,
assertion 3) gives
\[
\left(\underline C,\sum_{j\in J}\sum_{m\geq
1}\frac1m\underline{Y_j^m}\right)=\left(\underline{C_i},\sum_{m\geq
1}\frac1m\underline{Y_i^m}\right)=\frac1{p_i}=\frac1p.
\]
But, according to Lalonde \cite{Lal1}, one has
\[
\left(\underline C,\log\M(A,\theta)\right)=\left(\underline
C,\sum_{l\in Ly(A,\theta)}\sum_{m}\frac1ml^m\right)=\frac 1p.
\]
Hence
\begin{equation}\label{sum2log1}
\left(\underline C,\sum_{j\in J}\sum_{m\geq
1}\frac1m\underline{Y_j^m}\right)=\left(\underline
C,\log\M(A,\theta)\right).
\end{equation}
Now, if $C$ is not connected, by assertion 3), one has again
\begin{equation}\label{sum2log2}
\left(\underline C,\sum_{j\in J}\sum_{m\geq
1}\frac1m\underline{Y_j^m}\right)=0=\left(\underline
C,\log\M(A,\theta)\right).
\end{equation}
Let $\phi$ be the natural morphism from $\M(A,\theta)$ in the totaly
commutative monoid $\M_A=\M(A,A\times A-\Delta)\sim \N^A$. For each
$x\in \M_A$, the set $\phi^{-1}(x)$ is an union of conjugacy classes
and by (\ref{sum2log1}) and  (\ref{sum2log2}) one obtains
\begin{equation}\label{phi2log}
\left(\underline{\phi^{-1}(x)},\log(\M(A,\theta)\right)=\left(\underline{\phi^{-1}(x)},\sum_{j\in
J}\sum_{m\geq 1}\frac1m\underline{Y_j^m}\right).
\end{equation}
The morphism $\phi$ can be extend to a unique morphism of algebra
from the algebra of partially commutative formal series
$\Q\langle\langle A,\theta\rangle\rangle$ onto the algebra
commutative series $\Q[[A]]$, by
$\phi(S)=\displaystyle\sum_x\left(\underline{\phi^{-1}(x)},S\right)x$.
From (\ref{phi2log}), one obtains
\[
\phi\left(\log(\underline{\M(A,\theta)})\right)=\phi\left(\sum_{j\in
J}\sum_{m\geq 1}\frac1m\underline{Y_j^m}\right).  \nonumber
\]
The continuity of $\phi$ implies
\[
\log\left(\phi(\underline{\M(A,\theta)})\right)=\log\left(\prod_{i\in
J}\phi(\underline{\langle Y_j\rangle})\right). \nonumber \] and
\begin{equation}\label{phiprod}
\phi(\underline{\M(A,\theta)})=\prod_{i\in J}\phi(\underline{\langle
Y_j\rangle}).
\end{equation}
By Assertion 1) or 2), there exists a series $S\in\Q_+\langle\langle
A,\theta\rangle\rangle$ verifying
\begin{equation}\label{pmS}
\underline{\M(A,\theta)}=\prod_{i\in J}\phi(\underline{\langle
Y_j\rangle})\pm S
\end{equation}
Applying $\phi$ to (\ref{pmS}) and comparing with (\ref{phiprod}),
one proves that $\phi(S)$  is zero. The positivity of the
coefficient of $S$ implies $S=0$ and our result.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 Denote by ${\rm Cont}(\F)=\bigcup_{i\in J}Y_i$ the contents of the
  factorization $\F=(Y_i)_{i\in I}$. The following result
   is an extension of a classical result
due to Sch\"utzenberger \cite{onfact}.
\begin{corollary}
Let $\F$ be a complete factorization of $\M(A,\theta)$ (i.e., each
$Y_i$ is a singleton). Then for each conjugacy class $C$ we have
\[{\rm Card}(C\cap{\rm Cont}(\F))=\left\{\begin{array}{ll}1&\mbox{ if
} C \mbox{ is strongly connected }\\ &\mbox{(i.e., } C \mbox{ is
connected and } \sqrt C=C),\\ 0& otherwise.
\end{array}\right.\]
\end{corollary}
Hence,  complete factorizations of $\M(A,\theta)$ receive the same
combinatorics than in the free case. In particular, one recovers
that the generating series of a complete factorization is equal to
the Hilbert series of the free partially commutative Lie algebra.
\section{Transitive Lazard sets\label{TLS}}
\subsection{Complete elimination strings and transitive Lazard sets}

Let ${\mathcal M}(2,A)$ be the free magma on $A$ whose product will be
denoted by $(.,.)$ (i.e., the set of binary trees  with leaves in
$A$ endowed with the natural non associative product). The canonical
morphism ${\mathcal M}(2,A)\rightarrow \M(A,\theta)$ which is identical
on $A$ will be called the foliage morphism and denoted by $f$ as in
\cite{Re}. Observe that $\theta_\M=\{(w,w')|ww'=w'w\mbox{ and
}\Alph(w)\cap\Alph(w')=\emptyset\}$ is a commutation relation on
$\M(A,\theta)$ (\cite{DL}).

We consider  a commutation alphabet $(A,\theta)$ and some graphs
whose vertices belong to ${\mathcal M}(2,A)$ and such that  $(t_1,t_2)$
is an edge if and only if $(f(t_1), f(t_2))\in \theta_\M$.

 Let
$G=(V,E)$ be such a graph, we call an {\bf Elimination String} ({\bf
ES})  in $G$ a n-uple of vertices $(a_1,\cdots, a_n)$ such that for
each $i\in[1,n ]$ and $v_1,v_2\in V-\{a_1,\cdots,a_i\}$
\begin{equation}
(v_1,v_2)\in E\Rightarrow (v_1,a_i)\in E\mbox{ or } (v_2,a_i)\in E
\end{equation}
The vertex $a_1$ will be called the {\bf starting point} of the
{\bf ES}.

An {\bf ES} $(a_1,\cdots,a_n)$ will be called {\bf complete} ({\bf
CES} in the sequel) if $V=\{a_1,\cdots, a_n\}$. A graph admitting
a {\bf CES} will be called {\bf type-H graph}.
We will prove, in the last section, that when the commutation relation
is a type-H graph, we can construct analogues of Hall sets for trace monoids.

\medskip
In the sequel, we will denote by ${\mathcal M}(2,A)^{\leq n}$ the set of
trees with fewer than $n$ leaves.
\begin{example}
\begin{enumerate}
\item Let us consider the following graph
\[(A,\theta)=\begin{array}{ccccc}
a&-&d&-&e\\ |&&|&&\\ b&-&c&&
\end{array}\]
the family  $(a,d,b,c,e)$ is a {\bf CES} of $(A,\theta)$ and then
it is a type H graph.
\item The graph
\[
(A,\theta)=\begin{array}{ccc} a&-&b\\ c&-&d
\end{array}
\]
is not a type-H graph.
\end{enumerate}
\end{example}

Type-H graphs admits a nicer  graph-theoretic characterization.

\begin{proposition}
A graph is a type-H graph if and only if each of its
induced subgraphs%
\footnote{An induced subgraph $G'=(V',E')$ of a graph $G=(V,E)$ is a
graph such that $V'\subset V$ and $E'=E\cap (V'\times V').$}
contains at most one connected component of with two vertices.
\end{proposition}
\begin{proof} Let $G=(V,E)$ such that each of its (induced)
subgraphs contains at
most one  connected component with two vertices. We prove by
induction on the cardinality of $V$ that $G$ admits a {\bf CES}. If
$\Card(V)=1$, the result is straightforward. Suppose now
$\Card(V)>1$. Our strategy consists in proving the existence of a
starting point of the {\bf ES} in $G$. Suppose that such a vertex does
not exist: for each vertex $a$, there exist $b,c\neq a$ such that
$(b,c)\in E$ and $(a,b),(a,c)\not\in E$. Let $a,b,c$ such vertices.
There exists a pair $(d,e)$ verifying $d,e\neq b$, $(d,e)\in E$ and
$(d,b),(b,d)\not\in E$. Hence, the subgraph generated by the
vertices $\{b,c,d,e\}$ is the union of connected components with two
vertices. This contradicts our hypothesis on $G$ and proves that there
exists a vertex $a\in V$, such that for each $(b,c)\in E$, $(b,a)\in
E$ pr $(c,a)\in E$. Now, the subgraph of $G$ generated by
$V\setminus\{a\}$ is such that each of its subgraph contains at most
one connected component with two vertices. Hence, by induction,
it has a {\bf CES}, $s=(a_1,\dots,a_n)$. It is easy to see that the
sequence $(a_0=a,a_1,\dots,a_n)$ is a {\bf CES} of $G$. This proves
that $G$ is a type-H graph.

Conversely, let $G$ be a type-$H$ graph and $s=(a_1,\dots,a_n)$ be a
{\bf CES} of $G$. Suppose that there exists a subgraph $G'$ of $G$ with
two connected components $G'_1=(V'_1,E'_1)$, $G'_2=(V'_2,E'_2)$ with
at least two vertices. Let $(a_i,a_j)\in E'_1\subset E$ and
$(a_k,a_l)\in E'_2\subset E$. The fact that $(a_i,a_k), (a_i,a_l),
(a_j,a_k), (a_j,a_l)\not\in E$ implies that $s$ is not a {\bf
CES}.\end{proof}

According to this characterization, the type-H graphs are rare.
Nevertheless, we will prove that it is a sufficient and necessary
condition for producing complete factorizations using a Lazard
elimination process which preserves the property of "being a trace
monoid" for every factor.
\subsection{Transitive Lazard sets}
Let $v$ be a vertex of $G$, the {\bf H-star} of $G$ for $v$ of rank
$n>0$ is the graph $G_n^{*v}=(V_n^{*v},E_n^{*v})$ defined by
\begin{equation}
\begin{cases}
V_n^{*v}=(V\cap{\mathcal M}(2,A)^{\leq n}-v)\\
\kern4cm\cup \{(v'v^m)\in{\mathcal
M}(2,A)^{\leq n}|m>0, (v',v)\not\in E\},\\ 
E_n^{*v}=\{(v_1,v_2)\in
(V_n^*)^2|(f(v_1),f(v_2))\in\theta_\M\}.
\end{cases}
\end{equation}
\begin{example}
 For the following graph
\[(A,\theta)=a-b-c-d\]
then
\[(A^{*c}_4,\theta_4^{*c})=
\begin{array}{ccccccc}
&&ac&&\quad&\\ &&|&&&\\ a&-&b&-((a,c),c)&d\\ &&|&&&\\
&&(((a,c),c),c)&&&
\end{array}\]
\end{example}
\begin{proposition}\label{typeH}
Let $G$ be a type-H graph and $a_1$ be the starting point of a {\tt
CES} then $G_n^{*a_1}$ is a type-H graph.
\end{proposition}
\begin{proof} Let $\lambda=(a_1,\cdots, a_m)$ be a {\bf CES} of $G$.
We construct a list $\Lambda$ of vertices of  $G_n^{*a_1}=(V^*,E^*)$
removing $a_1$ from $\lambda$ and substituting each $a_i$ such that
$(a_i,a_1)\not\in E$ by the sequence
$$(a_i,a_1^{m-1}),\dots,(a_i,a_1),a_i.$$ Set
$\Lambda=(a'_1,\cdots,a'_M)$ and suppose that $\Lambda$ is not a
{\bf CES}, then there exists $\alpha<\beta<\gamma$ such that
$(a'_\beta,a'_\gamma)\in E^{*}$, $(a'_\alpha,a'_\beta)\not\in E^*$
and $(a'_\alpha,a'_\gamma)\not\in E^*$. If $a'_\alpha=(a_i,a_1^p)$,
$a'_\beta=(a_j,a_1^q)$ and $a'_\gamma=(a_k,a_1^r)$, then  the
construction implies $i\leq j<k$ and $p=0$ or $q=0$. If $i=j$ then
$p\neq 0$ which gives $(a_i,a_1)\not\in E$ and $r=0$. Hence,
$(a_1,a_k)\not\in E$ and $q=0$. This implies that $(a_i,a_k)\in E$,
$(a_1,a_i)\not\in E$ and $(a_1,a_k)\not\in E$ and contradicts the
fact that $\lambda$ is a {\bf CES}. If $i< j$, suppose that $r=0$
(the case $q=0$ is symmetric), we need to examine several cases
\begin{enumerate}
\item If $p=0$, then $q\neq 0$ (otherwise $(a_i,a_j),
(a_i,a_k)\not\in E$ and  $(a_j,a_k)\in E$, which contradicts
 the fact that
$\lambda$ is a {\bf CES}). But, as $(a_k,a_i)\not\in E$,
$(a_j,a_k)\in E$ and $\lambda$ being a {\bf CES}, one has
$(a_i,a_j)\in E$ and hence $(a_1,a_i)\not\in E$. Finally
$(a_1,a_j)\not\in E$, which contradicts the fact that $\lambda$ is a
{\bf CES}.
\item If $p\neq 0$ and $q=0$, then, as $\lambda$ is a {\bf CES},
either $(a_i,a_j)\in E$, either $(a_i,a_k)\in E$. Suppose that
$(a_i,a_j)\in E$ (the other case is symmetric), one has
$(a_1,a_j)\in E$ (otherwise $(a'_\alpha,a'_\beta)\in E^*$). But,
$\lambda$ being a {\bf CES}, one gets $(a_1,a_k)\in E$ and by
$(a'_\alpha,a'_\gamma)\not\in E^*$ one obtains $(a_i,a_k)\not\in
E$. Finally $(a_1,a_j), (a_1,a_i)\not\in E$ and $(a_i,a_j)\in E$
contradicts the fact that $\lambda$ is a {\bf CES}.
\item If $p, q\neq 0$ then, as $(a'_\gamma,a'_\beta)\in E^*$, one
as $(a_1,a_k)\in E$ and by $(a'_\alpha,a'_\gamma)\not\in E^*$, one
obtains $(a_i,a_k)\not\in E$. The sequence $\lambda$ being a {\bf
CES}, $(a_i,a_j)\in E$.  Hence $(a_1,a_j), (a_1,a_i)\not\in E$ and
$(a_i,a_j)\in E$ contradicts the fact that $\lambda$ is a {\bf CES}.
\end{enumerate}
This proves that $\Lambda$ is a {\bf CES}.
 \end{proof}
The definition of a transitive Lazard set follows:
\begin{definition}
 Let $G=(A,\theta)$ be a
commutation alphabet considered as a graph and $L\subset{\mathcal
M}(2,A)$, we will say that $L$ is a {\bf transitive Lazard set} if
and only if for each $n> 0$, $L\cap{\mathcal M}(2,A)^{\leq
n}=\{s_1,\cdots, s_k\}$ such that there exist $k+1$ graphs
$G_1=(A_1,\theta_1),\dots,G_{k+1}=(A_{k+1},\theta_{k+1})$ satisfying
the following conditions:
\begin{enumerate}
\item The first graph $G_1$ is equal to $G$.
\item The last graph $G_{k+1}$ is empty (i.e.,
$G_{k+1}=(\emptyset,\emptyset)$)
\item The graphs $G_2,\dots, G_{k+1}$ are defined by induction
\begin{enumerate}
\item For each $i<k+1$, $s_i\in A_i$ and $s_i$ is the starting
point of a {\bf CES} of $G_i$.
\item We have $G_{i+1}=(G_i)_n^{*s_i}$.
\end{enumerate}
\end{enumerate}
\end{definition}
\subsection{Type-H graphs and the transitive factorization theorem\label{TypeH}}
Classicaly, we will denote by $L(A,\theta)$ the free partially
commutative Lie algebra on the alphabet $A$ for the commutation
relation $\theta$. The well known properties of the (noncommutative)
Lazard sets hold true and can be seen as consequences of the
transitive factorization theorem \cite{DL}. We recall it here.

Let $(A,\theta)$ be a partially commutative alphabet and $B\subset A$.
Then $\M(B,\theta_B)$ is the left (resp. right) factor of a
bisection of $\M(A,\theta)$. Explicitly,
\[\underline{\M(A,\theta)}=\underline{\M(B,\theta_B)}.\underline{\langle \beta_Z(B)\rangle}\]
where $\langle \beta_Z(B)\rangle$ means the submonoid generated by
the set
\[\beta_Z(B)=\{zw/z\in Z, w\in \M(B,\theta_B), IA(zw)= \{z\}\}\]
and $IA(t)=\{z\in A|t=zw\}$ is the initial alphabet of the trace
$t$.

 Let $B\subset A$, we say that $B$ is a {\bf transitively
factorizing subalphabet} ({\bf TFSA}) if and only $\beta_Z(B)$ is a
partially commutative code. We prove the following theorem.
\begin{theorem}[Duchamp--Luque \cite{DL}]\label{transitive}
Let $(B,Z)$ be a partition of $A$.
\begin{enumerate}
\item  The following assertions are equivalent.
\begin{enumerate}
\item[(i)]The subalphabet $B$ is a {\bf TFSA}.
\item[(ii)]The subalphabet $B$ satisfies the following condition.

For each $z_1\neq z_2\in Z$ and $w_1, w_2, w'_1,
w'_2\in\M(A,\theta)$ such that 
$$IA(z_1w_1)=IA(z_1w'_1)=\{z_1\}$$
and 
$$IA(z_1w_2)=IA(z_2w'_2)=\{z_2\}$$ we have
\[z_1w_1z_2w_2=z_2w'_2z_1w'_1\Rightarrow w_1=w'_1, w_2=w'_2. \]
\item[(iii)] For each $(z,z')\in Z^2\cap \theta$, the
dependence graph  (i.e., noncommutation) has no partial graph
like
\[z-b_1-\dots-b_n-z'.\]
with $b_1,\dots,b_n\in B$.
\end{enumerate}
\item

We have the decomposition
\[L(A,\theta)=L(B,\theta_B)\oplus J\]
where $J$ is the Lie ideal generated (as a Lie algebra) by
\[\tau_Z(B)=\{[ \dots [z,b_1], \dots b_n]\quad|\quad zb_1 \dots b_n\in
\beta_Z(B)\}. \] Furthermore,
\begin{quote}
(i) The subalgebra $J$ is a free partially commutative Lie algebra
if $B$ is a {\bf TFSA} of $A$.

 (ii) Conversely if $J$ is a free
partially commutative Lie algebra with
code $\tau_Z(B)$ then %%@
$B$ is a {\bf TFSA}.
\end{quote}
\end{enumerate}
\end{theorem}
Applying Theorem~\ref{transitive} and taking the inductive limit
of the process one obtains.
\begin{proposition}
Let $L$ be a transitive Lazard set.
\begin{enumerate}
\item The foliage $f(L)$ is a complete factorization of
$\M(A,\theta)$.
\item Let $\Pi$ be the unique morphism
${\mathcal M}(2,A)\rightarrow L(A,\theta)$ such that $\Pi(a)=a$ for each
letter $a\in A$. Then $\Pi(L)$ is a basis of the Free Lie algebra
$L(A,\theta)$.
\end{enumerate}
\end{proposition}
Such a factorization will be called Transitive Lazard Factorization
({\bf TLF}).  Not all the trace monoids possess a {\bf TLF}. For
example, in the graph 
$\begin{smallmatrix}a-b\\ c-d\end{smallmatrix} $ 
we can not find a {\bf CES}.
Nevertheless, the property ``having a {\bf TLF}" is decidable as
shown by the following result.
\begin{theorem}
A trace monoid admits a {\bf TLF} if and only if its commutation
alphabet is a type-H graph.
\end{theorem}
\begin{proof} It suffices to observe that a trace monoid has a {\bf
TLF} if and only if one can construct a transitive Lazard set from
its commutation graph, which is a consequence of proposition
\ref{typeH}.\end{proof}


 \subsection{An alternative
definition for transitive Lazard sets} In order to generalize the
correspondance between Hall and Lazard sets, we introduce the notion
of ${\mathcal F}$-Lazard sets.
\begin{definition}
Let $E$ be a finite set. A subset $S$ of ${\mathcal M}(2,A)$ will be
called {\bf Local Transitive Complete Elimination} relatively to $E$
if and only if, denoting $S\cap E=\{s_i,\dots,s_k\}$, there exist
$k+1$ graphs $G_1=(A_1,\theta_1)$,\dots
$G_{k+1}=(A_{k+1},\theta_{k+1})$ verifying
\begin{enumerate}
\item The initial graph is $G_1=(A,\theta)$
\item The last graph is $G_{k+1}=(\emptyset,\emptyset)$
\item The intermediate graphs are constructed following the two
rules
\begin{enumerate}
\item for each $i<k+1$, $s_i\in A_i$ and $s_i$ is the starting point
of a {\bf CES} of $G_i$.
\item for each $i<k+1$, the commutation graphs
$G_{i+1}$ is defined by its alphabet
\[
A_{i+1}=(A_i-s_i)\cup\{(bc^n_i)\in E|n>0, \in A_i \mbox{ and }
(b,c_i)\not\in\theta_i\}
\]
and its commutation rules
$$\theta_{i+1}=\theta_{A_{i+1}}:=\{(t,t')\in A_i^2| \Alph(t)\times\Alph(t')\subset\theta\}$$

\end{enumerate}
\end{enumerate}
\end{definition}

\begin{definition}
Let $\emptyset\subset {\mathcal F}_0\subset {\mathcal
F}_1\subset\cdots\subset{\mathcal F}_n\subset\cdots$ be a filtration of
${\mathcal M}(2,A)$. And denote ${\mathcal F}=({\mathcal F}_n)_{n\in\N}$. A set
$L\subset{\mathcal M}(2,A)$ has the ${\mathcal F}$-Lazard property if
and only if for each $i\in\N$, $L$ is a {\bf LTCE} of $A$ relatively
to ${\mathcal F}_i$.
\end{definition}
Observe that each transitive Lazard set is a ${\mathcal F}$-Lazard set
when ${\mathcal F}$ denotes the filtration by degree.

 We will
say that a filtration ${\mathcal F}=\left({\mathcal F}_i\right)_{i\in \N}$
of ${\mathcal M}(2,A)$ is {\bf admissible} if and only if each ${\mathcal
F}_i$ is finite and each subtree of an item of ${\mathcal F}_i$ belongs
again in ${\mathcal F}_i$  (A set having this property is called {\bf
closed} set in \cite{Re}). The next result proves that, when ${\mathcal
F}$ is an admissible filtration, the notion of ${\mathcal F}$-Lazard
sets is independent of the choice of the filtration and hence
coincides with the notion of transitive Lazard sets.

  \begin{lemma}\label{tlstofls}
A set $L$ is a transitive Lazard set if and only if it is a ${\mathcal
F}$-Lazard set for an admissible filtration ${\mathcal F}$.
  \end{lemma}
  \begin{proof}
  The "if" part is straightforward. Let us prove the converse
  denoting by $L$ a ${\mathcal F}$-Lazard set for an admissible
  filtration ${\mathcal F}$. We have to prove that $L$ is a {\bf LTCE}
  relatively to ${\mathcal M}(2,A)^{\leq
  n}$ for each $n\geq 0$. We set $L\cap{\mathcal M}(2,A)^{\geq
  n}=\{s_1,\dots,s_k\}$ and $p=\max\{q|L\cap{\mathcal M}(2,A)^{\geq
  n}\subset{\mathcal F}_q\}$. The set $L$ is a {\bf LTCE} of $A$
  relatively to ${\mathcal F}_p$. Hence, if we set $L\cap{\mathcal
  F}_p=\{r_1,\dots,r_l\}$, one can construct $l+1$ graphs $G'_1=(A'_1,\theta'_1),\cdots ,
  G'_{l+1}=(A'_{l+1},\theta'_{l+1})$ according to the definition of
  ${\mathcal F}$-Lazard sets. Consider the indices $i_1,\dots,i_k$ for
  which $s_j=r_{i_j}$ and let $G_1=(A_1,\theta_1),\dots,
  G_k=(A_k,\theta_k)$ be the commutation graphs defined by
  $A_j=A'_{i_j}\cap{\mathcal M}^{\leq n}$ and
  $\theta_j=\theta'_j\cap(A_j\times A_j)$. Such a sequence of graphs
  satisfies the items (1)-(3) of the definition of a {\bf LTCE} relatively to ${\mathcal M}(2,A)^{\geq
  n}$. We
  conclude that $L$ is a transitive Lazard set.\end{proof}
As an immediate consequence of Lemma \ref{tlstofls}, one has
the following lemma.
\begin{lemma}\label{TLStoLTCE}
A set of trees $L$ is a transitive Lazard set if and only if it is a
{\bf LTCE} of $(A,\theta)$ relatively to each closed set.
\end{lemma}

\section{Transitive Hall sets}
\subsection{A total order on a transitive Lazard set}
\begin{definition}
 A {\bf Transitive Hall Set} ({\bf THS}) $H$ is a family of trees $(h)_{h\in H}$ endowed
with a total order $<$ such that
\begin{enumerate}
\item The family $(f(h))_{h\in H}$ is a complete factorization of
$\M(A,\theta)$ (for the reverse order).
\item The set $H$ contains the alphabet $A$.
\item If $h=(h',h'')\in H-A$ then $h''\in H$ and $h<h''$.
\item If $h=(h',h'')\in{\mathcal M}(2,A)-A$ then $h\in H$ if and only if the
following four assertions are true:
\begin{enumerate}
\item The two sub-trees $h'$ and $h''$ belong to $H$.
\item We have the inequality $h'<h''$.
\item The foliage of the two sub-trees are not related by the ``disjoint commutation'' relation (i.e., $(f(h'),f(h''))\not\in\theta_\M$).
\item Either $h'\in A$ or $h'=(x,y)$ with $y\geq h''$.
\end{enumerate}
\end{enumerate}
\end{definition}
Although no condition on the shape of the graph  is apparent in the
definition, we will see that  part (1) strongly restricts implicitly
the possibilities. For example, let us consider the commutation graph
\[a\qquad b-c\]
and a set $H$ such that
\[\begin{array}{rcl}
H\cap{\mathcal M}(2,A)^{\leq 3}
&=&\{a,(b,a),((c,a),a),c,((c,a),c),(c,a),(b,(c,a)),\\ &&
  ((b,a),c),b,((b,a),b),(b,a)\}.
\end{array}\]
We suppose that  trees above are ordered from the right to the
left. Clearly,
 trees listed here verify  axioms (2), (3) and (4) of the definition of
 transitive Hall sets,  but the trace $cba$ admits two decreasing decomposition $cba=f(c).f((b,a))=c.ba=bca=f(b,(c,a))$.



As in the free case we have a perfect correspondence between the
notions of transitive Hall and Lazard sets.
\begin{theorem}
A set $L$ is a transitive Lazard set if and only if it is a
transitive Hall set.
\end{theorem}
\begin{proof} A slight adaptation of the noncommutative case (see \cite{Re})
shows that each transitive Lazard set is a transitive Hall set.

\medskip
Let us prove the converse. According to Lemma \ref{TLStoLTCE}, it
suffices to prove that a transitive Hall set $H$ is a {\bf LTCE}
relatively to any finite closed set $E$. Let us show it by induction
on $\Card E$.
 If ${\rm Card\
}E=1$ the result is obvious. Now, we suppose  ${\rm Card\ }E>1$ and
 set
\begin{enumerate}
\item[] $c=max\{h\in H\cap E\}$
\item[] $X=\{(ac^n)\in E|a\in A-c,n\geq
0,(a,c)\in\theta\}\cap\{b|(b,c)\in\theta\}$
\item[] $\theta_X=\theta_\M\cap X\times X$
\item[] $H'=H\cap {\mathcal M}(2,X)$
\item[] and $E'=E\cap {\mathcal M}(2,X)$
\end{enumerate}
We endow $H'$ with the restriction to $H'$ of the total order $<$ on
$H$.

 First, we check that $H'$ is a transitive Hall set for the
alphabet $(X,\theta_X)$.
\begin{enumerate}
\item The family $(f_X(h))_{h\in H'}$ is a complete factorization of
$\M(X,\theta_X)$ where $f$ denotes here the natural morphism 
$${\mathcal
M}(2,X)\rightarrow \M(X,\theta).$$ The result follows from the
isomorphism between $\M(X,\theta_X)$ and
$\M(f_A(X),\theta_{f_A(X)})$ and the fact that the $(f_A(h))_{h\in H}$ is
a complete factorization of $\M(A,\theta)$.
\item The generator set $X$ belongs to $H'$ (it suffices to observe
that $X\subset H$).
\item If $(h',h'')\in H'$, either $h''=c$ and in this case
$h', (h',h'')\in X$, either $h''\in H'$ and as one has $h<h''$ in
$H$ the same inequality occurs in $H'$.
\item If $h=(h',h'')\in H'-X$, then
\begin{enumerate}
\item As $H'\in {\mathcal M}(2,A)$, $h',h''\in H'$,
\item the inequality $h'<h''$ follows from $H'\subset H$,
\item Suppose that $(f_X(h'),f_X(h''))\in \theta_X$, this implies
$(f(h'),\break f(h''))\in \theta$ which is in contradiction with
$h=(h',h'')\in H'\subset H$.
\item If $h''\not\in X$, then $h''=(x,y)$ with $x,y\in H'\subset H$
which implies $h'\leq y$ (by restriction of $<$ to $H'$).
\end{enumerate}
Conversely, if we let $h=(h',h'')\in{\mathcal M}(2,X)$ such that $h',h''\in
H'$, $(f_X(h'),f_X(h''))\not\in \theta_X$ and $h'<h''$. If $h''\in
A$ then $h\in H\cap {\mathcal M}(2,X)=H'$. If $h''\in X-A$, then
$h''=(x,c)$ but $c>h'$ which implies (from the fact that $H$ is a
transitive Hall set) $h\in H$. Finally, if $h''\in H'-X$ one has
$h''=(x,y)$ and $y\geq h'$ implies $h\in H$.
\end{enumerate}

It follows that $H'$ is a transitive Hall set over the alphabet
$(X,\theta_X)$. Observe that $\Card E'<\Card E$, hence
 by induction $H'$ is a {\bf LTCE} of $(X,\theta_X)$ relatively to
 $E'$.
 According to the definition of a {\bf LTCE}, one sets $H'\cap
 E'=\{s1,\dots,s_k\}$ and one constructs the associated graphs
 $G_1=(A_1,\theta_1),\dots,G_{k+1}=(A_{k+1},\theta_{k+1})$.
If we denote $(a_1,\cdots,a_{n-1})$ the subsequence of the letters
of $A$ appearing in $(s_1,\dots,s_k)$, then $(a_1,\dots, a_{n-1})$ is
a {\bf CES} of $A-c$. The fact that $H$ is a transitive Hall set
implies that $(c,a_1,\dots,a_{n-1})$ is a {\bf CES} of $A$. In fact,
if we suppose that $(c,a_1,\dots,a_{n-1})$ is not a {\bf CES}, then
there exist $i,j\in\{1,\dots,n-1\}$ such that
$(a_i,a_j)\not\in\theta$, $(a_i,c)\not\in\theta$ and
$(a_j,c)\not\in\theta$. But $(a_i,c), (a_j,c)\in H$ by definition of
$H$, and $a_i.a_jc=a_j.a_ic$ contradicts the first point of the
definition of transitive Hall sets. Then $(c,a_1,\cdots,a_{n-1})$ is
a {\bf CES} of $G_0=(A,\theta)$ and $c$ is its starting point.
Furthermore, $(A_0-c)\cup\{(ac^n)\in E|n>0,a\in A \mbox{ and }
(a,c)\not\in\theta\}=X=A_1$. It follows that $H$ is a {\bf LTCE} of
$(A,\theta)$ relatively to $E$ with associated graphs $G_0, G_1,
\cdots, G_{k+1}$. Applying Lemma \ref{TLStoLTCE}, one deduces that
$H$ is a transitive Lazard set. \end{proof}

 This correspondence is very useful to
construct decomposition algorithms.
\subsection{Rewriting process}
 We can construct {\bf standard
sequences} of Hall trees $(h_1,\cdots,h_n)$ such that  for each
$i\in[1,n]$ either $h_i\in A$, or $h_i=(h'_i,h''_i)$ with $h''_i\geq
h_{i+1},\dots,h_n$. In a standard sequence an {\bf ascent} is an
index $i$ such that $h_i<h_{i+1}$ and a {\bf legal ascent} is an
ascent $i$ such that $h_{i+1}\geq h_{i+2},\cdots, h_n$ (these
definitions are due to Sch\"utzenberger \cite{Sc}).  Let $s$ be a
standard sequence and
 $i$ a  legal
ascent. We write $s\rightarrow s'$ if
$s'=(h_1,\cdots,h_{i-1},(h_i,h_{i+1}),h_{i+2},\cdots, h_n)$ when
$(f(h_i),f(h_{i+1}))\not\in\theta_\M$ and
$s'=(h_1,\cdots,h_{i-1},h_{i+1},h_i,h_{i+2},\cdots,h_n)$
otherwise. The transitive closure
$\displaystyle\mathop\rightarrow^*$ of $\rightarrow$ is such that
for each standard sequence there exists a unique decreasing standard
sequence $s'$ such that $s \displaystyle\mathop\rightarrow^*s'$.
Using this property on a sequence of letters, we obtain an
algorithm which allows to find the factorization of a trace in a
decreasing concatenation of Hall traces.
\begin{example}\label{HallEx2}
Let us consider the following commutation alphabet:
\[(A,\theta)=a-b-c-d .\]
and let $H$ be a transitive hall set such that
\begin{multline*}
H\cap{\mathcal
M}(2,A)^{\leq
3}=\{c,b,a,(a,c),((a,c),c),(a,(a,c)),(d,b),((d,b),b),\\(d,(b,a)),
(d,(a,c)),(d,a),((d,a),a),(d,(d,b)),(d,(d,a)),d\}.
\end{multline*}
 We can
compute the factorization of the word $bcaccbdbddad$ in the
following way $$
\begin{array}{c}
(b,c,a,c,c,b,d,b,d,d,a,d)\\ \downarrow\\
(b,c,a,c,c,b,d,b,d,(d,a),d)\\ \downarrow\\
(b,c,a,c,c,b,d,b,(d,(d,a)),d)\\ \downarrow\\
(b,c,(a,c),c,b,(d,b),(d,(d,a)),d)\\ \downarrow\\
(b,c,((a,c),c),b,(d,b),(d,(d,a)),d)\\ \downarrow\\
(b,c,b,((a,c),c),(d,b),(d,(d,a)),d)\\ \downarrow\\
(c,b,b,((a,c),c),(d,b),(d,(d,a)),d)
\end{array}
$$ which gives $bcaccbdbddad=c.b.b.acc.db.dda.d$.
\end{example}
Let $s=(h_1,\cdots,h_n)$ be a standard sequence and $i$ a legal
ascent, we define
\begin{equation}
\lambda_i(s)=(h_1,\dots,h_{i-1},(h_i,h_{i+1}),h_{i+2},\dots,h_n)
\end{equation}
and
\begin{equation}
\rho_i(s)=(h_1,\cdots,h_{i-1},h_{i+1},h_i,h_{i+2},\cdots,h_n).
\end{equation}
The {\bf derivation tree} of $s$ is the tree $T(s)$ satisfying the
following
\begin{enumerate}
\item if $s$ is a decreasing sequence then $T(s)$ is only the root
labeled $s$
\item otherwise, we consider the greatest legal ascent $i$ of $s$.
Then
\begin{enumerate}
\item if $(h_i,h_{i+1})\in \theta_\M$, the root of the tree $T(s)$ is $s$
and $T(s)$ has only one subtree $T(\rho_i(s))$.
\item otherwise, the root of $T(s)$ is $s$, the left subtree of
$T(s)$ is $T(\lambda_i(s))$ and the right sub-tree of $T(s)$ is
$T(\rho_i(s))$
\end{enumerate}
\end{enumerate}
If we denote $[s]=[h_1]\cdots [h_n]$, one obtains
\begin{equation}
[s]=\sum_{s'\in{\goth F}(T(s))}[s']
\end{equation}
where ${\goth F}(T(s))$ denotes the set of the leaves of $T(s)$.
Applying this equality to sequences of words, one gets an
algorithm allowing to decompose a polynomial in the PBW  basis
associated to a transitive Hall set.
\begin{example} We use the transitive Hall set defined in the example \ref{HallEx2}. One
has for example:
\begin{center}\small
\begin{pspicture}(13,6)
%\psgrid
\rput(6.5,5.8){$(b,c,a,c,c,b,d)$} \rput(3,5){$(b,c,c,a,c,b,d)$}
\rput(1.5,4){$(b,c,c,c,a,b,d)$} \rput(1.5,3){$(b,c,c,c,b,a,d)$}
\rput(1.5,2){$(c,b,c,c,b,a,d)$} \rput(1.5,1){$(c,c,b,c,b,a,d)$}
\rput(1.5,0){$(c,c,c,b,b,a,d)$} \rput(4.5,4){$(b,c,c,(a,c),b,d)$}
\rput(4.5,3){$(b,c,c,b,(a,c),d)$}
\rput(4.5,2){$(c,b,c,b,(a,c),d)$}
\rput(4.5,1){$(c,c,b,b,(a,c),d)$} \rput(10,5){$(b,c,(a,c),c,b,d)$}
\rput(8.5,4){$(b,c,c,(a,c),b,d)$}
\rput(8.5,3){$(b,c,c,b,(a,c),d)$}
\rput(8.5,2){$(c,b,c,b,(a,c),d)$}
\rput(8.5,1){$(c,c,b,b,(a,c),d)$}
\rput(11.5,4){$(b,c,((a,c),c),b,d)$}
\rput(11.5,3){$(b,c,b,((a,c),c),d)$}
\rput(11.5,2){$(c,c,b,((a,c),c),d)$} \psline{->}(6.5,5.6)(3,5.2)
\psline{->}(3,4.8)(1.5,4.2) \psline{->}(1.5,3.8)(1.5,3.2)
\psline{->}(1.5,2.8)(1.5,2.2) \psline{->}(1.5,1.8)(1.5,1.2)
\psline{->}(1.5,0.8)(1.5,0.2) \psline{->}(3,4.8)(4.5,4.2)
\psline{->}(4.5,3.8)(4.5,3.2) \psline{->}(4.5,2.8)(4.5,2.2)
\psline{->}(4.5,1.8)(4.5,1.2) \psline{->}(6.5,5.6)(10,5.2)
\psline{->}(10,4.8)(8.5,4.2) \psline{->}(8.5,3.8)(8.5,3.2)
\psline{->}(8.5,2.8)(8.5,2.2) \psline{->}(8.5,1.8)(8.5,1.2)
\psline{->}(10,4.8)(11.5,4.2) \psline{->}(11.5,3.8)(11.5,3.2)
\psline{->}(11.5,2.8)(11.5,2.2)
%
\end{pspicture}\end{center}
which allows us to write $$
bcaccbd=c.c.c.b.b.a.d+2c.c.b.b.[a,c].d+c.b.b.[[a,c],c].d .$$

\end{example}
\section{Conclusion}

The stable concept of a transitive factorization allows the adaptation
of the Hall machinery as it has been here made explicit. The
construction is characteristic free. It would be interesting to
investigate such constructions in the case of $p$-commutations
\cite{DDM,Do,DL2}.

Another effective construction of bases of free partially
commutative Lie algebras (Klyachko idempotents) has been obtained
recently by F.~Patras and C.~Reutenauer \cite{PR}. Their construction
holds without restriction on the commutation rules but is not
characteristic free.

\section*{Acknowledgments}  We thank Christophe Tollu for
his assistance.

\begin{thebibliography}{ABC}

\bibitem{C1}
P. Cartier, {\em D\'eveloppements r\'ecents sur les groupes de tresses,
applications \`a la topologie et \`a l'alg\`ebre\/}, 
S\'eminaire Bourbaki, vol.~1989/90, {\em Ast\'erisque},  
no.~189-190 (1990), Exp.~No.~716, pp.~17--67.
%
\bibitem{CF}
P. Cartier, D. Foata, {\em Probl\`emes combinatoires de commutation
et r\'e\-ar\-range\-ment\/}, Lect. Notes in Math., vol.~85, 1969.
%
\bibitem{Cha} B. Chandler, W. Magnus, The history of combinatorial group
theory: a case study in the theory of ideas. Springer, 1982.
%
\bibitem{CH}
C. Choffrut, {\em Free partially commutative monoids,\/} Technical
Report 86, LITP, Universit\'e Paris 7, 1986.
%
\bibitem{DDM} N. Dobrynin, G. Duchamp, A. Michalev, V. Petrogradsky
{\em On free $p$-super algebras\/}, Comm.\ Algebra
{\bf 28} (2000), 5275--5302.
%
\bibitem{Do} N. Dobrynin {\em The free color Lie superstructures:
elimination of variables\/}, in press.
%
\bibitem{Dub}C. Duboc, {\em Commutations dans les mono\"\i des
libres:     un cadre th\'eorique pour l'\'etude du
parall\'elisme\/}, thesis, Universit\'e  de Rouen, 1986.
%
\bibitem{DK1}
G. Duchamp, D. Krob, {\em The free partially commutative Lie
algebra: bases and ranks,\/}
 Adv.\ Math.\ {\bf 95} (1992), 92--126.
%
\bibitem{DK2}
G. Duchamp, D. Krob, {\em Free partially commutative structures\/},
{\em J. Algebra\/} {\bf 156} (1993), 318--361.
%
%
\bibitem{DK3}
G. Duchamp, D. Krob, {\em Partially commutative Magnus
transformation\/}, Int. J. Alg. Comp. {\bf 3} (1993), 15--41.
%
%
\bibitem{DL}
G. Duchamp, J.G. Luque, {\em Transitive factorizations of partially
commutative free monoids and Lie algebras\/}, Discrete Math. {\bf
246} (2002), 83--97.
%
\bibitem{DL2} G. Duchamp, J.G. Luque,
{\em Congruences compatible with the shuffle product/}, FPSAC'00,
Moscow, 2000.
%
\bibitem{DR}
V. Diekert and G. Rozenberg, {\em The book of traces\/}, World
Scientific, Singapour, 1995.
%
\bibitem{GM} S. Gaubert, J. {\em Modeling and analysis of timed petri nets using heaps of pieces},
IEEE Trans. Autom. Control {\bf 44} (1999), 683--697.
%
\bibitem{K1} T. Kohno, {\em Linear representations of braid groups and
classical Yang-Baxter equations}, in: ``Braids'', Contemporary
Math. {\bf 78} (1988),  339--363.
%
\bibitem{KL} D. Krob and P. Lalonde, {\em Partially commutative
Lyndon words}, Lect. Notes in Comp. Sci. {\bf 665} (1993),
237--246.
%
\bibitem{Lal1} P. Lalonde, {\it Bases de Lyndon des alg\`ebres de Lie libres
partiellement commutatives}, Theoret.\ Comput.\ Sci.\ {\bf 117} (1993),
217--226.
%
\bibitem{Lal2} P. Lalonde, {\it Lyndon heaps: An analogue of Lyndon words in free
partially commutative monoids}, Discrete Math.\ {\bf 145} (1995),
171--189.
%
\bibitem{Lal} P. Lalonde, {\em Contribution \`a l'\'etude des
empilements}, th\`ese de doctorat, LACIM, 1991.
%
\bibitem{Laz} M. Lazard, {\em Groupes anneaux de Lie et probl\`eme de
Burnside}, Inst. Math. de l'Universita Roma, 1960.
%
\bibitem{MV} J. Mairesse, L. Vuillon, {\em Asymptotic behavior in a heap model with two pieces},
Theoret.\ Comput.\ Sci.\ {\bf 270} (2002), 525--560.
%
\bibitem{Me1} G. M\'elan\c con, {\em Combinatorics of Hall trees and
Hall words}, 
J. Combin.\ Theory Ser.~A {\bf 59} (1992), 285--308.
%
\bibitem{Me2} G. M\'elan\c con, C. Reutenauer, {\em Computing Hall
Exponents in the Free Group}, 
Int.\ J. Alg.\ Comp.\ {\bf 3} (1993), 275--294.
%
\bibitem{Me3} G. M\'elan\c con, {\em Bases of free Lie algebras, ``are
Lyndon words better ?''}, 3rd SIAM Conference on Control and its
Applications, Symposium on Combinatorial Methods in Control Theory,
Saint-Louis, Missouri, 1995. 
%
\bibitem{PR} F. Patras and C. Reutenauer, {\it On Dynkin and Klyachko idempotents in
graded bialgebras}, Adv.\ Appl.\ Math.\ {\bf 28} (2002), 560--579.
%
\bibitem{Re}
C. Reutenauer, {\em Free Lie algebras\/}, Oxford University Press,
New-York, 1993.
%
\bibitem{onfact} M.P. Sch\"utzenberger, {\em On a factorization of
free monoids}, Proc.\ Amer.\ Math.\ Soc.\ {\bf 16} (1965),
21--24.
%
\bibitem{Sc}
M.P. Sch\"utzenberger, {\em Sur une propri\'et\'e combinatoire des
alg\`ebres de Lie libre pouvant \^etre utilis\'ee dans un
probl\`eme de Math\'ematiques appliqu\'ees}, Seminaire
Dubreuil--Pisot Ann\'ee 1958--1959, Paris, 1958.
%
%
\bibitem{Vi1} G.X. Viennot, {\em Alg\`ebres de Lie libres et monoïdes libres},
Th\`ese d'Etat, Universit\'e Paris 7, 1974.

\bibitem{Vi2}
G. Viennot, {\em Alg\`ebre de Lie libres et Mono\"\i des Libres},
Lecture Notes in Math., vol.~691, 1978.

\bibitem{Vi3} G.X. Viennot, {\em Heaps of pieces, I: basic definitions
and combinatorial lemmas}, in: Combinatoire
\'Enum\'erative, G. Labelle and P. Leroux (eds.), 
Springer--Verlag, Berlin, 1986, pp.~321--350.

\end{thebibliography}
\end{document}