Reduction and unification in lambda calculi with a general notion of subtype

Reduction, equality, and unification are studied for a family of simply typed -calculi with subtypes. The subtype relation is required to relate base types only to base types and to satisfy some order-theoretic conditions. Constants are required to have a least type, that is, no overloading. We define the usual and a subtype-dependent -reduction. These are related to a typed equality relation and shown to be confluent in a certain sense. We present a generic algorithm for preunification modulo -conversion and an arbitrary subtype relation. Furthermore it is shown that unification with respect to any subtype relation is universal.     

新型周波控制器的设计与实现

简述了三种功率控制系统输出方式，讨论其各种加热方式的优缺点，并就其缺点提出相应改进方法。提出了一种单相周波控制时序，对应进行了新型单相周波控制器的设计，解决了现有控制器手动周波过零全控制问题，并最终实现电路。     

Intelligent backtracking in deduction systems by means of extended unification graphs

A method for unification as the basis for intelligent backtracking in deduction systems is described. This method is based on the unification graphs introduced by Cox. In this paper, unification graphs are used in an extended form such that they represent all the information which can be gained from the unification constraints, i.e., the expression to be unified, their subterms which, as a consequence, are to be unified, the number of deduction steps which cause the unification of two terms, and the term-subterm relation as far as necessary. If a unification conflict occurs from this information, the deduction steps which have led to these conflicts can be determined and reset. This is done by searching for loop-free paths or loops with certain properties in the extended unification graph, according to the type of unification conflict. Algorithms for the handling of the unification graph and for the extraction information from it are described and proved as correct.     

A comparison of the variable-abstraction and constant-abstraction methods for associative-commutative unification

The constant-abstraction and variable-abstraction methods for associative-commutative unification were proposed by Herold, Livesey, and Siekmann and by Stickel, respectively. These methods are compared here for efficiency and conceptual purity. The pure variable-abstraction method is easier to implement but less efficient for the variables and constants case than the constant-abstraction method. With obvious refinements, the former method can be made comparably efficient and similar in behavior to the latter. The refined method uses solutions of homogeneous linear Diophantine equations under additional constraints, instead of the conceptually simpler homogeneous or inhomogeneous linear Diophantine equations without additional constraints of the pure variable-abstraction method or the constant-abstraction method.This paper resulted from a visit to the University of Kaiserslautern, during which discussions with Alexander Herold and Jörg Siekmann enabled each of us to gain a greater understanding and appreciation of one another's algorithms. The visit was partially supported by the Deutsche Forschungsgemeinschaft, Sonderforschungsbereich 314, Künstliche Intelligenz-Wissensbasierte Systeme. Preparation of this paper was supported, in part, by the Defense Advanced Research Projects Agency under Contract N00039-84-K-0078 with the Space and Naval Warfare Systems Command. The views and conclusions contained herein are those of the author and should not be interpreted as representative of the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the United States government. Approved for public release. Distribution unlimited.     

The rue theorem-proving system: The complete set of LIM+ challenge problems

In this paper we discuss the successful execution of the LIM+ challenge problems as proposed by Bledsoe. This problem set ranges from a 12-step nonequality proof to a complex 41-step paramodulation proof. Our theorem prover is based on RUE resolution, which incorporates the axioms of equality into the definition of resolution. We apply hyperresolution as a restriction strategy and produce RUE hyper-refutations without the use of paramodulation. We present an extensive treatment of the heuristics applied to find proofs, both standalone and interactive.This work was supported by the National Science Foundation Grant CCR-9024953.     

A Logical Characterization of Forward and Backward Chaining in the Inverse Method

The inverse method is a generalization of resolution that can be applied to non-classical logics. We have recently shown how Andreoli’s focusing strategy can be adapted for the inverse method in linear logic. In this paper we introduce the notion of focusing bias for atoms and show that it gives rise to forward and backward chaining, generalizing both hyperresolution (forward) and SLD resolution (backward) on the Horn fragment. A key feature of our characterization is the structural, rather than purely operational, explanation for forward and backward chaining. A search procedure like the inverse method is thus able to perform both operations as appropriate, even simultaneously. We also present experimental results and an evaluation of the practical benefits of biased atoms for a number of examples from different problem domains. This work has been partially supported by the Office of Naval Research (ONR) under grant MURI N00014-04-1-0724 and by the National Science Foundation (NSF) under grant CCR-0306313. The first author was partially supported by a post-doctoral fellowship from INRIA-Futurs/école Polytechnique.     

An application of program unification to priority queue vectorization

In this experimental study, we apply the technique of program unification to priority queues. We examine the performance of a variety of unified priority queue implementations on a Cray Y-MP. The scope of the study is restricted to determining if different implementations of priority queues exhibit markedly different performance characteristics under program unification. We found this to be true. In a larger view, this result has interesting consequences in the application of program unification to discrete event simulations on vector or SIMD machines. We find the heap to be a promising data structure in the program unification paradigm.This research was supported by the National Science Foundation under Grant No. ASC-9002225, and by NATO under Grant CRG 900108.Also supported in part by the Mathematical Sciences Section of Oak Ridge National Laboratory under contract DE-AC05-84OR21400 with Marietta Energy Systems, Inc.     

一种电信统一网管平台系统架构的设计与分析

根据电信网管系统的功能结构,在分析特点的基础上,给出了一种兼容新老设备及新老系统的统一网管平台系统架构的方案,并对该方案提出的几种兼容方案进行了分析,指出了各种方案的优缺点。     

An examination of the relationship between cycle training,cycle accidents,attitudes and cycling behaviour among children

Around 40% of 10–11-year-old children receive cycle training every year in the UK, but concern has been expressed over the efficacy of training courses. One argument is that accidents occur too infrequently to be a viable evaluative criterion, and attitudes and behaviour have been suggested as alternatives. A questionnaire that measured a number of variables including accidents, attitudes, and behaviour was completed by 336 participants from two schools in the London Borough of Bromley. At least one cycling injury had been sustained by 58.3% of respondents, requiring hospital treatment in 19.1% of cases. Girls reported fewer accidents than boys. No relationship between training and accidents was found. A principal components analysis (PCA) of the attitudes items produced a ‘safe attitudes’ factor. Girls displayed ‘safer’ attitudes, but there was no evidence that training produced safer attitudes. A PCA of the cycling behaviour scales produced two factors, ‘safe cycling’ and ‘showing off’. Safe cyclists who obeyed basic safety rules were less likely to sustain cycle injuries, but showing off was not related to accidents. Girls were less likely to show off, but the safe behaviour gender difference did not reach significance. Training did not relate to either factor.     

Analysis of cycle stealing with switching times and thresholds

We consider two processors, each serving its own M/GI/1 queue, where one of the processors (the “donor”) can help the other processor (the “beneficiary”) with its jobs, during times when the donor processor is idle. That is the beneficiary processor “steals idle cycles” from the donor processor. There is a switching time required for the donor processor to start working on the beneficiary jobs, as well as a switching back time. We also allow for threshold constraints on both the beneficiary and donor sides, whereby the decision to help is based not only on idleness but also on satisfying threshold criteria in the number of jobs.

We analyze the mean response time for the donor and beneficiary processors. Our analysis is approximate, but can be made as accurate as desired, and is validated via simulation. Results of the analysis illuminate principles on the general benefits of cycle stealing and the design of cycle stealing policies.     

Dimensional Reduction of Surface Models for Analysis

This paper describes a set of procedures by which an analyst can idealise slender 2D shell structures for linear static analysis using reduced-dimensional beam finite elements. The first step is the development of the topological operations that are necessary to achieve the desired dimensionally reduced representation. Next, the automatic derivation of necessary geometric and physical properties of the reduced dimensional entities are described, together with the application of appropriate coupling constraints between dimensions. Dimensional reduction of shell models involves finding areas of the geometric model whose dimensions are such that this region may be represented in an analysis model with a 1D beam. Using the medial axis transform, geometric measures are defined for identifying such areas in the geometric model. However, topological features of the model and its medial axis were also identified as significant in the automation of dimensional reduction. The application of the medial axis transform to automatic dimensional reduction is described and example models given.     

基于粗糙集理论的分层递阶约简算法􀀂

粗糙集理论的分层递阶约简算法是根据属性的获取方式、采集成本和实时性要求等对属性进行分类,使信息系统或者决策系统中的所有属性在单层次和单粒度上的知识表示变为部分属性所构成的知识在多种层次和多种粒度上的表示,从而可以逐层对信息系统进行约简.分层递阶约简算法在某水泥窑炉控制决策获取中的应用证实其有效性.     

关于模型降阶的一些试验结果

把几种具有较高逼近精度的频域降阶模型用于控制系统设计,给出设计后的仿真结果.说明不仅应研究如何提高逼近精度,而且应研究降阶设计方法.     

基于二次精简的散乱点云精简方法

在逆向工程中,点云精简是一个重要的步骤,精简的质量直接关系到后续曲面重构的效率。分析了常用的几种点云精简方法,并针对现有方法的不足,提出一种改进的方法。该方法使用 PCA主成分析法,利用点的k邻域点集拟合切平面,将点到该平面距离作为判断特征点的依据进行初始精简,再利用均匀网格的方法对初始精简后的点云进行重采样处理,保留部分关键特征点。通过初始精简和后期精简两步法完成对点云的精简步骤,并通过实验验证了该方法的有效性。     

不完备信息系统下的属性约简算法

传统的粗糙集模型是处理完全信息系统的有力工具,但对于不完全信息系统却显得无能为力。因此对不完备信息系统的研究也是粗集理论研究领域之一。本文在M．Kryszkiewcz提出的一个容差关系的基础上提出改进,使之更加具有灵活性。然后以该改进模型为基础,运用属性重要性理论,给出属性约简算法,并通过一个实例来验证。最后将该算法和经典算法进行了比较。     

Hilbert's tenth problem is of unification type zero

We show that the problem of finding integer solutions to a polynomial equation over the integers has unification type zero, i.e. there exist polynomial equations which have unifiers, but which have no minimal and complete set of unifiers: In particular, it is shown that the equation uv=w+z has no minimal and complete set of solutions.     

低相噪低杂散C波段频率合成器的设计

直接数字频率合成（DDS）＋锁相环（PLL）是目前频率合成技术的常用组合方式之一。首先就DDS＋PLL的几种常用合成方式的特点进行了简单介绍,然后着重利用DDS内环分频式合成方式,实现了一种低杂散低相噪的频率合成器的设计。设计中首先在理论分析的基础上选出了合理的设计方案,然后对各项指标进行了可行性分析,尤其对输出相位噪声和组合杂散进行了详尽的阐述。最终用试验结果证明了该方案的可行性。