Measurement and defect modeling for a legacy software system

This paper analyzes the quality of a large-scale legacy software system using selected metrics. Quality measurements include defect information collected during product development and in-field operation. Other software metrics include measurements on various product and process attributes, including design, size, change, and complexity. Preliminary analyses revealed the high degree of skew in our data and a weak correlation between defects and software metrics. Tree-based models were then used to uncover relationships between defects and software metrics, and to identify high-defect modules together with their associated measurement characteristics. As results presented in tree forms are natural to the decision process and are easy to understand, tree-based modeling is shown to be suitable for change solicitation and useful in guiding remedial actions for quality improvement.The following are trademarks or service marks in the United States and/or other countries: IBM is a trademark of International Business Machines Corporation. REFINE and Software Refinery are trademarks of Reasoning Systems Inc. SAS is a trademark of the SAS Institute Inc. S-PLUS is a trademark of the Statistical Sciences, Inc.     

Automated Proof Construction in Type Theory Using Resolution

We provide techniques to integrate resolution logic with equality in type theory. The results may be rendered as follows. A clausification procedure in type theory, equipped with a correctness proof, all encoded using higher-order primitive recursion. A novel representation of clauses in minimal logic such that the -representation of resolution steps is linear in the size of the premisses. A translation of resolution proofs into lambda terms, yielding a verification procedure for those proofs. Availability of the power of resolution theorem provers in interactive proof construction systems based on type theory.     

On-line Learning and the Metrical Task System Problem

The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship between these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include: An analysis of how two recent algorithms for the MTS problem can be applied to the problem of tracking the best expert in the decision-theoretic setting, providing good bounds and an approach of a much different flavor from the well-known multiplicative-update algorithms. An analysis showing how the standard randomized Weighted Majority (or Hedge) algorithm can be used for the problem of combining on-line algorithms on-line, giving much stronger guarantees than the results of Azar, Y., Broder, A., & Manasse, M. (1993). Proc ACM-SIAM Symposium on Discrete Algorithms (pp. 432–440) when the algorithms being combined occupy a state space of bounded diameter. A generalization of the above, showing how (a simplified version of) Herbster and Warmuth's weight-sharing algorithm can be applied to give a finely competitive bound for the uniform-space Metrical Task System problem. We also give a new, simpler algorithm for tracking experts, which unfortunately does not carry over to the MTS problem.Finally, we present an experimental comparison of how these algorithms perform on a process migration problem, a problem that combines aspects of both the experts-tracking and MTS formalisms.     

Applying AI to Software Renovation

Lockheed Martin InVision provides software renovation and sustainment services, including analyzing systems for interesting features, transforming systems to new environments, and recasting systems to new architectures and languages. We seek an optimal blend of effort by automating the straightforward parts of a reengineering task under human control. We achieve this automation through a judicious combination of artificial intelligence and compiler-compiler techniques. This paper describes the InVision tool set and reengineering process and presents some examples of the applications of this technology.     

Minimization of norms and logarithmic norms by diagonal similarities

It is a commonly occurring problem to find good norms · or logarithmic norms (·) for a given matrix in the sense that they should be close to respectively the spectral radius (A) and the spectral abscissa (A). Examples may be the certification thatA is convergent, i.e. (A)A<1 or stable, i.e. (A)(A)<0. Often the ordinary norms do not suffice and one would like to try simple modifications of them such as using an ordinary norm for a diagonally transformed matrix. This paper treats this problem for some of the ordinary norms.

---

Minimisierung von Normen und Logarithmischen Normen durch Diagonale Transformationen

Zusammenfassung Ein oft vorkommendes praktisches Problem ist die Konstruktion von guten Normen · und logarithmischen Normen (·) für eine gegebene MatrixA. Mit gut wird dann verstanden, daß A den Spektralradius (A)=max |₁| und (A) die Spektralabszisse (A)=max Re _i gut approximieren. Beispiele findet man für konvergente Matrizen wo (A)A<1 gewünscht ist, und für stabile Matrizen wo (A)(A)<0 zu zeigen ist. Wir untersuchen hier, wie weit man mit Diagonaltransformationen und dengewöhnlichsten Normen kommen kann.

     

Directional derivatives of the maximum function

Directional differentiability of the function (x) = sup{f(x, u), u U} is proved for a class of smooth functions f. The result is applied to study the directional differentiability of the function (x) = sup{f(x, y), y F(x)}, where F is a multivalued mapping.Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 171–173, March–April, 1992.     

Path Integration on a Quantum Computer

We study path integration on a quantum computer that performs quantum summation. We assume that the measure of path integration is Gaussian, with the eigenvalues of its covariance operator of order j^-k with k>1. For the Wiener measure occurring in many applications we have k=2. We want to compute an -approximation to path integrals whose integrands are at least Lipschitz. We prove: Path integration on a quantum computer is tractable. Path integration on a quantum computer can be solved roughly ^-1 times faster than on a classical computer using randomization, and exponentially faster than on a classical computer with a worst case assurance. The number of quantum queries needed to solve path integration is roughly the square root of the number of function values needed on a classical computer using randomization. More precisely, the number of quantum queries is at most 4.46 ^-1. Furthermore, a lower bound is obtained for the minimal number of quantum queries which shows that this bound cannot be significantly improved. The number of qubits is polynomial in ^-1. Furthermore, for the Wiener measure the degree is 2 for Lipschitz functions, and the degree is 1 for smoother integrands. PACS: 03.67.Lx; 31.15Kb; 31.15.-p; 02.70.-c     

Characterization of desirable properties of general database decompositions

The classical theory of acyclicity of universal relational schemata identifies a set of desirable properties of such schemata, and then shows that all of these properties are equivalent to one another, and in turn equivalent to certain acyclicity characterizations of a hypergraph underlying the schema. The desirable properties include the simplicity of constraints, the correctness of certain efficient query evaluation algorithms, and the complexity of maintaining the integrity of a decomposed database. The principal result of this paper is to show that the essence of this result may be extended to a much more general setting; namely, that in which database schemata are just sets and database mappings just functions. Rather than identifying a single desirability class, our work shows that there are several, all of which collapse to a common group when restricted to the universal relational setting. Particularly, the classical notions of pairwise consistency implies global consistency and hypergraph acyclicity are not equivalent in the general case, but rather are independent of each other, and may be considered separately or in combination, to yield varying strengths of desirability.     

Browsers for distributed systems: Universal paradigm or siren's song?

Webbased browsers are quickly becoming ubiquitous in the workplace. Software development managers are quick to incorporate browsers into a broad range of software development projects, often inappropriately. The purpose of this paper is to examine the technical issues relevant to incorporating browsers as a component of a commercial offtheshelf (COTS)based solution. Issues examined include portability, performance, functionality, security, human factors, distribution, installation, upgrading, componentbased development, runtime configuration management, and licensing.     

Nonblockability of Switches with the Cayley Graph Structure for Serial Transfer of Data Blocks. Generalized Hypercubes and Multidimensional Grids

A general method of conflictless arbitrary permutation of large data elements that can be divided into a multitude of smaller data blocks was considered for switches structured as the Cayley graphs. The method was specified for arbitrary permutations in the generalized hypercubes and multidimensional grids, and their characteristics were considered.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

Decision procedures for elementary sublanguages of set theory: XIII. Model graphs,reflection and decidability

Positive solutions to the decision problem for a class of quantified formulae of the first order set theoretic language based on , , =, involving particular occurrences of restricted universal quantifiers and for the unquantified formulae of , , =, {...}, , where {...} is the tuple operator and is a general choice operator, are obtained. To that end a method is developed which also provides strong reflection principles over the hereditarily finite sets. As far as finite satisfiability is concerned such results apply also to the unquantified extention of , , =, {...}, , obtained by adding the operators of binary union, intersection and difference and the relation of inclusion, provided no nested term involving is allowed.     

On Some Vagaries of Vagueness and Information

The presence of vagueness in scientific theories (in particular, to those related to and connected with the management of information) is briefly analyzed. We consider, firstly, the problem whether vague predicates can be adequately represented by existing formal theories. A negative answer to this question produces, as a by-product, the suggestion that a good semantics for fuzzy sets can be offered by the notion of distance from idealized items. Secondly, some questions connected with the adequacy of theories of information to the multifaceted informal notion of information suggest to afford this problem within an enlarged dynamical setting.     

Automated Deduction Techniques for the Management of Personalized Documents

This work is about a real-world application of automated deduction. The application is the management of documents (such as mathematical textbooks) as they occur in a readily available tool. In this Slicing Information Technology tool, documents are decomposed (sliced) into small units. A particular application task is to assemble a new document from such units in a selective way, based on the user's current interest and knowledge. It is argued that this task can be naturally expressed through logic, and that automated deduction technology can be exploited for solving it. More precisely, we rely on first-order clausal logic with some default negation principle, and we propose a model computation theorem prover as a suitable deduction mechanism. Beyond solving the task at hand as such, with this work we contribute to the quest for arguments in favor of automated deduction techniques in the real world. Also, we argue why we think that automated deduction techniques are the best choice here.     

The specification of “specification”

The notion of specification plays a key role in the developing science of computing. It is typically considered to be the keystone in the software development process. However, there is no single, generally agreed meaning of specification that bears close scrutiny. Instead there is a variety of different, although partially interlocking and overlapping interpretations of the term.We catalogue this varietal profusion and attempt to lay bare both the sources and consequences of each major alternative. We attempt to present the full range of possibilities, and the biases inherent in each style of interpretation.We believe that there is a pressing need for clarification of the meaning of specification (and several other important terms), especially in view of the fact that so many practitioners and theoreticians assume, erroneously, that a clear meaning already exists (even though they might disagree as to what it is). In particular, we feel that a more general awareness of the difficulties that currently attach to this key concept may go some way towards bridging (if not actually healing) the rift that currently exists between the engineering and scientific aspects of computing.The most deadly thing in software is the concept ... that you are going to specify what you are going to do, and then do it. And that this is where most of our troubles come from. Ross, Garmisch.What happens is that specifications of software are regarded as functional specifications ... It is my belief that anybody who is responsible for the implementation of a piece of software ... must specify the design, the form. Sharp, Rome.No matter how precisely you try to specify a system, once you have built it you find it isn't exactly what is wanted. Oestreicher, Rome.... the admission of shortcomings is the primary condition for improvement. Dijkstra, Garmisch.     

A principle of independence for binary tree searching

Summary When searching unsuccessfully for a fixed element in a random binary search tree, the number of comparisons made whose result is less is independent from the number of comparisons whose result is greater. This principle can be used to compute the mean and variance of the total number of comparisons involved in both a successful and an unsuccessful search.This work was supported in part by a Hertz Graduate Fellowship and by the Xerox Palo Alto Research Center.     

A New Implementation of Automath

This paper presents aut, a modern Automath checker. It is a straightforward re-implementation of the Zandleven Automath checker from the seventies. It was implemented about five years ago, in the programming language C. It accepts both the AUT-68 and AUT-QE dialects of Automath. This program was written to restore a damaged version of Jutting's translation of Landau's Grundlagen. Some notable features: It is fast. On a 1 GHz machine it will check the full Jutting formalization (736 K of nonwhitespace Automath source) in 0.6 seconds. Its implementation of -terms does not use named variables or de Bruijn indices (the two common approaches) but instead uses a graph representation. In this representation variables are represented by pointers to a binder. The program can compile an Automath text into one big Automath single line-style -term. It outputs such a term using de Bruijn indices. (These -terms cannot be checked by modern systems like Coq or Agda, because the -typed -calculi of de Bruijn are different from the -typed -calculi of modern type theory.)The source of aut is freely available on the Web at the address .     

Fuzzy systems and neural networks in software engineering project management

To make reasonable estimates of resources, costs, and schedules, software project managers need to be provided with models that furnish the essential framework for software project planning and control by supplying important management numbers concerning the state and parameters of the project that are critical for resource allocation. Understanding that software development is not a mechanistic process brings about the realization that parameters that characterize the development of software possess an inherent fuzziness, thus providing the rationale for the development of realistic models based on fuzzy set or neural theories.Fuzzy and neural approaches offer a key advantage over traditional modeling approaches in that they aremodel-free estimators. This article opens up the possibility of applying fuzzy estimation theory and neural networks for the purpose of software engineering project management and control, using Putnam's manpower buildup index (MBI) estimation model as an example. It is shown that the MBI selection process can be based upon 64 different fuzzy associative memory (FAM) rules. The same rules are used to generate 64 training patterns for a feedforward neural network. The fuzzy associative memory and neural network approaches are compared qualitatively through estimation surfaces. The FAM estimation surfaces are stepped, whereas those from the neural system are smooth. Also, the FAM system sets up much faster than the neural system. FAM rules obtained from logical antecedent-consequent pairs are maintained distinct, giving the user the ability to determine which FAM rule contributed how much membership activation to a concluded output.     

Continuous reductions among combinatorial optimization problems

Summary Many reductions among combinatorial problems are known in the context of NP-completeness. These reductions preserve the optimality of solutions. However, they may change the relative error of approximative solutions dramatically. In this paper, we apply a new type of reductions, called continuous reductions. When one problem is continuously reduced to another, any approximation algorithm for the latter problem can be transformed into an approximation algorithm for the former. Moreover, the performance ratio is preserved up to a constant factor. We relate the problem Minimum Number of Inverters in CMOS-Circuits, which arises in the context of logic synthesis, to several classical combinatorial problems such as Maximum Independent Set and Deletion of a Minimum Number of Vertices (Edges) in Order to Obtain a Bipartite (Partial) Subgraph.