A New String Matching Algorithm

In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n . It requires only O ( m +σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.     

A family of goal directed theorem provers based on conjunction and implication: Part 1

This paper presents a family of theorem provers for classical, intuitionistic and neighbouring logics. The theorem provers are based on a formulation of these logics in terms of conjunction, implication and falsity. Computation is goal directed, and, for the special case of Horn clauses, coincides with pure Prolog computation. Our approach is generic, and, as we shall show in a subsequent paper, can be adapted to other logics, such as modal and temporal systems.The research described in this paper has been funded partially by Esprit project No. 393, ACORD, of the European Commission.     

ACT-P: A configurable theorem-prover

There has been a considerable amount of research into the provision of explicit representation of control regimes for resolution-based theorem provers. However, most of the existing systems are either not adequate or too inefficient to be of practical use. In this paper a theorem prover, ACT-P, which is adequate but retains satisfactory efficiency is presented. It does so by providing a number of user-changeable heuristics which are called at specific points during the search for a proof. The set of user-changeable heuristics was determined on the basis of a classification of the heuristics used by existing resolution-based theorem provers.     

基于复数法的几何定理可读机器证明

已有的机器证明方法在处理一些涉及大规模符号运算的几何问题时,常因算法复杂度过高或机器能力的限制,有时并不能在合理时间内实现可读机器证明. 故提出了复数法这一新的几何定理机器证明算法,并选用符号计算功能较为强大的软件Mathematica创建了新证明器CNMP(complex number method prover).新提出的复数法能有效地解决构造型几何命题,对用于测试与评价几何定理证明器性能的综合性平台TGTP(thousands of geometric problems for geometric theorem provers)上的180个几何问题的实验结果表明,CNMP的解题能力与运行效率均令人满意.尤其是对于一些具有相当难度的几何定理,如五圆定理、Morley定理、Lemoine圆定理、Thebault定理、Brocard圆定理等,CNMP均能在短时间内给出可读机器证明.     

钟罩式气体流量标准装置内部容积的测量方法

基于尺寸测量法,测量了1000L钟罩内部的分阶容积。2个接触式长度计和旋转测量臂构成弦长测量机构。将罩体沿轴向划分为若干等间距截面,以15°采样间隔测量长度计与罩体内壁的接触点到测量臂旋转中心的距离,由接触点空间坐标确定各截面的轮廓。提出一种新的面积扫描法计算各层截面面积。经与圆度误差法的测量数据对比,当采样间隔密集时(5°或15°)2种方法的测量结果比较吻合。由各层截面面积及其轴向间距,计算得到分阶容积数据表作为罩体内部容积的标定结果。     

用于指针逻辑的自动定理证明器

提出了一种为指针逻辑设计定理证明器的新技术,该项技术主要是基于变换和替代,已在APL 的工具中得以实现.APL 自动定理证明器是完全自动的,且其产生的证明可以被有效地记录和检验.已使用关于单链表、双链表和二叉树的指针程序测试了该自动定理证明器.     

高效字符匹配算法的研究

在分析BM算法以及它的衍生版本BMH、Sunday等算法的基础上,提出一种新的改进算法。改进算法有三个重要特点：（1）采用双字符启发策略,提高模式串最大移动位数及其概率,最大移动位数为n+2;（2）采用窗口动态分段方法,尽量减少字符匹配次数;（3）建立模式串中相同字符的位置链,充分利用启发字符,降低模式匹配的冗余度。实验结果表明,改进算法具有较高的匹配效率。     

标准体积管检定过程中的误差来源

着重介绍了容积法（称重法）检定标准体积管和用标准体积管检定计量体积量（质量）流量计的检定原理及其检定修正公式的理论分析，以及在实际检定过程中各种误差的来源分析，消除或减小各种误差的有效方法。     

微内核操作系统互斥量模块功能正确性的形式化验证

操作系统在许多安全攸关领域为软件系统提供关键性底层支撑,操作系统中一个微小的错误或漏洞都可能引起整个软件系统的重大故障,造成巨大经济损失或危及人身安全.为了减少此类安全事故的发生,对操作系统正确性进行验证十分必要.传统测试手段无法穷尽系统中的所有潜在错误,因而操作系统验证有必要使用具有严格数学理论基础的形式化方法.在操作系统中,互斥量可协调多任务对资源的访问,是一种常用的任务同步方式,其功能正确性对于保障多任务应用的正确性十分关键.本文基于定理证明方法,在交互式定理证明器Coq中对某抢占式微内核操作系统的互斥量模块进行代码级形式化建模,给出其接口函数的形式化规范,并实现这些接口函数的功能正确性验证.