Independent Languages Of Quasi-strict Relations And Codes

The concept of code was originated in the theory of communication initiated by Shannon in the late of 1940s, which induces the theory of codes. In the view of formal languages, a code is a special language which has the unique decomposition property. The main considered problems in the theory of codes are that how to certify codes and that how to construct codes. Many authors had ever considered the conditions of the independent languages of a relation being codes, as well as the properties and applications of the classes of codes which are the independent languages of a relation. The aim of the present paper is to continue these works.Prefix codes (especially, maximal prefix codes) are widely applied in the field of computer science and technology. Prefix codes are exactly the independent languages of prefix order on free monoids. The following statements exhibit some fundamental properties of prefix codes: a language is a prefix code if and only if it is exactly the set of leaves of its tree; each prefix code is contained in a maximal prefix code; every finite prefix code is the intersection of some finite maximal prefix codes. In this paper, by using Cantor space, a new description of prefix codes and maximal prefix codes is obtained, and a characterization of the maximal prefix codes containing a given prefix code is exhibited. Moreover, it is shown that each prefix code is the intersection of two maximal prefix codes.Also, to give a further consideration of the condition that the independent languages of a relation are codes, the concept that quasi-strict relation is introduced, and the ordering properties as well as some partial ordered subsets of the set of all quasi-strict relations are investigated. It is proved that the independent languages of co-compatible quasi-strict relations are codes.