bluuebunny/crossref_metadata_2025 huggingface dataset:
AN INTELLIGENT SYSTEM FOR MANAGING AND UTILIZING INFORMATION RESOURCES OVER THE INTERNET
Authors: OHTANI TAKESHI , CASE SIMON , AZARMI NADER , THINT MARCUS
Published: July 2002

The Internet is a vast, semi-structured information repository that is expanding ever-faster with two alarming results. First, finding information is becoming increasingly difficult, and second, the management of such information resources is also becoming more complex. We have developed an Intelligent Distributed Information Management System (IDIoMS) to solve these problems. IDIoMS provides a comprehensive set of tools for personalized information delivery, and a platform that enables straightforward management of distributed information resources using agent technologies. These agents enable the sharing, management, search, and presentation of useful information that is widely distributed over a network such as the Internet. IDIoMS benefits users through the automatic provision of timely and relevant information with minimal need for users to search for that information. In addition, the system also benefits service providers through the plug-and-play provision of information services that minimizes the overhead needed to make their service widely available. This paper describes the concept and the architecture of IDIoMS and discusses its utility through three field trials.
EQUIVARIANT KNOT SIGNATURES AND FLOER HOMOLOGIES
Authors: LI WEIPING
Published: July 2002

In this paper, we give a description of the equivariant signature of knots from the symplectic topology point of view. For certain knots K in S3, we define a symplectic Floer homology for the representation space of the knot group π1 (S3\ K) into SU(2) with trace [Formula: see text] along all meridians (p is an odd prime and 0<k<p). The symplectic Floer homology of knots is a new invariant of knots and its Euler number is half of the equivariant signature of knots.
ON FINITENESS OF VASSILIEV INVARIANTS AND A PROOF OF THE LIN-WANG CONJECTURE VIA BRAIDING POLYNOMIALS
Authors: Stoimenow A.
Published: July 2002

Using the new approach of braiding sequences we give a proof of the Lin-Wing conjecture, stating that a Vassiliev invariant ν of degree k has a value Oν (c(K)k) on a knot K, where c(K) is the crossing number of K and Oν depends on ν only. We extend our method to give a quadratic upper bound in k for the crossing number of alternating/positive knots, the values on which suffice to determine uniquely a Vassiliev invariant of degree k. This also makes orientation and mutation sensitivity of Vassiliev invariants decidable by testing them on alternating/positive knots/mutants only.

We give an exponential upper bound for the number of Vassiliev invariants on a special class of closed braids.
ALL UNIVERSES GREAT AND SMALL
Authors: BARROW JOHN D. , KODAMA HIDEO
Published: July 2002

If the topology of the universe is compact we show how it significantly changes our assessment of the naturalness of the observed structure of the universe and the likelihood of its present state of high isotropy and near flatness arising from generic initial conditions. We also identify the most general cosmological models with compact space.
THE PHASE PORTRAIT OF THE REDUCED EINSTEIN EQUATIONS
Authors: FISCHER ARTHUR E. , MONCRIEF VINCENT
Published: July 2002

We discuss the phase portrait of the reduced Einstein (3+1)-equations on a compact manifold of Yamabe type -1. We show that the flow for these equations either has a unique fixed point if the underlying manifold M is hyperbolizable or has no fixed points if M is not hyperbolizable. Thus the topology of M is a critical determinant of the phase portrait of the reduced equations. If, additionally, M is rigid, the fixed point is a local attractor, thereby answering an important question regarding the stability of these model universes. In the non-hyperbolizable case, under certain conditions, the reduced Einstein flow predicts that the conformal volume collapses M, in contrast to the physical volume which, as befits an expanding universe, goes to infinity as the coordinate time goes to infinity.
TUNNELING OF MACROSCOPIC UNIVERSES
Authors: CONRADI HEINZ-DIETER
Published: July 2002

The meaning of 'tunneling' in a timeless theory such as quantum cosmology is discussed. A recent suggestion of 'tunneling' of the macroscopic universe at the classical turning point is analyzed in an anisotropic and inhomogeneous toy model. This 'inhomogeneous tunneling' is a local process which cannot be interpreted as a tunneling of the universe.
ENHANCEMENT AND RESTRICTION OF SYSTEM COORDINATION BY INTERACTION OF PATHWAYS
Authors: LIU JUNLI
Published: July 2002

System coordination for a system with interaction of two pathways is investigated. Sufficient conditions for guaranteeing system coordination subject to any type, amplitude or period of external forcing are analytically derived. Effects of a pathway operating in the opposite direction on system coordination are examined in detail, and it is revealed that the pathway may enhance or restrict system coordination, depending on the values of kinetic parameters. It is concluded that increasing the complexity of enzymatic network by introducing interaction of pathways does not necessarily enhance system coordination. Numerical results using rectangular and sinusoidal forcing support the analytical results, and they quantitatively show how the system with interaction of two pathways maintain its coordination. When the sufficient conditions are satisfied, the system always develops to a finite stable (time-dependent) state under the forcing of any type, amplitude or period. When not, system coordination depends quantitatively on parameter values and the type, amplitude or period of external forcing. When two parameters are forced simultaneously, an additional factor, namely phase shifts between two forced parameters, also affects system coordination. It is shown that, unless the sufficient coordination conditions are maintained, external forcing may induce 'loss of coordination', resulting in the system having no biological functioning. The implications of the results for understanding biochemical coordination and for assessing possible consequences of modulating biochemical systems are discussed.
ELECTRONIC LOCAL DENSITY OF STATES FOR THE TiNi(001) SURFACE
Authors: CANTO G. , DE COSS R. , PAPACONSTANTOPOULOS D. A.
Published: July 2002

We present a self-consistent tight-binding calculation of the electronic structure for the (001) surface of TiNi in the CsCl (B2) structure. The results were obtained using a three-center s–p–d orthogonal tight-binding Hamiltonian fitted to first-principles calculations, within the surface Green function matching formalism. We have analyzed the local density of states (LDOS) for cases with Ni or Ti at the surface layer. For the case where Ni is at the atomic surface layer we find that the corresponding LDOS consists predominantly of bonding states, like in the bulk but with a value at EF reduced by 38% with respect to the bulk; for this surface a strong peak in the LDOS was found at -1.4 eV below EF. For the case where Ti is at the atomic surface layer the corresponding LDOS consists mainly of antibonding states, but with a value at EF higher than in the bulk by 30%. Comparatively, the case where Ni is at the surface layer presents lower values of LDOS at EF and d holes with respect to the case where Ti is at the surface layer, and therefore more chemical activity can be expected for the Ti surface.
TRANSFER OF A POLLUTANT MOLECULE THROUGH A WATER FILM SUPPORTED BY MgO(100): FREE ENERGY PROFILES
Authors: TOUBIN C. , PICAUD S. , HOANG P. N. M. , GIRARDET C. , LYNDEN-BELL R. M.
Published: July 2002

We have determined the free energy profiles for some pollutant molecules (HCl, HOCl and CO 2) entering and crossing a water film supported on a MgO substrate. This was done by using atomistic simulation with models for the pollutant–water, water–water, water–substrate and pollutant–substrate intermolecular potentials. Our aim is to establish these profiles in order to provide a foundation for the understanding of the kinetic processes of pollution on a water-covered surface. We show that the water–substrate interface gives rise to two mimima in the free energy profiles and influence strongly the transfer process.
CORRECTIVE SURGERY OF SYNDACTYLY WITHOUT THE USE OF SKIN GRAFTS
Authors: Vickers D. , Donnelly W.
Published: July 2002

This paper presents an operative technique of syndactyly release (syndactylysis) without skin grafting. A series of 31 cases, of simple, complex and complicated syndactylies are presented with a mean follow-up of 4.4 years. The results demonstrate that a good outcome can be reliably obtained by syndactylysis without the use of skin grafts.
A NEW CLASSIFICATION OF LUNATE NECROSIS
Authors: Martini Abdul K. , Schiltenwolf Marcus
Published: July 2002

The classifications of lunate necrosis used by Decoulxet al. (1957)3and Lichtmanet al. (1977)7and Lichtman and Degnan (1993),6respectively, do not refer to early changes in MRI nor to changes to the carpal architecture, but do attribute the onset of the disease to the presence of a fracture. A recent publication of Lichtman and Ross (1994)8did not solve the problem of a precise description of the disease. This necessitates a new, reliable classification based on the true natural course of the disease.

In a prospective study of 49 patients and in a retrospective analysis of 125 lunate necrosis, the findings obtained prove the regular natural course of the disease. It starts with normal x-ray appearance but the intensity of the signal in T1-weighted MRI is decreased; a fracture line is part of the latter course and not the beginning. It precedes the collapse of the lunate, followed by the collapse of the carpus and the arthritis of the wrist.
MORPHOLOGICAL STUDY OF THE ENTRAPMENT POINT OF UPPER EXTREMITY
Authors: Hirasawa Yasusuke , Okajima Seiichiro , Yoshioka Shinji
Published: July 2002

The morphological study of cubital tunnel, carpal tunnel and the ulnar (Guyon) canal of adult cadavers was done using stereoscopy after injection of the resin into the brachial artery. MRI (Magnetic Resonance Imaging) of the carpal tunnel was also performed for normal volunteers.

In the area of sulcus nervi ulnaris at the elbow, the amount of fibrofatty tissue was extremely small in the nerve trunk, and the nerve was superficially located and found to run close to the hard bony tissue. At the distal margin of the bony sulcus of the ulnar nerve, the nerve ran on the base of hard collateral ligament, where it was covered with a hard ligamentous aponeurosis. The nutrient vessel to the epineurium of the nerve did not exist in the tunnel under the cover of aponeurosis and the nerve was fed by vessels at the entrance of the tunnel and by the recurrent vessels ascending from the musculature at the distal end of the tunnel.

The thickness of the flexor retinaculum from the inlet to the midst of carpal tunnel increases and the thickness became maximum at the outlet. The images of MRI of the carpal tunnel were similar to the corresponding levels, and demonstrated the accuracy of imaging with the anatomical relationships. The ulnar canal itself had few bone elements, and there were neither tight connective tissue nor tendons on the palmar side except for the inlet portion.
FORMALIZATION AND PROOF OF CORRECTNESS OF THE CRASH RECOVERY ALGORITHM FOR AN OPEN AND SAFE NESTED TRANSACTION MODEL
Authors: MADRIA SANJAY KUMAR , MAHESHWARI S. N. , CHANDRA B. , BHARGAVA BHARAT
Published: July 2002

In this paper, we present, formalize and prove the correctness of recovery algorithm for our open and safe nested transaction model using I/O automaton model. Our nested transaction model uses the notion of a recovery point subtransaction in the nested transaction tree. It introduces a prewrite operation before each write operation to increase the potential concurrency. Our transaction model is termed as "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. The systems restart and buffer management operations are modelled as nested transactions to exploit possible concurrency during restart. Each non-access transaction, object, and the scheduler is modeled as I/O automaton. Each of these automata is specified with the help of some pre-and post-conditions. These pre-and post-conditions capture the operational semantics and the behavior of each automaton during recovery operations. Our proof technique makes use of assertional reasoning and provide many interesting invariant, thus gives a better understanding of our recovery algorithm.
MEAN-REVERTING STOCHASTIC VOLATILITY
Authors: FOUQUE JEAN-PIERRE , PAPANICOLAOU GEORGE , SIRCAR K. RONNIE
Published: July 2002

We present derivative pricing and estimation tools for a class of stochastic volatility models that exploit the observed "bursty" or persistent nature of stock price volatility. An empirical analysis of high-frequency S&P 500 index data confirms that volatility reverts slowly to its mean in comparison to the tick-by-tick fluctuations of the index value, but it is fast mean-reverting when looked at over the time scale of a derivative contract (many months). This motivates an asymptotic analysis of the partial differential equation satisfied by derivative prices, utilizing the distinction between these time scales.

The analysis yields pricing and implied volatility formulas, and the latter is used to "fit the smile" from European index option prices. The theory identifies the important group parameters that are needed for the derivative pricing and hedging problem for European-style securities, namely the average volatility and the slope and intercept of the implied volatility line, plotted as a function of the log-moneyness-to-maturity-ratio. The results considerably simplify the estimation procedure, and the data produces estimates of the three important parameters which are found to be stable within periods where the underlying volatility is close to being stationary. These segments of stationarity are identified using a wavelet-based tool.

The remaining parameters, including the growth rate of the underlying, the correlation between asset price and volatility shocks, the rate of mean-reversion of the volatility and the market price of volatility risk can be roughly estimated, but are not needed for the asymptotic pricing formulas for European derivatives. The extension to American and path-dependent contingent claims is the subject of future work.
VALUE-AT-RISK ESTIMATION FOR DYNAMIC HEDGING
Authors: YAMADA YUJI , PRIMBS JAMES A.
Published: July 2002

In this work, we develop an efficient methodology for analyzing risk in the wealth balance (hedging error) distribution arising from a mean square optimal dynamic hedge on a European call option, where the underlying stock price process is modeled on a multinomial lattice. By exploiting structure in mean square optimal hedging problems, we show that moments of the resulting wealth balance may be computed directly and efficiently on the stock lattice through the backward iteration of a matrix. Based on this moment information, convex optimization techniques are then used to estimate the Value-at-Risk of the hedge. This methodology is applied to a numerical example where the Value-at-Risk is estimated for a hedged European call option on a stock modeled on a trinomial lattice.
THE ENTROPY THEORY OF BOND OPTION PRICING
Authors: GULKO LES
Published: July 2002

An informationally efficient price keeps investors as a group in the state of maximum uncertainty about the next price change. The Entropy Pricing Theory (EPT) captures this intuition and suggests that, in informationally efficient markets, perfectly uncertain market beliefs must prevail. When the entropy functional is used to index collective market uncertainty, then the entropy-maximizing consensus beliefs must prevail. The EPT resolves the ambiguity of arbitrage-free valuation in incomplete markets. The EPT produces a new bond option model that is similar to Black–Scholes' with the lognormal distribution replaced by a beta distribution. Unlike alternative models, the beta model is valid for arbitrary term structure dynamics and for arbitrary credit risk of the underlying bonds. Option replication and hedging under the beta model accounts for random changes in the underlying bond price, price volatility and short-term interest rates.
ON MERGE PROPERTIES OF THE SHAPLEY VALUE
Authors: DERKS JEAN , TIJS STEF
Published: July 2002

Given a transferable utility game, where the players merge into subgroups described by a partition, we address the following question: under which conditions on the characteristic function and partition, merging is beneficial if the Shapley value is applied. Our results can be positioned among the search for well-defined classes of games where merging of players is possible without utility loss in case the Shapley value is chosen as the outcome of the game, and we will report on two of these classes of games arising from telecommunication problems.
BUCKLING OF THIN LAMINATED ORTHOTROPIC COMPOSITE RINGs/LONG CYLINDERS UNDER EXTERNAL PRESSURE
Authors: RASHEED HAYDER A. , YOUSIF OMER H.
Published: July 2002

The buckling of isotropic rings under external pressure has attracted the interest of researchers since late 1950s. The formula for critical fluid buckling pressure of thin rings is very well known. This formula was directly extended to account for homogeneous orthotropic rings as well. The buckling of orthotropic cylindrical shells was also a subject of interest since the 1960s. However, the formulations developed, to date, require numerical solutions to obtain the critical pressure. In this work, a generalized closed form analytical formula for the buckling of thin orthotropic multi-angle laminated rings/long cylinders is developed. Standard energy based formulation is used to express the kinematics and equilibrium equations. Classical lamination theory is implemented to introduce the constitutive equations of thin shells. These equations are statically condensed, in terms of the ring's boundary conditions, to produce effective axial, coupling and flexural rigidities for the cases of rings and long cylinders. The critical buckling pressure may be calculated by hand using the derived equation in terms of these effective elastic rigidities. Comparisons are made with some existing results. Parametric studies are conducted to compare the present results with those of the buckling equations implemented by design standards. Various fiber orientations and stacking sequences are considered.
FORECASTING PRICE INCREMENTS USING AN ARTIFICIAL NEURAL NETWORK
Authors: CASTIGLIONE FILIPPO
Published: July 2002

Financial forecasting is a difficult task due to the intrinsic complexity of the financial system. A simplified approach in forecasting is given by "black box" methods like neural networks that assume little about the structure of the economy. In the present paper we relate our experience using neural nets as financial time series forecast method. In particular we show that a neural net able to forecast the sign of the price increments with a success rate slightly above 50% can be found. Target series are the daily closing price of different assets and indexes during the period from about January 1990 to February 2000.
THE EFFECT OF AVALANCHING IN A TWO-SPECIES RIPPLE MODEL
Authors: HOYLE REBECCA B. , MEHTA ANITA
Published: July 2002

This paper discusses a simple two-species ripple model with avalanching. The effect of the avalanching term is investigated numerically, and is found to be crucial in producing realistic ripple profiles.
A COMPARISON OF EVOLUTIONARY AND COEVOLUTIONARY SEARCH
Authors: PAGIE LUDO , MITCHELL MELANIE
Published: July 2002

Previous work on coevolutionary search has demonstrated both successful and unsuccessful applications. As a step in explaining what factors lead to success or failure, we present a comparative study of an evolutionary and a coevolutionary search model. In the latter model, strategies for solving a problem coevolve with training cases. We find that the coevolutionary model has a relatively large efficacy: 86 out of 100 (86%) of the simulations produce high quality strategies. In contrast, the evolutionary model has a very low efficacy: a high quality strategy is found in only two out of 100 runs (2%). We show that the increased efficacy in the coevolutionary model results from the direct exploitation of low quality strategies by the population of training cases. We also present evidence that the generality of the high-quality strategies can suffer as a result of this same exploitation.
Paradigms for process interaction in distributed programs
Authors: Andrews Gregory R.
Published: July 2002

Distributed computations are concurrent programs in which processes communicate by message passing. Such programs typically execute on network architectures such as networks of workstations or distributed memory parallel machines (i.e., multicomputers such as hypercubes). Several paradigms—examples or models—for process interaction in distributed computations are described. These include networks of filters, clients, and servers, heartbeat algorithms, probe/echo algorithms, broadcast algorithms, token-passing algorithms, decentralized servers, and bags of tasks. These paradigms are appliable to numerous practical problems. They are illustrated by solving problems, including parallel sorting, file servers, computing the topology of a network, distributed termination detection, replicated databases, and parallel adaptive quadrature. Solutions to all problems are derived in a step-wise fashion from a general specification of the problem to a concrete solution. The derivations illustrate techniques for developing distributed algorithms.
Algorithm 689: Discretized collocation and iterated collocation for nonlinear Volterra integral equations of the second kind
Authors: Blom J. G. , Brunner H.
Published: July 2002

This paper describes a FORTRAN code for calculating approximate solutions to systems of nonlinear Volterra integral equations of the second kind. The algorithm is based on polynomial spline collocation, with the possibility of combination with the corresponding iterated collocation. It exploits certain local superconvergence properties for the error estimation and the stepsize strategy.
Associative searching in multiple storage units
Authors: Wu C. T. , Burkhard Walter A.
Published: July 2002

A file maintenance model, called the multiple random access storage units model, is introduced. Storage units can be accessed simultaneously, and the parallel processing of an associative query is achieved by distributing data evenly among the storage units. Maximum parallelism is obtained when data satisfying an associative query are evenly distributed for every possible query. An allocation scheme called
M
-cycle allocation is proposed to maintain large files of data on multiple random access storage units. The allocation scheme provides an efficient and straightforward indexing over multidimensional key spaces and supports the parallel processing of orthogonal range queries. Our analysis shows that
M
-cycle allocation achieves the near-optimum parallelism for processing the orthogonal range queries. Moreover, there is no duplication of records and no increase in insertion/deletion cost.
Recursive linear hashing
Authors: Ramamohanarao K , Sacks-Davis R
Published: July 2002

A modification of linear hashing is proposed for which the conventional use of overflow records is avoided. Furthermore, an implementation of linear hashing is presented for which the amount of physical storage claimed is only fractionally more than the minimum required. This implementation uses a fixed amount of in-core space. Simulation results are given which indicate that even for storage utilizations approaching 95 percent, the average successful search cost for this method is close to one disk access.
Designing database interfaces with DBface
Authors: King Roger , Novak Michael
Published: July 2002

DBface is a toolkit for designing interfaces to object-oriented databases. It provides users with a set of tools for building custom interfaces with minimal programming. This is accomplished by combining techniques from User Interface Management Systems (UIMS) with a built-in knowledge about the specific kinds of techniques used by object-oriented databases. DBface allows users to create graphical constructs and interactive techniques by taking advantage of an object-oriented database environment and tools. Not only can database tools be used for creating an interface, but information about the interface being built is stored within a database schema and is syntactically consistent with all other schema information. Thus, an interface can deal with data and schema information, including information about another interface. This allows for easy reusability of graphical constructs such as data representations.
Octrees for faster isosurface generation
Authors: Wilhelms Jane , Van Gelder Allen
Published: July 2002

The large size of many volume data sets often prevents visualization algorithms from providing interactive rendering. The use of hierarchical data structures can ameliorate this problem by storing summary information to prevent useless exploration of regions of little or no
current
interest within the volume. This paper discusses research into the use of the
octree
hierarchical data structure when the regions of current interest can vary during the application, and are not known
a priori
. Octrees are well suited to the six-sided cell structure of many volumes.

A new space-efficient design is introduced for octree representations of volumes whose resolutions are not conveniently a power of two; octrees following this design are called
branch-on-need octrees
(BONOs). Also, a caching method is described that essentially passes information between octree neighbors whose visitation times may be quite different, then discards it when its useful life is over.

Using the application of octrees to isosurface generation as a focus, space and time comparisons for octree-based versus more traditional “marching” methods are presented.
Stationarity detection in the initial transient problem
Authors: Asmussen Søren , Glynn Peter W. , Thorisson Hermann
Published: July 2002

Let
X
= {X(t)}
t ≥ 0
be a stochastic process with a stationary version

X
*

. It is investigated when it is possible to generate by simulation a version
X˜
of
X
with lower initial bias than
X
itself, in the sense that either
X˜
is strictly stationary (has the same distribution as

X
*

) or the distribution of
X˜
is close to the distribution of

X
*

. Particular attention is given to regenerative processes and Markov processes with a finite, countable, or general state space. The results are both positive and negative, and indicate that the tail of the distribution of the cycle length
τ
plays a critical role. The negative results essentially state that without some information on this tail, no a priori computable bias reduction is possible; in particular, this is the case for the class of all Markov processes with a countably infinite state space. On the contrary, the positive results give algorithms for simulating
X˜
for various classes of processes with some special structure on
τ
. In particular, one can generate
X˜
as strictly stationary for finite state Markov chains, Markov chains satisfying a Doeblin-type minorization, and regenerative processes with the cycle length
τ
bounded or having a stationary age distribution that can be generated by simulation.
Discrete-time optimal control problems with general constraints
Authors: Fisher M. E. , Jennings L. S.
Published: July 2002

This paper presents a computational procedure for solving combined discrete-time optimal control and optimal parameter selection problems subject to general constraints. The approach adopted is to convert the problem into a nonlinear programming problem which can be solved using standard optimization software. The main features of the procedure are the way the controls are parametrized and the conversion of all constraints into a standard form suitable for computation. The software is available commercially as a FORTRAN program DMISER3 together with a companion program MISER3 for solving continuous-time problems.
Exact equations of the nonlinear spline
Authors: Edwards John A.
Published: July 2002

We define the spline interpolating function, and obtain in directly computable form the elementary set of nonlinear equations describing nonlinear spline curves. Using Newton's and Newton-like methods, we solve typical spline configurations, and hence infer that the procedure will reliably yield precise extremum-energy solutions to nonlinear splines of arbitrary (but presumably reasonable) size and complexity.

In order to distinguish between stable and unstable states of spline equilibria, we evaluate the energy change resulting from a perturbation, and we briefly discuss aspects of spline existence and uniqueness in relation to the solved examples. We demonstrate the abrupt transition which occurs at the threshold between spline existence and nonexistence, and conclude that proof of a spline's existence is implicit in the solution set of constants yielded by the method.

The procedure may be regarded on the one hand as a precise and efficient research instrument for investigating the properties of true splines and elastica, and on the other as an everyday method for obtaining “the smoothest interpolating curve of all.

Contact is always maintained with the physical analogue to the curve, the thin uniform elastic beam, since the four assignable parameters used in each spline interval comprise the necessary and sufficient three angles and one length dimension of the actual physical spline.

On an historical note, the method may be seen to offer progress in the search, begun in the late 17th century, for a definitive solution to the elastica problem.
CHAOS
arc
: kernel support for multiweight objects, invocations, and atomicity in real-time multiprocessor applications
Authors: Gheith Ahmed , Schwan Karsten
Published: July 2002

CHAOS
arc
is an object-based multiprocessor operating system kernel that provides primitives with which programmers may easily construct objects of differing types and object invocations of differing semantics, targeting multiprocessor systems, and real-time applications. The CHAOS
arc
can
guarantee
desired performance and functionality levels of selected computations in real-time applications. Such guarantees can be made despite possible uncertainty in execution environments by allowing programs to
adapt
in performance and functionality to varying operating conditions. This paper reviews the primitives offered by CHAOS
arc
and demonstrates how the required elements of the CHAOS
arc
real-time kernel are constructed with those primitives.
Stochastic query optimization in distributed databases
Authors: Drenick P. E. , Smith E. J.
Published: July 2002

Many algorithms have been devised for minimizing the costs associated with obtaining the answer to a single, isolated query in a distributed database system. However, if more than one query may be processed by the system at the same time and if the arrival times of the queries are unknown, the determination of optimal query-processing strategies becomes a stochastic optimization problem. In order to cope with such problems, a theoretical state-transition model is presented that treats the system as one operating under a stochastic load. Query-processing strategies may then be distributed over the processors of a network as probability distributions, in a manner which accommodates many queries over time.

It is then shown that the model leads to the determination of optimal query-processing strategies as the solution of mathematical programming problems, and analytical results for several examples are presented. Furthermore, a divide-and-conquer approach is introduced for decomposing stochastic query optimization problems into distinct subproblems for processing queries sequentially and in parallel.
The maintenance of intermediate values in goal-directed evaluation
Authors: Walker Kenneth , Griswold Ralph E.
Published: July 2002

In programming languages that support goal-directed evaluation to make use of alternative results, an expression can produce a value, suspend, and later be resumed to produce another value. This causes control backtracking to earlier points in a computation and complicates the maintenance of intermediate values. This paper presents a space-efficient algorithm computing the lifetimes of intermediate values that is used by an optimizing compiler for the Icon programming language. The algorithm is applicable to other programming languages that employ goal-directed evaluation.
On computing condition numbers for the nonsymmetric eigenproblem
Authors: Bai Z. , Demmel James , McKenney A.
Published: July 2002

We review the theory of condition numbers for the nonsymmetric eigenproblem and give a tabular summary of bounds for eigenvalues, means of clusters of eigenvalues, eigenvectors, invariant subspaces, and related quantities. We describe the design of new algorithms for estimating these condition numbers. Fortran subroutines implementing these algorithms are in the LAPACK library [1].
A visual execution model for Ada tasking
Authors: Dillon Laura K.
Published: July 2002

A visual execution model for Ada tasking can help programmers attain a deeper understanding of the tasking semantics. It can illustrate subtleties in semantic definitions that are not apparent in natural language design. We describe a contour model of Ada tasking that depicts asynchronous tasks (threads of control), relationships between the environments in which tasks execute, and the manner in which tasks interact. The use of this high-level execution model makes it possible to see what happens during execution of a program. The paper provides an introduction to the contour model of Ada tasking and demonstrates its use.
Implementation of a lattice method for numerical multiple integration
Authors: Joe Stephen , Sloan Ian H.
Published: July 2002

An implementation of a method for numerical multiple integration based on a sequence of imbedded lattice rules is given. Besides yielding an approximation to the integral, this implementation also provides an error estimate which does not require much extra computation. The results of some numerical experiments conclude the paper.
Algorithm 727: Quantile estimation using overlapping batch statistics
Authors: Hashem Sherif , Schmeiser Bruce
Published: July 2002

An efficient algorithm for estimating the
q
th quantile of a set of
n
data points is introduced. The standard error of the quantile estimate is estimated using overlapping batch statistics. A driver program is included.
Implementing multiple locks using Lamport's mutual exclusion algorithm
Authors: Boehm Hans-J. , Demers Alan J. , Uhler Chris
Published: July 2002

We describe an approach for implementing higher-level mutual-exclusion constructs using Lamport's algorithm. A straightforward implementation of, for example, monitor locks based on Lamport's algorithm requires O(
n
) space per monitor lock if there are
n
processes that may share the lock. It has occasionally been claimed that this makes the algorithm undesirable in practice. The insight presented here is that we only need a (small) constant amount of space per lock, plus O(
n
) space shared by all locks in the system. For some common applications, this adds no memory references to the implementation of the algorithm. Fully general spin-lock acquisition and release can usually be implemented with the addition of one memory reference to Lamport's algorithm. On particularly unfavorable hardware, three additional memory references may be required in the contention-free case.
Interactive design of smooth objects with probabilistic point constraints
Authors: Rappoport Ari , Hel-Or Yaacov , Werman Michael
Published: July 2002

Point displacement constraints constitute an attractive technique for interactive design of smooth curves, surfaces, and volumes. The user defines an arbitrary number of “control points” on the object and specifies their desired spatial location, while the system computes the object's degrees of freedom so that the constraints are satisfied. A constraint-based interface gives a feeling of direct manipulation of the object. In this article we introduce
soft constraints
, constraints which do not have to be met exactly. The softness of each constraint serves as a nonisotropic, local
shape parameter
enabling the user to explore the space of objects conforming to the constraints. Additionally, there is a global shape parameter which determines the amount of similarity of the designed object to a rest shape, or equivalently, the rigidity of the rest shape.

We present an algorithm termed
probabilistic point constraints (PPC)
for implementing soft constraints. The PPC algorithm views constraints as stochastic measurements of the state of a static system. The softness of a constraint is derived from the
covariance
of the “measurement.” The resulting system of probabilistic equations is solved using the
Kalman filter
, a powerful estimation tool in the theory of stochastic systems. We also describe a user interface using
direct-manipulation devices
for specifying and visualizing covariances in 2D and 3D.

The algorithm is suitable for any object represented as a parametric blend of control points, including most spline representations. The covariance of a constraint provides a continuous transition from exact interpolation to controlled approximation of the constraint. The algorithm involves only linear operations and allows real-time interactive direct manipulation of curves and surfaces on current workstations.
Algorithm 732: solvers for self-adjoint elliptic problems in irregular two-dimensional domains
Authors: Cummins Patrick F. , Vallis Geoffrey K.
Published: July 2002

Software is provided for the rapid solution of certain types of elliptic equations in rectangular and irregular domains. Specifically, solutions are found in two dimensions for the nonseparable self-adjoint elliptic problem ∇·(
g∇Ψ
)=
f
, where
g
and
f
are given functions of
x
and
y
, in two-dimensional polygonal domains with Dirichlet boundary conditions. Helmholtz and Poisson problems in polygonal domains and the general variable coefficient problem (i.e.,
g≠1
) in a rectangular domain may be treated as special cases. The method of solution combines the use of the capacitance matrix method, to treat the irregular boundary, with an efficient iterative method (using the Laplacian as preconditioner) to deal 2 with nonseparability. Each iterative step thus involves solving the Poisson equation in a rectangular domain. The package includes separate, easy-to-use routines for the Helmholtz problem and the general problem in rectangular and general polygonal domains, and example driver routines for each. Both single- and double-precision routines are provided.

Second-order-accurate finite differencing is employed. Storage requirements increase approximately as

p
2

+

n
2

, where
p
is the number of irregular boundary points and where
n
is the linear domain dimension. The preprocessing time (the capacitance matrix calculation) varies as

pn
2

log
n
, and the solution time varies as

n
2

log
n
. If the equations are to be solved repeatedly in the same geometry, but with different source or diffusion functions, the capacitance matrix need only be calculated once, and hence the algorithm is particularly efficient for such cases.
How to forget the past without repeating it
Authors: Naughton Jeffrey F. , Ramakrishnan Raghu
Published: July 2002

Bottom-up evaluation of deductive database programs has the advantage that it avoids repeated computations by storing all intermediate results and replacing recomputation by table lookup. However, in general, storing all intermediate results for the duration of a computation wastes space. In this paper, we propose an evaluation scheme that avoids recomputation, yet for a fairly general class of programs at any given time stores only a small subset of the facts generated. The results constitute a significant first step in compile-time garbage collection for bottom-up evaluation of deductive database programs.
Learning Boolean formulas
Authors: Kearns Michael , Li Ming , Valiant Leslie
Published: July 2002

Efficient distribution-free learning of Boolean formulas from positive and negative examples is considered. It is shown that classes of formulas that are efficiently learnable from only positive examples or only negative examples have certain closure properties. A new substitution technique is used to show that in the distribution-free case learning DNF (disjunctive normal form formulas) is no harder than learning monotone DNF. We prove that monomials cannot be efficiently learned from negative examples alone, even if the negative examples are uniformly distributed. It is also shown that, if the examples are drawn from uniform distributions, then the class of DNF in which each variable occurs at most once is efficiently
weakly learnable
(i.e., individual examples are correctly classified with a probability larger than 1/2 + 1/
p
, where
p
is a polynomial in the relevant parameters of the learning problem). We then show an equivalence between the notion of weak learning and the notion of
group learning
, where a group of examples of polynomial size, either all positive or all negative, must be correctly classified with high probability.
How to create a successful failure
Authors: Charette Robert N.
Published: July 2002

Many people enjoy working on software projects that wing their way towards failure. After all, troubled projects offer so much more in the way of excitement and advantages than those that boringly plod their way to success. For instance, projects in turmoil provide numerous ways to look good. You can make both employer and customer deliriously happy, become a hero, and gain a promotion merely for getting something, anything, delivered on time—while on a smoothly running project, it's expected! Even if you don't make the delivery, you can still appear heroic and get promoted. But if you screw things up, who knows? Then there is the increased job security. Projects in turmoil usually go on far past their original deadlines, as customers are loath to cancel and lose their investment. Your company benefits too, as it gets paid much more than if the project was merely successful.
The information zone system
Authors: Kacmar Charles , Jue Dean
Published: July 2002

Spatial data is complex data composed of hundreds or thousands of attribute/value pairs that define logical, physical, and abstract geographic features. It has traditionally been available to researchers and other users as paper maps, but it is now commonplace to collect and distribute spatial data as structured graphical elements (e.g., vectors) and their associated relational data sets, or as scanned images (when no analysis is necessary). Even though vast stores of spatial data exist, awareness of and access to these data sets, images, and related documents remain tremendous problems [2]. This situation is due in part to the lack of integration between geographic information systems (GIS), storage management, and network tools. It also is due to the dependence on text-based menus and queries to support access. Text-based access is inconsistent for many spatial data users since users conceptualize and data is organized by geographic location [1].
The British Library's initiatives for access projects
Authors: Purday Jonathan
Published: July 2002

The British Library holds over 18 million volumes and is one of the world's greatest treasure houses of written information from every age and culture. In 1993 it published its
Strategic Objectives for the Year 2000
, which made a commitment to providing maximum access to the collection using digital and networking technologies for onsite and remote users.
Numerical analysis using nonprocedural paradigms
Authors: Sullivan Stephen J. , Zorn Benjamin G.
Published: July 2002

This article presents a survey on the innovative features of a handful of languages that offer new features that can be valuable in numerical analysis, and a survey of the pros and cons of the languages with regards to work in numerical analysis. Language features such as polymorphism, first-class functions, and object-oriented programming offer improved writability, readability, reliability, and maintenance of computer software. The article discusses language features and uses, and includes a comparison of current implementations. It is intended both as an introduction to nonprocedural language features for persons working in numerical mathematics and as an exploration of some of the language requirements of numerical mathematics for persons working in language development. The article discusses C++, Fortran 77, Fortran 90, Haskell, Lisp/CLOS, Modula-3, Sather, and SML with respect to a variety of numerical analysis tasks: interpolation, optimization, array access and update, iteration, recursion, random number generation, and Gaussian elimination on sparse matrices.
The effect of data structures on the logical complexity of programs
Authors: Bastani Farokh B. , Iyengar S. Sitharama
Published: July 2002

The logical complexity of a program is a measure of the effort required to understand it. We hypothesize that the logical complexity of a program increases with the increase in the opaqueness of the relationship between the physical data structures used in the program and their corresponding abstract data types. The results of an experiment conducted to investigate this hypothesis are reported. Documentation techniques for making programs easier to understand using complex data structures are discussed. Data structure diagrams, data structure invariants, stepwise transformation of data structures, and formal specification of the mapping between abstract and concrete data structures are illustrated using two nontrivial examples.
Computational issues for accessibility in discrete event simulation
Authors: Yücesan Enver , Jacobson Sheldon H.
Published: July 2002

Several simulation model building and analysis issues have been studied using a computational complexity approach. More specifically, four problems related to simulation model building and analysis (accessibility of states, ordering of events, noninterchangeability of model implementations, and execution stalling) have been shown to be NP-hard search problems. These results imply that it is unlikely that a polynomial-time algorithm can be devised to verify structural properties of discrete event simulation models, unless P = NP. This article considers the problem of
accessibility
, identifies special cases that are polynomially solvable or remain NP-hard, and discusses implications with respect to the other three problems. A local search procedure and variations of simulated annealing are presented to address
accessibility
. Computational results illustrate these heuristics and demonstrate their strengths limitations.
On linear potential functions for approximating Bayesian computations
Authors: Santos Eugene
Published: July 2002

Probabilistic reasoning suffers from NP-hard implementations. In particular, the amount of probabilistic information necessary to the computations is often overwhelming. For example, the size of conditional probability tables in Bayesian networks has long been a limiting factor in the general use of these networks.

We present a new approach for manipulating the probabilistic information given. This approach avoids being overwhelmed by essentially compressing the information using approximation functions called linear potential functions. We can potentially reduce the information from a combinatorial amount to roughly linear in the number of random variable assigments. Furthermore, we can compute these functions through closed form equations. As it turns out, our approximation method is quite general and may be applied to other data compression problems.