bluuebunny/crossref_metadata_2025 huggingface dataset:
Computing Partitions with Applications to the Knapsack Problem
Authors: Horowitz Ellis , Sahni Sartaj
Published: July 2002

Given
r
numbers
s
1
, …,

s
r

, algorithms are investigated for finding all possible combinations of these numbers which sum to
M
. This problem is a particular instance of the 0-1 unidimensional knapsack problem. All of the usual algorithms for this problem are investigated in terms of both asymptotic computing times and storage requirements, as well as average computing times. We develop a technique which improves all of the dynamic programming methods by a square root factor. Empirical studies indicate this new algorithm to be generally superior to all previously known algorithms. We then show how this improvement can be incorporated into the more general 0-1 knapsack problem obtaining a square root improvement in the asymptotic behavior. A new branch and search algorithm that is significantly faster than the Greenberg and Hegerich algorithm is also presented. The results of extensive empirical studies comparing these knapsack algorithms are given
Comments on a Paper by Gaver
Authors: Balkovich E. , Chiu W. , Presser L. , Wood R.
Published: July 2002

In a 1967 publication, D. P. Gaver studied a probabilistic model of a multiprogramming computer system. His results have been utilized recently by a number of authors. However, we have observed that Gaver's results contain inconsistencies. These inconsistencies are discussed in detail and a correction suggested and verified through an independent derivation.
The Undecidability of the Existence of Zeros of Real Elementary Functions
Authors: Wang Paul S.
Published: July 2002

From Richardson's undecidability results, it is shown that the predictive “there exists a real number
r
such that
G
(
r
) = 0” is recursively undecidable for
G
(
x
) in a class of functions which involves polynomials and the sine function. The deduction follows that the convergence of a class of improper integrals is recursively undecidable.
Allocating Storage for Extendible Arrays
Authors: Rosenberg Arnold L.
Published: July 2002

Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be appended dynamically). In this paper, the problem of allocating storage for extendible arrays is examined in the light of the author's earlier work on data graphs and addressing schemes. A formal analog of the assertion that simplicity of array extension precludes simplicity of traversal (marching along rows/columns) is proved. Two strategies for constructing extendible realizations of arrays are formulated, and certain inherent limitations of such realizations are established.
Semi-Implicit Runge-Kutta Procedures with Error Estimates for the Numerical Integration of Stiff Systems of Ordinary Differential Equations
Authors: Cash J. R.
Published: July 2002

A
-stable, semi-implicit Runge-Kutta procedures requiring at most one Jacobian evaluation per time step are developed for the approximate numerical integration of stiff systems of ordinary differential equations. A simple procedure for estimating the local truncation error is described and, with the help of this estimate, efficient integration procedures are derived. The algorithms are illustrated by direct application to a particular example.
Interactive ELLPACK
Authors: Dyksen Wayne R. , Ribbens Calvin J.
Published: July 2002

ELLPACK is a versatile, very high-level language for solving elliptic partial differential equations.
Solving elliptic problems with ELLPACK typically involves a process in which one repeatedly
computes a solution, analyzes the results, and modifies the solution technique. Although this process
is best suited for an interactive environment, ELLPACK itself is batch oriented. With this in mind,
we have developed Interactive ELLPACK, an extension of ELLPACK that provides true interactive
elliptic problem solving by allowing the user to interactively build grids, choose solution methods,
and analyze computed results. Interactive ELLPACK features a sophisticated interface with window-
ing, color graphics output, and graphics input.
A partial pivoting strategy for sparse symmetric matrix decomposition
Authors: Liu Joseph W. H.
Published: July 2002

It is well known that the partial pivoting strategy by Bunch and Kaufman is very effective for
factoring dense symmetric indefinite matrices using the diagonal pivoting method. In this paper, we
study a threshold version of the strategy for sparse symmetric matrix decomposition. The use of this
scheme is explored in the multifrontal method of Duff and Reid for sparse indefinite systems.
Experimental results show that it is at least as effective as the existing pivoting strategy used in the
current multifrontal implementation.
The fault span of crash failures
Authors: Varghese George , Jayaram Mahesh
Published: July 2002

A
crashing
network protocol is an asynchronous protocol whose memory does not survive crashes. We show that a crashing network protocol that works over unreliable links can be driven to arbitrary global states, where each node is in a state reached in some (possibly different) execution, and each link has an arbitrary mixture of packets sent in (possibly different) executions. Our theorem considerably generalizes an earlier result, due to Fekete et al., which states that there is no correct crashing Data Link Protocol. For example, we prove that there is no correct crashing protocol for token passing and for many other resource allocation protocols such as
k
-exclusion, and the drinking and dining philosophers problems. We further characterize the reachable states caused by crash failures using reliable non-FIFO and reliable FIFO links. We show that with reliable non-FIFO links any acyclic subset of nodes and links can be driven to arbitrary states. We show that with reliable FIFO links, only nodes can be driven to arbitrary states. Overall, we show a
strict
hierarchy in terms of the set of states reachable by crash failures in the three link models.
Sequential abstract-state machines capture sequential algorithms
Authors: Gurevich Yuri
Published: July 2002

We examine sequential algorithms and formulate a sequential-time postulate, an abstract-state postulate, and a bounded-exploration postulate . Analysis of the postulates leads us to the notion of sequential abstract-state machine and to the theorem in the title. First we treat sequential algorithms that are deterministic and noninteractive. Then we consider sequential algorithms that may be nondeterministic and that may interact with their environments.
Simulation in exponential families
Authors: Barbe Philippe , Broniatowski Michel
Published: July 2002

An acceptance-rejection algorithm for the simulation of random variables in statistical exponential families is described. This algorithm does not require any prior knowledge of the family, except sufficient stati stics and the value of the parameter. It allows simulation from many members of the exponential family. We present some bounds on computing time, as well as the main properties of the empirical measures of samples simulated by our methods (functional Glivenko-Cantelli and central limit theorems). This algorithm is applied in order to evaluate the distribution of M-estimators under composite alternatives; we also propose its use in Bayesian statistics in order to simulate from posterior distributions.
Efficient optimal design space characterization methodologies
Authors: Blythe Stephen A. , Walker Robert A.
Published: July 2002

One of the primary advantages of a high-level synthesis system is its ability to explore the design space. This paper presents several methodologies for design space exploration that compute
all
optimal tradeoff points for the combined problem of scheduling, clock-length determination, and module selection. We discuss how each methodology takes advantage of the structure within the design space itself as well as the structure of, and interactions among, each of the three subproblems. (CAD)
A codesign back-end approach for embedded system design
Authors: Gogniat G. , Auguin M. , Bianco L. , Pegatoquet A.
Published: July 2002

Continuous advances in processor and ASIC technologies enable the integration of more and more complex embedded systems. Since their implementations generally require the use of heterogeneous resources (e.g., processor cores, ASICs) in one system with stringent design constraints, the importance of hardware/software codesign methodologies increases steadily. Interfacing heterogeneous hardware and software components together through a communication structure is particularly error prone and time consuming. Hence, on the basis of a generic architecute dedicated to telecommunication and multimedia applications, we proposed an extended communication synthesis method that provides characterization of communications and their implementation schemes in the target architecture. This method takes place after the partitioning and scheduling phase and may constitute the basis of a back-end of a codesign framework leading to HW/SW integration.
Balancing cooperation and risk in intrusion detection
Authors: Frincke Deborah
Published: July 2002

Early systems for networked intrusion detection (or, more generally, intrusion or misuse management) required either a centralized architecture or a centralized decision-making point, even when the data gathering was distributed. More recently, researchers have developed far more decentralized intrusion detection systems using a variety of techniques. Such systems often rely upon data sharing between sites which do not have a common administrator and therefore cooperation will be required in order to detect and respond to security incidents. It has therefore become important to address cooperation and data sharing in a formal manner.

In this paper, we discuss the detection of distributed attacks across cooperating enterprises. We begin by defining relationships between cooperative hosts, then use the take-grant model to identify both when a host could identify a widespread attack and when that host is at increased risk due to data sharing. We further refine our definition of potential identification using access, integrity, and cooperation policies which limit sharing. Finally, we include a brief description of both a simple Prolog model encorporating data sharing policies and a prototype cooperative intrusion detection system.
How to vectorize the algebraic multilevel iteration
Authors: Grosz Lutz
Published: July 2002

We consider the algebraic multilevel iteration (AMLI) for the solution of systems of linear equations as they arise form a finite-difference discretization on a rectangular grid. Key operation is the matrix-vector product, which can efficiently be executed on vector and parallel-vector computer architectures if the nonzero entries of the matrix are concentrated in a few diagonals. In order to maintain this structure for all matrices on all levels coarsening in alternating directions is used. In some cases it is necessary to introduce additional dummy grid hyperplanes. The data movements in the restriction and prolongation are crucial, as they produce massive memory conflicts on vector architectures. By using a simple performance model the best of the possible vectorization strategies is automatically selected at runtime. Examples show that on a Fujitsu VPP300 the presented implementation of AMLI reaches about 85% of the useful performance, and scalability with respect to computing time can be achieved.
Limited bit manipulation using FORTRAN II
Authors: Oster C. A.
Published: July 2002

Techniques are developed for manipulating bits using only FORTRAN II. These techniques allow individual bits to be tested, certain fields to be shifted, and numbers coded in BCD to be converted to Binary.
A family of test matrices
Authors: Newbery A. C. R.
Published: July 2002

A family of test matrices with the following properties is described here: (a) an explicit inverse is given; (b) the characteristic polynomial is easily obtained; (c) a large measure of control over the eigenvalues is possible; (d) in special cases the eigenvalues and eigenvectors can be given explicitly, and the
P
-condition number can be arbitrarily assigned.
A class of matrices to test inversion procedures
Authors: Cline Randall E.
Published: July 2002

The test matrices given by M. L. Pei [
Comm. ACM 5
, 10 (Oct. 1962), 508] and R. D. Rodman [
Comm. ACM 6
, 9 (Sept. 1963, 515] are special cases of a general class of matrices with complex elements for which an explicit form of the inverse can be exhibited. This class of matrices is such that eigenvalues and a set of associated eigenvectors can also be obtained. Then not only inverses, but also eigenvalues of the Pei matrix given by W. S. Lasor [
Comm. ACM 6
, 3 (Mar. 1963), 102] and eigenvectors given by A. R. C. Newberry [
Comm. ACM 6
, 9 (Sept. 1963), 515], and eigenvalues of the Rodman matrix follow as special cases.
Note on the use of procedures
Authors: Healy M. J. R.
Published: July 2002

The very generality of a language like ALGOL renders it inefficient when a number of programs have to be written all dealing with a fairly narrow range of problems. This can be largely overcome by the construction of a package of suitable procedures, each of which embodies a fairly substantial piece of computation that will be required in several different contexts (see, for example [1]). A program for a specific purpose will consist of a set of these procedures linked by a more or less skeletal main program.
A model for type checking
Authors: Ledgard Henry F.
Published: July 2002

Most current programming languages treat computation over different classes of objects (e.g. numbers, strings, labels and functions). For correct compilation and execution, the following question then arises: is a program properly constructed so that its operations and operands are compatible? The activity of answering this question is usually called type checking.

This paper attempts to isolate the notion of type checking and presents a partial solution to the type checking problem based on the notions of abstraction and application of functions. In particular, a program is mapped into an expression within a decideable subset of the λ-calculus, which characterizes the type relations within the program and eliminates all other information. The determination of the type-wise correctness or incorrectness of the program is resolved by reducing its corresponding λ-calculus expression to one of two normal forms, the constant “correct” for a type-wise correct program or the constant “error.”

An application to type checking in Algol 60 is made, and the attendant problems faced for any notion of type checking are discussed.
A note on optimal doubly-chained trees
Authors: Kennedy Steve
Published: July 2002

This note concerns the recent paper by Hu [2] dealing with doubly-chained trees of the type introduced by Sussenguth [9]. In the second part of the paper, Hu deals with the problem of constructing an optimum weighted doubly-chained tree, under the standard assumption that no key is allowed to prefix another, as found, for example, in Patt [6]. He states that for the weights and elements of Figure 1, the optimum doubly-chained tree with all nodes reachable in less than five steps is the one shown in Figure 2. This tree is obtained from the optimal binary tree constructed in Hu and Tan [3], using the technique found in Knuth [5]. But the doubly-chained tree constructed by this method comes from an artificially restricted class of doubly-chained trees, and is thus not optimal in the sense usually defined in the literature [6-9] and described below. This fact is recognized by Hu [1], but was not explicitly stated in the paper in question.
An Unclever Time-Sharing System
Authors: Foster Caxton C.
Published: July 2002

This paper describes the internal structure of a time-sharing system in some detail. This system is dedicated to providing remote access, and has a simple file structure. It is intended for use in a university type environment where there are many short jobs that will profit from one- or two-second turnaround. Despite its simplicity, this system can serve as a useful introduction to the problems encountered by the designers of any time-sharing system. Included are a discussion of the command language, the hardware organization toward which the design is oriented, the general internal organization, the command sequences, the CPU scheduler, handling of interrupts, the assignment of core space, execution and control of the user's program, backup storage management, and the handling of errors.
Data Security
Authors: Denning Dorothy E. , Denning Peter J.
Published: July 2002

The rising abuse of computers and increasing threat to personal privacy through data banks have stimulated much interest in the technical safeguards for data. There are four kinds of safeguards, each related to but distinct from the others. Access controls regulate which users may enter the system and subsequently which data sets an active user may read or write. Flow controls regulate the dissemination of values among the data sets accessible to a user. Inference controls protect statistical databases by preventing questioners from deducing confidential information by posing carefully designed sequences of statistical queries and correlating the responses. Statistical data banks are much less secure than most people believe. Data encryption attempts to prevent unauthorized disclosure of confidential information in transit or in storage. This paper describes the general nature of controls of each type, the kinds of problems they can and cannot solve, and their inherent limitations and weaknesses. The paper is intended for a general audience with little background in the area.
Use of tree structures for processing files
Authors: Sussenguth Edward H.
Published: July 2002

In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted to the file alterations. Conversely, a chained file allocation permits elcient alteration but cannot be searched efficiently. A file organized into a tree-like structure is discussed, and it is shown that such a file may both be searched and altered with times proportional to
s
log,
N
, where
N
is the number of file items and
s
is a parameter of the tree. It is also shown that optimizing the value of
s
leads to a search time which is only 25 per cent slower than the binary search. The tree organization employs two data chains and may be considered to be a compromise between the organizations for the binary search and the chained file. The relation of the tree organization to multidimensional indexing and to the trie structure is also discussed.
The quadratic quotient method
Authors: Bell James R.
Published: July 2002

Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its elimination is presented. Comparisons with previous methods are made both analytically and empirically.
The computational metaphor and quantum physics
Authors: Manthey Michael J. , Moret Bernard M.E.
Published: July 2002

Concurrent computational systems, viewed as sets of cooperating processes, are shown to have close analogies in the world of quantum physics. In particular, analogies exist between processes and particles, between a process' state and a particle's mass, between a process'state changes and a particle's velocity, and between interprocess communications and particle interactions. This view allows the application in the computational world of special relativity theory, the uncertainty principle, the law of conservation of momentum, and many of particle physics' fundamental results. This paper describes the basic analogy and some fundamental results. It is the authors' belief that new insights into a computational processes will be gained as the analogy is developed and vice versa. It is conceivable that established results of the computational sciences may contribute to a new understanding of some of the problems of physics. Other process-oriented sciences, such as biology, economics, and psychology, could also benefit from such development.
Updating a database in an unsafe environment
Authors: Hinxman Anthony I.
Published: July 2002

Normally, when an application makes use of a database, considerable resources are invested in maintaining the integrity of that database. However, in situations where use of a database may be desirable even though the normal level of resources is unavailable, a simple technique using a partitioned data file protects the database if immediate transaction recording is not essential.
From Washington: The STARS program
Authors: Steier Rosalie
Published: July 2002

In 1979 the Department of Defense started its “software initiative,” an effort to maintain U.S. leadership in computer technology for support of its military systems. The “software initiative” evolved into the Software Technology for Adaptable Reliable Systems program (STARS), first outlined in the “Strategy for a DoD Software Initiative” in October 1982 and later refined in the “STARS Program Strategy” in March 1983. STARS is intended to address DoD software problems in the same way the Very High Speed Integrated Circuits
1
program (VHSIC) is intended to ameliorate DoD hardware limitations in defense systems. The basic plan is a cooperative effort of government, industry, and academia in software technology. Industry is offered contractual incentives; both industry and academia are encouraged to contribute their best talent.
Precision averaging for real-time analysis
Authors: Cloutier Mark J. , Friedman Matthew J.
Published: July 2002

An analysis of the computation of the arithmetic mean using only single-precision fixed-point arithmetic is presented. This is done to ease the timing constraints common to many on-line applications. Others have introduced several averaging algorithms in floating-point arithmetic for use in inferential statistics. In this paper, these algorithms are evaluated with respect to their feasibility as fixed-point methods in the context of real-time analysis. Modifications of these algorithms are presented, and previously unpublished ones are introduced in the interest of avoiding overflow (necessary) and minimizing truncation errors (highly desirable). All algorithms presented are tested for speed and accuracy on several sets of data, including their own “worst case.” The applicability of each algorithm is discussed with respect to some of the basic functions that real-time programs must perform.
A virtual memory system for picture processing
Authors: Wada Ben Tsutom
Published: July 2002

A virtual memory system designed specifically for picture processing, Raster Handler 2 provides programs with efficient access to pixels. It features square partition of images, imbalanced allocation of frames, and nondemand page replacement. RH2 is implemented in software and incorporates a prepaging algorithm designed specifically for picture processing.
From Washington
Authors: Steier Rosalie
Published: July 2002

We are entering a new era in very high performance computing that will be dominated by parallel architectured systems. It is critical for the United States to maintain its leadership as this new era, with its broadened applications, evolves over the next decade. Toward this end the National Science Foundation sponsored a workshop in November 1983 to focus the collective strength of universities, industry, and government on projects for development of knowledge-intensive industries.
Dhrystone
Authors: Weicker Reinhold P.
Published: July 2002

Reflecting current data on the use of programming language constructs in systems programming, a synthetic benchmark is constructed based on the distribution appearing in the data. The benchmark executes 100 Ada statements that are balanced in terms of the distribution of statement types, data types, and data locality. Pascal and C versions of the benchmark are discussed.
Superconvergent interpolants for collocation methods applied to mixed-order BVODEs
Authors: Enright Wayne H. , Sivasothinathan Ramanan
Published: July 2002

Continuous approximations to boundary value problems in ordinary differential equations (BVODEs), constructed using collocation at Gauss points, are more accurate at the mesh points than at off-mesh points. From these approximations, it is possible to construct improved continuous approximations by extending the high accuracy that is available at the mesh points to off-mesh points. One possibility is the bootstrap approach, which improves the accuracy of the approximate solution at the off-mesh points in a sequence of steps until the accuracy at the mesh points and off-mesh points is consistent. A bootstrap approach for systems of mixed-order BVODEs is developed to improve approximate solutions produced by COLNEW, a Gauss-collocation-based software package. An implementation of this approach is discussed and numerical results presented which confirm that the improved approximations satisfy the predicted error bounds and are relatively inexpensive to construct.
Strip trees: a hierarchical representation for curves
Authors: Ballard Dana H.
Published: July 2002

The use of curves to represent two-dimensional structures is an important part of many scientific investigations. For example, geographers use curves extensively to represent map features such as contour lines, roads, and rivers. Circuit layout designers use curves to specify the wiring between circuits. Because of the very large amount of data involved and the need to perform operations on this data efficiently, the representation of such curves is a crucial issue. A hierarchical representation consisting of binary trees with a special datum at each node is described. This datum is called a strip and the tree that contains such data is called a strip tree. Lower levels in the tree correspond to finer resolution representations of the curve. The strip tree structure is a direct consequence of using a special method for digitizing lines and retaining all intermediate steps. This gives several desirable properties. For curves that are well-behaved, intersection and point-membership (for closed curves) calculations can be solved in 0(log
n
) where
n
is the number of points describing the curve. The curves can be efficiently encoded and displayed at various resolutions. The representation is closed under intersection and union and these operations can be carried out at different resolutions. All these properties depend on the hierarchical tree structure which allows primitive operations to be performed at the lowest possible resolution with great computational time savings.

Strip trees is a linear interpolation scheme which realizes an important space savings by not representing all the points explicitly. This means that even when the overhead of the tree indexing is added, the storage requirement is comparable to raster representations which do represent most of the points explicitly.
HISDL—a structure description language
Authors: Lim Willie Y.-P.
Published: July 2002

The features of a language designed for the description of the structure of computer systems are described. The structure of a system is specified hierarchically as an interconnection of components with each component being a named instance of a component type. The system itself is another component type. The interconnection between components is specified in two ways: either by specifying all the ports that are connected together, or by specifying a component and the ports that are connected to its ports. A structure specification is a list of such connection specifications. The language has an iterative construct for specifying highly regular structures, and a conditional construct is also provided. A component type can be recursively specified while parameterization of component type specifications is supported. The latter is particularly useful for specifying classes of components of similar structure.
Timestamps in key distribution protocols
Authors: Denning Dorothy E. , Sacco Giovanni Maria
Published: July 2002

The distribution of keys in a computer network using single key or public key encryption is discussed. We consider the possibility that communication keys may be compromised, and show that key distribution protocols with timestamps prevent replays of compromised keys. The timestamps have the additional benefit of replacing a two-step handshake.
Conversion of decision tables to efficient sequential testing procedures
Authors: Sethi I. K. , Chatterjee B.
Published: July 2002

Sequential testing procedures for checking the rule-applicability of the decision tables encountered in practice are usually found to be minimum-path-length trees. On the basis of this observation, an algorithm is developed for converting decision tables to efficient decision trees. A criterion is defined for estimating the minimum expected cost of the tree in terms of rule probabilities and condition-testing costs and is utilized in arriving at the efficient decision tree. The algorithm is applicable to general limited-entry decision tables and can also be employed for manual coding.
Hierarchical binary search
Authors: Gill Arthur
Published: July 2002

In hierarchical search the data structure holding the file keys is partitioned into substructures of the same type; these are searched consecutively until the queried key is found or the substructures are exhausted. The interest here is in the conditions under which the performance of a hierarchical organization of static files is superior to that of the nonhierarchical organization and in the construction of the hierarchy when these conditions are met. The performance criterion is the average number of comparisons in a successful search, where averaging extends over all keys and over all permutations of the key's access probabilities. General properties of hierarchical search are first derived, and attention is then focused on the hierarchical binary organization—the special case where each of the data substructures is a sorted array (or a balanced binary tree) and where the keys are accessed by binary search. It is shown that an advantageous two-stage hierarchy is always implementable when the keys' access density function
φ
(
i
) is “steeper” than Zipf's density function
ζ
(
i
)—the steeper it is, the greater the advantage. A simple method for constructing the two-stage hierarchy is formulated, based on finding the intersection of
φ
(
i
) and
ζ
(
i
). For the
r
-stage hierarchical organization, partitioning procedures are proposed which are based on the iterative application of the two-stage techniques.
Logical construction of software
Authors: Chand Donald R. , Yadav Surya B.
Published: July 2002

The authors contend that it is both possible and necessary to clearly demark and explicitly define the transition between the software design and software implementation phases of the software life cycle. The output of the software design phase is defined to be a logical design of software, and the logical design can be described explicitly if the software is viewed as a system of data sets and data transforms. Logical Construction of Software (LCS) is a software design methodology that guides the designer in defining and describing these software components and their relationships. The methodology is illustrated via a practical application.
The paradigms of programming
Authors: Floyd Robert W.
Published: July 2002

Today I want to talk about the paradigms of programming, how they affect our success as designers of computer programs, how they should be taught, and how they should be embodied in our programming languages.
Proving termination with multiset orderings
Authors: Dershowitz Nachum , Manna Zohar
Published: July 2002

A common tool for proving the termination of programs is the
well-founded set
, a set ordered in such a way as to admit no infinite descending sequences. The basic approach is to find a
termination function
that maps the values of the program variables into some well-founded set, such that the value of the termination function is repeatedly reduced throughout the computation. All too often, the termination functions required are difficult to find and are of a complexity out of proportion to the program under consideration.

Multisets
(
bags
) over a given well-founded set
S
are sets that admit multiple occurrences of elements taken from
S
. The given ordering on
S
induces an ordering on the finite multisets over
S
. This
multiset ordering
is shown to be well-founded. The multiset ordering enables the use of relatively simple and intuitive termination functions in otherwise difficult termination proofs. In particular, the multiset ordering is used to prove the termination of
production systems
, programs defined in terms of sets of rewriting rules.
Analysis of design alternatives for virtual memory indexes
Authors: Maruyama K. , Smith S. E.
Published: July 2002

A class of index structures for use in a virtual memory environment is described. Design alternatives within this class of index structures are analyzed. These alternatives include a choice of search strategy, whether or not pages in the index are stuctured, and whether or not keys are compressed. The average cost of retrieving entries from these indexes is expressed as a weighted sum of the cost of a basis key comparison and the cost of crossing a page boundary in the index structure. Formulas for the retrieval costs possible combinations of design alternatives are given. These are used in numerical case studies which compare the retrieval costs of the alternatives. Qualitative comparisons of the maintenance costs (insertion, deletion, reorganization) of the design alternatives are also included.
A note on conditional expressions
Authors: Friedman Daniel P. , Wise David S.
Published: July 2002

Evaluation of a conditional expression may succeed even when the “deciding predicate” diverges and the alternatives are records (or nodes) whose fields have different content.
Using encryption for authentication in large networks of computers
Authors: Needham Roger M. , Schroeder Michael D.
Published: July 2002

Use of encryption to achieve authenticated communication in computer networks is discussed. Example protocols are presented for the establishment of authenticated connections, for the management of authenticated mail, and for signature verification and document integrity guarantee. Both conventional and public-key encryption algorithms are considered as the basis for protocols.
Development of an international system for legal protection of computer programs
Authors: Smoot Oliver R.
Published: July 2002

Is execution of a program “copying?” If a program is copyrighted, is execution an infringement of the copyright?

Is an algorithm, or a program, or a computer running a program, patentable?

If a program is licensed as a trade secret to
N
users with a nondisclosure clause, at what point is
N
so large as to be the equivalent of publication?

How far can old laws be stretched to accommodate new technology?

How can developing countries gain access to the computer software they need?

Questions such as these increasingly have concerned software developers and lawyers since computer programs first began to be sold. Now international diplomats responding to the call of the developing nations for increased assistance in their development are asking similar questions.
Weighted derivation trees
Authors: Loui Michael C.
Published: July 2002

The nodes of a weighted derivation tree are associated with weighting functions over the vocabulary of a context-free grammar. An algorithm is presented for constructing the optimal derivation tree having the same structure as a given weighted derivation tree. In addition, the correctness of the algorithm is established. The method may be applied to problems involving probabilistic parsing or combinatorial optimization.
A method of bivariate interpolation and smooth surface fitting based on local procedures
Authors: Akima Hiroshi
Published: July 2002

A method is designed for interpolating values given at points of a rectangular grid in a plane by a smooth bivariate function
z
=
z
(
x, y
). The interpolating function is a bicubic polynomial in each cell of the rectangular grid. Emphasis is on avoiding excessive undulation between given grid points. The proposed method is an extension of the method of univariate interpolation developed earlier by the author and is likewise based on local procedures.
Emotional content considered dangerous
Authors: Smoliar Stephen W.
Published: July 2002

I had hoped that Moorer's rebuttal to my short communication in the November 1972 Communications would close the debate on a topic which, like the computer itself, has provoked an inordinately large quantity of unqualified argument. Unfortunately, the short communications by McMorrow and Wexelblat in the May 1973 Communications lead me to believe that my position is still grossly misunderstood. Therefore, allow me to clarify these matters.
Comments on a paper by T.C. Chen and I.T. Ho
Authors: Smith Alan Jay
Published: July 2002

Tien Chi Chen and Irving T. Ho in their paper “Storage-Efficient Representation of Decimal Data” [1] present a scheme for the compression of numbers stored in binary coded decimal (BCD) form. Their compression scheme involves coding two or three digits at a time in seven bit or ten bit fields and requires only permutations, deletions, and insertions for coding and decoding. We would like to briefly present some alternatives to their compression method and to discuss the relative advantages of these other methods.
Minimal-total-processing time drum and disk scheduling disciplines
Authors: Fuller Samuel H.
Published: July 2002

This article investigates the application of minimal-total-processing-time (MTPT) scheduling disciplines to rotating storage units when random arrival of requests is allowed. Fixed-head drum and moving-head disk storage units are considered, and emphasis is placed on the relative merits of the MTPT scheduling discipline with respect to the shortest-latency-time-first (SLTF) scheduling discipline. The results of the simulation studies presented show that neither scheduling discipline is unconditionally superior to the other. For most fixed-head drum applications, the SLTF discipline is preferable to MTPT, but for intra-cylinder disk scheduling the MTPT discipline offers a distinct advantage over the SLTF discipline. The computational requirements of an algorithm that implements the MTPT scheduling discipline are shown to be comparable to SLTF algorithms. In both cases, the sorting procedure is the most time-consuming phase of the algorithm.
Merging with parallel processors
Authors: Gavril Fănică
Published: July 2002

Consider two linearly ordered sets
A, B
, |
A
| =
m
, |
B
| =
n, m
≤
n
, and
p, p
≤
m
, parallel processors working synchronously. The paper presents an algorithm for merging
A
and
B
with the
p
parallel processors, which requires at most 2⌈log
2
(2
m
+ 1)⌉ + ⌊3
m
/
p
⌋ + [
m
/
p
][log
2
(
n
/
m
)] steps. If
n
= 2

β

m
(
β
an integer), the algorithm requires at most 2[log
2
(
m
+ 1)] + [
m
/
p
](2 +
β
) steps. In the case where
m
and
n
are of the same order of magnitude, i.e.
n
=
km
with
k
being a constant, the algorithm requires 2[log
2
(
m
+ 1)] + [
m
/
p
](3 +
k
) steps. These performances compare very favorably with the previous best parallel merging algorithm, Batcher's algorithm, which requires
n
/
p
+ ((
m
+
n
)/2
p
)log
2
m
steps in the general case and
km
/
p
+ ((
k
+ 1)/2)(
m
/
p
)log
2
m
in the special case where
n
=
km
.
Optimizing static calendar queues
Authors: Erickson K. Bruce , Ladner Richard E. , Lamarca Anthony
Published: July 2002

The calendar queue is an important implementation of a priority queue that is particularly useful in discrete event simulators. We investigate the performance of the static calendar queue that maintains
N
active events. The main contribution of this article is to prove that, under reasonable assumptions and with the proper parameter settings, the calendar queue data structure will have constant (independent of
N
) expected time per event processed. A simple formula is derived to approximate the expected time per event. The formula can be used to set the parameters of the calendar queue to achieve optimal or near optimal performance. In addition, a technique is given to calibrate a specific calendar queue implementation so that the formula can be applied in a practical setting.
Computers and urban society
Authors: Sturman Gerald M.
Published: July 2002

This brief survey of the use of computers in urban society covers the broad range of activities found in any city. The future scope of applications is limited only by the imagination and inventiveness of future system designers, programmers, analysts, and decision makers. The computer can be, if properly used, with respect for human dignity and civil liberty, a significant factor in improving the efficiency of the urban process. It is expected that the benefits of such computer usage will outweigh the costs and that we may look forward to an expansion of such usage.
Interchange rolls of perforated tape for information interchange
Authors: Lynn M. Stuart
Published: July 2002

This proposed American National Standard has been accepted for publication by American National Standards (formerly USASI) Committee X3, Computers and Information Processing. In order that the final version of the proposed standard reflect the largest public consensus, X3 authorized publication of this document to elicit comment and general public reaction, with the understanding that such a working document is an intermediate result in the standardization process and is subject to change, modification, or withdrawal in part or in whole. Comments should be addressed to the X3 Secretary, Business Equipment Manufacturers Association, 235 East 42 Street, New York, NY 10017.—C.K.
Efficient multiprogramming resource allocation and accounting
Authors: Hamlet R. G.
Published: July 2002

Although sometimes thought of as only a component of time-sharing operation, multiprogramming can involve broader questions of resource allocation, since fairness is not required to meet a response criterion. In a multiprogrammed system, it may serve maximal resource use to be unfair, for example by holding an input/output channel idle for a program while it completes a small amount of processor usage, enabling further use of the channel. Several applications of this principle are given, and it is suggested that a multiprogramming executive might dynamically adjust its allocation algorithms to gain efficiency.

Allocation of resources is closely connected to accounting for those resources, raising the problems of repeatability, minimal uncharged overhead, and relative weighting of charges for dependent resources. Since weightings may depend on allocation algorithms, these are not arbitrary accounting parameters. Often the only repeatable accounting is one which omits an extensive overhead; this overhead can be multiple-charged to all programs which benefit from it, so that in the worst case the overhead will be paid, and should multiprogramming prove efficient, overcharges will result.

Multiprogramming turns on allocation of the memory resource essential to control of other resources. The general suggestions for allocation and accounting are applied to this question, and some details provided for the case of a monitor which controls a virtual-memory machine.
On the near-optimality of the shortest-latency-time-first drum scheduling discipline
Authors: Stone Harold S. , Fuller Samuel H.
Published: July 2002

For computer systems in which it is practical to determine the instantaneous drum position, a popular discipline for determining the sequence in which the records are to be accessed is the so-called shortest-latency-time-first, SLTF, discipline. When a collection of varying-length records is to be accessed from specified drum positions, it is known that the SLTF discipline does not necessarily minimize the drum latency time. However, we show that the total time to access the entire collection for any SLTF schedule is never as much as a drum revolution longer than a minimum latency schedule.
Creation and control of internal data bases under a Fortran programming environment
Authors: DeSalvio A. J. , Purdy J. G. , Rau J.
Published: July 2002

A method is described for the definition of a user's COMMON structure and the automatic generation of the necessary COMMON, DIMENSION, EQUIVALENCE, and type declarations for each of the user's routines. The definition for the COMMON is contained in an easy to modify form, thus allowing the control of general communications of data between routines. The described system has been implemented on the IBM 7094, CDC 6000 series, and the IBM 360. The method has proved to be invaluable for the definition and control of COMMON in many large-scale programs.
Comment on Lawler's multilevel Boolean minimization
Authors: de Vries Ronald C.
Published: July 2002

Lawler [1] proposed a method of multilevel Boolean minimization which is a generalization of the conventional prime implicant approach for two-level minimization. In his article, he presented two lemmas (Lemmas 1 and 2) that are important in reducing the number of calculations involved in obtaining a solution. These lemmas can be extended to increase the efficiency even more. In particular, it is possible to lower the upper limit of the function interval for an incompletely specified function [2]. Later, the extended version of these lemmas will be shown to be of value in several aspects of the minimization procedure.
Addendum to a multiple-precision division algorithm
Authors: Mifsud Charles J. , Bohlen Michael J.
Published: July 2002

In [1] Mifsud presented a generalized division algorithm for positive integral operands. The uniqueness of the method was advertised as causing each trial cipher in the quotient to be either equal to or one greater than its final replacement. The method of describing the algorithm was intended to stress the simple mathematical facts that were the basis of the algorithm. However, some difficulty arises with the programming and implementation of the algorithm. Article [1] addressed itself to the calculation of the trial cipher by using the first two digits of the partial dividend (step 6); i.e. it formed [
p
r+1

p
r

/

d
r

], with
p

r
+1

<

d
r

, where the bracket is used to indicate the integral part of its content. Thus the paper conveniently avoided the possibility of overflow which would happen if
p

r
+1

=

d
r

.
On the probability distribution of the values of binary trees
Authors: Hurwitz H.
Published: July 2002

An integral equation is derived for the generating function for binary tree values, the values reflecting sorting effort. The analysis does not assume uniformly distributed branching ratios, and therefore is applicable to a family of sorting algorithms discussed by Hoare, Singleton, and van Emden. The solution to the integral equation indicates that using more advanced algorithms in the family makes only minor reductions in the expected sorting efforts, but substantially reduces the variance in sorting effort.

Statistical tests of the values of several thousand trees containing up to 10,000 points have given first, second, and third moments of the value distribution function in satisfactory agreement with the moments computed from the generating function. The empirical tests, as well as the analytical results, are in agreement with previously pubished results for the first moment in the cases of uniform and nonuniform distribution of branching ratio, and for the second moment in the case of uniform distribution of branching ratio.