论文部分内容阅读
二十世纪四十年代后期，Shannon提出了码的概念，从而导致了码论的产生。从形式语言的角度看，码是一类特殊的语言，它具有唯一分解的性质。什么样的语言是码和如何产生码是码论的两个主要问题。自由幺半群上的二元关系的无关语言是码的一个重要来源。许多人对二元关系的无关语言是码的条件以及由此产生的码的性质和应用进行了研究。本文的主要工作就是继续这项研究。 前缀码，特别是极大前缀码，是信息科学中应用最广泛的一类码。前缀码就是自由幺半群上的前缀序的无关语言。关于前缀码有下面的重要结论:一个语言是前缀码的充分与必要条件是它恰好由它的树的叶子组成，每个前缀码都包含在一个极大前缀码中，一个有限前缀码是有限多个有限极大前缀码的交。本文利用Cantor空间给出了前缀码和极大前缀码的一种新判定方法，描述了包含一个前缀码的所有极大前缀码的特征，并证明了每个前缀码都是两个极大前缀码的交。 为了进一步考察无关语言是码的条件，本文还引入了准严格关系的概念，并对所有准严格关系的集合的序性质以及它的某些偏序子集进行了讨论，证明了余相容的准严格关系的无关语言都是码。