A note on the free submonoids of the monoid of prefix codes

Abstract

Let A* be a free monoid generated by a finite alphabet A and let A(+) = A*\ {1}, where 1 is the empty word. Let M = {L\L subset of or equal to A(+) or L = {1}} be the monoid of languages under the catenation. We consider {1} as a prefix code. The family of all prefix codes p is a free submonoid of M. For any L is an element of M, let L-L = {L' is an element of M\LL' is an element of P}. We show that L-L boolean OR {1} is a submonoid of p for every non-empty language L subset of or equal to A(+). The purpose of this note is to give a characterization for a finite language L in which L-L boolean OR {1}is a free submonoid of P for the case \A\ greater than or equal to 2. For an infinite language L whether the monoid L-L boolean OR {1} is free or not depends on L. We illustrate the above two cases with examples.