bluuebunny/crossref_metadata_2025 huggingface dataset:
Algorithms for scalable synchronization on shared-memory multiprocessors
Authors: Mellor-Crummey John M. , Scott Michael L.
Published: July 2002

Busy-wait techniques are heavily used for mutual exclusion and barrier synchronization in shared-memory parallel programs. Unfortunately, typical implementations of busy-waiting tend to produce large amounts of memory and interconnect contention, introducing performance bottlenecks that become markedly more pronounced as applications scale. We argue that this problem is not fundamental, and that one can in fact construct busy-wait synchronization algorithms that induce no memory or interconnect contention. The key to these algorithms is for every processor to spin on separate
locally-accessible
flag variables, and for some other processor to terminate the spin with a single remote write operation at an appropriate time. Flag variables may be locally-accessible as a result of coherent caching, or by virtue of allocation in the local portion of physically distributed shared memory.

We present a new scalable algorithm for spin locks that generates 0(1) remote references per lock acquisition, independent of the number of processors attempting to acquire the lock. Our algorithm provides reasonable latency in the absence of contention, requires only a constant amount of space per lock, and requires no hardware support other than a swap-with-memory instruction. We also present a new scalable barrier algorithm that generates 0(1) remote references per processor reaching the barrier, and observe that two previously-known barriers can likewise be cast in a form that spins only on locally-accessible flag variables. None of these barrier algorithms requires hardware support beyond the usual atomicity of memory reads and writes.

We compare the performance of our scalable algorithms with other software approaches to busy-wait synchronization on both a Sequent Symmetry and a BBN Butterfly. Our principal conclusion is that
contention due to synchronization need not be a problem in large-scale shared-memory multiprocessors.
The existence of scalable algorithms greatly weakens the case for costly special-purpose hardware support for synchronization, and provides a case against so-called “dance hall” architectures, in which shared memory locations are equally far from all processors. —
From the Authors' Abstract
Task-analytic approach to the automated design of graphic presentations
Authors: Casner Stephen M.
Published: July 2002

BOZ is an automated graphic design and presentation tool that designs graphics based on an analysis of the task for which a graphic is intended to support. When designing a graphic, BOZ aims to optimize two ways in which graphics help expedite human performance of information-processing tasks: (1) allowing users to substitute simple perceptual inferences in place of more demanding logical inferences, and (2) streamlining users' search for needed information. BOZ analyzes a logical description of a task to be performed by a human user and designs a provably equivalent perceptual task by substituting perceptual inferences in place of logical inferences in the task description. BOZ then designs and renders an accompanying graphic that encodes and structures data such that performance of each perceptual inference is supported and visual search is minimized. BOZ produces a graphic along with a perceptual procedure describing how to use the graphic to complete the task. A key feature of BOZ's approach is that it is able to design different presentations of the same information customized to the requirements of different tasks. BOZ is used to design graphic presentations of airline schedule information to support five different airline reservation tasks. Reaction time studies done with real users for one task and graphic show that the BOZ-designed graphic significantly reduces users' performance time to the task. Regression analyses link the observed efficiency savings to BOZ's two key design principles: perceptual inference substitutions and pruning of visual search.
Incremental clustering for dynamic information processing
Authors: Can Fazli
Published: July 2002

Clustering of very large document databases is useful for both searching and browsing. The periodic updating of clusters is required due to the dynamic nature of databases. An algorithm for incremental clustering is introduced. The complexity and cost analysis of the algorithm together with an investigation of its expected behavior are presented. Through empirical testing it is shown that the algorithm achieves cost effectiveness and generates statistically valid clusters that are compatible with those of reclustering. The experimental evidence shows that the algorithm creates an effective and efficient retrieval environment.
A survey of image registration techniques
Authors: Brown Lisa Gottesfeld
Published: July 2002

Registration is a fundamental task in image processing used to match two or more pictures taken, for example, at different times, from different sensors, or from different viewpoints. Virtually all large systems which evaluate images require the registration of images, or a closely related operation, as an intermediate step. Specific examples of systems where image registration is a significant component include matching a target with a real-time image of a scene for target recognition, monitoring global land usage using satellite images, matching stereo images to recover shape for autonomous navigation, and aligning images from different medical modalities for diagnosis.

Over the years, a broad range of techniques has been developed for various types of data and problems. These techniques have been independently studied for several different applications, resulting in a large body of research. This paper organizes this material by establishing the relationship between the variations in the images and the type of registration techniques which can most appropriately be applied. Three major types of variations are distinguished. The first type are the variations due to the differences in acquisition which cause the images to be misaligned. To register images, a spatial transformation is found which will remove these variations. The class of transformations which must be searched to find the optimal transformation is determined by knowledge about the variations of this type. The transformation class in turn influences the general technique that should be taken. The second type of variations are those which are also due to differences in acquisition, but cannot be modeled easily such as lighting and atmospheric conditions. This type usually effects intensity values, but they may also be spatial, such as perspective distortions. The third type of variations are differences in the images that are of interest such as object movements, growths, or other scene changes. Variations of the second and third type are not directly removed by registration, but they make registration more difficult since an exact match is no longer possible. In particular, it is critical that variations of the third type are not removed. Knowledge about the characteristics of each type of variation effect the choice of feature space, similarity measure, search space, and search strategy which will make up the final technique. All registration techniques can be viewed as different combinations of these choices. This framework is useful for understanding the merits and relationships between the wide variety of existing techniques and for assisting in the selection of the most suitable technique for a specific problem.
Algebraic methods for interactive proof systems
Authors: Lund Carsten , Fortnow Lance , Karloff Howard , Nisan Noam
Published: July 2002

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].
On the statistical independence of nonlinear congruential pseudorandom numbers
Authors: Eichenauer-Herrmann Jürgen , Niederreiter Harald
Published: July 2002

Recently, several nonlinear congruential methods for generating uniform pseudorandom numbers have been proposed and analysed. In the present note, further statistical independence properties of a general class of nonlinear congruential pseudorandom number generators are established. The results that are obtained are essentially best possible in an asymptotic sense and show that the generated pseudorandom numbers model truly random numbers very closely in terms of asymptotic discrepancy.
Automated learning of decision rules for text categorization
Authors: Apté Chidanand , Damerau Fred , Weiss Sholom M.
Published: July 2002

We describe the results of extensive experiments using optimized rule-based induction methods on large document collections. The goal of these methods is to discover automatically classification patterns that can be used for general document categorization or personalized filtering of free text. Previous reports indicate that human-engineered rule-based systems, requiring many man-years of developmental efforts, have been successfully built to “read” documents and assign topics to them. We show that machine-generated decision rules appear comparable to human performance, while using the identical rule-based representation. In comparison with other machine-learning techniques, results on a key benchmark from the Reuters collection show a large gain in performance, from a previously reported 67% recall/precision breakeven point to 80.5%. In the context of a very high-dimensional feature space, several methodological alternatives are examined, including universal versus local dictionaries, and binary versus frequency-related features.
HoloSketch
Authors: Deering Michael F.
Published: July 2002

This article describes HoloSketch, a virtual reality-based 3D geometry creation and manipulation tool. HoloSketch is aimed at providing nonprogrammers with an easy-to-use 3D “What-You-See-Is-What-You-Get” environment. Using head-tracked stereo shutter glasses and a desktop CRT display configuration, virtual objects can be created with a 3D wand manipulator directly in front of the user, at very high accuracy and much more rapidly than with traditional 3D drawing systems. HoloSketch also supports simple animation and audio control for virtual objects. This article describes the functions of the HoloSketch system, as well as our experience so far with more-general issues of head-tracked stereo 3D user interface design.
Performance of the VAX-11/780 translation buffer
Authors: Clark Douglas W. , Emer Joel S.
Published: July 2002

A virtual-address translation buffer (TB) is a hardware cache of recently used virtual-to-physical address mappings. The authors present the results of a set of measurements and simulations of translation buffer performance in the VAX-11/780. Two different hardware monitors were attached to VAX-11/780 computers, and translation buffer behavior was measured. Measurements were made under normal time-sharing use and while running reproducible synthetic time-sharing work loads. Reported measurements include the miss ratios of data and instruction references, the rate of TB invalidations due to context switches, and the amount of time taken to service TB misses. Additional hardware measurements were made with half the TB disabled. Trace-driven simulations of several programs were also run; the traces captured system activity as well as user-mode execution. Several variants of the 11/780 TB structure were simulated.
Using formal specifications in the design of a human-computer interface
Authors: Jacob Robert J. K.
Published: July 2002

Formal specification techniques are valuable in software development because they permit a designer to describe the external behavior of a system precisely without specifying its internal implementation. Although formal specifications have been applied to many areas of software systems, they have not been widely used for specifying user interfaces. In the Military Message System project at the Naval Research Laboratory, the user interfaces as well as the other components of a family of message systems are specified formally, and prototypes are then implemented from the specifications. This paper illustrates the specification of the user interface module for the family of message systems. It then surveys specification techniques that can be applied to human-computer interfaces and divides the techniques into two categories: those based on state transition diagrams and those based on BNF. Examples of both types of specifications are given. Specification notations based on state transition diagrams are preferable to those based on BNF because the former capture the surface structure of the user interface more perspicuously. In either notation, a high-level abstraction for describing the semantics of the user interface is needed, and an application-specific one is used here.
Cyberspace across the Sahara
Authors: Danowitz A. K. , Nassef Y. , Goodman S. E.
Published: July 2002

Spanning 7.2 million square kilometers from the Atlantic Ocean to the Red Sea, and encompassing the Great Saharan Desert and Nile River Valley, North Africa embraces Mauritania, Western Sahara, Morocco, Algeria, Tunisia, Libya, and Egypt. Charting the development of information technology (IT) is as challenging as traversing the souks, the labyrinthine ancient marketplaces.
High-speed visual estimation using preattentive processing
Authors: Healey Christopher G. , Booth Kellogg S. , Enns James T.
Published: July 2002

A new method is presented for performing rapid and accurate numerical estimation. The method is derived from an area of human cognitive psychology called preattentive processing. Preattentive processing refers to an initial organization of the visual field based on cognitive operations believed to be rapid, automatic, and spatially parallel. Examples of visual features that can be detected in this way include hue, intensity, orientation, size, and motion. We beleive that studies from preattentive vision should be used to assist in the design of visualization tools, especially those for which high-speed target detection, boundary identification, and region detection are important. In our present study, we investigated two known preattentive features (hue and orientation) in the context of a new task (numerical estimation) in order to see whether preattentive estimation was possible. Our experiments tested displays that were designed to visualize data from salmon migration simulations. The results showed that rapid and accurate estimation was indeed possible using either hue or orientation. Furthermore, random variation in one of these features resulted in no interference when subjects estimated the percentage of the other. To test the generality of our results, we varied two important display parameters—display duration and feature difference—and found boundary conditions for each. Implications of our results for application to real-world data and tasks are discussed.
Modeling formalisms for dynamic structure systems
Authors: Barros Fernando J.
Published: July 2002

We present a new concept for a system network to represent systems that are able to undergo structural change. Change in structure is defined in general terms, and includes the addition and deletion of systems and the modification of the relations among components. The structure of a system network is stored in the network executive. Any change in structure-related information is mapped into modifications in the network structure.

Based on these concepts, we derive three new system specifications that provide a shorthand notation to specify classes of dynamic structure systems. These new formalisms are: dynamic structure discrete time system, dynamic structure differential equation specified systems, and dynamic structure discrete event system specification. We demonstrate that these formalisms are closed under coupling, making hierarchical model construction possible. formalisms are described using set theoretic notation and general systems theory concepts.
Walsh-spectral test for GFSR pseudorandom numbers
Authors: Tezuka Shu
Published: July 2002

By applying Weyl's criterion for k-distributivity to GFSR sequences, we derive a new theoretical test for investigating the statistical property of GFSR sequences. This test provides a very useful measure for examining the k-distribution, that is, the statistical independence of the k-tuple of successive terms of GFSR sequences. In the latter half of this paper, we describe an efficient procedure for performing this test and furnish experimental results obtained from applying it to several GFSR generators with prime period lengths.
Amortized efficiency of list update and paging rules
Authors: Sleator Daniel D. , Tarjan Robert E.
Published: July 2002

In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes θ(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.
A threshold of ln
n
for approximating set cover
Authors: Feige Uriel
Published: July 2002

Given a collection ℱ of subsets of
S
= {1,…,
n
},
set cover
is the problem of selecting as few as possible subsets from ℱ such that their union covers
S,
, and
max k-cover
is the problem of selecting
k
subsets from ℱ such that their union has maximum cardinality. Both these problems are NP-hard. We prove that (1 -
o
(1)) ln
n
is a threshold below which set cover cannot be approximated efficiently, unless NP has slightly superpolynomial time algorithms. This closes the gap (up to low-order terms) between the ratio of approximation achievable by the greedy alogorithm (which is (1 -
o
(1)) ln n), and provious results of Lund and Yanakakis, that showed hardness of approximation within a ratio of (log
2
n
) / 2 ≃0.72 ln
n
. For max
k
-cover, we show an approximation threshold of (1 - 1/
e
)(up to low-order terms), under assumption that
P ≠ NP
.
Different perspectives on information systems: problems and solutions
Authors: Lyytinen Kalle
Published: July 2002

The paper puts information systems (IS) research dealing with IS problems into perspective. IS problems are surveyed and classified. Using the IS research framework suggested by Ives, Hamilton, and Davis, research into IS problems is classified into several perspectives whose relevance in coping with the problems is discussed. Research perspectives focusing on IS operations environment, IS development process, IS development organization, IS development methods, and IS theories are distinguished. The paper concludes with suggestions for future research and how to deal with IS problems in practice.
Reflectance and texture of real-world surfaces
Authors: Dana Kristin J. , van Ginneken Bram , Nayar Shree K. , Koenderink Jan J.
Published: July 2002

In this work, we investigate the visual appearance of real-world surfaces and the dependence of appearance on the geometry of imaging conditions. We discuss a new texture representation called the BTF (bidirectional texture function) which captures the variation in texture with illumination and viewing direction. We present a BTF database with image textures from over 60 different samples, each observed with over 200 different combinations of viewing and illumination directions. We describe the methods involved in collecting the database as well as the importqance and uniqueness of this database for computer graphics. A related quantity to the BTF is the familiar BRDF (bidirectional reflectance distribution function). The measurement methods involved in the BTF database are conducive to simultaneous measurement of the BRDF. Accordingly, we also present a BRDF database with reflectance measurements for over 60 different samples, each observed with over 200 different combinations of viewing and illumination directions. Both of these unique databases are publicly available and have important implications for computer graphics.
Incremental formalization with the hyper-object substrate
Authors: Shipman Frank M. , McCall Raymond J.
Published: July 2002

Computers require formally represented information to perform computations that support users; yet users who have needed such support have often proved to be unable or unwilling to formalize it. To address this problem, this article introduces an approach called incremental formalization, in which, first, users express information informally and then the system aids them in formalizing it. Incremental formalization requires a system architecture the (1) integrates formal and informal representations and (2) supports progressive formalization of information. The system should have both tools to capture naturally available informal information and techniques to suggest possible formalizations of this information. The hyper-object substrate (HOS) was developed to satisfy these requirements. HOS has been applied to a number of problem domains, including network design, archeological site analysis, and neuroscience education. Users have been successful in adding informal information and then later formalizing it incrementally with the aid of the system. Our experience with HOS has reaffirmed the need for information spaces to evolve during use and has identified additional considerations in the design and instantiation of systems enabling and supporting incremental formalization
Subresultants and Reduced Polynomial Remainder Sequences
Authors: Collins George E.
Published: July 2002

Let @@@@ be an integral domain, P(@@@@) the integral domain of polynomials over @@@@. Let
P
,
Q
∈ P(@@@@) with
m
@@@@ deg (
P
) ≥
n
= deg (
Q
) > 0. Let
M
be the matrix whose determinant defines the resultant of
P
and
Q
. Let

M
ij

be the submatrix of
M
obtained by deleting the last
j
rows of
P
coefficients, the last
j
rows of
Q
coefficients and the last 2
j
+1 columns, excepting column
m
—
n
—
i
—
j
(0 ≤
i
≤
j
<
n
). The polynomial

R
j

(
x
) = ∑

i

i
=0

det (

M
ij

)

x
i

is the
j-t subresultant
of
P
and
Q
,

R
0

being the resultant.
If
b
= £(
Q
), the leading coefficient of
Q
, then exist uniquely
R
,
S
∈ P(@@@@) such that
b

m-n
+1

P
=
QS
+
R
with deg (
R
) <
n
; define R(
P
,
Q
) =
R
. Define

P
i

∈ P(
F
),
F
the quotient field of @@@@, inductively:
P
1
=
P
,
P
2
=
Q
,
P
3
= R
P
1
,
P
2
P

i
-2

= R(

P
i

,
P

i
+1

)/
c

δ

i
-1

+1

i

for
i
≥
2
and
n

i
+1

> 0, where
c

i

= £(

P
i

),

n
i

= deg (

P
i

) and δ

i

=

n
i

—
n

i
+1

.
P
1
,
P
2
, …,

P
k

, for
k
≥ 3, is called a
reduced polynomial remainder sequence
. Some of the main results are: (1)

P
i

∈ P(@@@@) for 1 ≤
i
≤
k
; (2)

P
k

= ±

A
k
R

n

k
-1

-1

, when

A
k

= Π

k
-2

i
-2

c

δ

i
-1

(δ
i
-1)

i

; (3)
c

δ

k
-1

-1

k

P
k

= ±
A

k
+1

R

n

k

; (4)

R
j

= 0 for

n
k

<
j
<
n

k
-1

— 1. Taking @@@@ to be the integers
I
, or P

r

(
I
), these results provide new algorithms for computing resultant or greatest common divisors of univariate or multivariate polynomials. Theoretical analysis and extensive testing on a high-speed computer show the new g.c.d. algorithm to be faster than known algorithms by a large factor. When applied to bivariate polynomials, for example this factor grows rapidly with the degree and exceeds 100 in practical cases.
Iterative Refinement in Floating Point
Authors: Moler Cleve B.
Published: July 2002

Iterative refinement reduces the roundoff errors in the computed solution to a system of linear equations. Only one step requires higher precision arithmetic. If sufficiently high precision is used, the final result is shown to be very accurate.
On the Length of Programs for Computing Finite Binary Sequences
Authors: Chaitin Gregory J.
Published: July 2002

An attempt is made to carry out a program (outlined in a previous paper) for defining the concept of a random or patternless, finite binary sequence, and for subsequently defining a random or patternless, infinite binary sequence to be a sequence whose initial segments are all random or patternless finite binary sequences. A definition based on the bounded-transfer Turing machine is given detailed study, but insufficient understanding of this computing machine precludes a complete treatment. A computing machine is introduced which avoids these difficulties.
Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
Authors: Bellmore Mandell , Hong Saman
Published: July 2002

It is shown that the multisalesmen problem can be solved by solving the standard traveling salesman problem on an expanded graph. The expanded graph has
m
— 1 more nodes than the original graph where
m
is the number of salesmen available at the base.
A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph
Authors: Martelli Alberto
Published: July 2002

By defining a suitable algebra for cut sets, it is possible to reduce the problem of enumerating the cut sets between all pairs of nodes in a graph to the problem of solving a system of linear equations. An algorithm for solving this system using Gaussian elimination is presented in this paper. The efficiency of the algorithm depends on the implementation of sum and multiplication. Therefore, some properties of cut sets are investigated, which greatly simplify the implementation of these operations for the case of undirected graphs. The time required by the algorithm is shown to be linear with the number of cut sets for complete graphs. Some experimental results are given, proving that the efficiency of the algorithm increases by increasing the number of pairs of nodes for which the cut sets are computed.
Is paper safer? The role of paper flight strips in air traffic control
Authors: MacKay Wendy E.
Published: July 2002

Air traffic control is a complex, safety-critical activity, with well-established and successful work practices. Yet many attempts to automate the existing system have failed because controllers remain attached to a key work artifact: the paper flight strip. This article describes a four-month intensive study of a team of Paris en-route controllers in order to understand their use of paper flight strips. The article also describes a comparison study of eight different control rooms in France and the Netherlands. Our observations have convinced us that we do not know enough to simply get rid of paper strips, nor can we easily replace the physical interaction between controllers and paper strips.These observationshighlight the benefits of strips, including qualities difficult to quantify and replicate in new computer systems. Current thinking offers two basic alternatives: maintaining the existing strips without computer support and bearing the financial cost of limiting the air traffic, or replacing the strips with automated versions, which offer potential benefits in terms of increased efficiency through automation, but unknown risks through radical change of work practices. We conclude with a suggestion for a third alternative: to maintain the physical strips, but turn them into the interface to the computer. This would allow controllers to build directly upon their existing, safe work practices with paper strips, while offering them a gradual path for incorporating new computer-based functions. Augmented paper flight strips allow us to take advantage of uniquely human skills in the physical world, and allows us to leave the user interface and its subsequent evolution in the hands of the people most responsible, the air traffic controllers themselves.
IO-Lite
Authors: Pai Vivek S. , Druschel Peter , Zwaenepoel Willy
Published: July 2002

This article presents the design, implementation, and evaluation of IO -Lite, a unified I/O buffering and caching system for general-purpose operating systems. IO-Lite unifiesallbuffering and caching in the system, to the extent permitted by the hardware. In particular, it allows applications, the interprocess communication system, the file system, the file cache, and the network subsystem to safely and concurrently share a single physical copy of the data. Protection and security are maintained through a combination of access control and read-only sharing. IO-Lite eliminates all copying and multiple buffering of I/O data, and enables various cross-subsystem optimizations. Experiments with a Web server show performance improvements between 40 and 80% on real workloads as a result of IO-Lite.
Divide-and-conquer approximation algorithms via spreading metrics
Authors: Even Guy , Naor Joseph Seffi , Rao Satish , Schieber Baruch
Published: July 2002

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial have large diameters. In addition, the spreading metric provides a lower bound, τ, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm whose approximation factor is
O
(min{log τ, log log τ, log
k
log log
k
}) where
k
denotes the number of “interesting” vertices in the problem instance, and is at most the number of vertices.

We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a
d
-dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) balanced partitions and
p
-separators (for small values of
p
) in directed graphs.
Temporal logics for real-time system specification
Authors: Bellini P. , Mattolini R. , Nesi P.
Published: July 2002

The specification of reactive and real-time systems must be supported by formal, mathematically-founded methods in order to be satisfactory and reliable. Temporal logics have been used to this end for several years. Temporal logics allow the specification of system behavior in terms of logical formulas, including temporal constraints, events, and the relationships between the two. In the last ten years, temporal logics have reached a high degree of expressiveness. Most of the temporal logics proposed in the last few years can be used for specifying reactive systems, although not all are suitable for specifying real-time systems. In this paper we present a series of criteria for assessing the capabilities of temporal logics for the specification, validation, and verification of real-time systems. Among the criteria are the logic's expressiveness, the logic's order, presence of a metric for time, the type of temporal operators, the fundamental time entity, and the structure of time. We examine a selection of temporal logics proposed in the literature. To make the comparison clearer, a set of typical specifications is identified and used with most of the temporal logics considered, thus presenting the reader with a number of real examples.
A minimum spanning tree algorithm with inverse-Ackermann type complexity
Authors: Chazelle Bernard
Published: July 2002

A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is
0
(
m
α(
m, n
)), where α is the classical functional inverse of Ackermann's function and
n
(respectively,
m
) is the number of vertices (respectively, edges). The algorithm is comparison-based : it uses pointers, not arrays, and it makes no numeric assumptions on the edge costs.
A simple automatic derivative evaluation program
Authors: Wengert R. E.
Published: July 2002

A procedure for automatic evaluation of total/partial derivatives of arbitrary algebraic functions is presented. The technique permits computation of numerical values of derivatives without developing analytical expressions for the derivatives. The key to the method is the decomposition of the given function, by introduction of intermediate variables, into a series of elementary functional steps. A library of elementary function subroutines is provided for the automatic evaluation and differentiation of these new variables. The final step in this process produces the desired function's derivative.

The main feature of this approach is its simplicity. It can be used as a quick-reaction tool where the derivation of analytical derivatives is laborious and also as a debugging tool for programs which contain derivatives.
Occupational stress, attitudes, and health problems in the information systems professional
Authors: Ivancevich John M. , Napier H. Albert , Wetherbe James C.
Published: July 2002

This study examines occupational stress among information systems personnel. A self-report stress and health behavior instrument was completed by 580 respondents in 18 large corporations in the midwestern and southwestern sections of the United States. The data indicate that various job factors are perceived as stressful by respondents. However, the stress levels reported by respondents are not as excessive as have been found in studies of other occupational groups.
Multidimensional divide-and-conquer
Authors: Bentley Jon Louis
Published: July 2002

Most results in the field of algorithm design are single algorithms that solve single problems. In this paper we discuss
multidimensional divide-and-conquer
, an algorithmic
paradigm
that can be instantiated in many different ways to yield a number of algorithms and data structures for multidimensional problems. We use this paradigm to give best-known solutions to such problems as the ECDF, maxima, range searching, closest pair, and all nearest neighbor problems. The contributions of the paper are on two levels. On the first level are the particular algorithms and data structures given by applying the paradigm. On the second level is the more novel contribution of this paper: a detailed study of an algorithmic paradigm that is specific enough to be described precisely yet general enough to solve a wide variety of problems.
Texture and reflection in computer generated images
Authors: Blinn James F. , Newell Martin E.
Published: July 2002

In 1974 Catmull developed a new algorithm for rendering images of bivariate surface patches. This paper describes extensions of this algorithm in the areas of texture simulation and lighting models. The parametrization of a patch defines a coordinate system which is used as a key for mapping patterns onto the surface. The intensity of the pattern at each picture element is computed as a weighted average of regions of the pattern definition function. The shape and size of this weighting function are chosen using digital signal processing theory. The patch rendering algorithm allows accurate computation of the surface normal to the patch at each picture element, permitting the simulation of mirror reflections. The amount of light coming from a given direction is modeled in a similar manner to the texture mapping and then added to the intensity obtained from the texture mapping. Several examples of images synthesized using these new techniques are included.
Scalar- and planar-valued curve fitting using splines under tension
Authors: Cline A. K.
Published: July 2002

The spline under tension was introduced by Schweikert in an attempt to imitate cubic splines but avoid the spurious critical points they induce. The defining equations are presented here, together with an efficient method for determining the necessary parameters and computing the resultant spline. The standard scalar-valued curve fitting problem is discussed, as well as the fitting of open and closed curves in the plane. The use of these curves and the importance of the tension in the fitting of contour lines are mentioned as application.
Managing the computer resource
Authors: Nolan Richard L.
Published: July 2002

Based on the study of expenditures for data processing, a descriptive stage hypothesis is presented. It is suggested that the planning, organizing, and controlling activities associated with managing the computer resource will change in character over a period of time, and will evolve in patterns roughly correlated to four stages of the computer budget: Stage I (computer acquisition), Stage II (intense system development), Stage III (proliferation of controls), and Stage IV (user/service orientation). Each stage is described and related to individual tasks for managing the computer resource.
On the downhill method
Authors: Bach H.
Published: July 2002

The downhill method is a numerical method for solving complex equations ƒ(
z
) = 0 on which the only restriction is that the function
w
= ƒ(
z
) must be analytical. An introduction to this method is given and a critical review of relating literature is presented. Although in theory the method always converges, it is shown that a fundamental dilemma exists which may cause a breakdown in practical applications. To avoid this difficulty and to improve the rate of convergence toward a root, some modifications of the original method are proposed and a program (FORTRAN) based on the modified method is given in Algorithm 365. Some numerical examples are included.
The case for dynamic storage allocation
Authors: Sams Burnett H.
Published: July 2002

Programming is the process of developing a scheme for solving a problem using a computer. The programmer's task is to minimize the cost of achieving a solution. This cost involves the interrelated factors of planning, coding, debugging, storage space, and computation time. The storage allocation problem is the subtask of assigning the space-taking objects (programs and data) to the available storage devices (core, drum, disc and magnetic tape).
A storage allocation scheme for ALGOL 60
Authors: Jensen J. , Mondrup P. , Naur P.
Published: July 2002

A storage allocation scheme for a machine with a 2048-instruction core store and a magnetic drum is described. The use of the drum for storing program blocks and/or data must be directed by the programmer through auxiliary information in the ALGOL program. The administrative routines controlling the storage at run time are described in full. A detailed example is given.
Core allocation based on probability
Authors: Riskin Bernard N.
Published: July 2002

We are discussing a method of core allocation proposed for use in a large-scale, real-time, man-machine, data processing and display system.
A terminology proposal
Authors: Gruenberger Fred
Published: July 2002

It has been suggested that we need some new words in our industry. For example, consider the following two definitions of the term
random access
:

Access to storage under conditions in which the next position from which information is to be obtained is
in no way
dependent on the previous one.

Feature of certain internal memory systems,
particularly magnetic drum type
.

(In both cases the italics are the author's.)

of a set of publication standards suitable for use by the Association for Computing Machinery, based on the standards adopted by the Machine Computation Committee of the American Institute of Chemical Engineers. The writer, as a member of this Committee, is acting merely as agent of the Committee in presenting the following upon the request of the Editor for Standards of the ACM. This article is only a summary of the standards adopted by the AIChE; further details are contained in a pamphlet entitled “Guide to Abstracts and Manuals for Computer Program Interchange”, prepared by the Machine Computation Committee of the American Institute of Chemical Engineers.
1
Multiprogram scheduling
Authors: Codd E. F.
Published: July 2002

The scheduling algorithm examines the programs to be scheduled one by one and places their component rectangles in the corresponding load diagrams according to a set of placement rules.
Combining ALGOL statement analysis with validity checking
Authors: McIsaac Paul
Published: July 2002

The article by Robert W. Floyd in the March 1960 issue described an algorithm for determining whether a given symbol string is a permissible ALGOL assignment statement. In his method Mr. Floyd replaces certain character pairs by single characters in an array until, in the well-formed formula, the character Σ is obtained. Although this method indeed determines formation legality, one must still analyze and delimit each constituent of the statement in order to reduce the problem language to a workable format.
Augmenting thesauri for information systems
Authors: Rada Roy , Martin Brian K.
Published: July 2002

A thesaurus can be a critical component of an office information system. Access to various sets of documents can be facilitated by thesauri and by the connections that are made among thesauri. In the projects described in this paper, the thesauri are stored and manipulated through a relational database management system. The system detects inheritance properties in a thesaurus and uses them to guide a human expert in decisions about how to augment the thesaurus. New strategies will extend our ability to augment existing thesauri.
Connectionist expert systems
Authors: Gallant Stephen I.
Published: July 2002

Connectionist networks can be used as expert system knowledge bases. Furthermore, such networks can be constructed from training examples by machine learning techniques. This gives a way to automate the generation of expert systems for classification problems.
On visual formalisms
Authors: Harel David
Published: July 2002

The higraph, a general kind of diagramming object, forms a visual formalism of topological nature. Higraphs are suited for a wide array of applications to databases, knowledge representation, and, most notably, the behavioral specification of complex concurrent systems using the higraph-based language of statecharts.
Reflections on NoteCards: seven issues for the next generation of hypermedia systems
Authors: Halasz Frank,G.
Published: July 2002

NoteCards, developed by a team at Xerox PARC, was designed to support the task of transforming a chaotic collection of unrelated thoughts into an integrated, orderly interpretation of ideas and their interconnections. This article presents NoteCards as a foil against which to explore some of the major limitations of the current generation of hypermedia systems, and characterizes the issues that must be addressed in designing the next generation systems.
A field study of the software design process for large systems
Authors: Curtis Bill , Krasner Herb , Iscoe Neil
Published: July 2002

The problems of designing large software systems were studied through interviewing personnel from 17 large projects. A layered behavioral model is used to analyze how three of these problems—the thin spread of application domain knowledge, fluctuating and conflicting requirements, and communication bottlenecks and breakdowns—affected software productivity and quality through their impact on cognitive, social, and organizational processes.
Understanding the benefit and costs of communities of practice
Authors: Millen David R. , Fontaine Michael A. , Muller Michael J.
Published: July 2002

Promoting healthy collaboration in communities of practice takes management support at all levels. And management, of course, wants and needs to comprehend what the firm gets for that investment.
Petri-net-based hypertext: document structure with browsing semantics
Authors: Stotts P. David , Furuta Richard
Published: July 2002

We present a formal definition of the Trellis model of hypertext and describe an authoring and browsing prototype called αTrellis that is based on the model. The Trellis model not only represents the relationships that tie individual pieces of information together into a document (i.e., the adjacencies), but specifies the browsing semantics to be associated with the hypertext as well (i.e., the manner in which the information is to be visited and presented). The model is based on Petri nets, and is a generalization of existing directed graph-based forms of hypertext. The Petri net basis permits more powerful specification of what is to be displayed when a hypertext is browsed and permits application of previously developed Petri net analysis techniques to verify properties of the hypertext. A number of useful hypertext constructs, easily described in the Trellis model, are presented. These include the synchronization of simultaneous traversals of separate paths through a hypertext, the incorporation of access controls into a hypertext (i.e., specifying nodes that can be proven to be accessible only to certain classes of browsers), and construction of multiple specialized (tailored) versions from a single hypertext.
The future of high performance computers in science and engineering
Authors: Bell C. Gordon
Published: July 2002

A vast array of new, highly parallel machines are opening up new opportunities for new applications and new ways of computing.
Spacefilling curves and the planar travelling salesman problem
Authors: Platzman Loren K. , Bartholdi John J.
Published: July 2002

To construct a short tour through points in the plane, the points are sequenced as they appear along a spacefilling curve. This heuristic consists essentially of sorting, so it is easily coded and requires only
O
(
N
) memory and
O
(
N
log
N
) operations. Its performance is competitive with that of other fast methods.
Economic analysis of microcomputer hardware
Authors: Lynch Brian D. , Rao H. Raghav , Lin Winston T.
Published: July 2002

Economic analysis of the hardware characteristics of the personal computer segment of the microcomputer market indicates that the variables that most affect cost are the bundle of attributes offered by the micros. Interestingly, certain technological characteristics found to be important explanatory variables for cost in larger computers were not found to be significant for micros.
Contour tracing by piecewise linear approximations
Authors: Dobkin David P. , Wilks Allan R. , Levy Silvio V. F. , Thurston William P.
Published: July 2002

We present a method for tracing a curve that is represented as the contour of a function in Euclidean space of any dimension. The method proceeds locally by following the intersections of the contour with the facets of a triangulation of space. The algorithm does not fail in the presence of high curvature of the contour; it accumulates essentially no round-off error and has a well-defined integer test for detecting a loop. In developing the algorithm, we explore the nature of a particular class of triangulations of Euclidean space, namely, those generated by reflections.
Depth-order point classification techniques for CSG display algorithms
Authors: Jansen Frederik W.
Published: July 2002

Constructive Solid Geometry (CSG) defines objects as Boolean combinations (CSG trees) of primitive solids. To display such objects, one must classify points on the surfaces of the primitive solids with respect to the resulting composite object, to test whether these points lie on the boundary of the composite object or not. Although the point classification is trivial compared to the surface classification (i.e., the computation of the composite object), for CSG models with a large number of primitive solids (large CSG trees), the point classification may still consume a considerable fraction of the total processing time. This paper presents an overview of existing and new efficiency-improving techniques for classifying points in depth order. The different techniques are compared through experiments.