An experiment was carried out by a group of scientists to compare different tools and techniques for detecting duplicated or near-duplicated source code. The overall comparative results are presented elsewhere. This paper takes a closer look at the results for one tool, Dup, which finds code sections that are textually the same or the same except for systematic substitution of parameters such as identifiers and constants. Various factors that influenced the results are identified and their impact on the results is assessed via rerunning Dup with changed options and modifications. These improve the performance of Dup with regard to the experiment and could be incorporated into a postprocessor to be used with other tools.

As an aid in software maintenance, it would be useful to be able to track down duplication in large software systems efficiently. Duplication in code is often in the form of sections of code that are the same except for a systematic change of parameters such as identifiers and constants. To model such parameterized duplication in code, this paper introduces the notions of parameterized strings and parameterized matches of parameterized strings. A data structure called a parameterized suffix tree is defined to aid in searching for parameterized matches. For fixed alphabets, algorithms are given to construct a parameterized suffix tree in linear time and to find all maximal parameterized matches over a threshold length in a parameterized p-string in time linear in the size of the input plus the number of matches reported. The algorithms have been implemented, and experimental results show that they perform well on C code.

This paper describes a general technique that can be used to obtain approximation schemes for various NP-complete problems on planar graphs.The strategy depends on decomposing a planar graph into subgraphs of a form we call k-outerplanar.For fixed k, the problems of interest are solvable optimally in linear time on k-outerplanar graphs by dynamic programming.For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each k a linear time algorithm that produces a solution whose size is at least k/(k + 1)optimal.If the problem is a minimization problem, such as minimum vertex cover, it gives for each k a linear time algorithm that produces a solution whose size is at most (k + 1)/k optimal.Taking k = [c log log nl or k = [c log nl, where n is the number of nodes and c is some constant, we get polynomial time approximation algorithms whose solution sizes converge toward optimal as n increases.The class of problems for which this approach provides approximation schemes includes maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set.For these and certain other problems, the proof of solvability on k-outerplanar graphs also enlarges the class of planar gmphs for which the problems are known to be solvable in polynomial time.

This paper develops a theory and algoritbrns for an application problem arising in software maintenance.The application is to track down duplication in a large software system.We want to find not only exact matches between sections of code, but parametrized matches, where a parametrized match between two sections of code means that one section can be transformed into the other by replacing the parameter names (e.g.identifiers and constants) of one section by the parameter names of the other via a one-to-one function.This paper formalizes this problem in terms of parametrized strings and parametrized pattern matching and detirtes a new data structure (parametrized sujjfi.xtree) suitable for parametrized pattern matching.It gives efficient algorithms for constructing this data structure, efficient algorithms for parametrized pattern matchmg, and an efficient algorithm for timing all maximal parametrized matches over a threshold length in a parametrized string.The algorithms for constructing parametrized suffix trees and for reporting duplication over a threshold length have been implemented.Tests on C code indicate that these algorithms should perform well in the application.

In the Mead–Conway design methodology for LSI, modules are designed and then connected by wires to form larger modules in a hierarchical fashion. It would be helpful to have a design aid that would do the routing automatically and be guaranteed of coming within some fixed percentage of the size of an optimal routing. With this goal in mind, we investigate the problem of routing two-terminal nets between two modules of the same width but possibly different heights, assuming that the sides are aligned vertically. The terminals may lie on any of the sides of either module. Wires must be routed according to the “Manhattan” reserved-layer model, in which all wires must lie on a rectilinear grid, and wires running the same direction must be separated by at least unit distance. Finding an optimal routing for this problem is NP-hard, where the measure of performance is the perimeter of the bounding box around the whole routing region. We describe an algorithm whose worst-case performance is asymptotically at most 19/10 times that of an optimal routing. The algorithm runs in $O(n\log n)$ time, where n is the number of nets. One of the problems encountered in routing is how to evaluate a routing when the optimal routing is not available for comparison. The techniques given here can be used to calculate lower bounds on the size of an optimal routing. Thus, these techniques may be useful in evaluating routings produced by methods other than the algorithm in this paper.

We study grasps by a robot hand with three spring-loaded fingers. In two dimensions, the hand can grasp any polygon stably. That is, the grip is at a local minimum of the potential energy function defined by the springs of the fingers, ignoring friction. Surprisingly, under some conditions an equilibrium grasp on a circle is unstable even with respect to translation. In three dimensions, the hand can grasp and lift any cylindrical surface with a polygonal cross-section. In contrast we show that a hand with finger angles fixed at 120°, as proposed by Hanafusa and Asada, generally can not achieve a two-dimensional stable grip in the absence of friction.

We study grasps by a robot hand in the absence of friction. In two dimensions, a hand with three spring-loaded fingers and five degrees of freedom can achieve an equilibrium grasp on any object described by a polygon. Furthermore, the grasp is stable, that is, at a local minimum of the potential energy function defined by the springs of the fingers. In three dimensions, the hand can grasp any cylinder. In contrast, if the degrees of freedom of the hand are restricted to correspond to a hand built by Hanafusa and Asada, stable grips on a polygon cannot in general be achieved.

In dynamic storage allocation, successive allocation and freeing of blocks normally leads to fragmentation of storage.When a new block is to.beallocated, fragmentation may prevent any single region of available storage from being large enough for the new block, even though the total amount of available space is sufftcient.When such a conflict arises, dynamic storage allocation systems typically require time-consuming garbage collection or they simply break down.This paper investigates strategies for maintaining storage that allow allocation of blocks to proceed in spite of fragmentation conflicts, at the cost of moving some blocks already allocated are investigated.Such a scheme is reasonable only if it can be guaranteed that the cost of moving blocks never becomes too large relative to the size of the.block to be allocated.Two such schemes are described.They are similar to the buddy system in that they always align the left end of a block of size n at a position that is a multiple of 2"005"'.The schemes differ in the criterion for choosing an interval to free up when no interval of the right size is empty: the Not Full (NF) scheme chooses an interval that is not full, while the Not Too Full (NTF) scheme chooses an interval that is at most as full as all of memory.Tight worst-case bounds are obtained for these schemes as a function of the proportion of memory tilled.The results show that the worst-case cost for NF, the simpler of the two schemes, can be much worse than that for NTF when memory is not too full.However, simulations suggest that the average cost may be much less than the worst-case.cost.

Among the more difficult combinatorial problems in computer science are those occurring in dynamic storage allocation. We investigate the handling of memory conflicts occurring when a request for a block of storage is received, but no one region of available space is large enough due to fragmentation of storage. For arbitrary block sizes, we show that it is NP-hard to find a minimal cost reallocation of memory that will allow insertion of a new block. Therefore, we focus on the “bay restaurant” model studied by Robson, in which requests are for only one or two units of memory. We give a polynomial time algorithm for minimal cost insertions of batches of blocks and for minimal cost memory compaction. We show that the cost of inserting p blocks one at a time, i.e. on-line, is no worse than \[ \left\lfloor 2\left( \frac{3}{2} \right)^{\lceil \log p \rceil } - 1 \right\rfloor \] times the minimal cost of inserting the blocks in one batch, i.e. off-line. For p a power of two, this bound is tight.

This paper describes a general technique that can be used to obtain approximation algorithms for various NP-complete problems on planar graphs. The strategy depends on decomposing a planar graph into subgraphs of a form we call k- outerplanar. For fixed k, the problems of interest are solvable optimally in linear time on k-outerplanar graphs by dynamic programming. For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each k a linear time algorithm that produces a solution whose size is at least (k-1)/k optimal. If the problem is a minimization problem, such as minimum vertex cover, it gives for each k a linear time algorithm that produces a solution whose size is at most (k + 1)/k optimal. Taking k = c log log n or k = c log n, where n is the number of nodes and c is some constant, we get polynomial time approximation schemes, i.e. algorithms whose solution sizes converge toward optimal as n increases. The class of problems for which this approach provides approximation schemes includes maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set. For these and certain other problems, the proof of solvability on k-outerplanar graphs also enlarges the class of planar graphs for which the problems are known to be solvable.

As the final stage in laying out a chip, the logic of the integrated circuit is assembled into one (not necessarily rectangular) module which must then be connected to pads lying along a rectangular frame. A placement for the module must be determined to assure the feasibility of the (river) routing from the logic inside to the pads on the periphery. We first show how to solve the routing problem in a stationary context: given the placement, can the signals be wired in the given doughnut-shaped area? Then we use the routability analysis developed in the first part to find a placement of the circuit that yields a feasible routing (if one exists). Both algorithms run in time that is quadratic in the size of the input, and there exist cases for which this bound cannot be improved upon.

A linear-time approximation algorithm for routing multipoint net channels is presented. The algorithm uses at most a constant factor times the optimal number of tracks required. The notion of channel fluxis introduced and shown, like channel density, to be a lower bound for channel width. Every multipoint net channel having density d and flux f is routed within 2d+O(f) tracks, and every two-point net channel within d+O(f) tracks. Since the flux never exceeds θ(@@@@n), this proves a conjecture of Brown and Rivest [6] that every n-net channel can be routed in O(d+@@@@n) tracks.

This paper studies two approximation algorithms for packing rectangles, using the two-dimensional packing model of Baker, Coffman and Rivest [SIAM J. Comput., 9 (1980), pp. 846–855]. The algorithms studied are called next-fit and first-fit shelf algorithms, respectively. They differ from previous algorithms by packing the rectangles in the order given; the previous algorithms required sorting the rectangles by decreasing height or width before packing them, which is not possible in some applications. The shelf algorithms are a modification of the next-fit and first-fit decreasing height level algorithms of Coffman, Garey, Johnson and Tarjan [SIAM J. Comput., 9 (1980), pp. 808–826]. Each shelf algorithm takes a parameter r. It is shown that by choosing r appropriately, the asymptotic worst case performance of the shelf algorithms can be made arbitrarily close to that of the next-fit and first-fit level algorithms, without the restriction that items must be packed in order of decreasing height. Nonasymptotic worst case performance bounds are also investigated.

We consider problems of packing an arbitrary collection of rectangular pieces into an open-ended, rectangular bin so as to minimize the height achieved by any piece. This problem has numerous applications in operations research and studies of computer operation. We devise efficient approximation algorithms, study their limitations, and derive worst-case bounds on the performance of the packings they produce.

A study IS made of the descriptive power of if then else statements and repeat (do forever) statements, multilevel break statements (which cause a jump out of an enclosing repeat), and multilevel next statements (which cause a jump to an iteration of an enclosing repeat) Ledgard and Marcotty conjectured that multilevel next statements could be removed without increasing the number of levels of break statements to obtain another program with operations executed in the same order The conjecture is shown to be true for one level of next statement but false for next statements with level greater than l It is also shown that next statements are weaker than break statements in the sense that n levels of next statements can be transformed into 2n levels of break statement, while there is no functionf such that n levels of break can be replaced by f(n) levels of next

When trees are denoted by “terms” or “parenthesized expressions”, which are strings, the class of top-down tree transducers (automata which map trees into trees and read their input trees from the root toward the leaves) form a subclass of a nondeterministic version of the generalized syntax directed translations of Aho and Ullman. It is shown that every nondeterministic syntax directed translation (NGSDT), and therefore every top-down tree transduction, can be carried out by a Turing machine which uses an amount of work space which is linear with respect to the size of the input and output. For every n, the family consisting of the images of recognizable sets of trees under the composition of n top-down transductions is shown to be properly contained in the family of deterministic context-sensitive languages.

This paper describes an algorithm which transforms a flowgraph into a program containing control constructs such as if then else statements, repeat (do forever) statements, multilevel break statements (causing jumps out of enclosing repeats), and multilevel next statements (causing jumps to iterations of enclosing repeats). The algorithm can be extended to create other types of control constructs, such as while or until. The program appears natural because the constructs are used according to common programming practices. The algorithm does not copy code, create subroutines, or add new variables. Instead, goto statements are generated when no other available control construct describes the flow of control. The algorithm has been implemented in a program called STRUCT which rewrites Fortran programs using constructs such as while, repeat, and if then else statements. The resulting programs are substantially more readable than their Fortran counterparts.

Structured programming emphasizes programming language constructs such as while loops, until loops, and if then else statements. Properly used, these constructs make occurrences of loops and branching of control obvious. They are preferable to goto statements, which tend to obscure the flow of control [DDH,DIJ]. This paper describes an algorithm which transforms a flowgraph into a program written using repeat (do forever) and if then else statements. The goal of the algorithm is to produce readable programs, rather than to avoid the use of goto statements entirely. goto statements are generated when there is no better way to describe the flow of control.

Interest in the study of sets of trees, tree languages, has led to the definition of finite automata which accept trees [2,11] and transducers which map trees into other trees [7,9,10]. These generalized machines may read treesfinite automata which accept trees [2,11] and of transducers which map trees into other trees [7,9,10]. These generalized machines may read trees either “top-down” (from the root toward the leaves) or “bottom-up” (from the leaves toward the root).