bluuebunny/crossref_metadata_2025 huggingface dataset:
Binary summation
Authors: Walker R. J.
Published: July 2002

In discussing his binary summation method [1] Linz mentions two defects: “It is more difficult to program than the standard method, and it is difficult to use unless all numbers are available at the start of the summation.” A defect not mentioned is the extra storage space (approximately
N
words) required for the

S
ij

. The last two of these three defects can be removed by proper combination of partial sums. In the adjacent PL/
I
program, the only storage needed is for the
M
-component vector
T
, where
M
≧ [log
2
N
].
N
must be even, and
B
is a number not expressible as a sum of
A
(
I
)'s, e.g.
B
= -1 if
A
(
I
) ≥ 0, or
B
= 1
E
+ 75 for reasonably sized
A
(
I
).
An efficient bit table technique for dynamic storage allocation of 2

n

-word blocks
Authors: Isoda Sadahiro , Goto Eiichi , Kimura Izumi
Published: July 2002

An efficient bit table technique for dynamic storage allocation of 2

n

-word blocks, which requires a minimized amount of memory for bookkeeping purposes, is described. The technique has been tested in an implementation of the list processing language L
6
. A number of ideas incorporated in the processor are also described.
A note on data base deadlocks
Authors: Baecker H. D.
Published: July 2002

In “Synchronization in a Parallel-Accessed Data Base” [
Comm. ACM 12
, 11 (Nov. 1969), 604-607] A. Shoshani and A. J. Bernstein have given a very lucid synthesis of diverse techniques to assure the integrity of a data base. But it appears that one of the factors in the synthesis, the entry hold count, will prevent the return of a node to the free list in precisely those circumstances for which they invoked the facility.
Note on an anomaly in paging
Authors: Pomeranz John E.
Published: July 2002

In [1] the authors use a lemma to prove their Theorem 1 (pp. 352-353). While the lemma is true, there is a defect in its proof, for one cannot assume that each of the symbols appearing as a type IV reference is in
t
(

E
k

,
s
). Using their example (p. 350) as a reference string with
k
= 12,
t
(
E
12
, 3) is 534 and lacks the two symbols (1 and 2) which appear as type IV references.
CODAS
Authors: Day R. H. , Mansfield M. K. , Ellis M. E.
Published: July 2002

CODAS, a Customer Oriented Data System, is a user-oriented data retrieval and display system. The command language of the system provides the user with an easy means for specifying data retrieval and display requests. Data is displayed as tables and graphs produced in a format ready for publication. In this paper the statements of the request language and the general system design are described.
Reconstruction of pictures from their projections
Authors: Gordon Richard , Herman Gabor T.
Published: July 2002

There are situations in the natural sciences and medicine (e.g. in electron microscopy and X-ray photography) in which it is desirable to estimate the gray levels of a digital picture at the individual points from the sums of the gray levels along straight lines (projections) at a few angles. Usually, in such situations, the picture is far from determined and the problem is to find the “most representative” picture. Three algorithms are described (all using Monte Carlo methods) which were designed to solve this problem. The algorithms are applicable in a large and varied number of fields. The most important uses may be the reconstruction of possibly asymmetric particles from electron micrographs and three-dimensional X-ray analysis.
Rapid computation of general interpolation formulas and mechanical quadrature rules
Authors: Gustafson Sven-Åke
Published: July 2002

Let ƒ have
n
continuous derivatives on a closed interval [
a, b
] and let
L
be a linear functional. The attempt is made to approximate
L
(ƒ) with
L
(
Q
) where
Q
is a polynomial, approximating ƒ. Algorithms are developed for rapid computation of
L
(
Q
) for a wide class of selections of
Q
which includes the Lagrangian and Hermitian rules as special cases.
Algorithm 417: Rapid computation of weights of interpolatory quadrature rules
Authors: Gustafson Sven-Åke
Published: July 2002

This algorithm is a companion to [1] where the theoretical background is described
Accelerating LP algorithms
Authors: Fox B. L.
Published: July 2002

It is shown how a novel method for computing (related) inner products can accelerate the pricing phase of LP algorithms. Other LP applications are indicated.
On the expected lengths of sequences generated in sorting by replacement selecting
Authors: Hooker William W.
Published: July 2002

In the replacement-selecting technique of sorting, one is interested in the ratio L
j
of the expected length of the
j
th sequence generated by the technique to the number of memory cells used. Using complex-variable theory, it is shown that L
j
→ 2 and that, asymtotically, the average interval between sign changes of L
j
— 2 is 2.6662.
Computer typesetting of ALGOL
Authors: von Sydow L.
Published: July 2002

An application of computer-aided typesetting is introduced. A working method is described for publishing ALGOL by computerized translation from Hardware into Reference representation, computerized planning of typographical layout and computerized control of a typesetting machine. The point is made that experts in science, technology, and programming are guaranteed a correct ALGOL documentation without spending valuable time and power on typographic considerations and proofreading.
Numerical Analysis: Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations
Authors: Bartels Richard H. , Golub Gene H.
Published: July 2002

An implementation of Stiefel's exchange algorithm for determining a Chebyshev solution to an overdetermined system of linear equations is presented, that uses Gaussian LU decomposition with row interchanges. The implementation is computationally more stable than those usually given in the literature. A generalization of Stiefel's algorithm is developed which permits the occasional exchange of two equations simultaneously.
Towards standards for handwritten zero and oh
Authors: Bemer R. W.
Published: July 2002

The Chairman of the ACM Standards Committee, Julien Green, has charged me with making “more effective use of
CACM
for communication … to get grass-roots opinions from the ACM membership.” This paper is the first attempt.

A partial dossier on distinguishing between handwritten zero and the letter oh is assembled here. This presentation was triggered by a request for guidance in this matter presented by the United Kingdom Delegation to ISO/TC97/SC2, Character Sets and Coding, at the meeting in Paris on 1967 March 13-16. The matter is just now in the province of USASI X3.6, to which comments might be directed.

Comments will be expected within sixty days [by approximately October 1st].
An efficient composite formula for multidimensional quadrature
Authors: Thacher Henry C.
Published: July 2002

A (2
s
+1)-point, second-degree quadrature formula for integration over an
s
-dimensional hyper-rectangle is presented. All but one of the points lie on the surface with weights of opposite sign attached to points on opposite faces. When a large volume is subdivided into congruent rectangular subdivisions, only one point is required in each interior subdivision to achieve second-degree accuracy.
Comments on “a continued operation notation”
Authors: Barnett M. P. , Gerard J. M. , Sambles A. W.
Published: July 2002

This note is intended to clarify and correct several points in a recent paper describing some notations for symbol manipulation by M. P. Barnett [
Comm. ACM 6
(August, 1963)].
Rounding problems in commercial data processing
Authors: Kelley Thomas B.
Published: July 2002

A common requirement in commercial data processing is that the sum of a set of numbers, rounded in a generally understood manner, be equal to the sum of the numbers rounded individually. Four rounding procedures are described to accomplish this. The particular procedure that is appropriate depends upon whether the numbers being accumulated can vary in sign, whether their sum can vary in sign, and whether the last number being summed can be recognized as such prior to its rounding.
The new program of work for the international standard vocabulary in computers and information processing
Authors: Traub J. F.
Published: July 2002

The Vocabulary Subcommittee of the International Standards Organization's Technical Committee on Computers and Information Processing (ISO/TC97/SC1) held its third meeting in New York City in May, 1964. (More precisely, this was the subcommittee's first meeting. Its earlier meetings in Geneva and Paris were as a Working Group.) The program of work agreed upon at the New York meeting marks a sharp reversal of SC1's earlier plans.
Computing blocking probabilities in multiclass wavelength routing networks
Authors: Ramesh Sridhar , Rouskas George N. , Perros Harry G.
Published: July 2002

We present an approximate analytical method to evaluate efficiently and accurately the call blocking probabilities in wavelength routing networks with multiple classes of calls. The model is fairly general and allows each source-destination pair to service calls of different classes, with each call occupying one wavelength per link. Our approximate analytical approach involves two steps. The arrival process of calls on some routes is first modified slightly to obtain an approximate multiclass network model. Next, all classes of calls on a particular route are aggregated to give an equivalent single-class model. Thus, path decomposition algorithms for single-class wavelength routing networks may be readily extended to the multiclass case. This article is a first step towards understanding the issues arising in wavelength routing networks that serve multiple classes of customers.
Requirements for real-time languages
Authors: Opler Ascher
Published: July 2002

Real-time languages have different requirements from other programming languages because of the special nature of their applications, the environment in which their object programs are executed and the environment in which they may be compiled. It may not be the language extensions that ultimately advance developments in the field. Progress may be made by attacking the special compiling and executing system problems that must be solved.
A nonrecursive method of syntax specification
Authors: Carr John W. , Welland Jerome
Published: July 2002

The use of the Kleene regular expression notation for describing algebraic language syntax, in particular of ALGOL, is described in this paper. A FORTRAN II computer program for carrying out the elimination algorithm of Gorn, similar to Gaussian elimination for linear systems of algebraic equations, is described. This was applied to numerous smaller languages, including some sublanguages of ALGOL. A hand calculation result of the application of the algorithm to all of ALGOL is given, thus expressing the Revised ALGOL 1960 syntax in completely nonrecursive terms, as far as its context-free portion is concerned. This description in many ways is far more intuitively understood than the previous recursive description, it is suggested. The paper also includes results of the machine program, which does not include a simplification algorithm.
A method for locating zeros of complex functions
Authors: Cain George L.
Published: July 2002

A method for computing the index, or winding number, is developed and applied to the problem of finding zeros of functions from the plane into the plane.
Applications of differential equations in general problem solving
Authors: Klopfenstein R. W.
Published: July 2002

A large class of problems leading to digital computer processing can be formulated in terms of the numerical solution of systems of ordinary differential equations. Powerful methods are in existence for the solution of such systems. A good general purpose routine for the solution of such systems furnishes a powerful tool for processing many problems. This is true from the point of view of ease of programming, ease of debugging, and minimization of computer time. A number of examples are discussed in detail.
An observation on bisection software for the symmetric tridiagonal eigenvalue problem
Authors: Kaufman Linda
Published: July 2002

In this article we discuss a small modification of the bisection routines in EISPACK and LAPACK for finding a few of the eigenvalues of a symmetric tridiagonal matrix
A
. When the principal minors of the matrix A yield good approximations to the desired eigenvalues, these modifications can yield about 30% reduction in the computation times.
AUTOMAST: automatic mathematical analysis and symbolic translation
Authors: Ball William E. , Berns Robert I.
Published: July 2002

A procedure for numerically solving systems of ordinary differential equations is shown to also generate symbolic solutions. The procedure is based on a finite Taylor series expansion that includes an estimate of the error in the final result. A computer program is described that reads in a system of such equations and then generates the expansions for all of the dependent variables. The expansions are determined symbolically, hence any non-numeric parameters in the original equations are carried automatically into the final expansions. Thus the exact influence of any parameters on the problem solution can be easily displayed.
Code extension in ASCII
Authors: Gorn S.
Published: July 2002

The American Standard Code for Information Interchange (ASCII) contains a number of control characters associated with the principle of
code extension
, that is, with the representation of information which cannot be directly represented by means of the characters in the Code. The manner of use of these characters has not previously been completely described.

This paper presents a set of mutually consistent philosophies regarding code extension applications, and suggests a corollary set of doctrines for the application of the code extension characters. Distinctions are drawn between code extension and such other concepts as “graphic substitution” or “syntactic representation” which are often used to meet similar requirements.

Also covered are certain topics which are not truly concerned with code extension but which are often linked with it in discussion on code applications.

The material in this paper is equally applicable in principle to the (proposed) ISO international 7-bit code for information interchange.
Computer capabilities at western european universities
Authors: Finerman Aaron
Published: July 2002

This report on the author's trip to universities in Western Europe in the summer of 1966 gives brief descriptions of computing activities at each institution visited. Present equipment capabilities vary from moderate to large scale; however, many institutions plan to acquire complex time-shared systems in the near future. In the author's opinion, the state of the art lags behind that on this continent. This lag is attributed to four principal factors: (a) the handicapping organization of academic procedures; (b) the university-government financial relationship; (c) the subordinated organization of the computing facility; (d) the paucity of professional interchange of knowledge. The effects of these constraints are explicated.
Multiplexing of slow peripherals
Authors: Abraham C. , Lance G. N. , Pearcey T.
Published: July 2002

The philosophy of a monitor which allows slow output devices to be multiplexed is presented.
Least squares fitting of planes to surfaces using dynamic programming
Authors: Gluss Brian
Published: July 2002

Dynamic programming has recently been used by Stone, by Bellman and by Gluss to determine the closest fit of broken line segments to a curve in an interval under the constraint that the number of segments is fixed. In the present paper successive models are developed to extend the method to the fitting of broken plane segments to surfaces
z
=
g
(
x, y
) defined over certain types of subareas of the (
x, y
)-space. The first model considers a rectangular area, with the constraint that the plane segments are defined over a grid in the (
x, y
)-space. It is then shown how this model may be incorporated into an algorithm that provides successive approximations to optimal fits for any type of closed area. Finally, applications are briefly described.
A comparison between the polyphase and oscillating sort techniques
Authors: Goetz Martin A. , Toth Gloria S.
Published: July 2002

Read-backward Polyphase sorting provides more efficient use of the tapes available to a sort than most other sorting techniques. Backward Polyphase produces a continuous merging process from
n
- 1 tapes where
n
is the total number of tapes being used in the sorting process. Any of the available presorting techniques may be used in conjunction with the Polyphase merge sort provided that the presort has the capability of producing both ascending and descending strings and distributing the strings on the various tapes as required by the Polyphase Merge.
A method of comparing the time requirements of sorting methods
Authors: Hall Michael H.
Published: July 2002

Formulas have been developed for estimating the sorting time required by most of the known internal sorting methods in terms of parameters describing the file to be sorted and the computer time required for basic sorting operations. Procedures are described for using these estimates to compare the efficiency of various methods, and results of several comparisons are given. A procedure to determine optimum combinations of sorting methods is shown. An expression for tape time required by a balanced merge sort is obtained, and difficulties in obtaining such expressions for cascade, polyphase and oscillating sorts are discussed.
A note on range transformations for square root and logarithm
Authors: Bemer R. W.
Published: July 2002

There was the germ of an idea in two previous papers [1, 2] which no one seems to have picked up in almost five years. For certain functions it seems desirable to transform the argument to a short range symmetric about 1.0. I will give examples of this usage for the square root and logarithm function for both binary and decimal machines.
Incompressible flow network calculations
Authors: Cantrell H. N.
Published: July 2002

A general method for the calculation of flows and pressures in fluid flow networks is presented. The method is applicable to computer use.
COBOL
Authors: Mackinson Thomas N.
Published: July 2002

COBOL (COmmon Business Oriented Language) is an English Language programming system which is capable of being implemented on a wide variety of electronic digital computers for use in the solution of business data processing problems.

The idea was conceived in May, 1959 at a meeting called in the Pentagon by Mr. Charles Phillips of the Office of the Assistant Secretary of Defense, Comptroller. The purpose of this meeting was to consider the desirability and the feasibility of establishing a common language for the programming of electronic computers for data processing. Representatives from computer user installations, both government and industrial, computer manufacturers, universities, and others concerned with computers were present. There was almost unanimous agreement that the project was both desirable and feasible. The COnference on DAta SYstems Languages (CODASYL) was established, and three committees were defined and staffed. These committees were the Short Range Committee, the Intermediate Range Committee, and the Long Range Committee. Each committee had its own goal and its own time scale. The coordination of the work to be performed was to be accomplished by an Executive Committee.
A generalized polyphase merge algorithm
Authors: Reynolds Samuel W.
Published: July 2002

The
k
-generalized Fibonacci numbers are defined as in [1]. A polyphase merge (merging an equal number of sequences from
k
tapes onto a single unused tape) using
k
+1 tapes is defined in terms of linear combinations of these numbers. A method is described to output sequences onto
k
of
k
+1 tapes after the internal sorting of elements to form sequences. This method will permit a polyphase merge of sequences of sorted elements provided that enough sequences are generated internally to place the proper numbers of sequences on each of the
k
tapes. For each value of
k
, there is a set of permissible numbers that can represent the total number of sequences generated during the original output process. If one of these numbers is met exactly and if there is a specific distribution of sequences on the
k
tapes, then a polyphase merge may proceed. If these conditions are not met, an algorithm is necessary to adjust the numbers of sequences to permit a polyphase merge. This paper describes such an algorithm.
A note on approximating
e
x
Authors: Lubkin S.
Published: July 2002

In reference to the discussion about evaluation

e
x

on page 500 of the September
Communications of the ACM
, may I point out that there is no need to use Mr. Berin's lengthy expressions to obtain relation (9). If we use the simple formula (5) for
x
/2 and divide by the same formula for -
x
/2, we get (9) immediately.
Two methods for word inversion on the IBM 709
Authors: Price Robert A.
Published: July 2002

In some logical problems it is necessary or convenient to invert the bit structure of a word, i.e., replace bit
i
by bit
n
+ 1 -
i
for
i
= 1, 2, ···,
n,
thus creating a mirror image. The method described here exploits the CAQ instruction of the IBM 709 (or 7090) to accomplish such an inversion rapidly (
n
= 36).
DATA-DIAL
Authors: Marill Thomas , Edwards Daniel , Feurzeig Wallace
Published: July 2002

An operating system is described which allows users to call up a remotely located computer from ordinary dial telephones. No special hardware or connections are required at the users' telephones. Input to the computer is through the telephone dial; output from the computer is in spoken form. Results of a test with telephones in the Boston area are reported.
A comparison of disks and tapes
Authors: Hess Herman
Published: July 2002

The principal characteristics of current magnetic disks and tape units are summarized and compared. Some of the characteristics of disk files are illustrated in a sorting example and compared to a tapesort. The conclusion is presented that disk files are competitive to tapes in some important applications.
Solution of Eigenvalue problems with approximately known Eigenvectors
Authors: Appel Klaus
Published: July 2002

It is often desired to solve eigenvalue problems of the type (A - λ1)C = 0 or (A - λB)C = 0 repeatedly for similar values of the matrix elements

A
ij

, where A and B are Hermitean or real symmetric matrices. Among the various methods to find all eigenvalues and eigenvectors, Jacobi's method of two-dimensional rotations [1] has been very popular for its numerical stability, although it is comparatively time-consuming. The purpose of this note is to show how existing subroutines can be used to reduce substantially the computing time, if approximate eigenvectors are known from the previous solution of a similar problem.
Coding clinical laboratory data for automatic storage and retrieval
Authors: Gross Leonard D.
Published: July 2002

A series of clinical laboratory codes have been developed to accept and store urinalysis, blood chemistry, and hematology test results for automatic data processing. The codes, although constructed as part of a computerized hospital simulation, have been able to handle the results of every laboratory test that they have encountered. The unique feature of these codes is that they can accept conventionally recorded qualitative as well as quantitative test results. Consequently, clinical test results need not be arbitrarily stratified, standardized, or altered in any way to be coded. This paper describes how the codes were developed and presents a listing of the urinalysis codes. Five criteria used in developing the codes are outlined and the problem of multiple-synonymous terminology is discussed. A solution to the problem is described. Flexible, computer-produced, composite laboratory reports are also discussed, along with reproduction of such a report. The paper concludes that even though many problems remain unsolved, the next ten years could witness the emergence of a practical automated information system in the laboratory.
Co-synthesis of pipelined structures and instruction reordering constraints for instruction set processors
Authors: Huang Ing-Jer
Published: July 2002

This paper presents a hardware/software co-synthesis approach to pipelined ISP (instruction set processor) design. The approach synthesizes the pipeline structure from a given instruction set architecture (behavioral) specification. In addition, it generates a set of reordering constraints that guides the compiler back-end (reorderer) to properly schedule instructions so that possible pipeline hazards are avoided and throughput is improved.

Co-synthesis takes place while resolving pipeline hazards, which can be attributed to interin-struction dependencies (IIDs). An extended taxonomy of IIDs have been proposed for the systematic analysis of pipeline hazards. Hardware/software methods are developed to resolve IIDs. Algorithms based on taxonomy and resolutions are constructed and integrated into the pipeline synthesis process to explore hardware and software design space. Application benchmarks are used to evaluate possible designs and guide the design decision. The power of the co-synthesis tool PIPER is demonstrated through pipeline synthesis of one illustrative example and two ISPs, including an industrial one (TDY-43). In comparison with other related approaches, our approach achieves higher throughput and provides a systematic way to explore the hardware/software trade-off.
Estimating small cell-loss ratios in ATM switches via importance sampling
Authors: L'Ecuyer Pierre , Champoux Yanick
Published: July 2002

The cell-loss ratio at a given node in an ATM switch, defined as the steady-state fraction of packets of information that are lost at that node due to buffer overflow, is typically a very small quantity that is hard to estimate by simulation. Cell losses are rare events, and importance sampling is sometimes the appropriate tool in this situation. However, finding the right change of measure is generally difficult. In this article, importance sampling is applied to estimate the cell-loss ratio in an ATM switch modeled as a queuing network that is fed by several sources emitting cells according to a Markov-modulated ON/OFF process, and in which all the cells from the same source have the same destination. The charge of measure is obtained via an adaptation of a heuristic proposed by Chang et al. {1994} for intree networks. The numerical experiments confirm important efficiency improvements even for large nonintree networks and a large number of sources. Experiments with different variants of the importance sampling methodology are also reported, and a number of practical issues are illustrated and discussed.
Natural language with discrete speech as a mode for human-to-machine
Authors: Biermann Alan W. , Rodman Robert D. , Rubin David C. , Heidlage J. Francis
Published: July 2002

A voice interactive natural language system, which allows users to solve problems with spoken English commands, has been constructed. The system utilizes a commercially available discrete speech recognizer which requires that each word be followed by approximately a 300 millisecond pause. In a test of the system, subjects were able to learn its use after about two hours of training. The system correctly processed about 77 percent of the over 6000 input sentences spoken in problem-solving sessions. Subjects spoke at the rate of about three sentences per minute and were able to effectively use the system to complete the given tasks. Subjects found the system relatively easy to learn and use, and gave a generally positive report of their experience.
Solving systems of partial differential equations using object-oriented programming techniques with coupled heat and fluid flow as example
Authors: Langtangen Hans Petter , Munthe Otto
Published: July 2002

This paper exploits object-oriented implementation techniques to facilitate the development computer codes for solving systems of coupled partial differential equations. We show how to build a simulator for equation systems by merging independent solvers for each equation that enters the system. The main goal is to obtain a rapid, robust, and reliable software development process with extensive reuse of implemented code. Coupled heat and fluid flow in pipes is used as example for illustrating the implementation techniques. We also present some results for the particular case of temperature-dependent generalized Newtonian fluid flow between two nonconcentric cylinders. The general applicability of the approach is discussed.
The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
Authors: Manber Udi , Tompa Martin
Published: July 2002

This work generalizes decision trees in order to study lower bounds on the running times of algorithms that allow probabilistic, nondeterministic, or alternating control. It is shown that decision trees that are allowed internal randomization (at the expense of introducing a small probability of error) run no faster asymptotically than ordinary decision trees for a collection of natural problems. Two geometric techniques from the literature for proving lower bounds on the time required by ordinary decision trees are shown to be special cases of one unified technique that, in fact, applies to nondeterministic decision trees as well. Finally, it is shown that any lower bound on alternating decision tree time also applies to alternating Turing machine time.
Integrated test of interacting controllers and datapaths
Authors: Nourani Mehrdad , Carletta Joan , Papachristou Christos
Published: July 2002

In systems consisting of interacting datapaths and controllers and
utilizing built-in self test (BIST), the datapaths and controllers are traditionally tested separately by isolating each component from the environment of the system during test. This work facilitates the testing of datapath/controller pairs in an
integrated fashion
. The key to the approach is the addition of logic to the system that interacts with the existing controller to push the effects of controller faults
into the data flow
, so that they can be observed at the datapath registers rather than directly at the controller outputs. The result is to reduce the BIST overhead over what is needed if the datapath and controller are tested independently, and to allow a more complete test of the interface between datapath and controller, including the faults that do not manifest themselves in isolation. Fault coverage and overhead results are given for four example circuits.
FastSlim
Authors: Jin Wei , Sun Xiaobai , Chase Jeffrey S.
Published: July 2002

Trace-driven simulation is a valuable tool for evaluating I/O systems. This article presents a new algorithm, called FASTSLIM, that reduces the size of I/O traces and improves simulation performance without compromising simulation accuracy.

FASTSLIM is more general than existing trace reduction algorithms in two ways. First, it is prefetch-safe: traces reduced by FASTSLIM yield provably exact simulations of I/O systems that use prefetching, a key technique for improving I/O performance. Second, FASTSLIM is compatible with a wide range of replacement policies, including common practical approximations to LRU. FASTSLIM-reduced traces are safe for simulations of storage hierarchies and systems with parallel disks.

This article gives a formal treatment of prefetching and replacement issues for trace reduction, introduces the FASTSLIM algorithm, proves that FASTSLIM and variants are safe for a broad range of I/O caching and prefetching systems, and presents empirical results comparing FASTSLIM to competing trace reduction algorithms.
External memory algorithms and data structures
Authors: Vitter Jeffrey Scott
Published: July 2002

Data sets in large applications are often too massive to fit completely inside the computers internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this article we survey the state of the art in the design and analysis of external memory (or EM) algorithms and data structures, where the goal is to exploit locality in order to reduce the I/O costs. We consider a variety of EM paradigms for solving batched and online problems efficiently in external memory. For the batched problem of sorting and related problems such as permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We also consider useful techniques for batched EM problems involving matrices (such as matrix multiplication and transposition), geometric data (such as finding intersections and constructing convex hulls), and graphs (such as list ranking, connected components, topological sorting, and shortest paths). In the online domain, canonical EM applications include dictionary lookup and range searching. The two important classes of indexed data structures are based upon extendible hashing and B-trees. The paradigms of filtering and bootstrapping provide a convenient means in online data structures to make effective use of the data accessed from disk. We also reexamine some of the above EM problems in slightly different settings, such as when the data items are moving, when the data items are variable-length (e.g., text strings), or when the allocated amount of internal memory can change dynamically. Programming tools and environments are available for simplifying the EM programming task. During the course of the survey, we report on some experiments in the domain of spatial databases using the TPIE system (transparent parallel I/O programming environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss are significantly faster than methods currently used in practice.
Paradigms for design and implementation in ADA
Authors: Rajlich Václav
Published: July 2002

An examination of the respective advantages and disadvantages of three characteristic paradigms of design and implementation in Ada illustrates the importance of choosing the appropriate paradigm for a given set of circumstances.
A federated architecture for information management
Authors: Heimbigner Dennis , McLeod Dennis
Published: July 2002

An approach to the coordinated sharing and interchange of computerized information is described emphasizing partial, controlled sharing among autonomous databases. Office information systems provide a particularly appropriate context for this type of information sharing and exchange. A federated database architecture is described in which a collection of independent database systems are united into a loosely coupled federation in order to share and exchange information. A federation consists of components (of which there may be any number) and a single federal dictionary. The components represent individual users, applications, workstations, or other components in an office information system. The federal dictionary is a specialized component that maintains the topology of the federation and oversees the entry of new components. Each component in the federation controls its interactions with other components by means of an export schema and an import schema. The export schema specifies the information that a component will share with other components, while the import schema specifies the nonlocal information that a component wishes to manipulate. The federated architecture provides mechanisms for sharing data, for sharing transactions (via message types) for combining information from several components, and for coordinating activities among autonomous components (via negotiation). A prototype implementation of the federated database mechanism is currently operational on an experimental basis.
Database concurrency control using data flow graphs
Authors: Eich M. H. , Wells David L.
Published: July 2002

A specialized data flow graph,
Database Flow Graph
(
DBFG
) is introduced. DBFGs may be used for scheduling database operations, particularly in an MIMD database machine environment. A DBFG explicitly maintains intertransaction and intratransaction dependencies, and is constructed from the Transaction Flow Graphs (TFG) of active transactions. A TFG, in turn, is the generalization of a query tree used, for example, in DIRECT [15].

All DBFG schedules are serializable and deadlock free. Operations needed to create and maintain the DBFG structure as transactions are added or removed from the system are discussed. Simulation results show that DBFG scheduling performs as well as two-phase locking.
Parallel text search methods
Authors: Salton Gerard , Buckley Chris
Published: July 2002

A comparison of recently proposed parallel text search methods to alternative available search strategies that use serial processing machines suggests parallel methods do not provide large-scale gains in either retrieval effectiveness or efficiency.
Modeling california earthquakes and earth structures
Authors: Raugh Michael R.
Published: July 2002

Seismology has burgeoned into a modern science—force-fed by federal funding to advance technology for detecting underground nuclear explosions and predicting earthquakes, and by industry to improve tools for gas and oil exploration. Computers, seismic instrument systems, telemetry, and data reduction have played key roles in this growth.
KMS: a distributed hypermedia system for managing knowledge in organizations
Authors: Akscyn Robert M. , McCracken Donald L. , Yoder Elise A.
Published: July 2002

Developers of hypermedia systems face many design issues. The design for KMS, a large-scale hypermedia system for collaborative work, seeks improved user productivity through simplicity of the conceptual data model.
Revolutionizing the Traditional Classroom Course
Authors: Schank Roger C.
Published: July 2002

Is the computer the device that can change the campus as we know it?
Global Applications of Collaborative Technology
Authors: Davison Robert , De Vreede Gert-Jan
Published: July 2002

Collaborative technologies, sometimes referred to as "groupware applications" given their deployment to support groups of individuals engaging in collaborative tasks, have developed rapidly in the last few years. Much of this expansion has been fueled by the dramatic increases in Internet penetration in societies around the world, making it possible for globally distributed teams to work on projects. We see these technologies being applied in a variety of ways, ranging from organizational communication and decision making to distributed software inspections and development to virtual education initiatives. The systems themselves include an array of technologies that may include video- and audioconferencing, shared calendaring, (digital) document management systems, text-based group support systems, and many more.
HTTP Cookies
Authors: Kristol David M.
Published: July 2002

How did we get from a world where cookies were something you ate and where "nontechies" were unaware of "Netscape cookies" to a world where cookies are a hot-button privacy issue for many computer users? This article describes how HTTP "cookies" work and how Netscape's original specification evolved into an IETF Proposed Standard. I also offer a personal perspective on how what began as a straightforward technical specification turned into a political flashpoint when it tried to address nontechnical issues such as privacy.
Optimizing designs containing black boxes
Authors: Liu Tai-Hung , Aziz Adnan , Singhal Vigyan
Published: July 2002

We are concerned with optimizing gate-level netlists containing “black boxes,” that is, components whose functionality is not available to the optimization tool. We establish a notion of equivalence for gate-level netlists containing black boxes, and prove that it is sound and complete. We show that conventional approaches to optimizing such netlists fail to fully exploit the don't care flexibility available for synthesis. Based on our new notion of equivalence, we introduce a procedure that computes the complete don't care set. Experiments indicate that our procedure can achieve more minimization than conventional synthesis.
Why the digital millennium copyright act is a failure of reason
Authors: Grosso Andrew
Published: July 2002

What technologists consider speech, lawyers and courts consider hardware. Therein lies the problem with building effective legislation around code.
Introductory AI educational resources on the web
Authors: Amant Robert St. , Young R. Michael
Published: July 2002

Fortunately for people seeking to learn more about artificial intelligence, a wide range of general and introductory educational materials related to AI is available on the Web. The Web resources described below, available both in electronic form and as pointers to conventional media such as books or videos, are not, however, of interest just to university educators and their students. Many of them are of broad scope and are useful to information technology specialists or AI practitioners seeking a starting-off point from which to improve their knowledge of the field. Some of the materials listed here will also be of use to educators in high schools or middle schools where AI topics may play a role in course curricula.
Call it techonomics
Authors: McGinity Meg
Published: July 2002

New product cycles powered by R&D are just what the economy ordered.
Register-machine based processes
Authors: Bergstra Jan A. , Ponse Alban
Published: July 2002

We study extensions of the process algebra axiom system
ACP
with two recursive operations: the
binary Kleene star
*
, which is defined by
x
*
y
=
x
(
x
*
y
+
y
, and the
push-down
operation
$
, defined by
x
$
y
=
x
((
x
$
y
)(
x
$
y
)) +
y
. In this setting it is easy to represent register machine computation, and an equational theory results that is not decidable. In order to increase the expressive power, abstraction is then added: with
rooted branching bisimulation equivalence
each computable process can be expressed, and with
rooted ô-bisimilarity
each semi-computable process that initially is finitely branching can be expressed. Moreover, with abstraction and a finite number of auxiliary actions these results can be obtained without binary Kleene star. Finally, we consider two alternatives for the push-down operation. Each of these gives rise to similar results.
Vrije Universiteit
Authors: van der Veer Gerrit C. , Puerta Mari Carmen , Eliëns Anton , Chisalita Cristina , Smit Janke
Published: July 2002

Multimedia and Culture is a new master's program in computer science that takes four years of full-time study. About half of the curriculum consists of computer science classes, and the other half is made up of highly multidisciplinary content including humanities (psychology, anthropology, and ethnography), human-computer interaction (theory, task analysis, and practical design projects), artistic design and crafts, and modern culture (relation between literature and visual arts, and music).
Integrated IT management tool kit
Authors: Ben-Menachem Mordechai , Gelbard Roy
Published: July 2002

The tools track IT assets, performance, budgets, and resources, managing system development and deployment in the interests of the organization's strategic goals.
Tuple sequences and lexicographic indexes
Authors: Abiteboul Serge , Ginsburg Seymour
Published: July 2002

The concept of a tuple sequence is introduced in order to investigate structure connected with relational model implementation. Analogs are presented for the relational operations of projection, join, and selection, and the decomposition problem for tuple sequences is considered. The lexicographical ordering of tuple sequences is studied via the notion of (lexicographic) index. A sound and complete set of inference rules for indexes is exhibited, and two algorithmic questions related to indexes examined. Finally, indexes and functional dependencies in combination are studied.
Elimination of intersection anomalies from database schemes
Authors: Beeri Catriel , Kifer Michael
Published: July 2002

The desirability of acyclic (conflict-free) schemes is well argued in [8] and [13]. When a scheme is described by multivalued dependencies, acyclicity means that the dependencies do not split each other's left-hand side and do not form
intersection anomalies
. It is shown that if the second condition fails to hold, the scheme can be amended so that it does hold. The basic step is to add one attribute and some dependencies to resolve one intersection anomaly. This step generates an extension of the given scheme in which the anomaly does not exist. Also, the iterative use of the basic step is analyzed and it is proved that the transformation so defined terminates and removes all intersection anomalies.
Factory automation and robotics
Authors: Bernstein Herbert J.
Published: July 2002

Selected from papers presented at the Symposium on Factory Automation and Robotics held September 9-11, 1985, at New York University
A recursive algorithm for binary multiplication and its implementation
Authors: De Mori Renato , Cardin Régis
Published: July 2002

A new recursive algorithm for deriving the layout of parallel multipliers is presented. Based on this algorithm, a network for performing multiplications of two's complement numbers is proposed. The network can be implemented in a synchronous or an asynchronous way. If the factors to be multiplied have
N
bits, the area complexity of the network is
O
(

N
2

) for practical values of
N
as in the case of cellular multipliers. Due to the design approach based on a recursive algorithm, a time complexity
O
(log
N
) is achieved.

It is shown how the structure can he pipelined with period complexity
O
(1) and used for single and double precision multiplication.
A society model for office information systems
Authors: Ho Cheng-Seen , Hong Yang-Chang , Kuo Te-Son
Published: July 2002

A
society
model, which characterizes the behavior and procedure of offices, is proposed. It is our belief that an office system capable of dealing with all real office problems only through the modeling of the internal behavior of an office can be developed. In this society model, office entities are viewed as
agents
. An agent is modeled as a
microsociety
of interacting knowledge sources. Within the microsociety, there exists a
microknowledge exchange system
, which provides a set of microknowledge exchange protocols as a coordination system among those knowledge sources during their cooperative reasoning process. An office is then modeled as a society of various interacting agents using their knowledge to complete the office goals cooperatively. It is this unified view that allows offices to be modeled in a flexible and general way.
Numerical experience with sequential quadratic programming algorithms for equality constrained nonlinear programming
Authors: Shanno David F. , Phua Kang Hoh
Published: July 2002

Computational experience is given for a sequential quadratic programming algorithm when LaGrange multiplier estimates, Hessian approximations, and merit functions are varied to test for computational efficiency. Indications of areas for further research are given.
The category-partition method for specifying and generating fuctional tests
Authors: Ostrand T. J. , Balcer M. J.
Published: July 2002

A method for creating functional test suites has been developed in which a test engineer analyzes the system specification, writes a series of formal test specifications, and then uses a generator tool to produce test descriptions from which test scripts are written. The advantages of this method are that the tester can easily modify the test specification when necessary, and can control the complexity and number of the tests by annotating the tests specification with constraints.