bluuebunny/crossref_metadata_2025 huggingface dataset:
APPLICATION OF THE PIPPARD RELATIONS TO AMMONIA NEAR THE MELTING POINT
Authors: YURTSEVEN H.
Published: July 2002

This study gives our application of the Pippard relations to the ammonia near its melting point. The Pippard relations between the specific heat C P , the thermal expansivity α P and the isothermal compressibility κ T , have been established for the ammonia near its melting point. We have obtained that the Pippard relations are valid for the ammonia. We give here an evidence that on the basis of the experimental data the critical transition in this system near its melting point can be considered as the λ-type phase transition.
FACE LEARNING USING A SEQUENCE OF IMAGES
Authors: MARIANI ROBERT
Published: July 2002

We present a face matching algorithm used in the face learning stage. For this, several images of the same person are acquired under head movement constraints, the user rotating his head from left to right. After a precise eyes location, the normalization of the face under rotation and scale is achieved, setting the right and the left eyes at a fixed position. For the recognition, we represent a face as a set of weighted salient points attributed with a local feature vector, giving an invariant description of the image (signal) around each point. In order to compute the variability of the component of the feature vector, as well as the weight associated to each point, denoting its relative importance in the face representation, we have developed a matching algorithm throughout the same sequence. It is formalized as a maximal matching in a bipartite graph and is approximated, due to a planarity constraint, by a probabilistic relaxation scheme.
IMAGE RELATED APPLICATIONS FOR A CORE ALGORITHMS COURSE
Authors: STEVENSON DANIEL E.
Published: July 2002

Image related computations are becoming mainstream in today's computing environment. However, Computer Science departments still offer image related courses mostly as electives or at the graduate level. As imaging's importance increases, one needs to consider its coverage at the core courses. Most departments cannot afford to add another course into their curriculum at this level, so the only remaining choice is to integrate image related applications into the existing core courses. This paper addresses this issue as it relates to an Algorithms course. The specific prerequisites and goals of our Algorithms course are described. The image related applications that have been adopted are presented and their impact on the course is discussed.
USE CASE PATTERNS
Authors: LI LIWU
Published: July 2002

A use case represents a unit of the functionality specification of a system. Industrial object-oriented projects have applied use cases to capture user requirements. Use cases can be used throughout the whole process of object-oriented software development [14]. But, the problem of how to write use cases is still puzzling even software experts [6]. It reflects the lack of a systematic approach to capturing use cases. The set of use cases in a use case model is unstructured regarding the structure of the problem addressed by an application. This paper presents a notion of a use case pattern and proposes using a use case pattern to guide use case capturing. A use case pattern encodes reusable knowledge on the structure and function of a specific class of applications. It guides the work of use case gathering. We illustrate the approach to use case modeling with several use case patterns.
ON THE EXISTENCE OF SPATIALLY PATTERNED DORMANT MALIGNANCIES IN A MODEL FOR THE GROWTH OF NON-NECROTIC VASCULAR TUMORS
Authors: FRIEDMAN AVNER , REITICH FERNANDO
Published: July 2002

Despite their great importance in determining the dynamic evolution of solutions to mathematical models of tumor growth, equilibrium configurations within such models have remained largely unexplored. This was due, in part, to the complexity of the relevant free boundary problems, which is enhanced when the process deviates from radial symmetry. In this paper, we present the results of our investigation on the existence of non-spherical dormant states for a model of non-necrotic vascularized tumors. For the sake of clarity we perform the analysis on two-dimensional geometries, though our techniques are evidently applicable to the full three-dimensional problem. We rigorously show that there is, indeed, an abundance of steady states that are not radially symmetric. More precisely, we prove that at any radially symmetric stationary state with free boundary r=R0 (which we first show to exist), there begin infinitely many branches of equilibria that bifurcate from and break the symmetry of that radial state. The free boundaries along the bifurcation branches are of the form [Formula: see text], where ℓ=2,3,… and |ε|<ε0; each choice of ℓ and ε determines a non-radial steady configuration.
GENERALIZED KINETIC (BOLTZMANN) MODELS: MATHEMATICAL STRUCTURES AND APPLICATIONS
Authors: ARLOTTI L. , BELLOMO N. , DE ANGELIS E.
Published: July 2002

This paper deals with the development of suitable general mathematical structures including a large variety of Boltzmann type models. The contents are organized in three parts. The first part is devoted to modeling the above general framework. The second part to the development of specific models of interest in applied sciences. The third part develops a critical analysis towards research perspectives both on modeling and analytic problems.
DERIVATION AND JUSTIFICATION OF A CURVED ROD MODEL
Authors: JURAK MLADEN , TAMBAČA JOSIP
Published: July 2002

A one-dimensional model of a curved rod is derived from the three-dimensional linearized elasticity. The model is obtained by taking the limit in the equilibrium equation of the three-dimensional elastic rod when the thickness of the rod goes to zero. The appropriate convergence result is proved.
COLORINGS AND ALEXANDER POLYNOMIALS FOR RIBBON 2-KNOTS
Authors: SHIMA AKIKO
Published: July 2002

Let K be a ribbon 2-knot. We show that for any ideal J of the Laurent polynomial ring Λ, if Alexander polynomail of K is trivial, i.e., ΔK(t) = 1, then all colorings of K on Λ/J are trivial.
ON THE CONSISTENCY OF THE CONSTRAINT ALGEBRA IN SPIN NETWORK QUANTUM GRAVITY
Authors: GAMBINI RODOLFO , LEWANDOWSKI JERZY , MAROLF DONALD , PULLIN JORGE
Published: July 2002

We point out several features of the quantum Hamiltonian constraints recently introduced by Thiemann for Euclidean gravity. In particular we discuss the issue of the constraint algebra and of the quantum realization of the object qabVb, which is classically the Poisson Bracket of two Hamiltonians.
NEW COSMOLOGICAL SOLUTIONS AND STABILITY ANALYSIS IN FULL EXTENDED THERMODYNAMICS
Authors: CHIMENTO LUIS P. , JAKUBI ALEJANDRO S. , MÉNDEZ VICENÇ
Published: July 2002

The Einstein's field equations of FRW universes filled with a dissipative fluid described by full theory of causal transport equations are analyzed. New exact solutions are found using a nonlocal transformation on the nonlinear differential equation for the Hubble factor. The stability of the de Sitter and asymptotically Friedmannian solutions are analyzed using Lyapunov function method.
ON GROUP AVERAGING FOR SO(n, 1)
Authors: GOMBEROFF ANDRÉS , MAROLF DONALD
Published: July 2002

The technique known as group averaging provides powerful machinery for the study of constrained systems. However, it is likely to be well-defined only in a limited set of cases. Here, we investigate the possibility of using a "renormalized" group averaging in certain models. The results of our study may indicate a general connection between superselection sectors and the rate of divergence of the group averaging integral.
COVARIANT SYMMETRY CLASSIFICATIONS FOR OBSERVABLES OF COSMOLOGICAL BIREFRINGENCE
Authors: RALSTON JOHN P. , JAIN PANKAJ
Published: July 2002

Polarizations of electromagnetic waves from distant galaxies are known to be correlated with the source orientations. These quantities have been used to search for signals of cosmological birefringence. We review and classify transformation properties of the polarization and source orientation observables. The classifications give a firm foundation to certain practices which have sprung up informally in the literature. Transformations under parity play a central role, showing that parity violation in emission or in the subsequent propagation is an observable phenomenon. We also discuss statistical measures, correlations and distributions which transform properly and which can be used for systematic data analysis.
DENDRITIC BRANCHING PATTERNS OF PYRAMIDAL CELLS IN THE VISUAL CORTEX OF THE NEW WORLD MARMOSET MONKEY, WITH COMPARATIVE NOTES ON THE OLD WORLD MACAQUE MONKEY
Authors: ELSTON GUY N. , JELINEK HERBERT F.
Published: July 2002

The basal dendritic arbors of 442 supragranular pyramidal cells in visual cortex of the marmoset monkey were compared by fractal analyses. As detailed in a previous study,1 individual cells were injected with Lucifer Yellow and processed for a DAB reaction product. The basal dendritic arbors were drawn, in the tangential plane, and the fractal dimension (D) determined by the dilation method. The fractal dimensions were compared between cells in ten cortical areas containing cells involved in visual processing, including the primary visual area (V1), the second visual area (V2), the dorsoanterior area (DA), the dorsomedial area (DM), the dorsolateral area (DL), the middle temporal area (MT), the posterior parietal area (PP), the fundus of the superior temporal area (FST) and the caudal and rostral subdivisions of inferotemporal cortex (ITc and ITr, respectively). Of 45 pairwise interareal comparisons of the fractal dimension of neurones, 20 were significantly different. Moreover, comparison of data according to previously published visual processing pathways revealed a trend for cells with greater fractal dimensions in "higher" cortical areas. Comparison of the present results with those in homologous cortical areas in the macaque monkey2 revealed some similarities between the two species. The similarity in the trends of D values of cells in both species may reflect developmental features which result in different functional attributes.
RANKING FUZZY NUMBERS USING α-WEIGHTED VALUATIONS
Authors: DETYNIECKI MARCIN , YAGER RONALD R.
Published: July 2002

We studied here on some simple examples the interaction between valuation family, parameters and ranking result. The ranking method studied is based upon the idea of associating with a fuzzy number a scalar value, its valuation, and using this valuation to compare and order fuzzy numbers. The valuation method considered was introduced initially by the Yager and Filev. This valuation consists in the integration over α-levels, of the average of each α-cut weighted by a weight distribution function. We finish by introducing a new weight distribution function.
SYNCHROTRON RADIATION SCANNING PHOTOEMISSION MICROSCOPY: INSTRUMENTATION AND APPLICATION IN SURFACE SCIENCE
Authors: KISKINOVA M. , MARSI M. , FABRIZIO E. DI , GENTILI M.
Published: July 2002

X-ray photoelectron spectroscopy has become a true microscopic technique at third generation soft X-ray synchrotron sources, finding applications in many domains of academic and applied research. This paper describes the present status of scanning photoemission microscopy, where by using photon optics the photon beam can be focused to micron or submicron dimensions and imaging or spectroscopy can be performed. It discusses different photon focusing optical elements and describes the major components of the constructed scanning microscopes. The applications of imaging and spectroscopy with high lateral resolution in surface science are illustrated, and some recent results obtained in different laboratories are briefly reviewed.
SECOND-HARMONIC GENERATION AT SEMICONDUCTOR AND METAL SURFACES
Authors: McGILP J. F.
Published: July 2002

Optical second-harmonic generation, although a sophisticated technique, is making a significant contribution to the characterization of surfaces and interfaces. The advantages include: all pressure ranges are accessible; insulators are studied without the problem of charging effects; solid–solid and solid–liquid interfaces are characterized by utilizing the large penetration depth of optical radiation. Single wavelength studies yield information on the crystallographic and magnetic structure of surfaces and interfaces, and are particularly sensitive to symmetry changes. Spectroscopic studies, which have recently become simpler due to the availability of high pulse power, tunable, broadband laser sources, additionally provide electronic structure information, although the interpretation of this may not be simple. In this review examples from well-characterized interfaces are emphasized, and it is shown that the technique is now well understood at the phenomenological level, although theoretical calculations are proving to be difficult. Interfaces not accessible to conventional surface techniques can now be studied with confidence.
DETERMINATION OF THE SURFACE-BARRIER IMAGE-POTENTIAL ORIGIN ON Cu(001) FROM VERY LOW-ENERGY ELECTRON DIFFRACTION
Authors: READ M. N.
Published: July 2002

A set of experimental very low-energy electron diffraction VLEED intensities on Cu(001) for angles of incidence of 35°, 40°, 50°, 60°, 70° and 80° in the (11) azimuth obtained by Dietz, McRae and Campbell has been analyzed using a surface-barrier model which allows for the angle and energy dependence of both the saturation from the image form and the height of the barrier potential. All three parameters of the potential form were allowed to vary independently. It is found that a fit between experiment and theory of the energy position of all the features (minima and maxima) in the entire data set to ≤ 0.07 eV can be obtained with the image-plane origin at z0=-1.70± 0.05 Å from the center of the first row of atoms with a barrier height U0increasing in energy from 11.6 eV with respect to the muffin-tin zero at 35° incidence to 13.1 eV at 80°. The saturation from image form is found to show no trend in variation with respect to the energy or angle of approach of the electron to the barrier and has a value of UD=5.4± 1.0 eV with respect to the vacuum level at the jellium discontinuity. The value of z0and barrier form found here differs from that of previous work of others and the analysis uses the largest VLEED data set to date.
REALISTIC SIMULATIONS OF Au(100): GRAND CANONICAL MONTE CARLO AND MOLECULAR DYNAMICS
Authors: PASSERONE DANIELE , ERCOLESSI FURIO , CELESTINI FRANCK , TOSATTI ERIO
Published: July 2002

The large surface density changes associated with the (100) noble metals surface hex-reconstruction suggest the use of nonparticle-conserving simulation methods. We present an example of a surface Grand Canonical Monte Carlo applied to the transformation of a square nonreconstructed surface to the hexagonally covered low temperature stable Au(100). On the other hand, classical Molecular Dynamics allows one to investigate microscopic details of the reconstruction dynamics, and we show, as an example, retraction of a step and its interplay with the surface reconstruction/deconstruction mechanism.
SURFACE STRUCTURE OF O/Cu(104) FACETS DETERMINED BY X-RAY DIFFRACTION
Authors: WALKO D. A. , ROBINSON I. K.
Published: July 2002

We have determined the surface structure of O/Cu(104) using X-ray diffraction. This surface was prepared by dosing Cu(115) with oxygen, transforming the clean surface into facets with {104} and {113} orientations. This method of preparation, in essence, naturally grows the (104)-oriented substrate concurrent with the O-covered surface, resulting in O/Cu(104) facets which are smooth and highly ordered. Our results indicate that the top three atomic rows significantly expand away from the bulk, but no Cu rows are missing. The Cu–O structures of this surface are similar to those present on other O on Cu surface reconstructions, but the adsorbed O inhabits two adsorption sites with notably distinct geometries. The relationship between the O/Cu(104) and O/Cu(001)[Formula: see text] structures, in particular, is discussed.
RECURRENT DORSAL WRIST GANGLION: AETIOLOGY AND TREATMENT
Authors: Filan Susan L. , Herbert Timothy J.
Published: July 2002

Seven patients with symptomatic recurrent dorsal wrist ganglia were treated by excision of the origin of the ganglion from the scapholunate ligament combined with dorsal capsulorrhaphy. All patients presented with radial wrist pain associated with recurrent dorsal wrist ganglia. Examination revealed localised tenderness over the scapholunate joint with clinical signs of scaphoid instability in every case. Postoperatively, all patients reported pain relief and improved wrist function. There have been no recurrences, with an average follow-up of 14 months (range 12–22 months). Dorsal capsulorrhaphy appears to be a successful method of relieving symptoms, improving wrist function and preventing ganglion recurrence.
A NONLINEAR FILTERING APPROACH TO VOLATILITY ESTIMATION WITH A VIEW TOWARDS HIGH FREQUENCY DATA
Authors: FREY RÜDIGER , RUNGGALDIER WOLFGANG J.
Published: July 2002

In this paper we consider a nonlinear filtering approach to the estimation of asset price volatility. We are particularly interested in models which are suitable for high frequency data. In order to describe some of the typical features of high frequency data we consider marked point process models for the asset price dynamics. Both jump-intensity and jump-size distribution of this marked point process depend on a hidden state variable which is closely related to asset price volatility. In our setup volatility estimation can therefore be viewed as a nonlinear filtering problem with marked point process observations. We develop efficient recursive methods to compute approximations to the conditional distribution of this state variable using the so-called reference probability approach to nonlinear filtering.
HEDGING AND ARBITRAGE WARRANTS UNDER SMILE EFFECTS: ANALYSIS AND EVIDENCE
Authors: CHEN SON-NAN , CHEN AN-PIN , CHANG CAMUS
Published: July 2002

While the Black–Scholes (BS) model and binomial trees assume that the stock price evolves lognormally with constant volatility, volatility smiles are pronounced in almost all the worlds equity markets. To study the effects of volatility smiles on hedging and arbitrage, the method based on the BS model and implemented with observed market volatility smiles is proposed. The empirical results indicate that the proposed model can reduce risk exposure and increase profits on hedging as compared with the BS model, and hence leading to considerable returns on arbitrage-trading in the Taiwan warrant market. The model is proven to be not only useful for warrant issuers who attempt to reduce vega risk, but also practicable for investors to implement as arbitrage strategies under smile effects.
COUNTABLE BOREL EQUIVALENCE RELATIONS
Authors: JACKSON S. , KECHRIS A. S. , LOUVEAU A.
Published: July 2002

This paper develops the foundations of the descriptive set theory of countable Borel equivalence relations on Polish spaces with particular emphasis on the study of hyperfinite, amenable, treeable and universal equivalence relations.
LOCAL CALIBRATIONS FOR MINIMIZERS OF THE MUMFORD–SHAH FUNCTIONAL WITH A TRIPLE JUNCTION
Authors: MORA MARIA GIOVANNA
Published: July 2002

We prove that, if u is a function satisfying all Euler conditions for the Mumford–Shah functional and the discontinuity set of u is given by three line segments meeting at the origin with equal angles, then there exists a neighbourhood U of the origin such that u is a minimizer of the Mumford–Shah functional on U with respect to its own boundary conditions on ∂U. The proof is obtained by using the calibration method.
THE INFLUENCE OF COMBINED CONCENTRATED AND DISTRIBUTED FOLLOWER FORCES ON THE EIGENSOLUTIONS OF A SPINNING BEAM
Authors: HAN RAY P. S. , ZU JEAN W.
Published: July 2002

The free vibrations of a spinning Timoshenko beam under the action of the non-conservative follower forces are solved analytically for the first time. Three types of follower-force system are considered: concentrated follower forces, distributed follower forces and, combined concentrated and distributed follower forces. The resulting characteristic equation for computing frequencies is very complicated and a novel solution algorithm involving symbolic algebraic operations with each term determined recursively, is proposed. Critical values of the concentrated follower forces that correspond to the onset of the flutter-type instability for the first four modes of vibration are presented.
OPTIMAL DIFFUSIVE TRANSPORT IN A TILTED PERIODIC POTENTIAL
Authors: LINDNER BENJAMIN , KOSTUR MARCIN , SCHIMANSKY-GEIER LUTZ
Published: July 2002

We study the diffusive motion of an overdamped Brownian particle in a tilted periodic potential. Mapping the continuous dynamics onto a discrete cumulative process we find exact expressions for the diffusion coefficient and the Péclet number which characterize the transport. At a sufficiently strong but subcritical bias an optimized transport with respect to the noise strength is observed. These results are confirmed by numerical solution of the Fokker-Planck equation.
SYNCHRONIZING TO THE ENVIRONMENT: INFORMATION-THEORETIC CONSTRAINTS ON AGENT LEARNING
Authors: CRUTCHFIELD JAMES P. , FELDMAN DAVID P.
Published: July 2002

Using an information-theoretic framework, we examine how an intelligent agent, given an accurate model of its environment, synchronizes to the environment — i.e., comes to know in which state the environment is. We show that the total uncertainty experienced by the agent during the process is closely related to the transient information, a new quantity that captures the manner in which the environment's entropy growth curve converges to its asymptotic form. We also discuss how an agent's estimates of its environment's structural properties are related to its estimate of the environment entropy rate. If structural properties are ignored, the missed regularities are converted to apparent randomness. Conversely, using representations that assume too much memory results in false predictability.
LIQUID-SOLID TRANSITION IN BIDISPERSE GRANULATES
Authors: LUDING STEFAN
Published: July 2002

Simulation results of dense granulates with particles of different sizes are compared with theoretical predictions concerning the mixture pressure. An effective correlation function is computed which depends only on the total volume fraction and on the dimensionless width of the size-distribution function. From simulation data of elastic and weakly dissipative systems, one can predict how much disorder (size-dispersity) is necessary to avoid ordering effects due to crystallization. Finally, a global equation of state is proposed, which unifies both the dilute, disordered gas/fluid and the dense, solid regime.
Valanche dynamics and long time relaxation in complex systems
Authors: Vázquez Alexei , Sotolongo-Costa Oscar , Brouers Francois
Published: July 2002

We propose an iterative model which incorporates much of the physics of avalanche dynamics and logarithmic relaxation in complex systems. In particular it can be used to interpret the long time behavior in sandpile systems, since it reproduces quite well the long time relaxation in sandpiles under vibration.
Personal computing
Authors: Press Larry
Published: July 2002

It may be trite to say that “the world is shrinking,” but it is true nonetheless. Political and technological changes are edging us in the direction of the global village. We have the economic unification of Western Europe, the transition of Eastern Europe to market economies, and free trade agreements and negotiations in the Western hemisphere. Blue jeans and rock and roll music are found throughout the world, we can direct dial to Iceland, and your grandmother may have a FAX machine.
Reliable solution of special event location problems for ODEs
Authors: Shampine L. F. , Gladwell I. , Brankin R. W.
Published: July 2002

Computing the solution of the initial value problem in ordinary differential equations (ODEs) may be only part of a larger task. One such task is finding where an algebraic function of the solution (an event function) has a root (an event occurs). This is a task which is difficult both in theory and in software practice. For certain useful kinds of event functions, it is possible to avoid two fundamental difficulties. It is described how to achieve the reliable solutions of such problems in a way that allows the capability to be grafted onto popular codes for the initial value problem.
The philosophy of Lisp
Authors: Sinclair Kenneth H. , Moon David A.
Published: July 2002

We consider here the importance of an overall systems viewpoint in avoiding computer-related risks. According to Webster's, a system is a regularly interacting or interdependent group of items forming a unified whole. In computer systems, one person's components may be another person's system, and one person's system may in turn be one of another person's components. That is, each layer of abstraction may have it own concept of a system. We speak of a memory system, a multiprocessor system, a distributed system, a multisystem system, a networked system, and so on. A system design can most effectively be considered
as a unified whole
when it is possible to analyze the interdependent subsystems individually and then to evaluate, reason about, and test the behavior of the entire system based on the interactions among the subsystems. This is particularly true of distributed systems that mask the presence of distributed storage, processing, and control. At each layer of abstraction, it is desirable to design (sub)systems that are context-free, but in reality there may be subtle interactions that must be accommodated—particularly those involving the operating environment.
Investigations of the software testing coupling effect
Authors: Offutt A. Jefferson
Published: July 2002

Fault-based testing strategies test software by focusing on specific, common types of faults. The
coupling effect
hypothesizes that test data sets that detect simple types of faults are sensitive enough to detect more complex types of faults. This paper describes empirical investigations into the coupling effect over a specific class of software faults. All of the results from this investigation support the validity of the coupling effect. The major conclusion from this investigation is the fact that by explicitly testing for simple faults, we are also implicitly testing for more complicated faults, giving us confidence that fault-based testing is an effective way to test software.
Optimism and consistency in partitioned distributed database systems
Authors: Davidson Susan B.
Published: July 2002

A protocol for transaction processing during partition failures is presented which guarantees mutual consistency between copies of data-items after repair is completed. The protocol is “optimistic” in that transactions are processed without restrictions during failure; conflicts are then detected at repair time using a
precedence graph
, and are resolved by backing out transactions according to some
backout strategy
. The resulting database state then corresponds to a serial execution of some subset of transactions run during the failure. Results from simulation and probabilistic modeling show that the optimistic protocol is a reasonable alternative in many cases. Conditions under which the protocol performs well are noted, and suggestions are made as to how performance can be improved. In particular, a backout strategy is presented which takes into account individual transaction costs and attempts to minimize total backout cost. Although the problem of choosing transactions to minimize total backout cost is, in general, NP-complete, the backout strategy is efficient and produces very good results.
Concurrent reading and writing of clocks
Authors: Lamport Leslie
Published: July 2002

As an exercise in synchronization without mutual exclusion, algorithms are developed to implement both a monotonic and a cyclic multiple-word clock that is updated by one process and read by one or more other processes.
Join processing in relational databases
Authors: Mishra Priti , Eich Margaret H.
Published: July 2002

The join operation is one of the fundamental relational database query operations. It facilitates the retrieval of information from two different relations based on a Cartesian product of the two relations. The join is one of the most diffidult operations to implement efficiently, as no predefined links between relations are required to exist (as they are with network and hierarchical systems). The join is the only relational algebra operation that allows the combining of related tuples from relations on different attribute schemes. Since it is executed frequently and is expensive, much research effort has been applied to the optimization of join processing. In this paper, the different kinds of joins and the various implementation techniques are surveyed. These different methods are classified based on how they partition tuples from different relations. Some require that all tuples from one be compared to all tuples from another; other algorithms only compare some tuples from each. In addition, some techniques perform an explicit partitioning, whereas others are implicit.
Reconciling environment integration and software evolution
Authors: Sullivan Kevin J. , Notkin David
Published: July 2002

Common software design approaches complicate both tool integration and software evolution when applied in the development of integrated environments. We illustrate this by tracing the evolution of three different designs for a simple integrated environment as representative changes are made to the requirements. We present an approach that eases integration and evolution by preserving tool independence in the face of integration. We design tool integration relationships as separate components called
mediators
, and we design tools to implicitly invoke mediators that integrate them. Mediators separate tools from each other, while implicit invocation allows tools to remain independent of mediators. To enable the use of our approach on a range of platforms, we provide a formalized model and requirements for implicit invocation mechanisms. We apply this model both to analyze existing mechanisms and in the design of a mechanism for C++.
On statecharts with overlapping
Authors: Harel David , Kahana Chaim-arie
Published: July 2002

The problem of extending the language of statecharts to include overlapping states is considered. The need for such an extension is motivated and the subtlety of the problem is illustrated by exhibiting the shortcomings of naive approaches. The syntax and formal semantics of our extension are then presented, showing in the process that the definitions for conventional statecharts constitute a special case. Our definitions are rather complex, a fact that we feel points to the inherent difficulty of such an extension. We thus prefer to leave open the question of whether or not it should be adopted in practice.
Monitoring distributed systems
Authors: Joyce Jeffrey , Lomow Greg , Slind Konrad , Unger Brian
Published: July 2002

The monitoring of distributed systems involves the collection, interpretation, and display of information concerning the interactions among concurrently executing processes. This information and its display can support the debugging, testing, performance evaluation, and dynamic documentation of distributed systems. General problems associated with monitoring are outlined in this paper, and the architecture of a general purpose, extensible, distributed monitoring system is presented. Three approaches to the display of process interactions are described: textual traces, animated graphical traces, and a combination of aspects of the textual and graphical approaches. The roles that each of these approaches fulfill in monitoring and debugging distributed systems are identified and compared. Monitoring tools for collecting communication statistics, detecting deadlock, controlling the non-deterministic execution of distributed systems, and for using protocol specifications in monitoring are also described.

Our discussion is based on experience in the development and use of a monitoring system within a distributed programming environment called Jade. Jade was developed within the Computer Science Department of the University of Calgary and is now being used to support teaching and research at a number of university and research organizations.
An effective synchronization network for hot-spot accesses
Authors: Hsu William Tsun-Yuk , Yew Pen-Chung
Published: July 2002

In large multiprocessor systems, fast synchronization is crucial for high performance. However, synchronization traffic tends to create “hot-spots” in shared memory and cause network congestion. Multistage shuffle-exchange networks have been proposed and built to handle synchronization traffic. Software combining schemes have also been proposed to relieve network congestion caused by hot-spots. However, multistage combining networks could be very expensive and software combining could be very slow.

In this paper, we propose a single-stage combining network to handle synchronization traffic, which is separated from the regular memory traffic. A single-stage combining network has several advantages: (1) it is attractive from an implementation perspective because only one stage is needed(instead of log
N
stages); (2) Only one network is needed to handle both forward and returning requests; (3) combined requests are distributed evenly through the network—the wait buffer size is reduced; and (4) fast-finishing algorithms [30] can be used to shorten the network delay.

Because of all these advantages, we show that a single-stage combining network gives good performance at a lower cost than a multistage combining network.
An optimal algorithm for intersecting line segments in the plane
Authors: Chazelle Bernard , Edelsbrunner Herbert
Published: July 2002

The main contribution of this work is an
O
(
n
log
n
+
k
)-time algorithm for computing all
k
intersections among
n
line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of
n
+
k
in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.
A methodology for controlling the size of a test suite
Authors: Harrold M. Jean , Gupta Rajiv , Soffa Mary Lou
Published: July 2002

This paper presents a technique to select a representative set of test cases from a test suite that provides the same coverage as the entire test suite. This selection is performed by identifying, and then eliminating, the redundant and obsolete test cases in the test suite. The representative set replaces the original test suite and thus, potentially produces a smaller test suite. The representative set can also be used to identify those test cases that should be rerun to test the program after it has been changed. Our technique is independent of the testing methodology and only requires an association between a testing requirement and the test cases that satisfy the requirement. We illustrate the technique using the data flow testing methodology. The reduction that is possible with our technique is illustrated by experimental results.
Metascheduling for continuous media
Authors: Anderson David P.
Published: July 2002

Next-generation distributed systems will supportcontinuous media(digital audio and video) in the same framework as other data. Many applications that use continuous media need guaranteed end-to-end performance (bounds on throughput and delay). To reliably support these requirements, system components such as CPU schedulers, networks, and file systems must offer performance guarantees. Ametaschedulercoordinates these components, negotiating end-to-end guarantees on behalf of clients. TheCM-resource model, described in this paper, provides a basis for such a metascheduler. It defines a workload parameterization, an abstract interface to resources, and an algorithm for reserving multiple resources. The model uses an economic approach to dividing end-to-end delay, and it allows system components to “work ahead,” improving the performance of nonreal-time workload.
On the analytical modeling of database concurrency control
Authors: Yu Philip S. , Dias Daniel M. , Lavenberg Stephen S.
Published: July 2002

The Concurrency Control (CC) scheme employed can profoundly affect the performance of transaction-processing systems. In this paper, a simple unified approximate analysis methodology to model the effect on system performance of data contention under different CC schemes and for different system structures is developed. This paper concentrates on modeling data contention and then, as others have done in other papers, the solutions of the data contention model are coupled with a standard hardware resource contention model through an iteration. The methodology goes beyond previously published methods for analyzing CC schemes in terms of the generality of CC schemes and system structures that are handled. The methodology is applied to analyze the performance of centralized transaction processing systems using various optimistic- and pessimistic-type CC schemes and for both fixed-length and variable-length transactions. The accuracy of the analysis is demonstrated by comparison with simulations. It is also shown how the methodology can be applied to analyze the performance of distributed transaction-processing systems with replicated data.
The cost of selective recompilation and environment processing
Authors: Adams Rolf , Tichy Walter , Weinert Annette
Published: July 2002

When a single software module in a large system is modified, a potentially large number of other modules may have to be recompiled. By reducing both the number of compilations and the amount of input processed by each compilation run, the turnaround time after changes can be reduced significantly.

Potential time savings are measured in a medium-sized, industrial software project over a three-year period. The results indicate that a large number of compilations caused by traditional compilation unit dependencies may be redundant. On the available data, a mechanism that compares compiler output saves about 25 percent, smart recompilation saves 50 percent, and smartest recompilation may save up to 80 percent of compilation work.

Furthermore, all compilation methods other than smartest recompilation process large amounts of unused environment data. In the project analyzed, the average environment symbols are actually used. Reading only the actually used symbols would reduce total compiler input by about 50 percent.

Combining smart recompilation with a reduction in environment processing might double to triple perceived compilation speed and double linker speed, without sacrificing static type safety.
Implementing complex elementary functions using exception handling
Authors: Hull T. E. , Fairgrieve Thomas F. , Tang Ping-Tak Peter
Published: July 2002

Algorithms are developed for reliable and accurate evaluations of the complex elementary functions required in FORTRAN 77 and FORTRAN 9, namely, cabs, csqrt, cexp, clog, csin, and ccos. The algorithms are presented in a pseudocode that has a convenient exception-handling facility. A tight error bound is derived for each algorithm. Corresponding FORTRAN programs for an IEEE environment have also been developed to illustrate the practicality of the algorithms, and these programs have been tested very carefully to help confirm the correctness of the algorithms and their error bounds. The results of these tests are included in the paper, but the FORTRAN programs are not.
Conversion to Fortran 90
Authors: Buckley A. G.
Published: July 2002

The features of the new standard language Fortran 90 are introduced and discussed. In order to focus the discussion, the particular context is the conversiton of an existing published
ACM Transactions on Mathematical Software
algorithm from Fortran 77 to the new standard. Emphasis is on the new features of the language, including the array facilities, the use of modules, the applicability of user-defined (-derived) data types, the reduction in machine dependence of numeric codes, and the dynamic allocation of storage. The intent is that writers of software as well as those who use Fortran in scientific and engineering work will find this a helpful introduction to the new and powerful features of Fortran 90.
Bounded ignorance
Authors: Krishnakumar Narayanan , Bernstein Arthur J.
Published: July 2002

Databases are replicated to improve performance and availability. The notion of correctness that has commonly been adopted for concurrent access by transactions to shared, possibly replicated, data is serializability. However, serializability may be impractical in high-performance applications since it imposes too stringent a restriction on concurrency. When serializability is relaxed, the integrity constraints describing the data may be violated. By allowing bounded violations of the integrity constraints, however, we are able to increase the concurrency of transactions that execute in a replicated environment. In this article, we introduce the notion of an
N-ignorant
transaction, which is a transaction that may be ignorant of the results of at most
N
prior transactions, which is a transaction that may be ignorant of the results of at most
N
prior transactions. A system in which all transactions are
N-ignorant
can have an
N
+ 1-fold increase in concurrency over serializable systems, at the expense of bounded violations of its integrity constraints. We present algorithms for implementing replicated databases in
N-ignorant
systems. We then provide constructive methods for calculating the reachable states in such systems, given the value of
N
, so that one may assess the maximum liability that is incurred in allowing constraint violation. Finally, we generalize the notion of
N-ignorance
to a matrix of ignorance for the purpose of higher concurrency.
Visualizing quaternion rotation
Authors: Hart John C. , Francis George K. , Kauffman Louis H.
Published: July 2002

Quaternions play a vital role in the representation of rotations in computer graphics, primarily for animation and user interfaces. Unfortunately, quaternion rotation is often left as an advanced topic in computer graphics education due to difficulties in portraying the four-dimensional space of the quaternions. One tool for overcoming these obstacles is the quaternion demonstrator, a physical visual aid consisting primarily of a belt. Every quaternion used to specify a rotation can be represented by fixing one end of the belt and rotating the other. Multiplication of quaternions is demonstrated by the composition of rotations, and the resulting twists in the belt depict visually how quaternions interpolate rotation.

This article introduces to computer graphics the exponential notation that mathematicians have used to represent unit quaternions. Exponential notation combines the angle and axis of the rotation into concise quaternion expression. This notation allows the article to present more clearly a mechanical quaternion demonstrator consisting of a ribbon and a tag, and develop a computer simulation suitable for interactive educational packages. Local deformations and the belt trick are used to minimize the ribbon's twisting and simulate a natural-appearing interactive quaternion demonstrator.
Execution-driven simulation of multiprocessors
Authors: Dwarkadas S. , Jump J. R. , Sinclair J. B.
Published: July 2002

This article describes and evaluates an efficient execution-driven technique for the simulation of multiprocessors that includes the simulation of system memory and that is driven by real program work loads. The technique produces correctly interleaved address traces at run-time without disk access overhead or hardware support, allowing accurate simulation of the effects of a variety of architectural alternatives on programs. We have implemented a simulator based on this technique that offers substantial advantages in terms of reduced time and space overheads when compared to instruction-driven or trace-driven simulation techniques, without significant loss of accuracy. The article presents the results of several validation experiments used to quantify the accuracy and efficiency of the simulator for sequential, distributed, and shared-memory multiprocessors, and several parallel programs. These experiments show that prediction errors of less than 5 percent as compared to actual execution times, and overheads 6 to 30 times lower than those incurred by cycle-level simulation can be achieved. Predictions of relative performance metrics such as speedup tend to be even more accurate, making this technique especially attractive as an efficient method for comparative investigations of parallel system designs.
A rejection technique for sampling from
T
-concave distributions
Authors: Hörmann Wolfgang
Published: July 2002

A rejection algorithm that uses a new method for constructing simple hat functions for a unimodal, bounded density
f
is introduced called “transformed density rejection.” It is based on the idea of transforming
f
with a suitable transformation
T
such that
T(f(x))
is concave.
f
is then called
T
-concave, and tangents of
T(f(x))
in the mode and in a point on the left and right side are used to construct a hat function with a table-mountain shape. It is possible to give conditions for the optimal choice of these points of contact. With
T
= -1/xxx, the method can be used to construct a universal algorithm that is applicable to a large class of unimodal distributions, including the normal, beta, gamma, and
t
-distribution.
Calculating normalization constants of closed queueing networks by numerically inverting their generating functions
Authors: Choudhury Gagan L. , Leung Kin K. , Whitt Ward
Published: July 2002

A new algorithm is developed for calculating normalization constants (partition functions) and moments of product-form steady-state distributions of closed queuing networks and related models. The essential idea is to numerically invert the generating function of the normalization constant and related generating functions appearing in expressions for the moments. It is known that the generating function of the normalization constant often has a remarkably simple form, but numerical inversion evidently has not been considered before. For
p
-dimensional transforms, as occur with queuing networks having
p
closed chains, the algorithm recursively performs
p
one-dimensional inversions. The required computation grows exponentially in the dimension, but the dimension can often be reduced by exploiting conditional decomposition based on special structure. For large populations, the inversion algorithm is made more efficient by computing large sums using Euler summation. The inversion algorithm also has a very low storage requirement. A key ingredient in the inversion algorithm is scaling. An effective static scaling is developed for multichain closed queuing networks with only single-server and (optionally) infinite-server queues. An important feature of the inversion algorithm is a self-contained accuracy check, which allows the results to be verified in the absence of alternative algorithms.
A note on complex division
Authors: Stewart G. W.
Published: July 2002

An algorithm for computing the quotient of two complex numbers is modified to make it more robust in the presence of underflows.