A fast and practical bit-vector algorithm for the Longest Common Subsequence problem

This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw.     

Automated computation and consistency checking of physical dimensions and units in scientific programs

Physical dimensions and units form an essential part of the specification of constants and variables occurring in scientific programs, yet no standard compilable programming language implements direct support for automated dimensional consistency checking and unit conversion. This paper describes a conceptual basis and prototype implementation for such support within the framework of the standard Fortran 90 language. This is accomplished via an external module supplying appropriate user data types and operator interfaces. Legacy Fortran 77 scientific software can be easily modified to compile and run as ‘dimension‐aware’ programs utilizing the proposed enhancements. Copyright © 2001 John Wiley & Sons, Ltd.     

Design-code traceability recovery: selecting the basic linkage properties

Traceability ensures that software artifacts of subsequent phases of the development cycle are consistent. Few works have so far addressed the problem of automatically recovering traceability links between object-oriented (OO) design and code entities. Such a recovery process is required whenever there is no explicit support of traceability from the development process. The recovered information can drive the evolution of the available design so that it corresponds to the code, thus providing a still useful and updated high-level view of the system.

Automatic recovery of traceability links can be achieved by determining the similarity of paired elements from design and code. The choice of the properties involved in the similarity computation is crucial for the success of the recovery process. In fact, design and code objects are complex artifacts with several properties attached. The basic anchors of the recovered traceability links should be chosen as those properties (or property combinations) which are expected to be maintained during the transformation of design into code. This may depend on specific practices and/or the development environment, which should therefore be properly accounted for.

In this paper different categories of basic properties of design and code entities will be analyzed with respect to the contribution they give to traceability recovery. Several industrial software components will be employed as a benchmark on which the performances of the alternatives are measured.     

遗传程序设计方法综述

近年来,遗传程序设计（genetic programming,GP)的研究引起了人们很大的关注,它运用遗传算法（genetic algorithm,GA)的思想,通过生成计算机程序来解决问题,介绍了遗传程序设计的研究状况以及目前的研究进展,概述了它的基本算法、主要特点、理论与技术,同时介绍了一些GP实现系统以及主要的应用领域,最后探讨了遗传程序设计的研究方向。     

前向神经网络参数估计中的进化规划

人工神经网络在很多领域有着成功的应用。神经网络参数估计有许多训练算法,BP算法是前向多层神经网络的典型算法,但BP算法有时会陷入局部最小解。进化规划是一种随机优化技术,它可以发现全局最优解。文章介绍了进化规划在前向多层神经网络参数估计中的应用,结合具体例子给出了算法实现的具体操作步骤和实验结果。实验数据表明采用进化规划得到的网络参数是最优的,神经网络的性能优于基于BP算法的神经网络性能。     

Implementing tactics and tacticals in a higher-order logic programming language

We argue that a logic programming language with a higher-order intuitionistic logic as its foundation can be used both to naturally specify and implement tactic-style theorem provers. The language extends traditional logic programming languages by replacing first-order terms with simply-typed -terms, replacing first-order unification with higher-order unification, and allowing implication and universal quantification in queries and the bodies of clauses. Inference rules for a variety of inference systems can be naturally specified in this language. The higher-order features of the language contribute to a concise specification of provisos concerning variable occurrences in formulas and the discharge of assumptions present in many inference systems. Tactics and tacticals, which provide a framework for high-level control over search for proofs, can be directly and naturally implemented in the extended language. This framework serves as a starting point for implementing theorem provers and proof systems that can integrate many diversified operations on formulas and proofs for a variety of logics. We present an extensive set of examples that have been implemented in the higher-order logic programming language Prolog.     

Dynamics of Flexible Multibody Systems Using Virtual Work and Linear Graph Theory

By combining linear graph theory with the principle of virtualwork, a dynamic formulation is obtained that extends graph-theoreticmodelling methods to the analysis of flexible multibody systems. Thesystem is represented by a linear graph, in which nodes representreference frames on rigid and flexible bodies, and edges representcomponents that connect these frames. By selecting a spanning tree forthe graph, the analyst can choose the set of coordinates appearing inthe final system of equations. This set can include absolute, joint, orelastic coordinates, or some combination thereof. If desired, allnon-working constraint forces and torques can be automaticallyeliminated from the dynamic equations by exploiting the properties ofvirtual work. The formulation has been implemented in a computerprogram, DynaFlex, that generates the equations of motion in symbolicform. Three examples are presented to demonstrate the application of theformulation, and to validate the symbolic computer implementation.     

Christopher Strachey: Recollections of His Influence

My early research was inspired by the mathematical semantics of Scott and Strachey. Two such topics, recounted in this paper, were the fixed-point analysis of pointer loops and the expressibility of a style of functional programming introduced by Barron and Strachey.     

Systems programming for data communications on minicomputers

This paper examines some of the special considerations which apply to the development of such software for minicomputers. These are treated under the following general categories:

• loading and throughput
• the external interfaces of the system software
• the internal structure of the system software
• developing the software

.     

Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.