Formal Correctness of a Quadratic Unification Algorithm

We present a case study using ACL2 to verify a nontrivial algorithm that uses efficient data structures. The algorithm receives as input two first-order terms, and it returns a most general unifier of these terms if they are unifiable, failure otherwise. The verified implementation stores terms as directed acyclic graphs by means of a pointer structure. Its time complexity is and its space complexity , and it can be executed in ACL2 at a speed comparable to a similar C implementation. We report the main issues encountered to achieve this formally verified implementation. This work has been supported by project TIN2004-03884 (Ministerio de Educación y Ciencia, Spain) and FEDER funds.     

系列化工程图样的图形生成与标注方法之自动化及一体化研究

本文以参数化设计为考察之立足点，以工程图样处理为目的，对几类处理方法进行了比较，并相应提们的处理策略－交互参数法，使工程图样生成具有交互性、参数化、一体化、实用化之功能，即以环数据结构和布尔运算算法为前提实施零件图、装配图处理一体化，以尺寸为参变量实现图形与标注处理的一体化，以参数化为前提实现自动化，以交互参数法使其实用化。     

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.     

区间Wang-Said型广义Ball曲线的降阶

定义了区间Wang-Said型广义Ball曲线(WSGB曲线),它可作为误差控制和产品检验的有效工具;采用3种方法讨论了其降阶逼近问题,即扰动法、利用Chebyshev多项式导出的最佳一致逼近算法和插值端点的最佳一致逼近方法;给出了各种处理方法的显式误差表示.最后结合数值实例分析了3种方法的优劣.     

Unification Modulo <Emphasis Type="Italic">ACUI</Emphasis> Plus Distributivity Axioms

E-unification problems are central in automated deduction. In this work, we consider unification modulo theories that extend the well-known ACI or ACUI by adding a binary symbol * that distributes over the AC(U)I-symbol +. If this distributivity is one-sided (say, to the left), we get the theory denoted AC(U)ID_l; we show that AC(U)ID_l-unification is DEXPTIME-complete. If * is assumed two-sided distributive over +, we get the theory denoted AC(U)ID; we show unification modulo AC(U)ID to be NEXPTIME-decidable and DEXPTIME-hard. Both AC(U)ID_l and AC(U)ID seem to be of practical interest, for example, in the analysis of programs modeled in terms of process algebras. Our results, for the two theories considered, are obtained through two entirely different lines of reasoning. A consequence of our methods of proof is that, modulo the theory that adds to AC(U)ID the assumption that * is associative-commutative, or just associative, unification is undecidable.     

基于LDAP的统一用户管理系统研究与实现

在对基于角色的访问控制RBAC（Role-Based Access Control）模型研究的基础上,结合轻量级目录访问协议LDAP（Lightweight Directory Access Protocol）信息存储的特点,提出了基于LDAP的统一用户管理系统的设计思路并予以实现,应用于一个企业级的信息发布平台,为其提供了统一的用户管理机制,达到了预期效果。详细介绍了相关的基本概念、设计思路、开发环境和主要功能模块的实现。     

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.     

General <Emphasis Type="Italic">E</Emphasis>-unification with Eager Variable Elimination and a Nice Cycle Rule

We present a goal-directed E-unification procedure with eager Variable Elimination and a new rule, Cycle, for the case of collapsing equations – that is, equations of the type x ≈ v where x ∈Var(v). Cycle replaces Variable Decomposition (or the so-called Root Imitation) and thus removes possibility of some obviously unnecessary infinite paths of inferences in the E-unification procedure. We prove that, as in other approaches, such inferences into variable positions in our goal-directed procedure are not needed. Our system is independent of selection rule and complete for any E-unification problem.     

Quasi-Fully Dynamic Algorithms for Two-Connectivity and Cycle Equivalence

We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms , which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic updates occur on the remaining edges in the graph. We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for 2-edge connectivity and O(log n) amortized time per operation for cycle equivalence. The former is deterministic while the latter is Monte-Carlo-type randomized. For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log ³ n) amortized time per operation. The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers) is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is known for this problem. Received October 26, 1998; revised October 1, 1999, and April 15, 2001.     

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

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

Hexahedral Mesh Generation by Successive Dual Cycle Elimination

We propose a new method for constructing all-hexahedral finite element meshes. The core of our method is to build up a compatible combinatorial cell complex of hexahedra for a solid body which is topologically a ball, and for which a quadrilateral surface mesh of a certain structure is prescribed. The step-wise creation of the hex complex is guided by the cycle structure of the combinatorial dual of the surface mesh. Our method transforms the graph of the surface mesh iteratively by changing the dual cycle structure until we get the surface mesh of a single hexahedron. Starting with a single hexahedron and reversing the order of the graph transformations, each transformation step can be interpreted as adding one or more hexahedra to the so far created hex complex. Given an arbitrary solid body, we first decompose it into simpler subdomains equivalent to topological balls by adding virtual 2-manifolds. Secondly, we determine a compatible quadrilateral surface mesh for all subdomains created. Then, in the main part we can use the core routine to build up a hex complex for each subdomain independently. The embedding and smoothing of the combinatorial mesh(es) finishes the mesh generation process. First results obtained for complex geometries are encouraging.     

Optimal Graph Constraint Reduction for Symbolic Layout Compaction

The compaction problem in VLSI layout can be formulated as a linear program. To reduce the execution time and memory usage in compaction, it is important to reduce the size of the linear program. Since most constraints in compaction are derived directly or indirectly from physical separation and electrical connectivity requirements which can be expressed in the form of graph constraints, we study the graph constraint reduction problem. That is the problem of producing, for a given system of graph constraints, an equivalent system with the fewest graph constraints. After observing that the problem as previously formulated is NP-hard and overrestrictive in that the maximum possible reduction is not always attainable, we propose a new formulation in which the maximum possible reduction is guaranteed. We further present a polynomial-time algorithm for the new formulation. Received September 13, 1994; revised December 4, 1995.     

产品全生命周期模型中的xBOM映射研究

BOM是产品全生命周期信息模型的纽带。在产品研发过程的推进中,产品模型在不断地演化,BOM视图也同时发生了改变。为了有效地保证生命周期中的产品信息的完整性和正确性,该文给出了BOM视图的映射转换方法。文章在总结了生命周期各阶段中的BOM的特点的基础上,提出了三种映射方式和一种转换方式,详细地给出了设计BOM到制造BOM之间的转换算法,并研究了更为通用的xBOM转换解决方案。     

矩阵Padé型逼近及多变量控制系统的模型简化(英文)

本文给出了一个新的模型简化混合方法:矩阵Pade型方法,该方法首先任选一个矩阵多项式作为简化模型之分母,然后由矩阵Pade型逼近求出其分子,文中的数值例子表明由我们的方法得到的简化模型是原系统的一个好的近似,该法的计算步骤十分简洁。     

基于Lagrange乘子理论的轨迹跟踪和局部规划一体化

基于Ｌａｇｒａｎｇｅ 乘子理论,根据移动机器人自主行走的具体要求,提出完成轨迹跟踪、到达目标和避障的优化模型,实现了控制与规划的一体化。利用Ｌｙａｐｕｎｏｖ 稳定理论证明了系统的稳定性,讨论了Ｌａｇｒａｎｇｅ 乘子对系统响应的影响。仿真结果表明移动机器人可同时跟踪期望轨迹并完成局部规划     

DDFP语言的归约机实现技术

ＤＤＦＰ语言是一种基于表达式的泛函程序设计语言，这是一种具有归约语义的，引用透明的，能表达无限数据结构，高阶纯粹的函数式语言。它的实现是基于λ演算、ＳＬＩ演算、ＳＫＬ－Ｇ演算、ＬＮＦ演算及图归约技术。本文在［４］的基础上首先引进了ＬＮＦ演算，而后详细介绍了该语言的归约机实现技术，对结果作了讨论。     

模型降阶方法研究

本文综合了模型降阶领域的现有方法,首先着重介绍了模型降阶的主要方法,并以图表的方式给出了各方法的分类及特性归纳。最后基于模型降阶的研究现状和存在的问题提出了一些看法,以便为实际工程应用提供参考。