bluuebunny/crossref_metadata_2025 huggingface dataset:
APPL/A
Authors: Sutton Stanley M. , Heimbigner Dennis , Osterweil Leon J.
Published: July 2002

Software process programming is the coding of software processes in executable programming languages. Process programming offers many potential benefits, but their realization has been hampered by a lack of experience in the design and use of process programming languages. APPL/A is a prototype software process programming language developed to help gain this experience. It is intended for the coding of programs to represent and support software processes including process, product, and project management. APPL/A is defined as an extension to Ada, to which it adds persistent programmable relations, concurrent triggers on relation operations (for reactive control), optionally and dynamically enforceable predicates on relations (which may serve as constraints), and composite statements that provide alternative combinations of serializability, atomicity, and consistency enforcement (for programming high-level transactions). APPL/A has been used to code engineering-oriented applications, like requirements specification and design, as well as management-related activities, such as personnel assignment, task scheduling, and project monitoring. APPL/A has also enabled us to experiment with process program design techniques and architectures, including process state reification, intermittent (or persistent) processes, reflexive and metaprocesses, and multiple-process systems. Our ability to address a wide range of software processes and process characteristics indicates that the APPL/A constructs represent important and general capabilities for software process programming.—
Authors' Abstract
The measured performance of personal computer operating systems
Authors: Chen J. Bradley , Endo Yasuhiro , Chan Kee , Mazières David , Dias Antonio , Seltzer Margo , Smith Michael D.
Published: July 2002

This article presents a comparative study of the performance of three operating systems that run on the personal computer architecture derived form the IBM-PC. The operating systems, Windows for Workgroups, Windows NT, and NetBSD (a freely available variant of the UNIX operating system), cover a broad range of system functionality and user requirements, from a single-address-space model to full protection with preemptive multitasking. Our measurements are enable by hardware counters in Intel's Pentium processor that permit measurement of a broad range of processor events including instruction counts and on-chip cache miss counts. We use both microbenchmarks, which expose specific difference between the systems, and application workloads, which provide an indication of expected end-to-end performance. Our microbenchmark results show that accessing system functionality is often more expensive in Windows for Workgroups than in the other two systems due to frequent changes in machine mode and the use of system call hooks. When running native applications, Windows NT is more efficient than Windows, but it incurs overhead similar to that of a microkernel, since its application interface (the Win32 API) is implemented as a user-level server. Overall, system functionality can be accessed most efficiently in NetBSD; we attribute this to its monolithic structure and to the absence of the complications created by hardware backward-compatibility requirements in the other systems. Measurements of application performance show that although the impact of these differences is significant in terms of instruction counts and other hardware events (often a factor of 2 to 7 difference between the systems), overall performance is sometimes determined by the functionality provided by specific subsystems, such as the graphics subsystem or the file system buffer cache.
Creating presentation slides
Authors: Johnson Jeff A. , Nardi Bonnie A.
Published: July 2002

We conducted a study to investigate the use of generic versus task-specific application software by people who create and maintain presentation slides. Sixteen people were interviewed to determine how they prepare slides, what software they use to prepare and maintain slides, and how well the software they use supports various aspects of the task. The informants varied in how central slidemaking was to their jobs. The hypotheses driving the study were that: (1) some software applications are task generic, intended for use in a wide variety of tasks, while others are task specific, intended to support very specific tasks; (2) task-specific software is preferable, but is often not used because of cost, learning effort, or lack of availability, and (3) people who infrequently perform a task tend to use generic tools, while people who often perform it tend to use task-specific tools. Our findings suggest that several factors influence choice of slidemaking software, including desired quality, production time, user skill, willingness to use multiple tools, whether people work alone or in teams, and company policy. Furthermore, the task specificity/genericness of an application program is not a simple matter of
degree
, because it depends on several fairly independent software design issues. We (1) conclude that developing application software that supports all aspects of a task well is extremely difficult and (2) suggest an alternative approach that may be more fruitful: providing collections of interoperable tools and services.
An efficient algorithm for sequential random sampling
Authors: Vitter Jeffrey Scott
Published: July 2002

We examine several methods for drawing a sequential random sample of
n
records from a file containing
N
records. Method D is recommended for general use. The algorithm is on-line (so that CPU time can be overlapped with I/O), has a small constant memory requirement, and is easy to program. An improved implementation is detailed in the Appendix.
Information system behavior specification by high level Petri nets
Authors: Oberweis Andreas , Sander Peter
Published: July 2002

The specification of an information system should include a description of structural system aspects as well as a description of the system behavior. In this article, we show how this can be achieved by high-level Petri nets—namely, the so-called NR/T-nets (Nested-Relation/Transition Nets). In NR/T-nets, the structural part is modeled by nested relations, and the behavioral part is modeled by a novel Petri net formalism. Each place of a net represents a nested relation scheme, and the marking of each place is given as a nested relation of the respective type. Insert and delete operations in a nested relational database (NF2-database) are expressed by transitions in a net. These operations may operate not only on whole tuples of a given relation, but also on “subtuples” of existing tuples. The arcs of a net are inscribed with so-called Filter Tables, which allow (together with an optional logical expression as transition inscription) conditions to be formulated on the specified (sub-) tuples. The occurrence rule for NR/T-net transitions is defined by the operations union, intersection, and “negative” in lattices of nested relations. The structure of an NR/T-net, together with the occurrence rule, defines classes of possible information system procedures, i.e., sequences of (possibly concurrent) operations in an information system.
A high-speed network interface for distributed-memory systems
Authors: Steenkiste Peter
Published: July 2002

Distributed-memory systems have traditionally had great difficulty performing network I/O at rates proportional to their computational power. The problem is that the network interface has to support network I/O for a supercomputer, using computational and memory bandwidth resources similar to those of a workstation. As a result, the network interface becomes a bottleneck. In this article we present an I/O architecture that addresses these problems and supports high-speed network I/O on distributed-memory systems. The key to good performance is to partition the work appropriately between the system and the network interface. Some communication tasks are performed on the distributed-memory parallel system, since it is more powerful and less likely to become a bottleneck than the network interface. Tasks that do not parallelize well are performed on the network interface, and hardware support is provided for the most time-critical operations. This architecture has been implemented for the iWarp distributed-memory system and has been used by a number of applications. We describe this implementaiton, present performance results, and use application examples to validated the main features of the I/O architecture.
Recent developments in high-level synthesis
Authors: Lin Youn-Long
Published: July 2002

We survey recent developments in high level synthesis technology for VLSI design. The need for higher-level design automation tools are discussed first. We then describe some basic techniques for various subtasks of high-level synthesis. Techniques that have been proposed in the past few years (since 1994) for various subtasks of high-level synthesis are surveyed. We also survey some new synthesis objectives including testability, power efficiency, and reliability.
Contexts—a partitioning concept for hypertext
Authors: Delisle Norman M. , Schwartz Mayer D.
Published: July 2002

Hypertext systems provide good information management support for a wide variety of documentation efforts. These efforts range from developing software to writing a book. However, existing hypertext systems provide poor support for collaboration among teams of authors. This paper starts by briefly describing properties of several existing hypertext systems. Then several models for forming partitions in a hypertext database are examined and contexts, a partitioning scheme that supports multiperson cooperative efforts, are introduced. The semantic issues involved in defining contexts are explored in detail.
Safe query languages for constraint databases
Authors: Revesz Peter Z.
Published: July 2002

In the database framework of Kanellakis et al. [1990] it was argued that constraint query languages should take constraint databases as input and give other constraint databases that use the same type of atomic constraints as output. This closed-form requirement has been difficult to realize in constraint query languages that contain the negation symbol. This paper describes a general approach to restricting constraint query languages with negation to safe subsets that contain only programs that are evaluable in closed-form on any valid constraint database input.
High dictionary compression for proactive password checking
Authors: Bergadano Francesco , Crispo Bruno , Ruffo Giancarlo
Published: July 2002

The important problem of user password selection is addressed and a new proactive password-checking technique is presented. In a training phase, a decision tree is generated based on a given dictionary of weak passwords. Then, the decision tree is used to determine whether a user password should be accepted. Experimental results described here show that the method leads to a very high dictionary compression (up to 1000 to 1) with low error rates (of the order of 1%). A prototype implementation, called ProCheck, is made available online. We survey previous approaches to proactive password checking, and provide an in-depth comparison.
An object-oriented framework for block preconditioning
Authors: Chow Edmond , Heroux Michael A.
Published: July 2002

General software for preconditioning the iterative solution of linear systems is greatly lagging behind the literature. This is partly because specific problems and specific matrix and preconditioner data structures in order to be solved efficiently, i.e., multiple implementations of a preconditioner with specialized data structures are required. This article presents a framework to support preconditioning with various, possibly user-defined, data structures for matrices that are partitioned into blocks. The main idea is to define data structures for the blocks, and an upper layer of software which uses these blocks transparently of their data structure. This transparency can be accomplished by using an object-oriented language. Thus, various preconditioners, such as block relaxations and block-incomplete factorizations, only need to be defined once and will work with any block type. In addition, it is possible to transparently interchange various approximate or exact techniques for inverting pivot blocks, or solving systems whose coefficient matrices are diagonal blocks. This leads to a rich variety of preconditioners that can be selected. Operations with the blocks are performed with optimized libraries or fundamental data types. Comparisons with an optimized Fortran 77 code on both workstations and Cray supercomputers show that this framework can approach the efficiency of Fortran 77, as long as suitable block sized and block types are chosen.
UFO
Authors: Alexandrov Albert D. , Ibel Maximilian , Schauser Klaus E. , Scheiman Chris J.
Published: July 2002

In this article we show how to extend a wide range of functionality of standard operation systems completely at the user level. Our approach works by intercepting selected system calls at the user level, using tracing facilities such as the /proc file system provided by many Unix operating systems. The behavior of some intercepted system calls is then modified to implement new functionality. This approach does not require any relinking or recompilation of existing applications. In fact, the extensions can even be dynamically “installed” into already running processes. The extensions work completely at the user level and install without system administrator assistance. Individual users can choose what extensions to run, in effect creating a personalized operating system view for themselves. We used this approach to implement a global file system, called Ufo, which allows users to treat remote files exactly as if they were local. Currently, Ufo supports file access through the FTP and HTTP protocols and allows new protocols to be plugged in. While several other projects have implemented global file system abstractions, they all require either changes to the operating system or modifications to standard libraries. The article gives a detailed performance analysis of our approach to extending the OS and establishes that Ufo introduces acceptable overhead for common applications even though intercepting individual system calls incurs a high cost.
A formal approach to the definition and the design of conceptual schemata for databased systems
Authors: Zaniolo Carlo , Melkaoff Michel A.
Published: July 2002

A formal approach is proposed to the definition and the design of conceptual database diagrams to be used as conceptual schemata in a system featuring a multilevel schema architecture, and as an aid for the design of other forms of schemata. We consider E-R (entity-relationship) diagrams, and we introduce a new representation called
CAZ
-graphs. A rigorous connection is established between these diagrams and some formal constraints used to describe relationships in the framework of the relational data model. These include functional and multivalued dependencies of database relations. The basis for our schemata is a combined representation for two fundamental structures underlying every relation: the first defined by its minimal atomic decompositions, the second by its elementary functional dependencies.

The interaction between these two structures is explored, and we show that, jointly, they can represent a wide spectrum of database relationships, of which the well-known one-to-one, one-to-many, and many-to-many associations constitute only a small subset. It is suggested that a main objective in conceptual schema design is to ensure a complete representation of these two structures. A procedure is presented to design schemata which obtain this objective while eliminating redundancy. A simple correspondence between the topological properties of these schemata and the structure of multivalued dependencies of the original relation is established. Various applications are discussed and a number of illustrative examples are given.
Introduction to the electronic symposium on computer-supported cooperative work
Authors: Mills Kevin L.
Published: July 2002

Computer-supported cooperative work (CSCW) holds great importance and promise for modern society. This paper provides an overview of seventeen papers comprising a symposium on CSCW. The overview also discusses some relationships among the contributions made by each paper, and places those contributions into a larger context by identifying some of the key challenges faced by computer science reseachers who aim to help us work effectively as teams mediated through networks of computers. The paper also describes why the promise of CSCW holds particular salience for the U.S. military. In the context of a military setting, the paper describes five particular challenges for CSCW researchers. While most of these challenges might seem specific to military environments, many others probably already face similar challenges, or soon will, when attempting to collaborate through networks of computers. To support this claim, the paper includes a military scenario that might hit fairly close to home for many, and certainly for civilian emergency response personnel. After discussing the military needs for collaboration technology, the paper briefly outlines for motivation for a recent DARPA research program along these lines. That program, called Intelligent Collaboration and Visualization, sponsored the work reported in this symposium.
Bounded index exponential hashing
Authors: Lomet David B.
Published: July 2002

Bounded index exponential hashing, a new form of extendible hashing, is described. It has the important advantages over most of the other extendible hashing variants of both (i) providing random access to any record of a file in close to one disk access and (ii) having performance which does not vary with file size. It is straightforward to implement and demands only a fixed and specifiable amount of main storage to achieve this performance. Its underlying physical disk storage is readily managed and record overflow is handled so as to insure that unsuccessful searches never take more than two accesses. The method's ability to access data in close to a single disk access makes it possible to organize a database, in which files have a primary key and multiple secondary keys, such that the result is a significant performance advantage over existing organizations.
EAS-E
Authors: Malhotra A. , Markowitz H. M. , Pazel D. P.
Published: July 2002

EAS-E
(pronounced EASY) is an experimental programming language integrated with a database management system now running on VM/370 at the IBM Thomas J. Watson Research Center. The EAS-E programming language is built around the entity, attribute, and set (
EAS
) view of application development. It provides a means for translating operations on EAS structures directly into executable code. EAS-E commands have an English-like syntax, and thus EAS-E programs are easy to read and understand. EAS-E programs are also more compact than equivalent programs in other database languages.

The EAS-E database management system allows many users simultaneous access to the database. It supports locking and deadlock detection and is capable of efficiently supporting network databases of various sizes including very large databases, consisting of several millions of entities stored on multiple DASD extends. Also available is a nonprocedural facility that allows a user to browse and update the database without writing programs.
Independent components of relations
Authors: Rissanen Jorma
Published: July 2002

In a multiattribute relation or, equivalently, a multicolumn table a certain collection of the projections can be shown to be independent in much the same way as the factors in a Cartesian product or orthogonal components of a vector. A precise notion of independence for relations is defined and studied. The main result states that the operator which reconstructs the original relation from its independent components is the natural join, and that independent components split the full family of functional dependencies into corresponding component families. These give an easy-to-check criterion for independence.
New Formulas for Computing Incomplete Elliptic Integrals of the First and Second Kind
Authors: DiDonato A. R. , Hershey A. V.
Published: July 2002

New series expansions are developed for computing incomplete elliptic integrals of the first and second kind when the values of the amplitude and modulus are large. The classical series, which are obtained after a binomial expansion of the integrands, are used when the values of the amplitude and modulus are small. The range of use of each series is so selected as to maintain a minimum of rounding error. A special criterion is used to determine when the binomial series should be terminated.

The calculation of elliptic integrals by these series expansions is compared with the calculation by the previously established Landen transformation, which has been used by Legendre. The new series yield more accurate results and the average time of computation is 30 per cent shorter. The computing program in the NORC subroutine for the calculation of elliptic integrals is described.
Automatic Document Classification Part II . Additional Experiments
Authors: Borko Harold , Bernick Myrna
Published: July 2002

This study reports the results of a series of experiments in the techniques of automatic document classification. Two different classification schedules are compared along with two methods of automatically classifying documents into categories. It is concluded that, while there is no significant difference in the predictive efficiency between the Bayesian and the Factor Score methods, automatic document classification is enhanced by the use of a factor-analytically-derived classification schedule. Approximately 55 percent of the document were automatically and correctly classified.
Conversion of Limited-Entry Decision Tables to Optimal Computer Programs I: Minimum Average Processing Time
Authors: Reinwald Lewis T. , Soland Richard M.
Published: July 2002

This paper begins with a brief description of desicion tables, and then presents a discussion of alternative expressions for them as sequential testing procedures for computer implementation and as Boolean functions. An algorithm is developed which, in a finite number of steps, will convert any given limited entry decision table into an “optimal” computer program, one with minimum average processing time. The algorithm is more general than procedures previously developed and guarantees optimality of the resultant computer program. Previous procedures required two distinct steps and gave no assurance of overall optimality. Computer implementation of the algorithm is also discussed.
Some Binary Derivation Systems
Authors: Sibert E. E. , Michie D.
Published: July 2002

Previous studies of heuristic search techniques have usually considered situations for which the search space could be represented as a tree, which limits the applicability of the results obtained. Here Kowalski is followed and a more general formulation in terms of derivation graph is offered; the graphs correspond rather naturally to the search problems arising in automatic theorem proving and other areas. We consider a family of search procedures controlled by evaluation functions of a very general sort, having the form ƒ
Δ
(

x, L
k

), where

L
k

is that portion of the graph generated thus far by the procedure, and the node
x
is a candidate for incorporation into

L
k

. Completeness and minimality results are obtained for a number of procedures in this family, including methods analogous to those of Moore, Dijkstra, and Pohl.
Multikey access methods based on superimposed coding techniques
Authors: Sacks-Davis R. , Kent A. , Ramamohanarao K.
Published: July 2002

Both single-level and two-level indexed descriptor schemes for multikey retrieval are presented and compared. The descriptors are formed using superimposed coding techniques and stored using a bit-inversion technique. A fast-batch insertion algorithm for which the cost of forming the bit-inverted file is less than one disk access per record is presented. For large data files, it is shown that the two-level implementation is generally more efficient for queries with a small number of matching records. For queries that specify two or more values, there is a potential problem with the two-level implementation in that costs may accrue when blocks of records match the query but individual records within these blocks do not. One approach to overcoming this problem is to set bits in the descriptors based on pairs of indexed terms. This approach is presented and analyzed.
Beware of linear congruential generators with multipliers of the form
a
= ±2

q

±2

r
Authors: L'Ecuyer Pierre , Simard Richard
Published: July 2002

Linear congruential random-number generators with Mersenne prime
modulus and multipliers of the form
a
= ±2

q

±

r

have been proposed recently. Their main advantage is the availability of a simple and fast implementation algorithm for such multipliers. This note generalizes this algorithm, points out statistical weaknesses of these multipliers when used in a straightforward manner, and suggests in what context they could be used safely.
Simultaneous reference allocation in code generation for dual data memory bank ASIPs
Authors: Sudarsanam Ashok , Malik Sharad
Published: July 2002

We address the problem of code generation for DSP systems on a chip. In such systems, the amount of silicon devoted of program ROM is limited, so application software must be sufficiently dense. Additionally, the software must be written so as to meet various high-performance constraints, which may include hard real-time constraints. Unfortunately, current compiler technology is unable to generate high-quality code for DSPs, whose architectures are highly irregular. Thus, designers often resort to programming application software in assembly—a time-consuming task.

In this paper, we focus on providing support for architectural feature of DSPs that makes code generation difficult, namely multiple data memory banks. This feature increases memory bandwith by permitting multiple data memory accesses to occur in parallel when the referenced variables belong to different data memory banks and the registers involved conform to a strict set of conditions. We present an algorithm that attempst to maximize the benefit of this architectural feature. While previous approaches have decoupled the phases of register allocation and memory bank assignment, thereby compromising code quality, our algorithm performs these two phases simultaneously. Experimental results demonstrate that our algorithm not only generates high-quality compiled code, but also improves the quality of completely-referenced code.
Manageability, availability, and performance in porcupine
Authors: Saito Yasushi , Bershad Brian N. , Levy Henry M.
Published: July 2002

This paper describes the motivation, design and performance of Porcupine, a scalable mail server. The goal of Porcupine is to provide a highly available and scalable electronic mail service using a large cluster of commodity PCs. We designed Porcupine to be easy to manage by emphasizing dynamic load balancing, automatic configuration, and graceful degradation in the presence of failures. Key to the system's manageability, availability, and performance is that sessions, data, and underlying services are distributed homogeneously and dynamically across nodes in a cluster.
A software design method for real-time systems
Authors: Gomaa H.
Published: July 2002

DARTS—a design method for real-time systems—leads to a highly structured modular system with well-defined interfaces and reduced coupling between tasks.
Optimization criteria for checkpoint placement
Authors: Krishna C. M. , Lee Yann-Hang , Shin Kang G.
Published: July 2002

Mean response time and availability as optimization criteria for checkpoint placement are better replaced by workable formulas that calculate the ratio between the marginal gain accrued to users who experience system failure and the (presumably slight) loss suffered on average by all users.
Algorithm 805
Authors: Kolda Tamara G. , O'Leary Dianne P.
Published: July 2002

We present algorithms for computing a semidiscrete approximation to a matrix in a weighted norm, with the Frobenius norm as a special case. The approximation is formed as a weighted sum of outer products of vectors whose elements are ±1 or 0, so the storage required by the approximation is quite small. We also present a related algorithm for approximation of a tensor. Applications of the algorithms are presented to data compression, filtering, and information retrieval; software is provided in C and in Matlab.
Contemporary software development environments
Authors: Howden William E.
Published: July 2002

There are a wide variety of software development tools and methods currently available or which could be built using current research and technology. These tools and methods can be organized into four software development environments, ranging in complexity from a simple environment containing few automated tools or expensive methods to a complete one including many automated tools and built around a software engineering database. The environments were designed by considering the life-cycle products generated during two classes of software development projects. Relative cost figures for the environments are offered and related issues, such as standardization, effectiveness, and impact, then addressed.
A fast algorithm for copying list structures
Authors: Clark Douglas W.
Published: July 2002

An algorithm is presented for copying an arbitrarily linked list structure into a block of contiguous storage locations without destroying the original list. Apart from a fixed number of program variables, no auxillary storage, such as a stack, is used. The algorithm needs no mark bits and operates in linear time. It is shown to be significantly faster than Fisher's algorithm, the fastest previous linear-time algorithm for the same problem. Its speed comes mainly from its efficient list-traversal technique, which folds the processing stack into the structure being built, and from its classification of list cells into nine types, which enables processing operations to be optimized for each type.
An
O(n)
algorithm for determining a near-optimal computation order of matrix chain products
Authors: Chin Francis Y.
Published: July 2002

This paper discusses the computation of matrix chain products of the form
M
1
×
M
2
2 × ··· ×

M
n

where

M
i

's are matrices. The order in which the matrices are computed affects the number of operations. A sufficient condition about the association of the matrices in the optimal order is presented. An
O
(
n
) algorithm to find an order of computation which takes less than 25 percent longer than the optimal time
T
opt
is also presented. In most cases, the algorithm yields the optimal order or an order which takes only a few percent longer than
T
opt
(less than 1 percent on the average).
An anomaly in disk scheduling
Authors: Wilhelm Neil C.
Published: July 2002

A model for disk accesses based on published measurements is developed. The model is used to show that under highly probable conditions, FCFS seek scheduling is superior to SSTF scheduling in the sense of having a lower mean queue length. A simple example of an arrival sequence illustrating this anomaly is presented.
A reply to Gentleman and Marovich
Authors: Karp Richard Alan
Published: July 2002

Gentleman and Marovich in their short communication [
Comm. ACM 17
, 5 (May 1974) 276-277] make the claim that for FORTRAN “… the language definitions require that subprograms can be separately compiled…,” citing the ANSI FORTRAN standard X3.9-1966 as their authority.
An algorithm for locating adjacent storage blocks in the buddy system
Authors: Hinds James A.
Published: July 2002

A simple scheme for the determination of the location of a block of storage relative to other blocks is described. This scheme is applicable to the buddy type storage allocation systems.
Copying cyclic list structures in linear time using bounded workspace
Authors: Fisher David A.
Published: July 2002

A bounded workspace copying algorithm for arbitrary list structures is given. This algorithm operates in linear time and does not require tag bits. The best previous bounded workspace copying algorithms achieved
n
2
time without tag bits and
n
log
n
time with one tag. The only restriction on the algorithm given here is that the copy must be placed into a contiguous section of memory. The method is applicable to fixed or variable size nodes.
Recurrence relations for the Fresnel integral ∫
∞
0
exp(-ct)dt / √ t(1 + t
2
) and Similar Integrals
Authors: Acton Forman S.
Published: July 2002

The class of functions defined by ∫
∞
0
[exp(-
cX
)
dt
/(1 +
Y
) (√
t
)

k

] where
X
and
Y
are either
t
or
t
2
and
k
is -1, 0, or 1 can be evaluated by recurrences for all but small values of the parameter
c
. These recurrences, given here, are more efficient than the usual asymptotic series.
A hardware architecture for implementing protection rings
Authors: Schroeder Michael D. , Saltzer Jerome H.
Published: July 2002

Protection of computations and information is an important aspect of a computer utility. In a system which uses segmentation as a memory addressing scheme, protection can be achieved in part by associating concentric rings of decreasing access privilege with a computation. This paper describes hardware processor mechanisms for implementing these rings of protection. The mechanisms allow cross-ring calls and subsequent returns to occur without trapping to the supervisor. Automatic hardware validation of references across ring boundaries is also performed. Thus, a call by a user procedure to a protected subsystem (including the the supervisor) is identical to a call to a companion user procedure. The mechanisms of passing and referencing arguments are the same in both cases as well.
An implemented graph algorithm for winning Shannon Switching Games
Authors: Chase Stephen M.
Published: July 2002

In this tutorial paper a computer program which wins Shannon Switching Games is described. Since these games are played on graphs, the program is a good example of the implementation of graph algorithms.

The two players in a Shannon Switching Game, CONNECT and CUT, have nonsimilar goals. Either CONNECT, CUT, or the player moving first is guaranteed the existence of a winning strategy. The simple strategy explained in this paper is valid in all three cases. In fact, the major routines never need to know whether the computer is CONNECT or CUT.
On Foster's information storage and retrieval using AVL trees
Authors: Tan K. C.
Published: July 2002

Foster [2] has proposed a method of constructing an AVL tree with depth (height)
h
and the number of items
N
being fixed and with the weighted sum of the items a maximum. The purpose of this note is to show that this method does not work in general.
On Harrison's substring testing technique
Authors: Bookstein Abraham
Published: July 2002

This note comments on a technique by Malcolm Harrison [1] that tests whether a given string of characters,
S
1
, is a substring of another string of characters,
S
2
. This technique first transforms
S
2
into the set consisting of all the smaller fixed size substrings of length
k
and then hashes each of these segments into the
m
positions of a computer “word”; the bit corresponding to a position in this word is turned on if at least one segment is hashed onto it; else it is zero. The test is based on the observation that the same procedure applied to an arbitrary substring of the first string will not turn on any new bits. In the following we shall assume that
S
1
and
S
2
are decomposed into
l
1
and
l
2
segments respectively.
Representations for space planning
Authors: Eastman Charles M.
Published: July 2002

Problems involving the arrangement of objects in two- or three-space where the objective function primarily consists of derivatives of the distance between objects or their arrangement are called space planning problems. The representational requirements for this problem area are defined and compared with current computer graphic languages. Four alternative data structures that allow automated space planning are described and compared.
Algorithm 414: Chebyshev approximation of continuous functions by a Chebyshev system of functions
Authors: Golub G. H. , Smith L. B.
Published: July 2002

The second algorithm of Remez can be used to compute the minimax approximation to a function, ƒ(
x
), by a linear combination of functions, {

Q
i

(
x
)}

n

0
, which form a Chebyshev system. The only restriction on the function to be approximated is that it be continuous on a finite interval [
a
,
b
]. An Algol 60 procedure is given, which will accomplish the approximation. This implementation of the second algorithm of Remez is quite general in that the continuity of ƒ(
x
) is all that is required whereas previous implementations have required differentiability, that the end points of the interval be “critical points,” and that the number of “critical points” be exactly
n
+ 2. Discussion of the method used and of its numerical properties is given as well as some computational examples of the use of the algorithm. The use of orthogonal polynomials (which change at each iteration) as the Chebyshev system is also discussed.
The choice of base
Authors: Brown W. S. , Richman P. L.
Published: July 2002

A digital computer is considered, whose memory words are composed of
N
r
-state devices plus two sign bits (two state devices). The choice of base
β
for the internal representation of floating-point numbers on such a computer is discussed. It is shown that in a certain sense
β
=
r
is best.
A modification of Efroymson's technique for stepwise regression analysis
Authors: Breaux Harold J.
Published: July 2002

The computational technique conventionally used for stepwise multiple linear regression requires the storage of an
n
×
n
matrix of data. When the number of variables,
n
, is large, this requirement taxes the storage capacity of presently used machinery. The near symmetry of the matrices involved permits a modification requiring only half the storage and computations of the conventional algorithm and this additional storage allows the analysis of problems containing more variables. Alternatively, it permits the analysis of problems containing the same number of variables but with all computations performed in double precision.
A fast random number generator for IBM 360
Authors: Seraphin Dominic S.
Published: July 2002

Marsaglia and Bray [1] recommend incorporating two-line random number generators directly into FORTRAN programs. One of the advantages of this is the time saved in avoiding linkage to and fro from a subroutine. Implicit in their FORTRAN routine for IBM 360 for Lehmer's multiplicative congruence method, namely;
U

k
+1

= λ

U
k

(mod
P
),
X

k
+1

=
U

k
+1

/
P
is the use of 2
32
as the value of modulus
P
.
Numerical integration of a differential-difference equation with a decreasing time-lag
Authors: Bellman R. E. , Buell J. D. , Kalaba R. E.
Published: July 2002

Systems in which variable time-lags are present are of common occurrence in biology. Variable flow rates are a common cause of these variable lags. At present no extensive body of knowledge exists concerning the effects which these variable lags can cause. Shown here is a method of reducing some differential-difference equations to ordinary differential equations which can then be studied numerically with ease. Subsequent study will deal with situations in which multiple-lags and lags dependent on the solution itself are present.
Analysis of decay-type data
Authors: Worsley Beatrice H.
Published: July 2002

A comparative study has been made of a variety of numerical techniques for fitting experimental data of the decay type by forms involving the sums of exponentials. Statistical errors of the fitted parameters are also calculated. These methods have been applied to artificially-generated sets of data as well as to the results of experiments with radioactive tracers on both human and animal subjects. Results show that the values of the fitted parameters are very sensitive to variations in the fitting procedure. Therefore great care must be exercised in identifying such values with physical constants. Although the values of functions derived from these fitted parameters which can definitely be associated with physical entities are generally more stable under variations in the fitting techniques, error bounds can be so large that no great confidence can be placed even in them. It would therefore appear best to select a uniform technique both for running the experiments and for analyzing the data, and then to consider as significant only relative results between one subject and the next.
The stability of the fourth order Runge-Kutta method for the solution of systems of differential equations
Authors: Abdel Karim Abbas I.
Published: July 2002

The problem of the region of stability of the fourth order-Runge-Kutta method for the solution of systems of differential equations is studied. This region can be characterized by means of linear transformation but can not be given in a closed form. In the paper, this region is determined by the electronic digital computer Z22.
On the implementation of AMBIT, a language for symbol manipulation
Authors: Christensen Carlos
Published: July 2002

A brief description is given of the implementation technique for the replacement rule of the AMBIT programming language. The algorithm for the “AMBIT scan” and an example of its application are given. The algorithm is applicable to other members of the family of string transformation languages of which AMBIT is a member, and it provides a rationale for the design of the AMBIT language.
A computer method for radiation treatment planning
Authors: Siler William , Laughlin John S.
Published: July 2002

Automatic computation methods were first developed and applied to the problem of radiation therapy treatment planning by the Physics staff at Memorial Hospital and Sloan-Kettering Institute in 1954 and reported in 1955 [1]. The field of radiation from a single port was stored as a matrix in a library of punched cards, and a sorter and accounting machine were used to combine various fields for rotation, cycling and multi-port therapy. This system was in continuous routine use from then until 1961, when the equipment was replaced by a Bendix G15-D digital computer. Subsequent work by Sterling [2] followed essentially the same method of describing the radiation field as used by the Physics staff at Memorial Hospital [1], except that more powerful equipment has been used. An analytic expression for the dose distribution produced by rotation had been previously applied successfully in 1951 to treatment planning with high-energy X-rays [3].
Short proofs are narrow—resolution made simple
Authors: Ben-Sasson Eli , Wigderson Avi
Published: July 2002

The
width
of a Resolution proof is defined to be the maximal number of literals in any clause of the proof. In this paper, we relate proof width to proof length (=size), in both general Resolution, and its tree-like variant. The following consequences of these relations reveal width as a crucial “resource” of Resolution proofs.

In one direction, the relations allow us to give
simple, unified
proofs for almost all known exponential lower bounds on size of resolution proofs, as well as several interesting new ones. They all follow from width lower bounds, and we show how these follow from natural expansion property of clauses of the input tautology.

In the other direction, the width-size relations naturally suggest a simple dynamic programming procedure for automated theorem proving—one which simply searches for small width proofs. This relation guarantees that the runnuing time (and thus the size of the produced proof) is at most quasi-polynomial in the smallest tree-like proof. This algorithm is never much worse than any of the recursive automated provers (such as DLL) used in practice. In contrast, we present a family of tautologies on which it is exponentially faster.
Computing programs in small colleges
Authors: Beidler John , Austing Richard H. , Cassel Lillian N.
Published: July 2002

This Summary Report of The ACM Small College Task Force outlines resources, courses, and problems for small colleges developing degree programs in computing.
Transporting the linguistic string project system from a medical to a Navy domain
Authors: Marsh Elaine , Friedman Carol
Published: July 2002

The Linguistic String Project (LSP) natural language processing system has been developed as a domain-independent natural language processing system. Initially utilized for processing sets of medical messages and other texts in the medical domain, it has been used at the Naval Research Laboratory for processing Navy messages about shipboard equipment failures. This paper describes the structure of the LSP system and the features that make it transportable from one domain to another. The processing procedures encourage the isolation of domain-specific information, yet take advantage of the syntactic and semantic similarities between the medical and Navy domains. From our experience in transporting the LSP system, we identify the features that are required for transportable natural language systems.
Recommended curriculum for CS2, 1984
Authors: Koffman Elliot B. , Stemple David , Wardle Caroline E.
Published: July 2002

A Report of the ACM Curriculum Task Force for CS2
Line drawings of octree-represented objects
Authors: Veenstra Jack , Ahuja Narendra
Published: July 2002

The octree structure represents the space occupied by an object as a juxtaposition of cubes, where the sizes and position coordinates of the cubes are integer powers of 2 and are defined by a recursive decomposition of three-dimensional space. This makes the octree structure highly sensitive to object location and orientation, and the three-dimensional shape of the represented object obscure. It is helpful to be able to see the actual object represented by an octree, especially for visual performance evaluation of octree algorithms. Presented in this paper is a display algorithm that helps visualize the three-dimensional space represented by the octree. Given an octree, the algorithm produces a line drawing of the objects represented by the octree, using parallel projection, from any specified viewpoint with hidden lines removed. The order in which the algorithm traverses the octree has the property that if node
x
occludes node
y
, then node
x
is visited before node
y
. The algorithm produces a set of long, straight visible edge segments corresponding to the visible surface of the polyhedral object represented by the octree. Examples of some line drawing produced by the algorithm are given. The complexity of the algorithm is also discussed.
Measurement and evaluation of the MIPS architecture and processor
Authors: Gross Thomas R. , Hennessy John L. , Przybylski Steven A. , Rowen Christopher
Published: July 2002

MIPS is a 32-bit processor architecture that has been implemented as an nMOS VLSI chip. The instruction set architecture is RISC-based. Close coupling with compilers and efficient use of the instruction set by compiled programs were goals of the architecture. The MIPS architecture requires that the software implement some constraints in the design that are normally considered part of the hardware implementation. This paper presents experimental results on the effectiveness of this processor as a program host. Using sets of large and small benchmarks, the instruction and operand usage patterns are examined both for optimized and unoptimized code. Several of the architectural and organizational innovations in MIPS, including software pipeline scheduling, multiple-operation instructions, and word-based addressing, are examined in light of this data.