bluuebunny/crossref_metadata_2025 huggingface dataset:
RIGOROUS NUMERICAL ESTIMATION OF LYAPUNOV EXPONENTS AND INVARIANT MEASURES OF ITERATED FUNCTION SYSTEMS AND RANDOM MATRIX PRODUCTS
Authors: FROYLAND GARY , AIHARA KAZUYUKI
Published: July 2002

We present a fast, simple matrix method of computing the unique invariant measure and associated Lyapunov exponents of a nonlinear iterated function system. Analytic bounds for the error in our approximate invariant measure (in terms of the Hutchinson metric) are provided, while convergence of the Lyapunov exponent estimates to the true value is assured. As a special case, we are able to rigorously estimate the Lyapunov exponents of an iid random matrix product. Computation of the Lyapunov exponents is carried out by evaluating an integral with respect to the unique invariant measure, rather than following a random orbit. For low-dimensional systems, our method is considerably quicker and more accurate than conventional methods of exponent computation. An application to Markov random matrix product is also described.
THE OSEBERG TRANSITION: VISUALIZATION OF GLOBAL BIFURCATIONS FOR THE KURAMOTO–SIVASHINSKY EQUATION
Authors: JOHNSON M. E. , JOLLY M. S. , KEVREKIDIS I. G.
Published: July 2002

We present and discuss certain global bifurcations involving the interaction of one- and two-dimensional invariant manifolds of steady and periodic solutions of the Kuramoto–Sivashinsky equation. Numerical bifurcation calculations, dimensionality reduction using approximate inertial manifolds/forms, as well as approximation and visualization of invariant manifolds are combined in order to characterize what we term the "Oseberg transition".
UNMASKING CHAOTIC MASK BY A WAVELET MULTISCALE DECOMPOSITION ALGORITHM
Authors: HUANG XIANGAO , XU JIANXUE , HUANG WEI , LU ZEJUN
Published: July 2002

A method is proposed for extracting a useful signal hidden in a deterministic chaotic signal using a wavelet multiscale decomposition algorithm that can separate two signals with different wavelet scales. The mask removal is done without resorting to chaos synchronization. It is a noise reduction method without knowing the dynamical model of chaotic system, and restricting the modulation ratio of the chaos signal and useful signal. So this method is effective for unmasking chaotic mask through the quantitative analyses and the numerical simulations of three examples.
ANALYSIS OF BIFURCATIONS IN A POWER SYSTEM MODEL WITH EXCITATION LIMITS
Authors: KAVASSERI RAJESH G. , PADIYAR K. R.
Published: July 2002

This paper studies bifurcations in a three node power system when excitation limits are considered. This is done by approximating the limiter by a smooth function to facilitate bifurcation analysis. Spectacular qualitative changes in the system behavior induced by the limiter are illustrated by two case studies. Period doubling bifurcations and multiple attractors are shown to result due to the limiter. Detailed numerical simulations are presented to verify the results and illustrate the nature of the attractors and solutions involved.
ON HOMOTOPICAL AND HOMOLOGICAL FINITENESS CONDITIONS FOR FINITELY PRESENTED MONOIDS
Authors: KOBAYASHI YUJI , OTTO FRIEDRICH
Published: July 2002

An example of a finitely presented monoid is given that does not satisfy the homotopical finiteness condition [Formula: see text], although it satisfies both the homological finiteness conditions left [Formula: see text] and right [Formula: see text].
QUASI-ISOMETRY INVARIANTS AND ASYMPTOTIC CONES
Authors: DRUŢU CORNELIA
Published: July 2002

We present some results about quasi-isometry invariants, particularly emphasizing the relationships between their behavior and properties of asymptotic cones. Our main objects of study are hyperbolic metric spaces, hyperbolic and solvable groups.
FICTITIOUS DOMAINS METHODS WITH DISTRIBUTED LAGRANGE MULTIPLIERS PART II: APPLICATION TO THE SOLUTION OF SHAPE OPTIMIZATION PROBLEMS
Authors: HASLINGER JAROSLAV , MAITRE JEAN-FRANCOIS , TOMAS LAURENT
Published: July 2002

The distributed Lagrange multipliers based fictitious domain method for the numerical computation of state problems presented in Part I is now used in the frame of shape optimization. Practical aspects of this approach are discussed. In general it is shown that the resulting minimization problem is nonsmooth, due to the locking effect. Two possible regularization techniques are described and the results of one numerical example is shown.
SPATIAL DECAY IN THE PIPE FLOW OF A VISCOUS FLUID INTERFACING A POROUS MEDIUM
Authors: AMES K. A. , PAYNE L. E. , SONG J. C.
Published: July 2002

This paper establishes exponential decay of weighted energy in the pipe flow of a slowly moving viscous fluid interfacing with a porous medium when homogeneous initial and lateral surface boundary conditions and appropriate interface conditions are applied. This decay requires that the net flow across the intake section of the semi-infinite pipe be zero.
Presentations of homotopy skein modules of oriented 3-manifolds
Authors: Kaiser Uwe
Published: July 2002

A new method to derive presentations of skein modules is developed. For the case of homotopy skein modules it will be shown how the topology of a 3-manifold is reflected in the structure of the module. The freeness problem for q-homotopy skein modules is solved, and a natural skein module related to linking numbers is computed.
A MATHEMATICAL ANALYSIS OF A MINIMAL MODEL OF NEMATODE MIGRATION IN SOIL
Authors: FELTHAM D. L. , CHAPLAIN M. A. J. , YOUNG I. M. , CRAWFORD J. W.
Published: July 2002

A minimal model of nematode migration through soil in response to a chemical gradient is presented. We consider Fickian, fractal and porous-media type diffusion of the nematodes, for which the steady-state nematode distributions are found to compare favourably with experimental observations. Analytical results for Fickian nematode diffusion are presented, which are appropriate for the small- and large-time evolution of a nematode distribution. Numerical integrations allow us to compare the three types of nematode diffusion, to provide numerical validation of our analytical results, and to investigate the dependence of the results of our model upon certain key parameters. We conclude with a summary of results and a call for further experimental work.
ADAPTIVE FINITE ELEMENT TECHNIQUES FOR THE ACOUSTIC WAVE EQUATION
Authors: BANGERTH WOLFGANG , RANNACHER ROLF
Published: July 2002

We present an adaptive finite element method for solving the acoustic wave equation. Using a global duality argument and Galerkin orthogonality, we derive an identity for the error with respect to an arbitrary functional output of the solution. The error identity is evaluated by solving the dual problem numerically. The resulting local cell-wise error indicators are used in the grid adaptation process. In this way, the space-time mesh can be tailored for the efficient computation of the quantity of interest. We give an overview of the implementation of the proposed method and illustrate its performance by several numerical examples.
FERROMAGNETS AND KELVIN'S MEDIUM: BASIC EQUATIONS AND WAVE PROCESSES
Authors: GREKOVA ELENA F.
Published: July 2002

The nonlinear constitutive equations of Kelvin's medium (a nonlinear elastic polar medium consisting of rotating particles) are obtained. We establish the analogy between basic equations of saturated elastic ferromagnetic insulators and basic equations of Kelvin's medium. The most general way of taking the couplings of magnetic and elastic subsystems into account is suggested. Wave processes are investigated from this point of view. All results are interpreted both in terms of mechanical medium and ferromagnets.
DOMAIN GROWTH OF THE DAS STRUCTURE ON A QUENCHED Si(111) SURFACE STUDIED BY STM
Authors: SHIMADA WATARU , TOCHIHARA HIROSHI , SATO TOMOSHIGE , IWATSUKI MASASHI
Published: July 2002

We continuously observed the growth of the dimer–adatom–stacking-fault (DAS) domain, in unreconstructed regions remaining after quenching a Si(111) surface to 370–380°C, by using scanning tunneling microscopy. It was observed that a single faulted (F) half of the 9×9 unit cell of the DAS structure grows to a small 9×9 DAS domain. Continuous measurements showed that new F-halves are created sharing corner holes with existing F-halves. The creation of new isolated F-halves was very seldom at 370–380°C, and the region of the DAS structure was grown by expanding the area of the existing DAS domains.
IN SITU GROWTH STUDIES OF In AND Ga ON Si(001) USING STM
Authors: NOGAMI J. , EVANS M. M. R.
Published: July 2002

In an STM experiment, the ability to look at the same area of the surface at different stages of growth gives information on phenomena such as nucleation that would be difficult or impossible to obtain otherwise. In this paper, we illustrate the usefulness of this capability by showing in situ growth data for In and Ga on Si(001). We show that in this system, nucleation is not dominated by defects on the substrate, and that one-dimensional metal rows grow by preferential accommodation of metal atoms at the row ends.
SPEEDING UP MATERIALIZED VIEW SELECTION IN DATA WAREHOUSES USING A RANDOMIZED ALGORITHM
Authors: LEE MINSOO , HAMMER JOACHIM
Published: July 2002

A data warehouse stores information that is collected from multiple, heterogeneous information sources for the purpose of complex querying and analysis. Information in the warehouse is typically stored in the form of materialized views, which represent pre-computed portions of frequently asked queries. One of the most important tasks when designing a warehouse is the selection of materialized views to be maintained in the warehouse. The goal is to select a set of views in such a way as to minimize the total query response time over all queries, given a limited amount of time for maintaining the views (maintenance-cost view selection problem).

In this paper, we propose an efficient solution to the maintenance-cost view selection problem using a genetic algorithm for computing a near-optimal set of views. Specifically, we explore the maintenance-cost view selection problem in the context of OR view graphs. We show that our approach represents a dramatic improvement in time complexity over existing search-based approaches using heuristics. Our analysis shows that the algorithm consistently yields a solution that lies within 10% of the optimal query benefit while at the same time exhibiting only a linear increase in execution time. We have implemented a prototype version of our algorithm which is used to simulate the measurements used in the analysis of our approach.
STACKELBERG LEADERSHIP IN A MARKETING CHANNEL
Authors: JØRGENSEN STEFFEN , SIGUÉ SIMON-PIERRE , ZACCOUR GEORGES
Published: July 2002

This paper provides an answer to the question who should, if any, lead a marketing channel? We consider a channel consisting of one manufacturer and one retailer where each player controls his advertising rate and margin. Supposing that advertising has a carry over effect on demand, we adopt a dynamic model. Nash and Stackelberg equilibria are characterised and outcomes compared with an efficient coordinated solution. Our findings suggest that manufacturer's leadership reduces inefficiency in a channel and is more beneficial to the consumer.
BUCKLING OF RECTANGULAR PLATES WITH INTERNAL HINGE
Authors: XIANG Y. , WANG C. M. , WANG C. Y.
Published: July 2002

This paper is concerned with the elastic buckling of uniaxially/biaxially loaded rectangular plates with an internal hinge and two opposite sides simply supported. The buckling problem is solved analytically using the Levy method. The exact buckling solutions furnished by the Levy method provide benchmark solutions for such plates with an internal hinge. Extensive buckling results are presented for plates of a wide range of aspect ratios, hinge locations and in-plane loading configurations. Based on these results, the buckling behaviour of plates with an internal hinge may be observed with respect to the aforementioned design parameters.
FUZZY IMAGE PROCESSING AND RECOGNITION: UNCERTAINTY HANDLING AND APPLICATIONS
Authors: PAL SANKAR K.
Published: July 2002

Image processing and analysis in fuzzy set theoretic framework is addressed. Various uncertainties involved in these problems and the relevance of fuzzy set theory in handling them are explained. Different image ambiguity measures based on fuzzy entropy and fuzzy geometry of image subsets are mentioned. A discussion is made on the flexibility in choosing membership functions. Illustrations of commonly used fuzzy image processing operations such as enhancement, edge detection segmentation, skeleton extraction, feature extraction are then provided, along with their significance and characteristics. Their applications to some real life problems, e.g., motion frame analysis, remotely sensed image analysis, modeling face images are finally described. An extensive bibliography is also provided.
ZIPF'S LAW AND RANDOM TEXTS
Authors: CANCHO RAMON FERRER i , SOLÉ RICARD V.
Published: July 2002

Random-text models have been proposed as an explanation for the power law relationship between word frequency and rank, the so-called Zipf's law. They are generally regarded as null hypotheses rather than models in the strict sense. In this context, recent theories of language emergence and evolution assume this law as a priori information with no need of explanation. Here, random texts and real texts are compared through (a) the so-called lexical spectrum and (b) the distribution of words having the same length. It is shown that real texts fill the lexical spectrum much more efficiently and regardless of the word length, suggesting that the meaningfulness of Zipf's law is high.
Detection of linear errors via domain testing
Authors: Zeil Steven J. , Afifi Faten H. , White Lee J.
Published: July 2002

Domain testing attempts to find errors in the numeric expressions affecting the flow of control through a program. Intuitively, domain testing provides a systematic form of boundary value testing for the conditional statements within a program. Several forms of domain testing have been proposed, all dealing with the detection of linear errors in linear functions.

Perturbation analysis has been previously developed as a measure of the volume of faults, from within a selected space of possible faults, left undetected by a test set. It is adapted here to errors and error spaces. The adapted form is used to show that the different forms of domain testing are closer in error detection ability than had been supposed. They may all be considered effective for finding linear errors in linear predicate functions. A simple extension is proposed, which allows them to detect linear errors in nonlinear predicate functions using only a single additional test point.
Cost-effective object space management for hardware-assisted real-time garbage collection
Authors: Nilsen Kelvin D. , Schmidt William J.
Published: July 2002

Modern object-oriented languages and programming paradigms require finer-grain division of memory than is provided by traditional paging and segmentation systems. This paper describes the design of an OSM (Object Space Manager) that allows partitioning of real memory on object, rather than page, boundaries. The time required by the OSM to create an object, or to find the beginning of an object given a pointer to any location within it, is approximately one memory cycle. Object sizes are limited only by the availability of address bits. In typical configurations of object-oriented memory modules, one OSM chip is required for every 16 RAM chips. The OSM serves a central role in the implementation of a hardware-assisted garbage collection system in which the worst-case stop-and-wait garbage collection delay ranges between 10 and 500 μsec, depending on the system configuration.
An efficient representation for sparse sets
Authors: Briggs Preston , Torczon Linda
Published: July 2002

Sets are a fundamental abstraction widely used in programming. Many representations are possible, each offering different advantages. We describe a representation that supports constant-time implementations of
clear-set, add-member,
and
delete-member
. Additionally, it supports an efficient
forall
iterator, allowing enumeration of all the members of a set in time proportional to the cardinality of the set.

We present detailed comparisons of the costs of operations on our representation and on a bit vector representation. Additionally, we give experimental results showing the effectiveness of our representation in a practical application: construction of an interference graph for use during graph-coloring register allocation.

While this representation was developed to solve a specific problem arising in register allocation, we have found it useful throughout our work, especially when implementing efficient analysis techniques for large programs. However, the new representation is not a panacea. The operations required for a particular set should be carefully considered before this representation, or any other representation, is chosen.
Effects of the checkpoint interval on time and space in time warp
Authors: Preiss Bruno R. , Loucks Wayne M. , Macintyre Ian D.
Published: July 2002

Optimistically synchronized parallel discrete-event simulation is based on the use of communicating sequential processes. Optimistic synchronization means that the processes proceed under the assumption that a synchronized execution schedule is fortuitous. Periodic checkpointing of the state of a process allows the process to roll back to an earlier state when synchronization errors are detected. This article examines the effects of varying the checkpoint interval on the execution time and memory space needed to perform a parallel simulation.

The empirical results presented in this article were obtained from the simulation of closed stochastic queuing networks with several different topologies. Various intraprocessor process-scheduling algorithms and both lazy and aggressive cancellation strategies are considered. The empirical results are compared with analytical formulae predicting time-optimal checkpoint intervals. Two modes of operation,
throttling
and
thrashing
, have been noted and their effect examined. As the checkpoint interval is increased from one, there is a throttling effect among processes on the same processor, which improves performance. When the checkpoint interval is made too large, there is a thrashing effect caused by interaction between processes on different processors. It is shown that the time-optimal and space-optimal checkpoint intervals are not the same. Furthermore, a checkpoint interval that is too small affects space adversely more than time, whereas, a checkpoint interval that is too large affects time adversely more than space.
Planar-adaptive routing
Authors: Chien Andrew A. , Kim Jae H.
Published: July 2002

Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in
k
-ary
n
-cubes require an exponential number of virtual channels. We describe a family of deadlock-free routing algorithms, called
planar-adaptive routing
algorithms, that require only a constant number of virtual channels, independent of networks size and dimension. Planar-adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar-adaptive networks can simultaneously support both in-order and adaptive, out-of-order packet delivery.

Planar-adaptive routing is of practical significance. It provides the simplest known support for deadlock-free adaptive routing in
k
-ary
n
-cubes of more than two dimensions (with
k
>2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient implementation.

Simulation studies show that planar-adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-adaptive routers increases this advantage. Comparisons with fully adaptive routers show that planar-adaptive routers, limited adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes.

Planar-adaptive routers are a special case of limited adaptivity routers. We define a class of adaptive routers with
f
degrees of routing freedom. This class, termed
f-flat adaptive routers
, allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the routing freedom. However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-adaptive routers, such as deadlock and livelock freedom, also apply to
f
-flat adaptive routers.
Participatory analysis of flexibility
Authors: Kjær Arne , Madsen Kim Halskov
Published: July 2002

Analysis as part of requirements gathering, conducted according to conventional systems development approaches like structured analysis and object-oriented analysis, focuses on standard data formats and general data flow. The data dictionaries and data flow diagrams of Yourdon's structured project life-cycle [21] model the general standard data format and flow, respectively. Within the object-oriented paradigm Booch [2] emphasizes, quoting W. Wulf, that:

We (humans) have developed an exceptionally powerful technique for dealing with complexity. We abstract from it. Unable to master the entirely of an object, we choose to ignore its essential details, dealing with the generalized, idealized model of the object.
(Our emphasis).
A software architecture for supporting the exchange of electronic manuscripts
Authors: Mamrak S. A , Kaelbling M. J , Nicholas C. K. , Share M.
Published: July 2002

As electronic-manuscript exchange becomes more prevalent, problems arise in translating among the wide variety of electronic representations. The optimum solution is a system that can support both the use and the creation of translation tools.
Experiences with selecting search engines using metasearch
Authors: Dreilinger Daniel , Howe Adele E.
Published: July 2002

Search engines are among the most useful and high-profile resources on the Internet. The problem of finding information on the Internet has been replaced with the problem of knowing where search engines are, what they are designed to retrieve, and how to use them. This article describes and evaluates SavvySearch, a metasearch engine designed to intelligently select and interface with multiple remote search engines. The primary metasearch issue examined is the importance of carefully selecting and ranking remote search engines for user queries. We studied the efficacy of SavvySearch's incrementally acquired
metaindex
approach to selecting search engines by analyzing the effect of time and experience on performance. We also compared the metaindex approach to the
simpler categorical approach and showed how much experience is required to surpass the simple scheme.
Unified versioning through feature logic
Authors: Zeller Andreas , Snelting Gregor
Published: July 2002

Software configuration management (SCM) suffers from tight coupling between SCM version-ing models and the imposed SCM processes. In order to adapt SCM tools to SCM processes, rather than vice versa, we propose a unified versioning model, the
version set model
. Version sets denote versions, components, and configurations by
feature terms
, that is, Boolean terms over (
feature : value
)-attributions. Through
feature logic
, we deduce consistency of abstract configurations as well as features of derived components and describe how features propagate in the SCM process; using
feature implications
, we integrate change-oriented and version-oriented SCM models. We have implemented the version set model in an SCM system called ICE, for
Incremental Configuration Environment
. ICE is based on a
featured file system (FFS)
, where version sets are accessed as virtual files and directories. Using the well-known C preprocessor (CPP) representation, users can view and edit multiple versions simultaneously, while only the differences between versions are stored. It turns out that all major SCM models can be realized and integrated efficiently on top of the FFS, demonstrating the flexible and unifying nature of the version set model.
Managing level of detail through peripheral degradation
Authors: Watson Benjamin , Walker Neff , Hodges Larry F. , Worden Aileen
Published: July 2002

Two user studies were performed to evaluate the effect of level-of-detail (LOD) degradation in the periphery of head-mounted displays on visual search performance. In the first study, spatial detail was degraded by reducing resolution. In the second study, detail was degraded in the color domain by using grayscale in the periphery. In each study, 10 subjects were given a complex search task that required users to indicate whether or not a target object was present among distracters. Subjects used several different displays varying in the amount of detail presented. Frame rate, object location, subject input method, and order of display use were all controlled. The primary dependent measures were search time on correctly performed trials and the percentage of all trials correctly performed. Results indicated that peripheral LOD degradation can be used to reduce color or spatial visual complexity by almost half in some search tasks with out significantly reducing performance.
Algorithm 776: SRRIT
Authors: Bai Z. , Stewart G. W.
Published: July 2002

SRRT is a Fortran program to calculate an approximate orthonomral basis fr a dominant invariant subspace of a real matrix
A
by the method of simultaneous iteration. Specifically, given an integer
m
, SRRIT computes a matrix
Q
with
m
orthonormal columns and real quasi-triangular matrix
T
or order
m
such that the equation
AQ = QT
is satisfied up to a tolerance specified by the user. The eigenvalues of
T
are approximations to the
m
eigenvalues of largest absolute magnitude of
A
and the columns of
Q
span the invariant subspace corresponding to those eigenvalues. SRRIT references
A
only through a user-provided subroutine to form the product
AQ
; hence it is suitable for large sparse problems.
The quadcode and its arithmetic
Authors: Li Shu-Xiang , Loew Murray H.
Published: July 2002

The quadcode is a hierarchical data structure for describing digital images. It has the following properties: (1) straightforward representation of dimension, size, and the relationship between an image and its subsets; (2) explicit description of geometric properties, such as location, distance, and adjacency; and (3) ease of conversion from and to raster representation. The quadcode has applications to computer graphics and image processing because of its ability to focus on selected subsets of the data and to allow utilization of multiple resolutions in different parts of the image. A related approach is the quadtree. Samet recently presented a thorough survey of the literature in that field [
7
].
Gargantini
[
2
]
and Abel and Smith
[
1
] presented linear quadtrees and linear locational keys that are efficient labeling techniques for quadtrees. In those papers the geometric concepts of the image are discussed by using the tree as an interpretive medium, and the approaches and procedures are based on traversal of the nodes in the tree. In this paper we present the quadcode system, which is a direct description of the image, and discuss the geometric concepts in terms of the coded images themselves.
Stochastic catastrophe theory in computer performance modeling
Authors: Nelson Randolph
Published: July 2002

In this paper catastrophic behavior found in computer systems is investigated. Deterministic Catastrophe theory is introduced first. Then it is shown how the theory can be applied in a stochastic framework, which is useful for understanding computer system performance models. Computer system models that exhibit stochastic cusp catastrophe behavior are then analyzed. These models include slotted ALOHA, multiprogramming in computer systems, and buffer flow control in computer networks.
Efficient noise-tolerant learning from statistical queries
Authors: Kearns Michael
Published: July 2002

In this paper, we study the problem of learning in the presence of classification noise in the probabilistic learning model of Valiant and its variants. In order to identify the class of “robust” learning algorithms in the most general way, we formalize a new but related model of learning from
statistical queries
. Intuitively, in this model a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given acess to an oracle providing estimates of probabilities over the sample space of random examples.

One of our main results shows that any class of functions learnable from statistical queries is in fact learnable with classification noise in Valiant's model, with a noise rate approaching the information-theoretic barrier of 1/2. We then demonstrate the generality of the statistical query model, showing that practically every class learnable in Valiant's model and its variants can also be learned in the new model (and thus can be learned in the presence of noise). A notable exception to this statement is the class of parity functions, which we prove is not learnable from statistical queries, and for which no noise-tolerant algorithm is known.
On Local Roundoff Errors in Floating-Point Arithmetic
Authors: Kaneko Toyohisa , Liu Bede
Published: July 2002

A bound on the relative error in floating-point addition using a single-precision accumulator with guard digits is derived. It is shown that even with a single guard digit, the accuracy can be almost as good as that using a double-precision accumulator. A statistical model for the roundoff error in double-precision multiplication and addition is also derived. The model is confirmed by experimental measurements.
Efficient Planarity Testing
Authors: Hopcroft John , Tarjan Robert
Published: July 2002

This paper describes an efficient algorithm to determine whether an arbitrary graph
G
can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm used depth-first search and has
O
(
V
) time and space bounds, where
V
is the number of vertices in
G
. An ALGOL implementation of the algorithm succesfully tested graphs with as many as 900 vertices in less than 12 seconds.
An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
Authors: Lehot Philippe G. H.
Published: July 2002

Given a graph
H
with
E
edges and
N
nodes, a graph
G
is sought such that
H
is the line graph of
G
, if
G
exists. The algorithm does this within the order of
E
steps, in fact in
E
+
O
(
N
) steps. This algorithm is optimal in its complexity.
Global Data Flow Analysis and Iterative Algorithms
Authors: Kam John B. , Ullman Jeffrey D.
Published: July 2002

Kildall has developed data propagation algorithms for code optimization in a general lattice theoretic framework. In another direction, Hecht and Ullman gave a strong upper bound on the number of iterations required for propagation algorithms when the data is represented by bit vectors and depth-first ordering of the flow graph is used. The present paper combines the ideas of these two papers by considering conditions under which the bound of Hecht and Ullman applies to the depth-first version of Kildall's general data propagation algorithm. It is shown that the following condition is necessary and sufficient: Let ƒ and
g
be any two functions which could be associated with blocks of a flow graph, let
x
be an arbitrary lattice element, and let 0 be the lattice zero. Then (*) (∀ƒ
,g,x
) [ƒ
g
(0) ≥
g
(0) ∧ ƒ(
x
) ∧
x
]. Then it is shown that several of the particular instances of the techniques Kildall found useful do not meet condition (*).
Product Form and Local Balance in Queueing Networks
Authors: Chandy K. Mani , Howard John H. , Towsley Donald F.
Published: July 2002

A new property of queueing discipline,
station balance
, seems to explain why some disciplines yield product form solutions for queues and networks using nonexponential service disciplines and other disciplines do not. A queueing discipline satisfies station balance if rates at which customers receive service at each position of the queue are proportional to the probability that a customer arrives at that position. Station and local balance in queues and networks of queues are investigated. In addition to characterizing local balance and product form, the results of the paper generalize previous results on local balance to arbitrary differentiable service distribution functions.
Model-checking continuous-time Markov chains
Authors: Aziz Adnan , Sanwal Kumud , Singhal Vigyan , Brayton Robert
Published: July 2002

We present a logical formalism for expressing properties of continuous-time Markov chains. The semantics for such properties arise as a natural extension of previous work on discrete-time Markov chains to continuous time. The major result is that the verification problem is decidable; this is shown using results in algebraic and transcendental number theory.
Complexity of finite-horizon Markov decision process problems
Authors: Mundhenk Martin , Goldsmith Judy , Lusena Christopher , Allender Eric
Published: July 2002

Controlled stochastic systems occur in science engineering, manufacturing, social sciences, and many other cntexts. If the systems is modeled as a Markov decision process (MDP) and will run
ad infinitum
, the optimal control policy can be computed in polynomial time using linear programming. The problems considered here assume that the time that the process will run is finite, and based on the size of the input. There are mny factors that compound the complexity of computing the optimal policy. For instance, there are many factors that compound the complexity of this computation. For instance, if the controller does not have complete information about the state of the system, or if the system is represented in some very succint manner, the optimal policy is provably not computable in time polynomial in the size of the input. We analyze the computational complexity of evaluating policies and of determining whether a sufficiently good policy exists for a MDP, based on a number of confounding factors, including the observability of the system state; the succinctness of the representation; the type of policy; even the number of actions relative to the number of states. In almost every case, we show that the decision problem is complete for some known complexity class. Some of these results are familiar from work by Papadimitriou and Tsitsiklis and others, but some, such as our PL-completeness proofs, are surprising. We include proofs of completeness for natural problems in the as yet little-studied classes NP
PP
.
An empirical evaluation of several methods to select the best system
Authors: Inoue Koichiro , Chick Stephen E. , Chen Chun-Hung
Published: July 2002

Simulation is an important tool for comparing the performance of several alternative systems. There is therefore significant interest in procedures that efficiently select the best system, where best is defined by the maximum or minimum expected simulation output. In this paper, we examine both two-stage and sequential procedures that represent three structurally different modeling methodologies for allocating simulation replications to identify the best system, and we evaluate them empirically with respect to several measures of effectiveness. Empirical evidence suggests that sequential procedures perform better than their two-stage counterparts, including a heuristic sequential variation on Rinott's procedure. Further, there appears to be significant benefit to using procedures based on a Bayesian, average-case analysis as opposed to the statistically-conservative indifference-zone formulation.
Algorithms to reveal properties of floating-point arithmetic
Authors: Malcolm Michael A.
Published: July 2002

Two algorithms are presented in the form of Fortran subroutines. Each subroutine computes the radix and number of digits of the floating-point numbers and whether rounding or chopping is done by the machine on which it is run. The methods are shown to work on any “reasonable” floating-point computer.
Comments on price/performance patterns of U. S. computer systems
Authors: Fedorowicz Jane
Published: July 2002

Several errors are noted in the formulation of econometric models describing computer price/performance patterns. An alternative model is presented which shows the effects of technological advances and computer size on price reduction.
Computer information systems and organization structure
Authors: Robey Daniel
Published: July 2002

A study of Computer Information Systems and Management (CISM) is described and selected results relating to changes in organizational structure in eight organizations are presented. In five of the organizations
no
changes in formal structure accompanied the introduction of CIS. Where organizational changes did occur, the existing structure of the organization was usually reinforced. These findings suggest that CIS is a flexible tool that is compatible with a variety of organizational design options and not a cause of design
per se
.
A unifying look at data structures
Authors: Vuillemin Jean
Published: July 2002

Examples of fruitful interaction between geometrical combinatorics and the design and analysis of algorithms are presented. A demonstration is given of the way in which a simple geometrical construction yields new and efficient algorithms for various searching and list manipulation problems.
High level programming for distributed computing
Authors: Feldman Jerome A.
Published: July 2002

Programming for distributed and other loosely coupled systems is a problem of growing interest. This paper describes an approach to distributed computing at the level of general purpose programming languages. Based on primitive notions of module, message, and transaction key, the methodology is shown to be independent of particular languages and machines. It appears to be useful for programming a wide range of tasks. This is part of an ambitious program of development in advanced programming languages, and relations with other aspects of the project are also discussed.
B-trees re-examined
Authors: Held Gerald , Stonebraker Michael
Published: July 2002

The B-tree and its variants have, with increasing frequency, been proposed as a basic storage structure for multiuser database applications. Here, three potential problems which must be dealt with in such a structure that do not arise in more traditional static directory structures are indicated. One problem is a possible performance penalty.
Interpolation search—a log log
N
search
Authors: Perl Yehoshua , Itai Alon , Avni Haim
Published: July 2002

Interpolation search is a method of retrieving a desired record by key in an ordered file by using the value of the key and the statistical distribution of the keys. It is shown that on the average log log
N
file accesses are required to retrieve a key, assuming that the
N
keys are uniformly distributed. The number of extra accesses is also estimated and shown to be very low. The same holds if the cumulative distribution function of the keys is known. Computational experiments confirm these results.
Jump searching
Authors: Shneiderman Ben
Published: July 2002

When sequential file structures must be used and binary searching is not feasible, jump searching becomes an appealing alternative. This paper explores variants of the classic jump searching scheme where the optimum jump size is the square root of the number of records. Multiple level and variable size jump strategies are explored, appropriate applications are discussed and performance is evaluated.
Synthesizing constraint expressions
Authors: Freuder Eugene C.
Published: July 2002

A constraint network representation is presented for a combinatorial search problem: finding values for a set of variables subject to a set of constraints. A theory of consistency levels in such networks is formulated, which is related to problems of backtrack tree search efficiency. An algorithm is developed that can achieve any level of consistency desired, in order to preprocess the problem for subsequent backtrack search, or to function as an alternative to backtrack search by explicitly determining all solutions.
Generating parsers for affix grammars
Authors: Crowe David
Published: July 2002

Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing than are the latter, however. Koster, the inventor of affix grammars, suggests a top-down scheme for parsing them, based on recursive procedures. This paper presents a bottom-up scheme for parsing them, based on an extension of Floyd Production Language (FPL). Included is an algorithm, similar to that of DeRemer's, for converting a large class of affix grammars into FPL. The paper concludes by discussing briefly the applicabilities of the conversion algorithm and affix grammars in general, and some possible extensions to Koster's definition of affix grammars.
A scheduling algorithm for a computer assisted registration system
Authors: Winters W. K.
Published: July 2002

This paper presents the scheduling algorithm used in the Computer Assisted Registration System at the University of Tennessee. Notation is defined and the logic of the algorithm necessary to implement educational policy is described. Results from the first term's implementation are presented.
The automatic integration of ordinary differential equations
Authors: Gear C. W.
Published: July 2002

An integration technique for the automatic solution of an initial value problem for a set of ordinary differential equations is described. A criterion for the selection of the order of approximation is proposed. The objective of the criterion is to increase the step size so as to reduce solution time. An option permits the solution of “stiff” differential equations. A program embodying the techniques discussed appears in Algorithm 407.
On finding minimum routes in a network with turn penalties
Authors: Caldwell Tom
Published: July 2002

In some highway engineering work it is necessary to find a route between two points in a city's street and freeway network such that a function of time and distance is minimized. Such a route is called a “best” route, and finding such a route is not a difficult task. The Moore Algorithm
1
accomplishes this quite nicely, and using that algorithm and a procedure developed by Hoffman and Pavley
2
(programmed by them for the IBM 650) it is even possible to find the “
N
th best path.”
A comparative study of coarse- and fine-grained safe regression test-selection techniques
Authors: Bible John , Rothermel Gregg , Rosenblum David S.
Published: July 2002

Regression test-selection techniques
reduce the cost of regression testing by selecting a subset of an existing test suite to use in retesting a modified program. Over the past two decades, numerous regression test-selection techniques have been described in the literature. Initial empirical studies of some of these techniques have suggested that they can indeed benefit testers, but so far, few studies have empirically compared different techniques. In this paper, we present the results of a comparative empirical study of two safe regression test-selection techniques. The techniques we studied have been implemented as the tools DejaVu and TestTube; we compared these tools in terms of a cost model incorporating
precision
(ability to eliminate unnecessary test cases),
analysis cost
, and
test execution cost
. Our results indicate, that in many instances, despite its relative lack of precision, TestTube can reduce the time required for regression testing as much as the more precise DejaVu. In other instances, particularly where the time required to execute test cases is long, DejaVu's superior precision gives it a clear advantage over TestTube. Such variations in relative performance can complicate a tester's choice of which tool to use. Our experimental results suggest that a hybrid regression test-selection tool that combines features of TestTube and DejaVu may be an answer to these complications; we present an initial case study that demonstrates the potential benefit of such a tool.
A method for overlapping and erasure of lists
Authors: Collins George E.
Published: July 2002

An important property of the Newell Shaw-Simon scheme for computer storage of lists is that data having multiple occurrences need not be stored at more than one place in the computer. That is, lists may be “overlapped.” Unfortunately, overlapping poses a problem for subsequent erasure. Given a list that is no longer needed, it is desired to erase just those parts that do not overlap other lists. In LISP, McCarthy employs an elegant but inefficient solution to the problem. The present paper describes a general method which enables efficient erasure. The method employs interspersed reference counts to describe the extent of the overlapping.
A note on sampling a tape-file
Authors: Jones T. G.
Published: July 2002

The problem of selecting a random sample of precisely
n
records from a tape film containing
N
records sometimes arises in data processing applications. If a means of obtaining a random sample of
n
integers
r
1
,
r
2
, … ,

r
n

selected from the
N
integers 1, 2, … ,
N
is available, the problem is theoretically simple. All that need be done is to then select the
r
1
th,
r
2
th, … ,

r
n

th records.
Report of a visit to discuss common programming languages in Czechoslavakia and Poland, 1963
Authors: Gosden John A. , Gay Roger E. , Jones John L. , Merner Jack N. , Shaw Christopher J.
Published: July 2002

Early in June 1963 there was a meeting in Berlin [1] of the Subcommittee for Programming Languages, SC5 of TC97, the Technical Committee for Standardization of Computers and Information Processing [2]. Taking advantage of the proximity of Poland and Czechoslovakia, who are interested in the subject but have not actively participated in SC5, a small group representing the Secretariat of SC5 visited those countries. The major purpose of the visit was to discuss such topics as the state of the art of programming languages in each country—both development and use, any national standardization activity, participation in international standardization, and the present state and future prospects of international standardization. A formal report was made to SC5 in Berlin after the visit. The present report is not an official report of the visit. It is a private report of the group, intended for public dissemination. It includes some material not directly relevant to the official purpose of the visit and omits some of the material pertinent only to the official ISO activity, or parts of the discussions which it would be premature or discourteous to publish at this time.