4 ROLAND BACHER AND CHRISTOPHE REUTENAUER
Observe that
X∗ \CX∗
is not the set of proper prefixes of C if the prefix-free set
C is not maximal: The set
X∗
\
CX∗
contains then all proper prefixes of elements
in C but it contains also all words of
X∗
having no element of C as a prefix. If C
is for example reduced to the singleton {x} of {x,
y}∗
then {x,
y}∗
\ x{x,
y}∗
is the
set {1} y{x,
y}∗
given by the empty word 1 which is the unique proper prefix of
x and by the set y{x, y}∗ of all words starting with y.
A maximal prefix-free set C is finite if and only if every infinite word contains
an element of C as a prefix. Indeed, a finite prefix-free set C consisting of words of
length at most l and containing no prefix of an infinite word W = w1w2w3 · · · XN
can be augmented by adjoining the prefix w1w2 . . . wl of W . Conversely, given
an infinite prefix-free set C, the finite alphabet X contains at least one letter x1
occuring as a prefix of infinitely many elements in C. Similarly, there exists a second
letter x2, such that x1x2 is a prefix of infinitely many elements in C. Iteration of
this argument yields an infinite word w1w2 . . . containing no element of C as a
prefix.
5. Weak prefix bases for right ideals
A weak prefix basis is a subset {bc}c∈C in F X with elements of the form
bc = c
p∈X∗\CX∗
αc,pp, αc,p F,
indexed by elements c of a prefix-free set C.
Every element in a weak prefix basis involves thus exactly one monomial in
a prefix-free set C. No monomial appearing in a weak prefix basis contains an
element of C as a proper prefix. The following result (see Theorem 3.2 of Chapter
2 in [BR]) explains the terminology:
Proposition 5.1. (i) The right ideal I =

c∈C
bcF X generated by a weak
prefix basis {bc}c∈C is a free right F X -module over the set {bc}c∈C .
(ii) The quotient F X /I is a free F-vector space over the set
X∗
\
CX∗.
(iii) Every right ideal of F X has a weak prefix basis.
Assertions (i) and (iii) of Proposition 5.1 imply of course Cohn’s result on
freeness of every right ideal in F X .
Since bc bc =

p∈X∗\CX∗
(αc,p αc,p)p for two weak prefix bases (bc)c∈C
and (bc)c∈C of an ideal I indexed by a common prefix-free set C, assertion (ii) of
Proposition 5.1 determines the coefficients αc,p uniquely for a weak prefix basis of
an ideal I with basis elements indexed by a given prefix-free set C. In particular, a
right ideal I of F X has at most one weak prefix basis indexed by a given prefix-free
set C.
Proof of Proposition 5.1 We consider a linear combination
c∈C
bchc =
c∈C

⎝c

p∈C\CX∗
αc,pp⎠

hc (1)
where the coefficients hc are non-zero polynomials in F X . Since only finitely many
coefficients hc are non-zero, there exists an index cm C such that the degree of
hcm is maximal among all polynomials hc involved in (1). Given a monomial w
of maximal degree in hcm , the product bcm hcm = (cm

p∈P
αcm,pp)hcm involves
Previous Page Next Page