Sub-classes of the monoid of left cancellative languages

Аннотация

Prefix codes are widely used in information theory and computer science, for example, in encoding and decoding, data compression and transmission, DES and Huffman’s algorithms [4,5,7–9]. Left cancellative languages are a kind of generalization of prefix codes. For the properties of left cancellative languages, see [3,10–12]. Especially in [12], maximal left cancellative languages are studied. From [10], we know that left singular languages are a kind of left cancellative languages and they are studied in [2,6,10]. In this paper, we find that maximal left cancellative languages and left singular languages have some characteristics in common.They are all semi-singular languages. In fact, the notions of semi-singular and inf-singular languages are discussed and introduced in [3]. Based on [3], we make a further study on semi-singular and inf-singular languages.