bluuebunny/crossref_metadata_2025 huggingface dataset:
PERFORMANCE OF GZRP AD HOC ROUTING PROTOCOL
Authors: BOUKERCHE AZZEDINE , ROGERS STEVE
Published: July 2002

Ad hoc networks are useful for providing communication support where no fixed infrastructure exists or the deployment of a fixed infrastructure is not economically profitable, and movement of communicating parties is allowed. Therefore, such networks are designed to operate in widely varying environments, from military networks to low-power sensor networks and other embedded systems. Frequent topology changes caused by node mobility make routing in ad hoc wireless networks a challenging problem.

In this paper, we propose an efficient ad hoc routing algorithm, which we refer to as GZRP, a hybrid protocol that makes use of the ZRP scheme and the Global Positioning System (GPS). As opposed to the ZRP original scheme, our GZRP scheme consists of propagating the routing (query) messages only to the nodes that are further away from the query source. We discuss the algorithm, its implementation, and report on the performance of GZRP scheme, and compare it to the ZRP routing protocol using an extensive simulation experiment. Our results indicate clearly that GZRP outperforms ZRP by reducing significantly the number of route query messages, and thereby increases the efficiency of the network load. Furthermore, we show that careful GPS screening angle is an important factor in the success of the GZRP ad hoc routing protocol.
ARTISTIC IMAGE GENERATION BY DEVIATION MAPPING
Authors: LIU WENYIN , TONG XIN , XU YINGQING , SHUM HARRY , ZHONG HUA
Published: July 2002

This paper describes a novel technique (deviation mapping) that generates images with artistic appearances, e.g. spray painted wall, embossment, cashmere painting, etc. Our technique employs a deviation map constructed from a single background image in the image generation process. Instead of recovering the exact geometry from the background image, the deviation map can be regarded as a virtual surface. This virtual surface is then painted with a foreground image and illuminated to generate the final result. Interestingly, the synthesized images exhibit some artistic appearances. Our method is very fast and very simple to implement.
RECURRENCE TIME STATISTICS IN CHAOTIC DYNAMICS: MULTIPLE RECURRENCES IN INTERMITTENT CHAOS
Authors: BALAKRISHNAN V. , NICOLIS G. , NICOLIS C.
Published: July 2002

An exact expression is derived for the distribution of successive recurrences in a finite-cell partition of a general family of one-dimensional maps exhibiting intermittent chaos due to a tangency at a marginally stable fixed point, characterized by an index α. It is shown that multiple recurrences are not statistically independent events in the strict sense of the term. The asymptotic factorization of the joint distribution into a product of first recurrence time distributions is also analyzed.
THE GROWTH DYNAMICS OF GERMAN BUSINESS FIRMS
Authors: VOIT JOHANNES
Published: July 2002

We determine the distribution of size and growth rates of German business firms in 1987–1997. We find a log-normal size distribution. The distribution of growth rates has fat tails. It can be fitted to an exponential in a narrow central region and is dominated by finite-sample-size effects far in its wings. We study the dependence of the growth rate distribution on firm size: depending on procedures, we find almost no dependence when the center of the distribution is considered or, similar to previous work, a power-law when the wings are weighted more strongly. Correlations in the growth of different firms are essentially random. We determine the annual growth of the entire economy, and successfully correlate it with a standard economic indicator of business cycles in Germany. We emphasize possible problems related to the finite number of firms comprised in our database and its short extension in time.
TECHNOLOGICAL COMPETENCIES AND COMPETITIVE ADVANTAGE IN THE SPANISH ELECTRICITY INDUSTRY: NEW CHALLENGES, NEW TOOLS
Authors: RODRÍGUEZ POMEDA JESÚS , MORCILLO ORTEGA PATRICIO , FERNÁNDEZ DE NAVARRETE FERNANDO CASANI , RODRÍGUEZ ANTÓN JOSÉ MIGUEL
Published: July 2002

Recently, the electricity industry in Spain has experienced a deep transformation, aimed to improve the degree of concurrence between the operating firms. This change must be explained in the framework of the regional integration of markets with an European scale. The European Union is shaped as a relevant region in the world energy (and specifically, in electricity) market.

Facing this change, the Spanish electricity firms must adopt a wider business vision, to cope with all the aspects of the new competitive environment in order to obtain business success.

Firms, following the resource-based view, must generate and strengthen the competitive advantage derived from its core competencies. Those competencies, that constitutes the base for the inter-firm heterogeneity, are created (and evolve) from several mechanisms of organisational learning.

Our research tries to show what the business vision of the Spanish electricity firms is, based on the efficient management of its personal, technological and organisational competencies. We have focused on technological competencies, because, in a more competitive scheme, they can support the sustained competitive advantage of the firm. So, we develop a model based on the Strategic Matrix of Technological Competencies (SMTC). The model is tested with a sample of 20 Spanish electricity firms (representing 71.25% of the industry total turnover in 1996). That matrix combines, in a dynamic sense, several scenarios and strategic business units in order to determine the critical technological competencies that the firm must master in each economic situation.

The empirical analysis developed concludes (for the firms in the sample), among other issues, the existence of statistical relationships between certain technological competencies (as "Clean Use of Coal", "Advanced Technologies for Control and Communication", and "Electricity Transmission Technologies"), and several sources of competitive advantage (as the "The firm must difficult its resources' imitability").

In conclusion, facing the new competitive environment (in Spain and in the EU), technological competencies are considered by those firms as sources of competitive advantage. These competencies evolves using several organisational learning systems adopted by the firm. In this changing environment, the SMTC can be a relevant tool for the strategic management of the firms in the electricity industry.
Rounding errors in certain algorithms involving Markov chains
Authors: Grassmann Winfried K.
Published: July 2002

A number of algorithms involving Markov chains contain no subtractions. This property makes the analysis of rounding errors particularly simple. To show this, some principles for analyzing the propagation and generation of rounding errors in algorithms containing no subtraction are discussed first. These principles are then applied in the context of a simple recursive algorithm involving the transient solution of discrete-time Markov chains, Jensen's algorithm, and state reduction. Jensen's algorithm, also known as randomization or uniformization, is an algorithm for finding transient solutions of continuous-time Markov chains. State reduction is a method for finding equilibrium probabilities for discrete-time or continuous-time Markov chains.
Channel routing of multiterminal nets
Authors: Gao Shaodi , Kaufmann Michael
Published: July 2002

This paper presents new upper bounds for channel routing of multiterminal nets, which answers the long-standing open question whether or not multiterminal problems really require channels two times wider than 2-terminal problems. We transform any multiterminal problem of density
d
into a so-called extended simple channel routing problem (ESCRP) of density
3d /2 + O√ d log d)
. We then descibe routing algorithms for solving ESCRPs in three different models. The channel width
w
is ≤
3d/2 +O(√d log d)
in the knock-knee and unit-vertical-overlap models, and
w ≤ 3d/2 + O√d log d) + O(ƒ)
in the Manhattan model, where
f
is the flux of the problem. In all three cases, we improve the best-known upper bounds.
The accelerated integer GCD algorithm
Authors: Weber Kenneth
Published: July 2002

Since the greatest common divisor (GCD) of two integers is a basic arithmetic operation used in many mathematical software systems, new algorithms for its computation are of widespread interest. The accelerated integer GCD algorithm discussed here is based on a reduction step proposed by Sorenson (
k
-ary reduction), coupled with the dmod operation similar to Norton's smod. Some practical limitations of Sorenson's reduction have been eliminated. Worst-case complexity is still
O
(n
2
) for
n
-bit input, but actual implementations given input about 4096 bits long perform over 5.5 times as fast as the binary GCD on one computer architecture having a multiply instruction. Independent research by Jebelean points to the same conclusions.
A class of logic problems solvable by linear programming
Authors: Conforti Michele , Cornuéjols Gérard
Published: July 2002

In propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In this paper, we consider sets of clauses for which the corresponding integer programs can be solved as linear programs. We prove that balanced sets of clauses have this property.
Generating test cases for real-time systems from logic specifications
Authors: Mandrioli Dino , Morasca Sandro , Morzenti Angelo
Published: July 2002

We address the problem of automated derivation of functional test cases for real-time systems, by introducing techniques for generating test cases from formal specifications written in TRIO, a language that extends classical temporal logic to deal explicitly with time measures. We describe an interactive tool that has been built to implement these techniques, based on interpretation algorithms of the TRIO language. Several heuristic criteria are suggested to reduce drastically the size of the test cases that are generated. Experience in the use of the tool on real-life cases is reported.
Computing global virtual time in shared-memory multiprocessors
Authors: Fujimoto Richard M. , Hybinette Maria
Published: July 2002

Global virtual time (GVT) is used in the Time Warp synchronization mechanism to perform irrevocable operations such as I/O and to reclaim storage. Most existing algorithms for computing GVT assume a message-passing programming model. Here, GVT computation is examined in the context of a shared-memory model. We observe that computation of GVT is much simpler in shared-memory multiprocessors because these machines normally guarantee that no two processors will observe a set of memory operations as occurring in different orders. Exploiting this fact, we propose an efficient, asynchronous, shared-memory GVT algorithm and prove its correctness. This algorithm does not require message acknowledgments, special GVT messages, or FIFO delivery of messages, and requires only a minimal number of shared variables and data structures. The algorithm only requires one round of interprocessor communication to compute GVT, in contrast to many message-based algorithms that require two. An efficient implementatin is described that eliminates the need for a processor to explicitly compute a local minimum for time warp systems using a lowest-timestamp-first scheduling policy in each processor.

In addition, we propose a new mechanism called
on-the-fly fossil collection
that enables efficient storage reclamation for simulations containing large numbers, e.g., hundreds of thousand or even millions of simulator objects. On-the-fly fossil collection can be used in time warp systems executing on either shared-memory or message-based machines. Performance measurements of the GVT algorithm and the on-the-fly fossil collection mechanism on a Kendall Square Research KSR-2 machine demonstrate that these techniques enable frequent GVT and fossil collections, e.g., every millisecond, without incurring a significant performance penalty
Systems of linear equations with dense univariate polynomial coefficients
Authors: Cabay Stanley , Domzy Bart
Published: July 2002

An algorithm for computing the power series solution of a system of linear equations with components that are dense univariate polynomials over a field is described and analyzed. A method for converting the power series solution to rational form is derived. Theoretical and experimental cost estimates are obtained and used to identify classes of problems for which the power series method outperforms modular methods. Finally, it is shown that the power series method also provides an effective mechanism for solving the problem in which the coefficients of the polynomials are from the ring of integers.
Remark on algorithm 761
Authors: Renka Robert J. , Brown Ron
Published: July 2002

Several inprovements to algorithm 761 are presented. The problems corrected consist of (1) the computation of a determinant in subroutine SDLEQN may result in overflow, (2) subroutine SDTRCH may fail to correctly determine the set of boundary edges, (3) subroutine SDTRTT, which removes long thin triangles from the boundary in order to improve the accuracy of extrapolation, may remove too many triangles, and (4) the nodal derivative estimation procedure, SDPD3P, often fails to achieve cubic precision.
The computational complexity of knot and link problems
Authors: Hass Joel , Lagarias Jeffrey C. , Pippenger Nicholas
Published: July 2002

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, ie., capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, UNKNOTTING PROBLEM is in NP. We also consider the problem, SPLITTING PROBLEM of determining whether two or more such polygons can be split, or continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it. We show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE. We also give exponential worst-case running time bounds for deterministic algorithms to solve each of these problems. These algorithms are based on the use of normal surfaces and decision procedures due to W. Haken, with recent extensions by W. Jaco and J. L. Tollefson.
Algorithm 789: SLTSTPAK
Authors: Pryce J. D.
Published: July 2002

We give technical details of the Sturm-Liouville test package SLTSTPAK, complementing the companion article (this issue) on its design. SLTSTPAK comprises the follwing : a specification of how to write a routine TSTSET containing a set of Sturm-Liouville problems; a number of routines that act as a harness between a TSTSET, written to this specification, and a driver program. A set of 60 standard problems is provided, but it is simple to replace this by another one.
Remark on Algorithm 716
Authors: Testa F. J. , Renka Robert J.
Published: July 2002

The curve-fitting package TSPACK has been converted to double precision. Also, portability has been improved by eliminating some potential errors.
Reifying variants in configuration management
Authors: Jézéquel Jean-Marc
Published: July 2002

Using a solid software configuration management (SCM) is mandatory to establish and maintain the integrity of the products of a software project throughout the project's software life cycle. Even with the help of sophisticated tools, handling the various dimensions of SCM can be a daunting (and costly) task for many projects. The contribution of this article is to (1)propose a method (based on the use creational design patterns) to simplify SCM by reifying the
variants
of an object-oriented software system into language-level objects and (2)show that newly available compilation technology makes this proposal attractive with respect to performance (memory footprint and execution time) by inferring which classes are needed for a specific configuration and optimizing the generated code accordingly.
Soundness and completeness of a synthesis algorithm based on example computations
Authors: Bauer M. A.
Published: July 2002

The problem of synthesizing a procedure from example computations is examined. An algorithm for this task is presented, and its success is considered. To do this, a model of procedures and example computations is introduced, and the class of acceptable examples is defined. The synthesis algorithm is shown to be successful, with respect to the model of procedures and examples, from two perspectives. First, it is shown to be sound, that is, that the procedure synthesized from a set of examples produces the same result as the intended one on the inputs used to generate that set of examples. Second, it is shown to be complete, that is, that for any procedure in the class of procedures, there exists a finite set of examples such that the procedure synthesized behaves as the intended one on all inputs for which the intended one halts.
Dense multiway trees
Authors: Culik K. , Ottmann Th. , Wood D.
Published: July 2002

B-trees of order
m
are a “balanced” class of
m
-ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion algorithms, their storage utilization, that is, the number of keys per page or node, is at worst 50 percent. In the present paper we investigate a new class of balanced
m
-ary trees, the dense multiway trees, and compare their storage utilization with that of B-trees of order
m
.

Surprisingly, we are able to demonstrate that weakly dense multiway trees have an
Ο
(log
2
N
) insertion algorithm. We also show that inserting

m
h

- 1 keys in ascending order into an initially empty dense multiway tree yields the complete
m
-ary tree of height
h
, and that at intermediate steps in the insertion sequence the intermediate trees can also be considered to be as dense as possible. Furthermore, an analysis of the limiting dynamic behavior of the dense
m
-ary trees under insertion shows that the average storage utilization tends to 1; that is, the trees become as dense as possible. This motivates the use of the term “dense.”
Functions in databases
Authors: Graham Marc H.
Published: July 2002

We discuss the objectives of including functional dependencies in the definition of a relational database. We find two distinct objectives. The appearance of a dependency in the definition of a database indicates that the states of the database are to encode a function. A method based on the chase of calculating the function encoded by a particular state is given and compared to methods utilizing derivations of the dependency. A test for deciding whether the states of a schema may encode a nonempty function is presented as is a characterization of the class of schemas which are capable of encoding nonempty functions for all the dependencies in the definition. This class is the class of dependency preserving schemas as defined by Beeri et al. and is strictly larger than the class presented by Bernstein.

The second objective of including a functional dependency in the definition of a database is that the dependency be capable of constraining the states of the database; that is, capable of uncovering input errors made by the users. We show that this capability is weaker than the first objective; thus, even dependencies whose functions are everywhere empty may still act as constraints. Bounds on the requirements for a dependency to act as a constraint are derived.

These results are founded on the notion of a weak instance for a database state, which replaces the universal relation instance assumption and is both intuitively and computationally more nearly acceptable.
The IBM Magnetic Drum Calculator Type 650
Authors: Hamilton F. E. , Kubie E. C.
Published: July 2002

The IBM Magnetic Drum Calculator Type 650 is an electronic calculator intermediate in speed, capacity and cost. It takes a logical position between the IBM Card Programmed Electronic Calculator and the IBM Electronic Data Processing Machines Type 701. It is a more powerful computing tool as required by those who have “outgrown” the Card Programmed Electronic Calculator. It is also a machine which may be used economically by those who are not as yet ready for a large scale computer such as the 701. It will serve not only to perform their required computing tasks, but it will also result in gaining valuable experience for later use of large scale equipment. The Magnetic Drum Calculator, through its stored program control, comprehensive order list, punched card input-output, self-checking and moderate memory capacity, gains the flexibility required of a computer which is to serve in both the commercial and scientific computing fields.

Approximately 2000 tubes are used in the machine. They are the 5965, 6211, 12AY7, 6AL5, 2D21 and 5687. Types 6211, and 5965 are similar to the 12AV7. These are used because they meet special IBM acceptance tests.
On the Increase of Convergence Rates of Relaxation Procedures for Elliptic Partial Difference Equations
Authors: Juncosa M. L. , Mullikin T. W.
Published: July 2002

Occasionally in the numerical solution of elliptic partial differential equations the rate of convergence of relaxation methods to the solution is adversely affected by the relative proximity of certain points in the grid. It has been proposed that the removal of the unknown functional values at these points by Gaussian elimination may accelerate the convergence.

By application of the Perron-Frobenius theory of non-negative matrices it is shown that the rates of convergence of the Jacobi-Richardson and Gauss-Seidel iterations are not decreased and could be increased by this elimination. Although this may indicate that the elimination could improve the convergence rate for overrelaxation, it is still strictly an unsolved problem.
Some Methods for Simplifying Switching Circuits Using “Don't Care” Conditions
Authors: Chu J. T.
Published: July 2002

Several methods for simplifying switching circuits using “don't-care” conditions are suggested. One of the methods uses the following procedure: Let the given circuit be represented by the truth function
F
. Let the given “don't-care” conditions be denoted by
D
= 0. (For example, if
x
1
= 1 and
x
2
= 0 represent the combination of input signals which never takes place, then
D
=
x
1
x
2
.) Generate all the irredundant disjunctive and conjunctive forms which are equivalent to
F
whenever
D
= 0. From these forms, the simplest ones may then be chosen according to a given measure of simplicity. They correspond to the simplest two-level AND/OR or OR/AND switching circuits which, under the “don't-care” conditions, perform the same function as the given circuit. Several methods for generating the equivalent irredundant forms are suggested. They are generalizations of those due to Quine, Ghazala and Mott, and may be programmed for use on computers. Alternative simplification methods are also given.
Tape Sets and Automata
Authors: Brown R. R.
Published: July 2002

Tape sets and a tape set product are defined, and relationships are found between a table of products of tape sets and elements in the operation-preserving group of a finite automaton.
Two New Classes of Algorithms for Finding the Eigenvalues and Eigenvectors of Real Symmetric Matrices
Authors: La Budde C. Donald
Published: July 2002

The algorithms described in this paper are essentially Jacobi-like iterative procedures employing Householder orthogonal similarity transformations and Jacobi orthogonal similarity transformations to reduce a real symmetrix matrix to diagonal form. The convergence of the first class of algorithms depends upon the fact that the algebraic value of one diagonal element is increased at each step in the iteration and the convergence of the second class of algorithms depends upon the fact that the absolute value of one off-diagonal element is increased at each step in the iteration. Then it is shown how it is possible to combine one algorithm from each class together into a “mixed” strategy for diagonalizing a real symmetric matrix.
Function Evaluation in Unnormalized Arithmetic
Authors: Ashenhurst R. L.
Published: July 2002

The evaluation of a function of one argument is a standard computational task. When an unnormalized number representation is used, it is appropriate that function evaluation to subject to certain “adjustment” criteria, defined independently of the computing method. In this paper some such criteria are developed, and their application described.

In particular, consideration is given to questions of the extent to which general principles apply (i.e. for large classes of functions of a single argument) and the manner in which particular properties of the functions involved (e.g. the functions evaluated by standard library subroutines) may be invoked. The analysis, although framed in terms of unnormalized arithmetic, gives insight into the general nature of significance propagation through function evaluation, and provides a means for analyzing calculations carried out in the usual normalized arithmetic, particularly in the case where an “index of significance” is employed.
A Note on Linear Extrapolation of Multivariable Functions by the Monte Carlo Method
Authors: Tsuda Takao , Matsumoto Hiroshi
Published: July 2002

The feasibility of Monte Carlo linear extrapolation of multivariable functions is discussed. The method considered is a modified version of the Monte Carlo method for linear interpolation. An effective truncation procedure is introduced, which not only economizes the machine time to a greet extent, but also serves for the purpose of variance reduction. A few examples were tested, all of which have shown that the method is promising.
Group-Type Automata
Authors: Trauth Charles A.
Published: July 2002

The purpose is to investigate the input structure of automata which have a group-like character. The class of perfect automata investigated by Fleck in [2] and Weeg in [6] is a proper subclass of those considered here.
A Formal System for Differentiation
Authors: Blum E. K.
Published: July 2002

A formal system is presented for the differentiation of mathematical formulas which can be implemented on a digital computer. The system departs in concept from others in that the programming language is nonprocedural, permitting the statement of the problem for the machine to more closely resemble the corresponding statement for the human. Although limited ostensibly to the narrow and well-defined problem of mechanizing differentiation, many of the ideas and techniques presented can be applied in the broader context of the deeper problem of mechanizing mathematics. They should also be useful in programming theory, where the fundamental problem continues to be the narrowing of the gap between a natural language statement of a problem and a formal language statement acceptable to a computer.
Statistical Determination of Certain Mathematical Constants and Functions Using Computers
Authors: Dubey Satya D.
Published: July 2002

With the availability of high speed electronic computers it is now quite convenient to devise statistical experiments for the purpose of estimating certain mathematical constants and functions. The paper contains statistical formulas for estimating such mathematical constants and functions as π,
C
(Euler's constant),
e
, Ψ
(1)
(1), Γ(
x
), In
x
,
B
(
x, y
), arctan
x
, Ψ(
p
) and polygamma functions. Statistical estimates of these quantities may be used to construct desired confidence intervals for these parameters. Although numerical techniques are available to approximate these mathematical quantities very satisfactorily, a statistical approach to these problems seems to deserve mention in the scientific literature. Numerical illustrations are given in the paper which also give some indication of the effect of pseudorandom numbers on the final results. Statistical procedures, considered in the paper, make extensive use of a high speed electronic computer which may help to develop a positive attitude among theoreticians, promising students of mathematics and others toward the role of computers in the ever-expanding scientific work.
Binomial-Weighted Orthogonal Polynomials
Authors: Young Tzay Y.
Published: July 2002

This paper discusses a set of polynomials, {φ

r

(
s
)}, orthogonal over a discrete range, with binomial distribution,
b
(
s
;
n
,
p
), as the weighting function. Two recurrence relations are derived. One expresses φ

r

in terms of φ

r
-1

and Δφ

r
-1

, while the other relates φ

r

with φ

r
-1

and φ

r
-2

. It is shown that these polynomials are solutions of a finite difference equation. Also considered are two special cases. The first is the set of Hermite polynomials derived as a limiting case of the binomial-weighted orthogonal polynomials. The second deals with the Poisson distribution used as the weighting function.
Minimal Experiments for Input-Independent Machines
Authors: Barnes Bruce H. , Fitzgerald John M.
Published: July 2002

If, in a sequential machine, the output upon application of an input character depends only upon the current state of the machine and not upon the input character, the machine is called input-independent. Two states,
p
and
q,
of an input-independent machine are compatible if and only if the output strings from the machine starting in initial state,
p
, are the same as the output strings from the machine with initial state,
q
, for all input strings to the machine in both states.

The minimal length of tape which tests compatibility of states in an input-independent sequential machine with
n
states is (
n
2
- 2
n
)/4 + 1 if
n
is even, and (
n
2
- 2
n
+ 1)/4 if
n
is odd. There are machines with incompatible states such that no tapes of length less than the given bounds will detect the incompatibility.
Common Solutions for
n
Matrix Equations With Applications
Authors: Morris Gerald L. , Odell Patrick L.
Published: July 2002

A solution of
n
matrix equations is formulated by using existing theory of pseudo inverses of matrices. Techniques for solving recursively such systems, techniques for determining the rank of matrices, techniques for testing whether or not a vector is a null vector of a given matrix, and techniques for testing whether or not a constant is an eigenvalue are indicated.
Computational Complexity of One-Tape Turing Machine Computations
Authors: Hartmanis J.
Published: July 2002

The quantitative aspects of one-tape Turing machine computations are considered. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of nonregular sets of sequences. It is shown that the computation time can be used to characterize the complexity of recursive sets of sequences, and several results are obtained about this classification. These results are then applied to the recognition speed of context-free languages and it is shown, among other things, that it is recursively undecidable how much time is required to recognize a nonregular context-free language on a one-tape Turing machine. Several unsolved problems are discussed.
Inversion of Matrices by Partitioning
Authors: Pease Marshall C.
Published: July 2002

The inversion of nonsingular matrices is considered. A method is developed which starts with an arbitrary partitioning of the given matrix. The separate submatrices are grouped into sets determined by the nonzero entries of some appropriate group,
G
, of permutation matrices. The group structure of
G
then establishes a sequence of operations on these sets of submatrices from which the corresponding representation of the inverse is obtained.

Whether the method described is to be preferred to, say, Gauss's algorithm will depend on the capabilities that are required by other parts of the algorithm that is to be implemented in the special-purpose parallel computer. The basic speed, measured by the count of parallel multiplications and divisions, is comparable to that obtained with Gauss's algorithm and is slightly better under certain conditions. The principal difference is that this method uses primarily matrix multiplication, whereas Gauss's algorithm uses primarily row combinations. When the special-purpose computer under design must supply this capability anyway, the method developed here should be considered.

Application of the process is limited to matrices for which we can set up a partitioning such that we can guarantee, a priori, that certain of the submatrices are nonsingular. Hence the method is not useful for arbitrary nonsingular matrices. However, it can be applied to certain important classes of matrices, notably those that are “dominated by the diagonal.” Noise covariance matrices are of this type; therefore the method can be applied to them. The inversion of a noise covariance matrix is required in some problems of optimal prediction and control. It is for applications of this sort that the method seems particularly attractive.
A Linear Format for Resolution With Merging and a New Technique for Establishing Completeness
Authors: Anderson Robert , Bledsoe W. W.
Published: July 2002

A new technique is given for establishing the completeness of resolution-based deductive systems for first-order logic (with or without equality) and several new completeness results are proved using this technique. The technique leads to very simple and clear completeness proofs and can be used to establish the completeness of most resolution-based deductive systems reported in the literature. The main new result obtained by means of this technique is that a linear format for resolution with merging and set of support and with several further restrictions is a complete deductive system for the first-order predicate calculus.
Formalization of Properties of Functional Programs
Authors: Manna Zohar , Pnueli Amir
Published: July 2002

The problems of convergence, correctness, and equivalence of computer programs can be formulated by means of the satisfiability or validity of certain first-order formulas. An algorithm is presented for constructing such formulas for functional programs, i.e. programs defined by LISP-like conditional recursive expressions.
Tree-Manipulating Systems and Church-Rosser Theorems
Authors: Rosen Barry K.
Published: July 2002

Subtree replacement systems form a broad class of tree-manipulating systems. Systems with the “Church-Rosser property” are appropriate for evaluation or translation processes: the end result of a complete sequence of applications of the rules does not depend on the order in which the rules were applied. Theoretical and practical advantages of such flexibility are sketched. Values or meanings for trees can be defined by simple mathematical systems and then computed by the cheapest available algorithm, however intricate that algorithm may be.

We derive sufficient conditions for the Church-Rosser property and discuss their applications to recursive definitions, to the lambda calculus, and to parallel programming. Only the first application is treated in detail. We extend McCarthy's recursive calculus by allowing a choice between call-by-value and call-by-name. We show that recursively defined functions are single-valued despite the nondeterminism of the evaluation algorithm. We also show that these functions solve their defining equations in a “canonical” manner.
Processing Times for Segmented Jobs with I/O Compute Overlap
Authors: Cotten L. W. , Abd-Alla A. M.
Published: July 2002

Compute-output processing times are determined for
n
-segment jobs that are preloaded into main storage and processed with overlap. A queueing model with tandem servers is utilized for the performance analysis. In particular, the solution presented involves determination of the transient response for a batched arrival of
n
segments to be processed through two stages of tandem service with unlimited output buffering. The performance results provide insight into conditions arising in systems consisting of a single CPU and I/O channel with overlap capabilities. Two cases, single-segment overlap and unlimited overlap, are considered. Segmental compute and output (or input) service times are taken to be exponentially distributed; however, the approach is not limited to the exponential case if service is independent. The ratio of mean output time to mean compute time is varied to explore the full range between compute-bound and output-bound extremes. Final results are presented as relative gain over sequential processing.
Some Distribution-Free Aspects of Paging Algorithm Performance
Authors: Franaszek P. A. , Wagner T. J.
Published: July 2002

The topic of this paper is a probabilistic analysis of demand paging algorithms for storage hierarchies. Two aspects of algorithm performance are studied under the assumption that the sequence of page requests is statistically independent: the page fault probability for a fixed memory size and the variation of performance with memory. Performance bounds are obtained which are independent of the page request probabilities. It is shown that simple algorithms exist which yield fault probabilities close to optimal with only a modest increase in memory.
Calculating the Eigenvectors of Diagonally Dominant Matrices
Authors: Blevins M. M. , Stewart G. W.
Published: July 2002

An algorithm is proposed for calculating the eigenvectors of a diagonally dominant matrix all of whose elements are known to high relative accuracy. Eigenvectors corresponding to pathologically close eigenvalues are treated by computing the invariant subspace that they span. If the off-diagonal elements of the matrix are sufficiently small, the method is superior to standard techniques, and indeed it may produce a complete set of eigenvectors with an amount of work proportional to the square of the order of the matrix. An analysis is given of the effects of perturbations in the matrix on the eigenvectors.
Efficiency of a Binary Comparison Storage Technique
Authors: Palmer E. M. , Rahimi M. A. , Robinson R. W.
Published: July 2002

The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of
n
items. Surprisingly, the variance approaches 7 - 2/3π
2
for large
n
.
Efficiency of Computation of Cayley Tables of 2-Groups
Authors: Larson Richard G.
Published: July 2002

Two algorithms for computing the multiplication table of a 2-group are described and discussed. One of the algorithms works in an element-by-element fashion; the other works in terms of subgroups generated by initial subsequences of the given sequence of generators. Estimates of computation times are given which show that the second algorithm is much more efficient than the first. It is also shown how the second algorithm can be modified to make it more useful, without using significantly more time.
Design of a high-performance ATM firewall
Authors: Xu Jun , Singhal Mukesh
Published: July 2002

A router-based packet-filtering firewall is an effective way of protecting an enterprise network from unauthorized access. However, it will not work efficiently in an ATM network because it requires the termination of end-to-end ATM connections at a packet-filtering router, which incurs huge overhead of SAR (Segmentation and Reassembly). Very few approaches to this problem have been proposed in the literature, and none is completely satisfactory. In this paper we present the hardware design of a high-speed ATM firewall that does not require the termination of an end-to-end connection in the middle. We propose a novel firewall design philosophy, called Quality of Firewalling (QoF), that applies security measures of different strength to traffic with different risk levels and show how it can be implemented in our firewall. Compared with the traditional firewalls, this ATM firewall performs exactly the same packet-level filtering without compromising the performance and has the same "look and feel" by sitting at the chokepoint between the trusted ATM LAN and untrusted ATM WAN. It is also easy to manage and flexible to use.
Task-based information management
Authors: Wolverton Michael
Published: July 2002

Effective collaboration in fast-changing environment can put great dem ands on a collaborator's time. Therefore, information retrieval and filtering tools for these environments should impose as little on that time as possible. Not only should they exclude as many irrelevant documents as possible from those presented to the user (to avoid the time wasted sorting through and reading those documents), they should also minimize the user's effort in characterizing his or her information needs. The goal of the Task-based Information Distribution Environment (TIDE) system is to achieve these objectives by explicitly representing each collaborator's current task and using those representations to deliver documents that meet the information needs implied by those tasks. It does this by treating information gathering as a diagnosis problem, in which the situation (i.e., the current state of beliefs about various questions related to a task) leads probabilistically to test that will provide the most evidence toward reaching a diagnosis (i.e., a description of the documents most likely to be useful to that task). It encodes tasks as nodes in a Bayesian network, and computes document descriptions based on the probabilistic relationship among tasks and their corresponding information requirements.
Strength of two data encryption standard implementations under timing attacks
Authors: Hevia Alejandro , Kiwi Marcos
Published: July 2002

We study the vulnerability of two implementations of the Data Encryption Standard (DES) cryptosystem under a timing attack. A timing attack is a method, recently proposed by Paul Kocher, that is designed to break cryptographic systems. It exploits the engineering aspects involved in the implementation of cryptosystems and might succeed even against cryptosys-tems that remain impervious to sophisticated cryptanalytic techniques. A timing attack is, essentially, a way of obtaining some users private information by carefully measuring the time it takes the user to carry out cryptographic operations.
In this work, we analyze two implementations of DES. We show that a timing attack yields the Hamming weight of the key used by both DES implementations. Moreover, the attack is computationally inexpensive. We also show that all the design characteristics of the target system, necessary to carry out the timing attack, can be inferred from timing measurements.
A frontal code for the solution of sparse positive-definite symmetric systems arising from finite-element applications
Authors: Duff Iain S. , Scott Jennifer A.
Published: July 2002

We describe the design, implementation, and performance of a frontal code for the solution of large sparse symmetric systems of linear finite-element equations. The code is intended primarily for positive-definite systems, since numerical pivoting is not performed. The resulting software package, MA62, will be included in the Harwell Subroutine Library. We illustrate the performance of our new code on a range of problems arising from real engineering and industrial applications. The performance of the code is compared with that of the Harwell Subroutine Library general frontal solver MA42 and with other positive-definite codes from the Harwell Subroutine Library.
Improving the effectiveness of information retrieval with local context analysis
Authors: Xu Jinxi , Croft W. Bruce
Published: July 2002

Techniques for automatic query expansion have been extensively studied in information research as a means of addressing the word mismatch between queries and documents. These techniques can be categorized as either global or local. While global techniques rely on analysis of a whole collection to discover word relationships, local techniques emphasize analysis of the top-ranked documents retrieved for a query. While local techniques have shown to be more effective that global techniques in general, existing local techniques are not robust and can seriously hurt retrieved when few of the retrieval documents are relevant. We propose a new technique, called
local context analysis,
which selects expansion terms based on cooccurrence with the query terms within the top-ranked documents. Experiments on a number of collections, both English and non-English, show that local context analysis offers more effective and consistent retrieval results.
Modeling the effect of the atmosphere on light
Authors: Klassen R. Victor
Published: July 2002

The interaction of light with particles suspended in the air is the cause of some beautiful effects. Among these effects are the colors of the sunset, the blue of the sky, and the appearance of a scene in fog. A lighting model that takes into account the effects of scattering by suspended particles is presented. A method of computing the colors of the sun and sky, for any sun position above the horizon, is derived from the lighting model. The model is also suitable for rendering fog under general lighting conditions. As an example of the use of the model for rendering fog, the special case of fog lit by the sun, without shadows, is considered.
On an improved algorithm for decentralized extrema finding in circular configurations of processors
Authors: Franklin Randolph
Published: July 2002

This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2
N
*floor(lg
N
) + 3
N
messages in the worst case, compared to Chang and Roberts'
N
(
N
+ 1)/2 and Hirschberg and Sinclair's 8
N
+ 8*ceiling(
N
lg
N
) messages. The technique is a selective elimination of possible processes, which then merely relay future messages between the remaining contenders.
Computer system design using a hierarchical approach to performance evaluation
Authors: Kumar B. , Davidson E. S.
Published: July 2002

The concept of a hierarchy of performance models is introduced. It is argued that such a hierarchy should consist of models spanning a wide range of accuracy and cost in order to be a cost-effective tool in the design of computer systems. Judicious use of the hierarchy can satisfy the conflicting needs of high accuracy and low cost of performance evaluation. A system design procedure that uses the hierarchy is developed.

The concepts developed are illustrated by applying them to a case study of system design. The results of optimizations conducted using a two-level performance model hierarchy and a simple cost model are discussed. In almost all the experiments conducted, the optimization procedure converged to a region very close to a locally optimum system. The efficiency of the procedure is shown to be considerably greater than that of the brute force approach to system design.
A very high level programming language for data processing applications
Authors: Hammer Michael , Howe W. Gerry , Kruskal Vincent J. , Wladawsky Irving
Published: July 2002

Application development today is too labor-intensive. In recent years, very high-level languages have been increasingly explored as a solution to this problem. The Business Definition Language (BDL) is such a language, one aimed at business data processing problems. The concepts in BDL mimic those which have evolved through the years in businesses using manual methods. This results in three different sublanguages or components: one for defining the business forms, one for describing the business organization, and one for writing calculations.