bluuebunny/crossref_metadata_2025 huggingface dataset:
Decision-theoretic troubleshooting
Authors: Heckerman David , Breese John S. , Rommelse Koos
Published: July 2002

You have just finished typing that big report into your word processor. It is formatted correctly and looks beautiful on the screen. You hit print, go to the printer—and nothing is there. Your try again—still nothing. The report needs to go out today. What do you do?
Rich interaction in the digital library
Authors: Rao Ramana , Pedersen Jan O. , Hearst Marti A. , Mackinlay Jock D. , Card Stuart K. , Masinter Larry , Halvorsen Per-Kristian , Robertson George C.
Published: July 2002

Effective information access involves rich interactions between users and information residing in diverse locations. Users seek and retrieve information from the sources—for example, file serves, databases, and digital libraries—and use various tools to browse, manipulate, reuse, and generally process the information. We have developed a number of techniques that support various aspects of the process of user/information interaction. These techniques can be considered attempts to increase the bandwidth and quality of the interactions between users and information in an
information workspace
—an environment designed to support information work (see Figure 1).
The reuse of uses in Smalltalk programming
Authors: Rosson Mary Beth , Carroll John M.
Published: July 2002

Software reuse, a long-standing and refractory issue in software technology, has been specifically emphasized as an advantage of the object-oriented programming paradigm. We report an empirical study of expert Smalltalk programmers reusing user interface classes in small graphical applications. Our primary goal was to develop a qualitative characterization of expert reuse strategies that could be used to identify requirements for teaching and supporting reuse programming. A secondary interest was to demonstrate to these experts the Reuse View Matcher—a prototype reuse tool—and to collect some initial observations of this tool in use during reuse programming. We observed extensive “reuse of uses” in the programmers' work: they relied heavily on code in expample applications that provided an implicit specification for reuse of the target class. We called this implicit specification a “usage context.” The programmers searched for relevant usage contexts early. They repeatedly evaluated the contextualized information to develop solution plans, and they borrowed and adapted it when the sample context suited their immediate reuse goals. The process of code development was highly dynamic and incremental; analysis and implementation were tightly interleaved, frequently driven by testing and debugging. These results are considered in terms of the tradeoffs that inhere in the reuse of uses and the teaching and tool support that might improve the efficiency and accuracy of this approach to reuse.
The quickhull algorithm for convex hulls
Authors: Barber C. Bradford , Dobkin David P. , Huhdanpaa Hannu
Published: July 2002

The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory. computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating-point arithmetic, this assumption can lead to serous errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of “thick” facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.
Gate-level test generation for sequential circuits
Authors: Cheng Kwang-Ting
Published: July 2002

This paper discusses the gate-level automatic test pattern generation (ATPG) methods and techniques for sequential circuits. The basic concepts, examples, advantages, and limitations of representative methods are reviewed in detail. The relationship between gate-level sequential circuit ATPG and the partial scan design is also discussed.
Rooms: the use of multiple virtual workspaces to reduce space contention in a window-based graphical user interface
Authors: Henderson D. Austin , Card Stuart
Published: July 2002

A key constraint on the effectiveness of window-based human-computer interfaces is that the display screen is too small for many applications. This results in “window thrashing,” in which the user must expend considerable effort to keep desired windows visible.
Rooms
is a window manager that overcomes small screen size by exploiting the statistics of window access, dividing the user's workspace into a suite of virtual workspaces with transitions among them. Mechanisms are described for solving the problems of navigation and simultaneous access to separated information that arise from multiple workspaces.
Algebraic laws for nondeterminism and concurrency
Authors: Hennessy Matthew , Milner Robin
Published: July 2002

Since a nondeterministic and concurrent program may, in general, communicate repeatedly with its environment, its meaning cannot be presented naturally as an input/output function (as is often done in the denotational approach to semantics). In this paper, an alternative is put forth. First, a definition is given of what it is for two programs or program parts to be equivalent for all observers; then two program parts are said to be
observation congruent
if they are, in all program contexts, equivalent. The
behavior
of a program part, that is, its meaning, is defined to be its observation congruence class.

The paper demonstrates, for a sequence of simple languages expressing finite (terminating) behaviors, that in each case observation congruence can be axiomatized algebraically. Moreover, with the addition of recursion and another simple extension, the algebraic language described here becomes a calculus for writing and specifying concurrent programs and for proving their properties.
Comparative analysis of the quantization of color spaces on the basis of the CIELAB color-difference formula
Authors: Hill B. , Roger Th. , Vorhagen F. W.
Published: July 2002

This article discusses the CIELAB color spave within the limits of optimal colors including the complete volume of object colors. A graphical representation of this color space is composed of planes of constant lightness
L
* with an net of lines parallel to the
a
* and
b
* axes. This uniform net is projected onto a number of other color spaces (CIE XYZ, tristimulus RGB, predistorted RGB, and YCC color space) to demonstrate and study the structure of color differences in these spaces on the basis of CIELAB color difference formulas. Two formulas are considered: the CIE 1976 formula *** and the newer CiE 1994 formula ***. The various color spaces considered are uniformly quantized and the grid of quantized points is transformed into CIELAB colordinates to study the distribution of color differences due to basic quantization steps and to spacify the areas of the colors with the highest sensitivity to color discrimination. From a threshold value for the maximum color difference among neighboring quantized points searched for in each color space, concepts for the quantization of the color spaces are drived. The results are compared to quantization concepts based on average values of quantization errors published in previous work. In addition to color spaces bounded by the optimal colors, the studies are also applied to device-dependent color spaces limited by the range of a positive RGB cube or by the gamut of colors of practical print processes (thermal dye sublimation, chromalin, and match print). For all the color spaces, estimation of the number of distinguishable colors are given on the basis of a threshold value for the color difference perception of *** = 1 and *** = 1.
Global illumination using local linear density estimation
Authors: Walter Bruce , Hubbard Philip M. , Shirley Peter , Greenberg Donald P.
Published: July 2002

This article presents the density estimation framework for generating view-independent global illumination solutions. It works by probabilistically simulating the light flow in an environment with light particles that trace random walks origination at luminaires and then using statistical density estimation techniques to reconstruct the lighting on each surface. By splitting the computation into separate transport and reconstruction stages, we gain many advantages including reduced memory usage, the ability to simulate nondiffuse transport, and natural parallelism. Solutions to several theoretical and practical difficulties in implementing this framework are also described. Light sources that vary spectrally and directionally are integrated into a spectral particle tracer using nonuniform rejection. A new local linear density estimation technique eliminates boundary bias and extends to arbitrary polygons. A mesh decimation algorithm with perceptual calibration is introduced to simplify the Gouraud-shaded representation of the solution for interactive display.
Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems
Authors: Sun Chengzheng , Jia Xiaohua , Zhang Yanchun , Yang Yun , Chen David
Published: July 2002

Real-time cooperative editing systems allow multiple users to view and edit the same text/graphic/image/multimedia document at the same time for multiple sites connected by communication networks. Consistency maintenance is one of the most significant challenges in designing and implementing real-time cooperative editing systems. In this article, a consistency model, with properties of convergence, causality preservation, and intention preservation, is proposed as a framework for consistency maintenance in real-time cooperative editing systems. Moreover, an integrated set of schemes and algorithms, which support the proposed consistency model, are devised and discussed in detail. In particular, we have contributed (1) a novel generic operation transformation control algorithm for achieving intention preservation in combination with schemes for achieving convergence and causality preservation and (2) a pair of reversible inclusion and exclusion transformation algorithms for stringwise operations for text editing. An Internet-based prototype system has been built to test the feasibility of the proposed schemes and algorithms
Algorithm 775
Authors: Greenberg Leon , Marletta Marco
Published: July 2002

We describe a new code (SLEUTH) for numerical solution of regular two-point fourth-order Sturm-Liouvlle eigenvalue problems. Eigenvalues are computed according to index: the user specifies an integer
k
***0, and the code computes an approximation to the
k
th eigenvalue. Eigenfunctions are also avialable through an auxiliary routine, called after the eigenvalue has been determined. The code will be made available through netlib.
Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm—Corrigenda for this article is available here
Authors: Corana A. , Marchesi M. , Martini C. , Ridella S.
Published: July 2002

A new global optimization algorithm for functions of continuous variables is presented, derived from the “Simulated Annealing” algorithm recently introduced in combinatorial optimization.

The algorithm is essentially an iterative random search procedure with adaptive moves along the coordinate directions. It permits uphill moves under the control of a probabilistic criterion, thus tending to avoid the first local minima encountered.

The algorithm has been tested against the Nelder and Mead simplex method and against a version of Adaptive Random Search. The test functions were Rosenbrock valleys and multiminima functions in 2,4, and 10 dimensions.

The new method proved to be more reliable than the others, being always able to find the optimum, or at least a point very close to it. It is quite costly in term of function evaluations, but its cost can be predicted in advance, depending only slightly on the starting point.
Query processing in a system for distributed databases (SDD-1)
Authors: Bernstein Philip A. , Goodman Nathan , Wong Eugene , Reeve Christopher L. , Rothnie James B.
Published: July 2002

This paper describes the techniques used to optimize relational queries in the SDD-1 distributed database system. Queries are submitted to SDD-1 in a high-level procedural language called Datalanguage. Optimization begins by translating each Datalanguage query into a relational calculus form called an
envelope
, which is essentially an aggregate-free QUEL query. This paper is primarily concerned with the optimization of envelopes.

Envelopes are processed in two phases. The first phase executes relational operations at various sites of the distributed database in order to delimit a subset of the database that contains all data relevant to the envelope. This subset is called a
reduction
of the database. The second phase transmits the reduction to one designated site, and the query is executed locally at that site.

The critical optimization problem is to perform the reduction phase efficiently. Success depends on designing a good repertoire of operators to use during this phase, and an effective algorithm for deciding which of these operators to use in processing a given envelope against a given database. The principal reduction operator that we employ is called a
semijoin
. In this paper we define the semijoin operator, explain why semijoin is an effective reduction operator, and present an algorithm that constructs a cost-effective program of semijoins, given an envelope and a database.
Optimal allocation of resources in distributed information networks
Authors: Mahmoud Samy , Riordon J. S.
Published: July 2002

The problems of file allocation and capacity assignment in a fixed topology distributed computer network are examined. These two aspects of the design are tightly coupled by means of an average message delay constraint. The objective is to allocate copies of information files to network nodes and capacities to network links so that a minimum cost is achieved subject to network delay and file availability constraints. A model for solving the problem is formulated and the resulting optimization problem is shown to fall into a class of nonlinear integer programming problems. Deterministic techniques for solving this class of problems are computationally cumbersome, even for small size problems. A new heuristic algorithm is developed, which is based on a decomposition technique that greatly reduces the computational complexity of the problem. Numerical results for a variety of network configurations indicate that the heuristic algorithm, while not theoretically convergent, yields practicable low cost solutions with substantial savings in computer processing time and storage requirements. Moreover, it is shown that this algorithm is capable of solving realistic network problems whose solutions using deterministic techniques are computationally intractable.
On Relevance, Probabilistic Indexing and Information Retrieval
Authors: Maron M. E. , Kuhns J. L.
Published: July 2002

This paper reports on a novel technique for literature indexing and searching in a mechanized library system. The notion of
relevance
is taken as the key concept in the theory of information retrieval and a comparative concept of relevance is explicated in terms of the theory of probability. The resulting technique called “Probabilistic Indexing,” allows a computing machine, given a request for information, to make a statistical inference and derive a number (called the “relevance number”) for each document, which is a measure of the probability that the document will satisfy the given request. The result of a search is an ordered list of those documents which satisfy the request ranked according to their probable relevance.

The paper goes on to show that whereas in a conventional library system the cross-referencing (“see” and “see also”) is based solely on the “semantical closeness” between index terms, statistical measures of closeness between index terms can be defined and computed. Thus, given an arbitrary request consisting of one (or many) index term(s), a machine can elaborate on it to increase the probability of selecting relevant documents that would not otherwise have been selected.

Finally, the paper suggests an interpretation of the whole library problem as one where the request is considered as a clue on the basis of which the library system makes a concatenated statistical inference in order to provide as an output an ordered list of those documents which most probably satisfy the information needs of the user.
Ambiguity in context free languages
Authors: Ginsburg Seymour , Ullian Joseph
Published: July 2002

Four principal results about ambiguity in languages (i.e., context free languages) are proved. It is first shown that the problem of determining whether an arbitrary language is inherently ambiguous is recursively unsolvable. Then a decision procedure is presented for determining whether an arbitrary bounded grammar is ambiguous. Next, a necessary and sufficient algebraic condition is given for a bounded language to be inherently ambiguous. Finally, it is shown that no language contained in
w
1
*
w
2
*, each
w
1
a word, is inherently ambiguous.
On the Length of Programs for Computing Finite Binary Sequences
Authors: Chaitin Gregory J.
Published: July 2002

The use of Turing machines for calculating finite binary sequences is studied from the point of view of information theory and the theory of recursive functions. Various results are obtained concerning the number of instructions in programs. A modified form of Turing machine is studied from the same point of view. An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed.
A Computer Program for the Nonnumerical Testing and Reduction of Sets of Algebraic Partial Differential Equations
Authors: Brans Carl H.
Published: July 2002

A program is described which enables a digital computer to perform the formal algebraic manipulations and differentiations required to test a set of algebraic partial differential equations for consistency, and, if the set is consistent, to reduce the equations in it to such an extent that the nature of the arbitrary functions uniquely generating all local, analytic solutions is apparent upon inspection. The computer performs these operations on polynomials in a nonnumerical sense, treating variables and derivatives of variables precisely as they are treated in the symbolic operations of algebra and calculus. The language which permits the computer to deal with variables and polynomials in this fashion is described. The general mathematical problem of testing and reduction of sets of algebraic partial differential equations is briefly described together with the techniques available for resolving it as adapted to this computer language. A brief description of the FORTRAN program itself is also given. The motivation for the development of this program was the study of the Einstein gravitational equations in general relativity. It has been shown that these equations can be invariantly reduced to a finite number of sets of algebraic partial differential equations, and the problem of testing and reducing these sets led to this program. The program reported on in this paper has been successfully tested for comparatively simple problems, some of which are described here, but must be further developed for the relativity applications.
Pseudo-Runge-Kutta Methods of the Fifth Order
Authors: Gruttke William B.
Published: July 2002

A family of fifth-order pseudo-Runge-Kutta methods for the numerical solution of systems of ordinary differential equations is presented. A procedure for determining an “optimal” set of parameters is given, and several examples are considered. The principal advantage of these methods is that, for a fixed stepsize, they require two less function evaluations at each step than do the corresponding fifth-order Runge-Kutta methods. Their principal disadvantage is that they are not self-starting; they require two initial values. Numerically, pseudo-Runge-Kutta and Runge-Kutta methods seem to be comparable.
Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
Authors: Morgenstern Jacques
Published: July 2002

A lower bound for the number of additions necessary to compute a family of linear functions by a linear algorithm is given when an upper bound
c
can be assigned to the modulus of the complex numbers involved in the computation. In the case of the fast Fourier transform, the lower bound is (
n
/2) log
2
n
when
c
= 1.
On the Linear Convergence of a Covariance Factorization Algorithm
Authors: Pagano Marcello
Published: July 2002

An algorithm for factoring a covariance function into its Hurwitz factors, which is based on the Cholesky factors of a certain matrix, was proposed by F.L. Bauer and others. This algorithm bears a close connection to the theory of orthogonal polynomials, and a closer one to the theory of prediction of stationary time series. In this paper these relations are pointed out and then used to advantage to prove the linear convergence of this algorithm.
Equality and Domain Closure in First-Order Databases
Authors: Reiter Raymond
Published: July 2002

A class of first-order databases with no function signs is considered. A closed database DB is one for which the only existing individuals are those explicitly referred to in the formulas of DB. Formally, this is expressed by including in DB a domain closure axiom (
x
)
x
=
c
1
∨···∨
x
=

c
p

, where
c
1
,…,

c
p

are all of the constants occurring in DB. It is shown how to completely capture the effects of this axiom by means of suitable generalizations of the projection and division operators of relational algebra, thereby permitting the underlying theorem prover used for query evaluation to ignore this axiom.

A database is E-saturated if all of its constants denote distinct individuals. It is shown that such databases circumvent the usual problems associated with equality, which arise in more general databases.

Finally, it is proved for Horn databases and positive queries that only definite answers are obtained, and for databases with infinitely many constants that infinitely long indefinite answers can arise.
Minimum cuts in near-linear time
Authors: Karger David R.
Published: July 2002

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an
m
-edge,
n
-vertex graph with high probability in
O
(m log
3
n
) time. We also give a simpler randomized algorithm that finds
all
minimum cuts with high probability in O(
m
log
3
n
) time. This variant has an optimal
RNC
parallelization. Both variants improve on the previous best time bound of
O
(
n
2
log
3
n
). Other applications of the tree-packing approach are new, nearly tight bounds on the number of
near-minimum
cuts a graph may have and a new data structure for representing them in a space-efficient manner.
On-chip vs. off-chip memory
Authors: Panda Preeti Ranjan , Dutt Nikil D. , Nicolau Alexandru
Published: July 2002

Efficient utilization of on-chip memory space is extremely important in modern embedded system applications based on processor cores. In addition to a data cache that interfaces with slower off-chip memory, a fast on-chip SRAM, called Scratch-Pad memory, is often used in several applications, so that critical data can be stored there with a guaranteed fast access time. We present a technique for efficiently exploiting on-chip Scratch-Pad memory by partitioning the application's scalar and arrayed variables into off-chip DRAM and on-chip Scratch-Pad SRAM, with the goal of minimizing the total execution time of embedded applications. We also present extensions of our proposed memory assignment strategy to handle context switching between multiple programs, as well as a generalized memory hierarchy. Our experiments on code kernels from typical applications show that our technique results in significant performance improvements.
Chimera
Authors: Anderson Kenneth M. , Taylor Richard N. , Whitehead E. James
Published: July 2002

Emerging software development environments are characterized by heterogeneity: they are composed of diverse object stores, user interfaces, and tools. This paper presents an approach for providing hypermedia services in this heterogeneous setting. Central notions of the approach include the following: anchors are established with respect to interactiveviewsof objects, rather than the objects themselves; composable,n-ary links can be established between anchors on different views of objects which may be stored in distinct object bases; viewers may be implemented in different programming languages; and, hypermedia services are provided to multiple, concurrently active, viewers. The paper describes the approach, supporting architecture, and lessons learned. Related work in the areas of supporing heterogeneity and hypermedia data modeling is discussed. The system has been employed in a variety of contexts including research, development, and education.
Enforceable security policies
Authors: Schneider Fred B.
Published: July 2002

A precise characterization is given for the class of security policies enforceable with mechanisms that work by monitoring system execution, and automata are introduced for specifying exactly that class of security policies. Techniques to enforce security policies specified by such automata are also discussed.
The measurement of user information satisfaction
Authors: Ives Blake , Olson Margrethe H. , Baroudi Jack J.
Published: July 2002

This paper critically reviews measures of user information satisfaction and selects one for replication and extension. A survey of production managers is used to provide additional support for the instrument, eliminate scales that are psychometrically unsound, and develop a standard short form for use when only an overall assessment of information satisfaction is required and survey time is limited.
An improved illumination model for shaded display
Authors: Whitted Turner
Published: July 2002

To accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this information is stored in a tree of “rays” extending from the viewer to the first surface encountered and from there to other surfaces and to the light sources. A visible surface algorithm creates this tree for each pixel of the display and passes it to the shader. The shader then traverses the tree to determine the intensity of the light received by the viewer. Consideration of all of these factors allows the shader to accurately simulate true reflection, shadows, and refraction, as well as the effects simulated by conventional shaders. Anti-aliasing is included as an integral part of the visibility calculations. Surfaces displayed include curved as well as polygonal surfaces.
Social processes and proofs of theorems and programs
Authors: De Millo Richard A. , Lipton Richard J. , Perlis Alan J.
Published: July 2002

It is argued that formal verifications of programs, no matter how obtained, will not play the same key role in the development of computer science and software engineering as proofs do in mathematics. Furthermore the absence of continuity, the inevitability of change, and the complexity of specification of significantly many real programs make the formal verification process difficult to justify and manage. It is felt that ease of formal verification should not dominate program language design.
An analysis of algorithms for the Dutch National Flag Problem
Authors: McMaster Colin L.
Published: July 2002

Solutions to the Dutch National Flag Problem have been given by Dijkstra [1] and Meyer [3]. Dijkstra starts with a simple program and arrives at an improved program by refinement. Both of the algorithms given by Dijkstra are shown to have an expected number of swaps which is 2/3
N
+ θ(1) and that these values differ at most by 1/3 of a swap and asymptotically by 1/4 of a swap. The algorithm of Meyer is shown to have expected swap complexity 5/9
N
.
Modularization and hierarchy in a family of operating systems
Authors: Habermann A. N. , Flon Lawrence , Cooprider Lee
Published: July 2002

This paper describes the design philosophy used in the construction of a family of operating systems. It is shown that the concepts of module and level do not coincide in a hierarchy of functions. Family members can share much software as a result of the implementation of run-time modules at the lowest system level.
A new solution of Dijkstra's concurrent programming problem
Authors: Lamport Leslie
Published: July 2002

A simple solution to the mutual exclusion problem is presented which allows the system to continue to operate despite the failure of any individual component.
Some comments on the use of ambiguous decision tables and their conversion to computer programs
Authors: King P. J. H. , Johnson R. G.
Published: July 2002

This paper comments upon recently published work on decision table translation using methods similar to the rule-mask technique. The applicability of these methods under various possible conventions on overall table meaning is discussed, and it is argued that there is a place both for the multi-rule and the single-rule (or action set) convention in decision table usage.
Hierarchical storage in information retrieval
Authors: Salasin John
Published: July 2002

A probabilistic analysis is employed to determine the effect of hierarchical storage organizations on information retrieval operations. The data storage hardware is assumed to consist of
n
-levels of linearly connected memory hardware with increasing data access times and increasing data storage capabilities. A system might, for example, consist of fast semiconductor memory, computer core memory, extended core storage, disk memory, and data cells. Equations are derived to predict the effect of such a system on data access times using sequential files, random access files, and structured files employing multiple-hierarchical linked lists.
On the conversion of decision tables to computer programs
Authors: Muthukrishnan C. R. , Rajaraman V.
Published: July 2002

The use of execution time diagnostics in pinpointing ambiguities in decision tables is discussed. It is pointed out that any attempt at resolving ambiguities at compile time will, in general, be impossible. It is shown that, as a consequence, tree methods of converting decision tables to programs are inadequate in regard to ambiguity detection. Two algorithms for programming decision tables whose merits are simplicity of implementation and detection of ambiguities at execution time are presented. The first algorithm is for limited entry decision tables and clarifies the importance of proper coding of the information in the decision table. The second algorithm programs a mixed entry decision table directly without going through the intermediate step of conversion to a limited entry form, thereby resulting in storage economy. A comparison of the algorithms and others proposed in the literature is made. Some features of a decision table to FORTRAN IV translator for the IBM 7044 developed by the authors are given.
Pattern width at a given angle
Authors: Klinger Allen
Published: July 2002

That the pattern feature “width as a function of angle” possesses several possible interpretations is demonstrated in this paper, which is a review of the width concept in pattern recognition and the geometrical concept itself.

The object of the work is to clarify how the word description can be made precise so that computer algorithms for feature extraction may be obtained; the focus is on theoretical subject matter. The results consist of a set-theoretic definition of width-at-angle, a theorem relating it to the pattern boundary radius vector, and descriptions of alternate widths. All widths are calculated for an illustrative example; graphical and tabular comparisons are given. Substantial variation in width-at-angle magnitude is found. The principal conclusion is that the set-theoretic width-at-angle is a useful pattern feature when it can be easily computed. Further investigation of the information contained in only part of a width function is recommended for cases where computation of width-at-angle is difficult.
NEATER2
Authors: Conrow Kenneth , Smith Ronald G.
Published: July 2002

NEATER2 accepts a PL/I source program and operates on it to produce a reformatted version. When in the LOGICAL mode, NEATER2 indicates the logical structure of the source program in the indentation pattern of its output. Logic errors discovered through NEATER2 logical analysis are discovered much more economically than is possible through compilation and trial runs. A number of options are available to give the user full control over the output format and to maximize the utility of NEATER2 as an aid during the early stages of development of a PL/I source deck. One option, USAGE, causes NEATER2 to insert into each logical unit of coding a statement which will cause the number of times each one is executed to be recorded during execution. This feature is expected to provide a major aid in optimization of PL/I programs.
Correction to “logical” arithmetric on computers with two's complement binary arithmetic
Authors: Ehrman John R.
Published: July 2002

In reference [1] algorithms for performing arithmetic with unsigned two's complement operands were described. The scheme for division was implemented in a set of multiple-precision floating-point arithmetic routines [2]. User experience with those routines showed that there is one case where the algorithm fails [3]. We give here a modification to the algorithm which eliminates the error condition. Equations are numbered beginning with (20), so that we may refer to equations in the original paper as well.
Implementation of the substring test by hashing
Authors: Harrison Malcolm C.
Published: July 2002

In a paper in the November 1970 Communications of the ACM, V.Y. Lum introduced a technique of file indexing named combined indices. This technique permitted decreased retrieval time at the cost of increased storage space. This paper examines combined indices under conditions of file usage with different fractions of retrieval and update. Tradeoff curves are developed to show minimal cost of file usage by grouping various partially combined indices.
System performance evaluation
Authors: Calingaert Peter
Published: July 2002

The state of the art of system performance evaluation is reviewed and evaluation goals and problems are examined. Throughput, turnaround, and availability are defined as fundamental measures of performance; overhead and CPU speed are placed in perspective. The appropriateness of instruction mixes, kernels, simulators, and other tools is discussed, as well as pitfalls which may be encountered when using them. Analysis, simulation, and synthesis are presented as three levels of approach to evaluation, requiring successively greater amounts of information. The central role of measurement in performance evaluation and in the development of evaluation methods is explored.
DITRAN—a compiler emphasizing diagnostics
Authors: Moulton P. G. , Muller M. E.
Published: July 2002

DITRAN
DI
agnostic FOR
TRAN
) is an implementation of ASA Basic FORTRAN with rather extensive error checking capabilities both at compilation time and during execution of a program. The need for improved diagnostic capabilities and some objectives to be met by any compiler are discussed. Attention is given to the design and implementation of DITRAN and the particular techniques employed to provide the diagnostic features. The handling of error messages by a general macro approach is described. Special features which provide teaching aids for use by instructors are noted.
An axiomatic basis for computer programming
Authors: Hoare C. A. R.
Published: July 2002

In this paper an attempt is made to explore the logical foundations of computer programming by use of techniques which were first applied in the study of geometry and have later been extended to other branches of mathematics. This involves the elucidation of sets of axioms and rules of inference which can be used in proofs of the properties of computer programs. Examples are given of such axioms and rules, and a formal proof of a simple theorem is displayed. Finally, it is argued that important advantage, both theoretical and practical, may follow from a pursuance of these topics.
Parsing of decision tables
Authors: Chapin Ned
Published: July 2002

Reduction in the size of decision tables can be accomplished by several techniques. The techniques considered in this paper are on the parsing of decision tables with regard to horizontal and vertical data structures, job identity, hardware and job priorities, and context relationships. Such parsing rests upon some conventions for the linkage of decision tables.
Secondary key retrieval using an IBM 7090-1301 system
Authors: Davis D. R. , Lin A. D.
Published: July 2002

The secondary key retrieval method involves the preparation of secondary storage lists from primary data records. Search requests are satisfied by logical operations on appropriate lists, producing a complete set of addresses of primary records relevant to the request. Experimental results are presented and a comparative analysis is given.
Tests of probabilistic models for propagation of roundoff errors
Authors: Hull T. E. , Swenson J. R.
Published: July 2002

In any prolonged computation it is generally assumed that the accumulated effect of roundoff errors is in some sense statistical.

The purpose of this paper is to give precise descriptions of certain probabilistic models for roundoff error, and then to describe a series of experiments for testing the validity of these models.

It is concluded that the models are in general very good. Discrepancies are both rare and mild.

The test techniques can also be used to experiment with various types of special arithmetic.
Programming semantics for multiprogrammed computations
Authors: Dennis Jack B. , Van Horn Earl C.
Published: July 2002

The semantics are defined for a number of meta-instructions which perform operations essential to the writing of programs in multiprogrammed computer systems. These meta-instructions relate to parallel processing, protecting of separate computations, program debugging, and the sharing among users of memory segments and other computing objects, the names of which are hierarchically structured. The language sophistication contemplated is midway between an assembly language and an advanced algebraic language.
American standard code for information interchange
Authors: Gorn S. , Bemer R. W. , Green J.
Published: July 2002

There was the germ of an idea in two previous papers [1, 2] which no one seems to have picked up in almost five years. For certain functions it seems desirable to transform the argument to a short range symmetric about 1.0. I will give examples of this usage for the square root and logarithm function for both binary and decimal machines.
Approximate spatio-temporal retrieval
Authors: Papadias Dimitris , Mamoulis Nikos , Delis Vasilis
Published: July 2002

This paper proposes a framework for the handling of spatio-temporal queries with inexact matches, using the concept of relation similarity. We initially describe a binary string encoding for 1D relations that permits the automatic derivation of similarity measures. We then extend this model to various granularity levels and many dimensions, and show that reasoning on spatio-temporal structure is significantly facilitated in the new framework. Finally, we provide algorithms and optimization methods for four types of queries: (i) object retrieval based on some spatio-temporal relations with respect to a reference object, (ii) spatial joins, i.e., retrieval of object pairs that satisfy some input relation, (iii) structural queries, which retrieve configurations matching a particular spatio-temporal structure, and (iv) special cases of motion queries. Considering the current large availability of multidimensional data and the increasing need for flexible query-answering mechanisms, our techniques can be used as the core of spatio-temporal query processors.
The description list of concepts
Authors: Banerji R. B.
Published: July 2002

A
concept
is defined as a class of objects whose members can be distinguished by processing its properties.
Property
is defined to mean a partition of the set of all objects into disjoint classes. The formal definition of a concept is recursive in nature.

A concept is described by a list structure. A one-to-one correspondence is established between the recursive definition of a concept and its description list structure. Like the definition, the description list structure of a concept is also built up from elementary list structures by a recursive process.

The list structures obtained this way are compared with the description list structure discussed by the author in a previous publication.
Syntactic analysis by digital computer
Authors: Barnett M. P. , Futrelle R. P.
Published: July 2002

This paper provides an account of the Shadow language that is used to describe syntax and of a corresponding subroutine that enables a computer to perform syntactic analysis. The input to this subroutine consists of a string to be analyzed and a description of the syntax that is to be used. The syntax is expressed in the Shadow language. The output consists of a trace table that expresses the results of the syntactic analysis in a tabular form. Several versions of the subroutine and some associated programs have been in use now for over three years. The present account of the language and the subroutine contains a summary of material that has been described previously in unpublished reports and also some additional discussion of the work in relation to the more general questions of problem-oriented languages and string transformations.
A modal analysis of staged computation
Authors: Davies Rowan , Pfenning Frank
Published: July 2002

We show that a type system based on the intuitionistic modal logic S4 provides an expressive framework for specifying and analyzing computation stages in the context of typed λ-calculi and functional languages. We directly demonstrate the sense in which our λ
e
→□
-calculus captures staging, and also give a conservative embeddng of Nielson and Nielson's two-level functional language in our functional language Mini-ML
□
, thus proving that binding-time correctness is equivalent to modal correctness on this fragment. In addition, Mini-ML
□
can also express immediate evaluation and sharing of code across multiple stages, thus supporting run-time code generation as well as partial evaluation.
Complexity of network synchronization
Authors: Awerbuch Baruch
Published: July 2002

The problem of simulating a synchronous network by an asynchronous network is investigated. A new simulation technique, referred to as a synchronizer, which is a new, simple methodology for designing efficient distributed algorithms in asynchronous networks, is proposed. The synchronizer exhibits a trade-off between its communication and time complexities, which is proved to be within a constant factor of the lower bound.
An extended set of FORTRAN basic linear algebra subprograms
Authors: Dongarra Jack J. , Du Croz Jeremy , Hammarling Sven , Hanson Richard J.
Published: July 2002

This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extensions are targeted at matrix-vector operations that should provide for efficient and portable implementations of algorithms for high-performance computers.
Algorithm 656: an extended set of basic linear algebra subprograms: model implementation and test programs
Authors: Dongarra Jack J. , Du Croz Jeremy , Hammarling Sven , Hanson Richard J.
Published: July 2002

This paper describes a model implementation and test software for the Level 2 Basic Linear Algebra Subprograms (Level 2 BLAS). Level 2 BLAS are targeted at matrix-vector operations with the aim of providing more efficient, but portable, implementations of algorithms on high-performance computers. The model implementation provides a portable set of FORTRAN 77 Level 2 BLAS for machines where specialized implementations do not exist or are not required. The test software aims to verify that specialized implementations meet the specification of Level 2 BLAS and that implementations are correctly installed.
The V distributed system
Authors: Cheriton David
Published: July 2002

The V distributed System was developed at Stanford University as part of a research project to explore issues in distributed systems. Aspects of the design suggest important directions for the design of future operating systems and communication systems.
Information technology and dataveillance
Authors: Clarke Roger
Published: July 2002

Data surveillance is now supplanting conventional surveillance techniques. With this trend come new monitoring methods such as personal dataveillance and mass dataveillance that require more effective safeguards and a formal policy framework.
Survey of software tools for evaluating reliability, availability, and serviceability
Authors: Johnson Allen M. , Malek Miroslaw
Published: July 2002

In computer design, it is essential to know the effectiveness of different design options in improving performance and dependability. Various software tools have been created to evaluate these parameters, applying both analytic and simulation techniques, and this paper reviews those related primarily to reliability, availability, and serviceability. The purpose, type of models used, type of systems modeled, inputs, and outputs are given for each package. Examples of some of the key modeling elements such as Markov chains, fault trees, and Petri nets are discussed. The information is compiled to facilitate recognition of similarities and differences between various models and tools and can be used to aid in selecting models and tools for a particular application or designing tools for future needs. Tools included in the evaluation are CARE-III, ARIES-82, SAVE, MARKl, HARP, SHARPE, GRAMP, SURF, SURE, ASSIST, METASAN, METFAC, ARM, and SUPER. Modeling tools, such as REL70, RELCOMP, CARE, CARSRA, and CAST, that were forerunners to some of the current tools are noted for their contributions. Modeling elements that have gained widespread use for general systems, as well as fault-tolerant systems, are included. Tools capable of modeling both repairable and nonrepairable systems, accepting constant or time varying failure rates, and predicting reliability, availability, and serviceability parameters are surveyed.
Cultural Perceptions of Task-Technology Fit
Authors: Massey Anne P. , Montoya-Weiss Mitzi , Hung Caisy , Ramesh V.
Published: July 2002

Acknowledging cultural differences helps companies build the strongest global virtual teams and determine the strongest tools they need.