bluuebunny/crossref_metadata_2025 huggingface dataset:
A dynamic network architecture
Authors: O'Malley Sean W. , Peterson Larry L.
Published: July 2002

Network software is a critical component of any distributed system. Because of its complexity, network software is commonly layered into a hierarchy of protocols, or more generally, into a
protocol graph
. Typical protocol graphs—including those standardized in the ISO and TCP/IP network architectures—share three important properties; the protocol graph is simple, the nodes of the graph (protocols) encapsulate complex functionality, and the topology of the graph is relatively static. This paper describes a new way to organize network software that differs from conventional architectures in all three of these properties. In our approach, the protocol graph is complex, individual protocols encapsulate a single function, and the topology of the graph is dynamic. The main contribution of this paper is to describe the ideas behind our new architecture, illustrate the advantages of using the architecture, and demonstrate that the architecture results in efficient network software.
Algorithm 711: BTN: software for parallel unconstrained optimization
Authors: Nash Stephen G. , Sofer Ariela
Published: July 2002

BTN is a collection of FORTRAN subroutines for solving unconstrained nonlinear optimization problems. It currently runs on both Intel hypercube computers (distributed memory) and Sequent computers (shared memory), and can take advantage of vector processors if they are available. The software can also be run on traditional computers to simulate the performance of a parallel computer. BTN is a general-purpose algorithm, capable of solving problems with a large numbers of variables and suitable for users inexperienced with parallel computing. It is designed to be as easy to use as traditional algorithms for this problem, requiring only that a (scalar) subroutine be provided to evaluate the objective function and its gradient vector of first derivatives. The algorithm is based on a block truncated-Newton method. Truncated-Newton methods obtain the search direction by approximately solving the Newton equations via some iterative method. The particular method used in BTN is a block version of the Lanczos method, which is numerically stable for nonconvex problems. In addition to the optimization software, a parallel derivative checker is also provided.
An MEBDF code for stiff initial value problems
Authors: Cash J. R. , Considine S.
Published: July 2002

In two recent papers one of the present authors has proposed a class of modified extended backward differentiation formulae for the numerical integration of stiff initial value problems. In this paper we describe a code based on this class of formulae and discuss its performance on a large set of stiff test problems.
Scheduler activations
Authors: Anderson Thomas E. , Bershad Brian N. , Lazowska Edward D. , Levy Henry M.
Published: July 2002

Threadsare the vehicle for concurrency in many approaches to parallel programming. Threads can be supported either by the operating system kernel or by user-level library code in the application address space, but neither approach has been fully satisfactory.

This paper addresses this dilemma. First, we argue that the performance of kernel threads isinherentlyworse than that of user-level threads, rather than this being an artifact of existing implementations; managing parallelism at the user level is essential to high-performance parallel computing. Next, we argue that the problems encountered in integrating user-level threads with other system services is a consequence of the lack of kernel support for user-level threads provided by contemporary multiprocessor operating systems; kernel threads are thewrong abstractionon which to support user-level management of parallelism. Finally, we describe the design, implementation, and performance of a new kernel interface and user-level thread package that together provide the same functionality as kernel threads without compromising the performance and flexibility advantages of user-level management of parallelism.
Institutions: abstract model theory for specification and programming
Authors: Goguen Joseph A. , Burstall Rod M.
Published: July 2002

There is a population explosion among the logical systems used in computing science. Examples include first-order logic, equational logic, Horn-clause logic, higher-order logic, infinitary logic, dynamic logic, intuitionistic logic, order-sorted logic, and temporal logic; moreover, there is a tendency for each theorem prover to have its own idiosyncratic logical system. The concept of
institution
is introduced to formalize the informal notion of “logical system.” The major requirement is that there is a satisfaction relation between models and sentences that is consistent under change of notation. Institutions enable abstracting away from syntactic and semantic detail when working on language structure “in-the-large”; for example, we can define language features for building large logical system. This applies to both specification languages and programming languages. Institutions also have applications to such areas as database theory and the semantics of artificial and natural languages. A first main result of this paper says that any institution such that signatures (which define notation) can be glued together, also allows gluing together theories (which are just collections of sentences over a fixed signature). A second main result considers when theory structuring is preserved by institution morphisms. A third main result gives conditions under which it is sound to use a theorem prover for one institution on theories from another. A fourth main result shows how to extend institutions so that their theories may include, in addition to the original sentences, various kinds of constraint that are useful for defining abstract data types, including both “data” and “hierarchy” constraints. Further results show how to define institutions that allow sentences and constraints from two or more institutions. All our general results apply to such “duplex” and “multiplex” institutions.
On the lattice structure of the add-with-carry and subtract-with-borrow random number generators
Authors: Tezuka Shu , L'Ecuyer Pierre , Couture Raymond
Published: July 2002

Marsaglia and Zaman recently proposed new classes of random number generators, called
add-with-carry
(AWC) and
subtract-with-borrow
(SWB), which are capable of quickly generating very long-period (pseudo)-random number sequences using very little memory. We show that these sequences are essentially equivalent to linear congruential sequences with very large prime moduli. So, the AWC/SWB generators can be viewed as efficient ways of implementing such large linear congruential generators. As a consequence, the theoretical properties of such generators can be studied in the same way as for linear congruential generators, namely, via the spectral and lattice tests. We also show how the equivalence can be exploited to implement efficient jumping-ahead facilities for the AWC and SWB sequences. Our numerical examples illustrate the fact that AWC/SWB generators have extremely bad lattice structure in high dimensions.
Sparse QR factorization in MATLAB
Authors: Matstoms Pontus
Published: July 2002

In the recently presented sparse matrix extension of MATLAB, there is no routine for sparse QR factorization. Sparse linear least-squares problems are instead solved by the augmented system method. The accuracy in computed solutions is strongly dependent on a scaling parameter δ. Its optimal value is expensive to compute, and it must therefore be approximated by a simple heuristic. We describe a multifrontal method for sparse QR factorization and its implementation in MATLAB. It is well known that the multifrontal approach is suitable for vector machines. We show that it is also attractive in MATLAB. In both cases, scalar operations are expensive, and the reformulation of the sparse problem into dense subproblems is advantageous. Using the new routine, we implement two methods for the solution of sparse linear least-squares problems and compare these with the built-in MATLAB function. We show that the QR-based methods normally are much faster and more accurate than the MATLAB implementation of the augmented system method. A better choice of the parameter δ or iterative refinement must be used to make the augmented system method as accurate as the methods based on QR factorization.
Compiling for shared-memory and message-passing computers
Authors: Larus James R.
Published: July 2002

Many parallel languages presume a shared address space in which any portion of a computation can access any datum. Some parallel computers directly support this abstraction with hardware shared memory. Other computers provide distinct (per-processor) address spaces and communication mechanisms on which software can construct a shared address space. Since programmers have difficulty explicitly managing address spaces, there is considerable interest in compiler support for shared address spaces on the widely available message-passing computers.

At first glance, it might appear that hardware-implemented shared memory is unquestionably a better base on which to implement a language. This paper argues, however, that compiler-implemented shared memory, despite its short-comings, has the potential to exploit more effectively the resources in a parallel computer. Hardware designers need to find mechanisms to combine the advantages of both approaches in a single system.
Information extraction as a basis for high-precision text classification
Authors: Riloff Ellen , Lehnert Wendy
Published: July 2002

We describe an approach to text classification that represents a compromise between traditional word-based techniques and in-depth natural language processing. Our approach uses a natural language processing task called “information extraction” as a basis for high-precision text classification. We present three algorithms that use varying amounts of extracted information to classify texts. The
relevancy signatures algorithm
uses linguistic phrases; the
augmented relevancy signatures algorithm
uses phrases and local context; and the
case-based text classification algorithm
uses larger pieces of context. Relevant phrases and contexts are acquired automatically using a training corpus. We evaluate the algorithms on the basis of two test sets from the MUC-4 corpus. All three algorithms achieved high precision on both test sets, with the augmented relevancy signatures algorithm and the case-based algorithm reaching 100% precision with over 60% recall on one set. Additionally, we compare the algorithms on a larger collection of 1700 texts and describe an automated method for empirically deriving appropriate threshold values. The results suggest that information extraction techniques can support high-precision text classification and, in general, that using more extracted information improves performance. As a practical matter, we also explain how the text classification system can be easily ported across domains.
On modeling information retrieval with probabilistic inference
Authors: Wong S. K. M. , Yao Y. Y.
Published: July 2002

This article examines and extends the logical models of information retrieval in the context of probability theory. The fundamental notions of term weights and relevance are given probabilistic interpretations. A unified framework is developed for modeling the retrieval process with probabilistic inference. This new approach provides a common conceptual and mathematical basis for many retrieval models, such as the Boolean, fuzzy set, vector space, and conventional probabilistic models. Within this framework, the underlying assumptions employed by each model are identified, and the inherent relationships between these models are analyzed. Although this article is mainly a theoretical analysis of probabilistic inference for information retrieval, practical methods for estimating the required probabilities are provided by simple examples.
Evaluation and approximate evaluation of the multivariate Bernstein-Bézier form on a regularly partitioned simplex
Authors: Peters Jörg
Published: July 2002

Polynomials of the total degree
d
in
m
variables have a geometrically intuitive representation in the Bernstein-Be´zier form defined over an
m
-dimensional simplex. The two algorithms given in this article evaluate the Bernstein-Be´zier form on a large number of points corresponding to a regular partition of the simplicial domain. The first algorithm is an adaptation of isoparametric evaluation. The second is a subdivision algorithm. In contrast to de Casteljau's algorithm, both algorithms have a cost of evaluation per point that is linear in the degree regardless of the number of variables. To demonstrate practicality, implementations of both algorithms on a triangular domain are compared with generic implementations of six algorithms in the literature.
Developing a reflective model of collaborative systems
Authors: Dourish Paul
Published: July 2002

Recent years have seen a shift in perception of the nature of HCI and interactive systems. As interface work has increasingly become a focus of attention for the social sciences, we have expanded our appreciation of the importance of issues such as work practice, adaptation, and evolution in interactive systems. The reorientation in our view of interactive systems has been accompanied by a call for a new model of design centered around user needs and participation. This article argues that a new process of design is not enough and that the new view necessitates a similar reorientation in the
structure
of the systems we build. It outlines some requirements for systems that support a deeper conception of interaction and argues that the traditional system design techniques are not suited to creating such systems. Finally, using examples from ongoing work in the design of an open toolkit for collaborative applications, it illustrates how the principles of computational reflection and metaobject protocols can lead us toward a new model based on open abstraction that holds great promise in addressing these issues.
A Fortran 90-based multiprecision system
Authors: Bailey David H.
Published: July 2002

A new version of a Fortran multiprecision computation system, based on the Fortran 90 language, is described. With this new approach, a translator program is not required—translation of Fortran code for multiprecision is accomplished by merely utilizing advanced features of Fortran 90, such as derived data types and operator extensions. This approach results in more-reliable translation and permits programmers of multiprecision applications to utilize the full power of Fortran 90. Three multiprecision data types are supported in this system: multiprecision integer, real, and complex. All the usual Fortran conventions for mixed-mode operations are supported, and many of the Fortran intrinsics, such as SIN, EXP, and MOD, are supported with multiprecision arguments. An interesting application of this software, wherein new number-theoretic identities have been discovered by means of multiprecision computations, is included also.
The HP AutoRAID hierarchical storage system
Authors: Wilkes John , Golding Richard , Staelin Carl , Sullivan Tim
Published: July 2002

Configuring redundant disk arrays is a black art. To configure an array properly, a system administrator must understand the details of both the array and the workload it will support. Incorrect understanding of either, or changes in the workload over time, can lead to poor performance. We present a solution to this problem: a two-level storage hierarchy implemented inside a single disk-array controller. In the upper level of this hierarchy, two copies of active data are stored to provide full redundancy and excellent performance. In the lower level, RAID 5 parity protection is used to provide excellent storage cost for inactive data, at somewhat lower performance. The technology we describe in this article, know as HP AutoRAID, automatically and transparently manages migration of data blocks between these two levels as access patterns change. The result is a fully redundant storage system that is extremely easy to use, is suitable for a wide variety of workloads, is largely insensitive to dynamic workload changes, and performs much better than disk arrays with comparable numbers of spindles and much larger amounts of front-end RAM cache. Because the implementation of the HP AutoRAID technology is almost entirely in software, the additional hardware cost for these benefits is very small. We describe the HP AutoRAID technology in detail, provide performance data for an embodiment of it in a storage array, and summarize the results of simulation studies used to choose algorithms implemented in the array.
A framework for formalizing inconsistencies and deviations in human-centered systems
Authors: Cugola Gianpaolo , Di Nitto Elisabetta , Fuggetta Alfonso , Ghezzi Carlo
Published: July 2002

Most modern business activities are carried out by a combination of computerized tools and human agents. Typical examples are engineering design activities, office procedures, and banking systems. All these
human-centered systems
are characterized by the interaction among people, and between people and computerized tools. This interaction defines a process, whose effectiveness is essential to ensure the quality of the delivered products and/or services. To support these systems, process-centered environments and workflow management systems have been recently developed. They can be collectively identified with the term
process technology
. This technology is based on the explicit definition of the process to be followed (the
process model
). The model specifies the kind of support that has to be provided to human agents. An essential property that process technology mut exhibit is the ability of tolerating, controlling, and supporting
deviations
and
inconsistencies
of the real-world behaviors with respect to the proocess model. This is necessary to provide consistent and effective support to the human-centered system, still maintaining a high degree of flexibility and adaptability to the evolving needs, preferences, an expertise of the the human agents. This article presents a formal framework to characterize the interaction between a human-centered system and its automated support. It does not aim at introducing a new language or system to describe processes. Rather, it aims at identifying the basic properties and features that make it possible to formally define the concepts of inconsistency and deviation. This formal framework can then be used to compare existing solutions and guide future research work.
Approximation schemes for covering and packing problems in image processing and VLSI
Authors: Hochbaum Dorit S. , Maass Wolfgang
Published: July 2002

A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative error ε > Ο, with running time that is polynomial when ε is fixed. Though the polynomiality of these algorithms depends on the degree of approximation ε being fixed, they cannot be improved, owing to a negative result stating that there are no fully polynomial approximation schemes for strongly NP-complete problems unless NP = P.

The unified technique that is introduced here, referred to as the shifting strategy, is applicable to numerous geometric covering and packing problems. The method of using the technique and how it varies with problem parameters are illustrated. A similar technique, independently devised by B. S. Baker, was shown to be applicable for covering and packing problems on planar graphs.
A programmable interface language for heterogeneous distributed systems
Authors: Falcone Joseph R.
Published: July 2002

The 1980s have witnessed the emergence of a new architecture for computing based on networks of personal computer workstations. The performance requirements of such systems of workstations places a strain on traditional approaches to network architecture. The integration of diverse systems into this environment introduces functional compatibility issues that are not present in homogeneous networks. Effective prescriptions for functional compatibility, therefore, must go beyond the communication paradigms used in present distributed systems, such as remote procedure calls.

This paper proposes a distributed system architecture in which communication follows a programming paradigm. In this architecture a programming language provides remote service interfaces for the heterogeneous distributed system environment. This language is a flexible and efficient medium for implementing service function protocols. In essence, clients and servers communicate by programming one another.
Secure audit logs to support computer forensics
Authors: Schneier Bruce , Kelsey John
Published: July 2002

In many real-world applications, sensitive information must be kept it log files on an untrusted machine. In the event that an attacker captures this machine, we would like to guarantee that he will gain little or no information from the log files and to limit his ability to corrupt the log files. We describe a computationally cheap method for making all log entries generated prior to the logging machine's compromise impossible for the attacker to read, and also impossible to modify or destroy undetectably.
Two-Tape Simulation of Multitape Turing Machines
Authors: Hennie F. C. , Stearns R. E.
Published: July 2002

It has long been known that increasing the number of tapes used by a Turing machine does not provide the ability to compute any new functions. On the other hand, the use of extra tapes does make it possible to speed up the computation of certain functions. It is known that a square factor is sometimes required for a one-tape machine to behave as a two-tape machine and that a square factor is always sufficient.

The purpose of this paper is to show that, if a given function requires computation time
T
for a
k
-tape realization, then it requires at most computation time
T
log
T
for a two-tape realization. The proof of this fact is constructive; given any
k
-tape machine, it is shown how to design an equivalent two-tape machine that operates within the stated time bounds. In addition to being interesting in its own right, the trade-off relation between number of tapes and speed of computation can be used in a diagonalization argument to show that if
T
(
n
) and
U
(
n
) are two time functions such that inf
T
(
n
) log
T
(
n
) ÷
U
(
n
) = 0 then there exists a function that can be computed within the time bound
U
(
n
) but not within the time bound
T
(
n
).
Matrix Equations and Normal Forms for Context-Free Grammars
Authors: Rosenkrantz Daniel J.
Published: July 2002

The relationship between the set of productions of a context-free grammar and the corresponding set of defining equations is first pointed out. The closure operation on a matrix of strings is defined and this concept is used to formalize the solution to a set of linear equations. A procedure is then given for rewriting a context-free grammar in Greibach normal form, where the replacements string of each production begins with a terminal symbol. An additional procedure is given for rewriting the grammar so that each replacement string both begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular expressions over the total vocabulary of the grammar, as is required by Greibach's procedure.
Morphology of ``Information Flow''
Authors: Fairthorne Robert A.
Published: July 2002

Such phrases as “information flow” may be purely metaphorical, or may refer to porterage and storage of physical documents, transmission of signals, power required for signaling, Shannon's Selective Information, changes in the state of one's personal knowledge, propagation of announcements concerning messages, social increase of awareness, propagation of or reaction to imperatives, and so on. These matters are distinct and must be distinguished. Then conditions must be stated under which one can validly speak of and measure the appropriate flow. In this paper it is shown that within the field of Notification (mention and delivery of recorded messages to users) there are twenty basic activities formed by choosing triads from the six variables, Message, Code, Channel, Source, Destination, and Designation.

“Flow” has meaning only when two such triads have two variables in common, forming a tetrad. Then flow or correspondence between any pair of variables is inextricable from a conjugate flow or correspondence between the other pair. Between any pair of endpoints there are six possible distinct types of flow, according to which two of the remaining four variables are directly used to achieve the flow.
Priority Disciplines in a Loop System
Authors: Katz Steven , Konheim Alan G.
Published: July 2002

A loop system with
N
buffered terminals sharing a common time-multiplexed channel is studied. The service discipline is prescribed by a permutation φ = (φ(1), ···, φ(
N
)) which gives the relative ranking of the terminals. Data from the
i
th terminal may be buffered at an intermediate terminal—its transmission to the CPU interrupted—if there is a conflict with data from a terminal with higher ranking. It is shown how such systems may be analyzed and how the system performance, as measured by average response time, may be improved by imposing a suitable priority discipline.
Scheduling Tasks with Nonuniform Deadlines on Two Processors
Authors: Garey M. R. , Johnson D. S.
Published: July 2002

Given a set @@@@ = {
T
1
,
T
2
,···,
T
n
} of tasks, with each
T
i
having execution time 1 and a deadline
d
i
> 0, and a set of precedence constraints which restrict allowable schedules, the problem of determining whether there exists a schedule using two processors in which each task is completed before its deadline is examined. An efficient algorithm for finding such a schedule, whenever one exists, is given. The algorithm may also be used to find the shortest such schedule. In addition it is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.
Secrecy by typing in security protocols
Authors: Abadi Martín
Published: July 2002

We develop principles and rules for achieving secrecy properties in security protocols. Our approach is based on traditional classification techniques, and extends those techniques to handle concurrent processes that use shared-key cryptography. The rules have the form of typing rules for a basic concurrent language with cryptographic primitives, the spi calculus. They guarantee that, if a protocol typechecks, then it does not leak its secret inputs.
Algorithm 797
Authors: Ribeiro Celso C. , Resende Mauricio G. C.
Published: July 2002

We describe Fortran subroutines for finding approximate solutions of the maximum planar subgraph problem (graph planarization) using a Greedy Randomized Adaptive Search Procedure (GRASP). The design and implementation of the code are described in detail. Computational results with the subroutines illustrate the quality of solutions found as a function of number of GRASP iterations.
Navigating through triangle meshes implemented as linear quadtrees
Authors: Lee Michael , Samet Hanan
Published: July 2002

Techniques are presented for navigating between adjacent triangles of greater or equal size in a hierarchical triangle mesh where the triangles are obtained by a recursive quadtree-like subdivision of the underlying space into four equilateral triangles. These techniques are useful in a number of applications, including finite element analysis, ray tracing, and the modeling of spherical data. The operations are implemented in a manner analogous to that used in a quadtree representation of data on the two-dimensional plane where the underlying space is tessellated into a square mesh. A new technique is described for labeling the triangles, which is useful in implementing the quadtree triangle mesh as a linear quadtree (i.e., a pointer-less quadtree); the navigation can then take place in this linear quadtree. When the neighbors are of equal size, the algorithms have a worst-case constant time complexity. The algorithms are very efficient, as they make use of just a few bit manipulation operations, and can be implemented in hardware using just a few machine language instructions. The use of these techniques when modeling spherical data by projecting it onto the faces of a regular solid whose faces are equilateral triangles, which are represented as quadtree triangle meshes, is discussed in detail. The methods are applicable to the icosahedron, octahedron, and tetrahedron. The difference lies in the way transitions are made between the faces of the polyhedron. However, regardless of the type of polyhedron, the computational complexity of the methods is the same.
Beyond intratransaction association analysis
Authors: Lu Hongjun , Feng Ling , Han Jiawei
Published: July 2002

In this paper, we extend the scope of mining association rules from traditional single-dimensional intratransaction associations, to multidimensional intertransaction associations. Intratransaction associations are the associations among items with thesame transaction, where the notion of the transaction could be the items bought by thesame customer, the events happened on thesame day, and so on. However, an intertransaction association describes the association relationships amongdifferent transactions, such as “if(company) A's stock goes up on day 1, B's stock will go down on day 2, but go up on day 4.” In this case, whether we treat company or day as the unit of transaction, the associated items belong to different transactions. Moreover, such an intertransaction association can be extended to associate multiple contextual properties in the same rule, so thatmultidimensionalintertransaction associations can be defined and discovered. A two-dimensional intertransaction association rule example is“After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away,”which involves two dimensions:time and space. Mining intertransaction associations poses more challenges on efficient processing than mining intratransaction associations. Interestingly, intratransaction association can be treated as a special case of intertransaction association from both a conceptual and algorithmic point of view. In this study, we introduce the notion of multidimensional intertransaction association rules, study their measurements—supportand confidence—and develop algorithms for mining intertransaction associations by extension of Apriori. We overview our experience using the algorithms on both real-life and synthetic data sets. Further extensions of multidimensional intertransaction association rules and potential applications are also discussed.
Reduction
Authors: Lipton Richard J.
Published: July 2002

When proving that a parallel program has a given property it is often convenient to assume that a statement is indivisible, i.e. that the statement cannot be interleaved with the rest of the program. Here sufficient conditions are obtained to show that the assumption that a statement is indivisible can be relaxed and still preserve properties such as halting. Thus correctness proofs of a parallel system can often be greatly simplified.
An efficient context-free parsing algorithm
Authors: Earley Jay
Published: July 2002

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(
k
) algorithm and the familiar top-down algorithm. It has a time bound proportional to
n
3
(where
n
is the length of the string being parsed) in general; it has an
n
2
bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
Average binary search length for dense ordered lists
Authors: Flores Ivan , Madpis George
Published: July 2002

A binary search is effective only when the list searched is ordered. It is efficient only when the list is dense—i.e. when records are in contiguous locations. It is easy to show that the maximum number of looks for a search
L
is given by [1].
L
= [log
2
N
+1], (1) where
N
is the number of records in the list and the square bracket means “integral part of.”
On accurate floating-point summation
Authors: Malcolm Michael A.
Published: July 2002

cumulation of floating-point sums is considered on a computer which performs
t
-digit base
β
floating-point addition with exponents in the range —
m
to
M
. An algorithm is given for accurately summing
n t
-digit floating-point numbers. Each of these
n
numbers is split into
q
parts, forming
q
·
n t
-digit floating-point numbers. Each of these is then added to the appropriate one of
η
auxiliary
t
-digit accumulators. Finally, the accumulators are added together to yield the computed sum. In all,
q
·
n
+
η
- 1
t
-digit floating-point additions are performed. Let
ν
= ⌈(
M
+
m
+ 1)/(
η
+ 1)⌉. If
n
≤ (1/
q
)
β

⌈((
q
-1)/
q
)
t
⌈-
ν
+1

(*), then the relative error in the computed sum is at most ⌈(
t
+ 1)/
ν
⌉
β

1-
t

. Further, with an additional
q
+
η
- 1
t
-digit additions, the computed sum can be corrected to full
t
-digit accuracy.

For example, for the IBM/360 (
β
= 16,
t
= 14,
M
= 63,
m
= 64), typical values for
q
and
η
are
q
= 2 and
η
= 32.

In this case, (*) becomes
n
≤ 1/2 × 16
4
= 32,768, and we have ⌈(
t
+ 1)/
ν
⌉
β

1-
t

= 4 × 16
-13
.
TACCLE
Authors: Chen Huo Yan , Tse T. H. , Chen T. Y.
Published: July 2002

Object-oriented programming consists of several different levels of abstraction, namely, the algorithmic level, class level, cluster level, and system level. The testing of object-oriented software at the algorithmic and system levels is similar to conventional program testing. Testing at the class and cluster levels poses new challenges. Since methods and objects may interact with one another with unforeseen combinations and invocations, they are much more complex to simulate and test than the hierarchy of functional calls in conventional programs. In this paper, we propose a methodology for object-oriented software testing at the class and cluster levels. In class-level testing, it is essential to determine whether objects produced from the execution of implemented systems would preserve the properties defined by the specification, such as behavioral equivalence and nonequivalence. Our class-level testing methodology addresses both of these aspects. For the testing of behavioral equivalence, we propose to select fundamental pairs of equivalent ground terms as test cases using a black-box technique based on algebraic specifications, and then determine by means of a white-box technique whether the objects resulting from executing such test cases are observationally equivalent. To address the testing of behavioral nonequivalence, we have identified and analyzed several nontrivial problems in the current literature. We propose to classify term equivalence into four types, thereby setting up new concepts and deriving important properties. Based on these results, we propose an approach to deal with the problems in the generation of nonequivalent ground terms as test cases. Relatively little research has contributed to cluster-level testing. In this paper, we also discuss black-box testing at the cluster level. We illustrate the feasibility of using contract, a formal specification language for the behavioral dependencies and interactions among cooperating objects of different classes in a given cluster. We propose an approach to test the interactions among different classes using every individual message-passing rule in the given Contract specification. We also present an approach to examine the interactions among composite message-passing sequences. We have developed four testing tools to support our methodology.
ALGOL 60 confidential
Authors: Knuth Donald E. , Merner Jack N.
Published: July 2002

The ALGOL 60 Report,
*
when first encountered, seems to describe a very complex language which will be difficult to learn. The “metalinguistic formulae” admirably serve the purpose of precisely specifying a language, but they are certainly not very readable for a beginner. However, experience has shown that once the report is explained it is in fact easy to learn ALGOL and to write algorithms in it. The language is so general and powerful it can handle an enormous class of problems.

It is not hard to learn those parts of ALGOL present in other compiler languages: how to write
assignment
and
go to
and
for
statements, etc. Indeed, a lot of the unnecessary restrictions imposed by other compiling languages have finally been lifted. But ALGOL also allows many unobvious things to be written, as we will see later, and herein lies a problem: ALGOL seems to have become too general. So many restrictions have been lifted that a lot of technical details crop up which are hard to learn and to use correctly. In this paper some of the more obscure features of the language are considered and their usefulness is discussed. Remarks are based on the authors' interpretations of the ALGOL 60 Report.
A software engineering perspective on algorithmics
Authors: Weihe Karsten
Published: July 2002

Analgorithm componentis an implementation of an algorithm which is not intended to be a stand-alone module, but to perform a specific task within a large software package or even within several distinct software packages. Therefore, the design of algorithm components must also incorporate software-engineering aspects. A key design goal is adaptability. This goal is important for maintenance throughout a project, prototypical development, and reuse in new, unforseen contexts. From a theoretical viewpoint most algorithms apply to a range of possible use scenarios. Ideally, each algorithm is implemented by one algorithm component, which is easily, safely, and efficiently adaptable to all of these contexts.

Various techniques have been developed for the design and implementation of algorithm components. However, a common basis for systematic, detailed evaluations and comparisons in view of therealpractical needs is still missing. Basically, this means a set of concrete criteria, which specify what sort of adaptability isreallyrequired in practice, and which are well-justified by convincing, representative use scenarios.

This paper is intended to be a first “milestone” on the way towards such a system of criteria. We will present a set of concrete goals, which are general and problem-independent and might appear ubiquitously in the algorithmic realm. These goals are illustrated, motivated, and justified by an extensive requirements analysis for a particular algorithm from a particular algorithmic domain: Dijkstra's algorithm for shortest paths in networks.

Clearly, the field of algorithmics might be too versatile to allow a comprehensive, yet concise set of precise, justified criteria. Even a domain as restricted as graph and network algorithms includes aspects that are not fully understood. The analysis will include a discussion of the limits of the case study and the scope of the goals. The case study was chosen because it seems to be close to the “boderline” between the aspects that are well understood and the aspects that are not. Hence, this example may well serve as an“acid test” for programming techniques in view of the state of the art.
Remote pipes and procedures for efficient distributed communication
Authors: Gifford David K. , Glasser Nathan
Published: July 2002

We describe a new communication model for distributed systems that combines the advantages of remote procedure call with the efficient transfer of bulk data. Three ideas form the basis of this model. First, remote procedures are first-class values which can be freely exchanged among nodes, thus enabling a greater variety of protocols to be directly implemented in a remote procedure call framework. Second, a new type of abstract object, called a
pipe
, allows bulk data and incremental results to be efficiently transported in a type-safe manner. Unlike procedure calls, pipe calls do not return values and do not block a caller. Data sent down a pipe is received by the pipe's sink node in the order sent. Third, the relative sequencing of pipes and procedures can be controlled by combining them into
channel groups
. Calls on the members of a channel group are guaranteed to be processed in order. Application experience with this model, which we call the
Channel Model
, is reported. Derived performance bounds and experimental measures demonstrate
k
pipe calls can perform
min
( 1 + (
r
/
p
),
k
) times faster than
k
procedure calls, where
r
is the total roundtrip remote communication time and
p
is the procedure execution time.
Experiments in SR with different upcall program structures
Authors: Atkins M. Stella
Published: July 2002

This paper explores program designs for layered systems such as communication protocols and server/client systems that do not exhibit a strict hierarchy in their control flow. Clark has proposed structuring such systems, where both upward and downward control flow are required, to use efficient synchronous procedure calls between the layers whenever possible. The termupcallis used by Clark to describe this synchronous upward communication from server to client.

Several techniques are possible for structuring such programs using upcalls. Comparisons are made by implementing a communication protocol described by Clark in three different ways. The first method implements all the protocol routines in a single large module. The second method structures the routines into modules occupying vertical slices of the protocol layers, and the third method structures the routines into modules corresponding to the protocol layers.

Comparisons are made on two fronts: Preservation of modularity, in order to determine which method shows fault-tolerance and ease of programming, and program performance, which is a key motivation for the upcalls programming style. We conclude that the vertically layered protocol design is to be preferred unless there are many shared variables between the send-side and receive-side, as it is very efficient and provides the best protection of clients from each other. The horizontally layered design is the least efficient, but it is the easiest to program.
A digital multisignature scheme using bijective public-key cryptosystems
Authors: Okamoto Tatsuaki
Published: July 2002

A new digital multisignature scheme using bijective public-key cryptosystems that overcomes the problems of previous signature schemes used for multisignatures is proposed. The principal features of this scheme are (1) the length of a multisignature message is nearly equivalent to that for a singlesignature message; (2) by using a one-way hash function, multisignature generation and verification are processed in an efficient manner; (3) the order of signing is not restricted; and (4) this scheme can be constructed on any bijective public-key cryptosystem as well as the RSA scheme. In addition, it is shown that the new scheme is considered as safe as the public-key cryptosystem used in this new scheme. Some variations based on the scheme are also presented.
Intersection algorithms for lines and circles
Authors: Middleditch A. E. , Stacey T. W. , Tor S. B.
Published: July 2002

This paper presents a unified representation scheme for the implicit equations of points, lines, and circles. An associated set of geometric algorithms operates successfully on degenerate and nearly degenerate geometry, and when necessary produces degenerate geometric results. Computation errors are interpreted geometrically in order to establish preconditions for reliable results and requirements on the resolution of computer arithmetic. The algorithms thus provide a basis for the wide range of geometric constructions required by computer-aided drafting and design systems.
Will UML 2.0 be agile or awkward?
Authors: Kobryn Cris
Published: July 2002

The UML sits at an architectural crossroad. Will UML 2.0 resolve the problems of UML 1.x or will it succumb to the dreaded second-language syndrome?
Applying cartoon animation techniques to graphical user interfaces
Authors: Thomas Bruce H. , Calder Paul
Published: July 2002

If judiciously applied, animation techniques can enhance the look and feel of computer applications that present a graphical human interface. Such techniques can smooth the rough edges and abrupt transitions common in many current graphical interfaces, and strengthen the illusion of direct manipulation that many interfaces strive to present. To date, few applications include such animation techniques. One possible reason is that animated interfaces are difficult to implement: they are difficult to design, place great burdens on programmers, and demand high-performance from underlying graphics systems.This article describes how direct manipulation human computer interfaces can be augmented with techniques borrowed from cartoon animators. In particular, we wish to improve the visual feedback of a direct manipulation interface by smoothing the changes of an interface, giving manipulated objects a feeling of substance and providing cues that anticipate the result of a manipulation. Our approach is to add support for animation techniques such as object distortion and keyframe interpolation, and to provide prepackaged animation effects such as animated widgets for common user interface interactions.To determine if these tools and techniques are practical and effective, we built a prototype direct manipulation drawing editor with an animated interface and used the prototype editor to carry out a set of human factors experiments. The experiments show that the techniques are practical even on standard workstation hardware, and that the effects can indeed enhance direct manipulation interfaces.
A Laplace transform algorithm for the volume of a convex polytope
Authors: Lasserre Jean B. , Zeron Eduardo S.
Published: July 2002

We provide two algorithms for computing the volume of the convex polytope Ω : = {
x
∈ ℝ
n
+
|
Ax
≤
b
}, for
A
, ∈ ℝ

m
×
n

,
b
∈ ℝ

n

. The computational complexity of both algorithms is essentially described by
n

m

, which makes them especially attractive for large
n
and relatively small
m
, when the other methods with
O
(
m

n

) complexity fail. The methodology, which differs from previous existing methods, uses a Laplace transform technique that is well suited to the half-space representation of Ω.
A framework for choosing a database query language
Authors: Jarke Matthias , Vassiliou Yannis
Published: July 2002

This paper presents a systematic approach to matching categories of query language interfaces with the requirements of certain user types. The method is based on a trend model of query language development on the dimensions of functional capabilities and usability. From the trend model the following are derived: a classification scheme for query languages, a criterion hierarchy for query language evaluation, a comprehensive classification scheme of query language users and their requirements, and preliminary recommendations for allocating language classes to user types.

The method integrates the results of existing human factors studies and provides a structured framework for future research in this area. Current and expected developments are exemplified by the description of "new generation" database query languages. In a practical query language selection problem, the results of this paper can be used for preselecting suitable query language types; the final selection decision will also depend on organization-specific factors, such as the available database management system, hardware and software strategies, and financial system costs.