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 coeﬃcients α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 coeﬃcients hc are non-zero polynomials in F X . Since only finitely many

coeﬃcients 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