逻辑自动机分析中的递归泛函方法

§1.引言所谓逻辑自动机(logical automata),指的是一种逻辑结构,它的唯一功能是对给予它的刺激作出相应的反应.这种刺激与反应通常由一连串的离散的信号组成,分别叫做自动机的输入与输出.对于那些出现信号的时刻,从自动机开始工作的时刻算起用非负整数给予编号以后,每一输入与每一输出就表现为一个从非负整数到信号集的映照.再进一步地对所有可能出现的信号用非负整数编号后,输入与输出就表现为以非负整数为定义域及值域的函数,而一个给定的自动机就表现为以这些函数作为自变元及值的泛函.     

连续检索组织的构造

本文研究文件对于固定查询集的连续检索组织(CRO)存在的条件.导出了必要条件,得到了由三个查询组成的查询集存在CRO的充分必要条件.对于一般CRO结构规律的研究,在证明了“固定结构唯一性引理”的基础上,给出一个构造CRO的递归方法.本文给出的算法把任何查询集划分成满足CRO存在的小块,并对这些小块构造它们的CRO.     

前缀码和汉字存贮编码的码长下界

存贮编码是信息压缩的一种手段,目的是使一定数量的存贮空间存放尽可能多的信息. 用前缀码理论[Chung L.Liu,离散数学基础,复旦大学计算机科学系译]可获得最佳存贮编码系统,但是当涉及到象汉字这样庞大的待编码集时,人工处理就成了一个困难问题,即使是码长的估计也难于精确. 1981年,张毅首先提出了汉字的存贮编码问题[张毅,存贮编码的特点及其作用,全国中文信息研究会学术交流材料;最优存贮编码的存在性及其编码效率的估计,来源同     

关于二叉树的高

用二叉树作检索工具,D.E.Knuth曾作过详尽的介绍(见The Art of Computer Programming,Vol.3,Second edition,§6.22,1973 By Addison-wesley Publishing Company),它的特点是:在检索时,可像二分法一样,以正比于log_2N(N为记录个数)的比较次数找到所要记录,而在新记录插入时,又可用链结办法而不必移动记录的位置。因而它具有记录顺序排列和链结排列这两种优点。二叉树方法的缺点是其随机性很大。在文件生成时,随着记录出现的次序不同,生成的二叉树也不同,有能达到比log_2N大得多的比较次数,因而影响检索速度。本文讨论的是与二叉树检索速度直接相关的二叉树的高,或称最大路径长。文中给出了有确定节点数和确定高度的二叉树数目的计算公式,也研究了N个记录的各种可能排列和它们所生成的二叉树之间的对应关系,并由此计算了各个高度的概率分布。最后对平均高度提出了一个经验公式。     

SQL外联接及其性质

以ＯＲＡＣＥ的ＳＱＬ＊ＰＬＵＳ所实现的外联接运算入手，给出一种简单法则判定ＳＱＬ语文中外联接符合“（＋）”的使用的正确性；进而研究了外联接作为关系代数运算的基本性质，从而为正确的使用外联提供依据。