bluuebunny/crossref_metadata_2025 huggingface dataset:
OPTICAL RESPONSE OF A CONFINED EXCITON IN A SPHERE WITH THE EFFECTS OF LT SPLITTING AND BACKGROUND POLARIZATION: COMPARISON OF TWO DIFFERENT APPROACHES
Authors: CHO KIKUO , KAWANO KIYOHIKO , TSUJI TETSUYA , AJIKI HIROSHI
Published: July 2002

The optical response spectra of a weakly confined exciton in a sphere, obtained via microscopic nonlocal response theory, have been compared with the macroscopic approach combined with Pekar type additional boundary condition (ABC). The results give a good agreement with respect to the peak positions and their intensities, indicating that the non-escape boundary condition for the exciton wave function is equivalent to Pekar type ABC. It is also stressed that the microscopic approach is much suitable to discussing the details of the quantized excitons, such as the character of transverse (T), longitudinal (L) and LT-mixed modes, and the radiative shift and width of each level, and the details of the internal field.
COMMENTS ON THE DEFORMED WN ALGEBRA
Authors: ODAKE SATORU
Published: July 2002

We obtain an explicit expression for the defining relation of the deformed WN algebra, [Formula: see text]. Using this expression we can show that, in the q→1 limit, [Formula: see text] with [Formula: see text] reduces to the [Formula: see text]-version of the Lepowsky–Wilson's [Formula: see text]-algebra of level k, [Formula: see text]. In other words [Formula: see text] with [Formula: see text] can be considered as a q-deformation of [Formula: see text].

In the appendix given by H. Awata, S. Odake and J. Shiraishi, we present an interesting relation between [Formula: see text] and ζ-function regularization.
CHAOTIC ATTRACTORS IN ONE-DIMENSION GENERATED BY A SINGULAR SHILNIKOV ORBIT
Authors: TAYLOR KRISTA J. , DENG BO
Published: July 2002

Chaotic attractors containing Shilnikov's saddle-focus homoclinic orbits have been observed in many physical systems. Past and current researches of this type of Shilnikov homoclinic phenomena have focused on the orbit and nearby structures only. In this paper we will look at the role such orbits play in a type of attractor, which arises from one-dimensional return maps at the singular limits of some singularly perturbed systems. Results on symbolic dynamics, natural measures, and Lyapunov exponents are obtained for a sequence of a one-parameter caricature family of such attractors.
SPATIOTEMPORAL DYNAMICS OF COUPLED ARRAY OF MURALI–LAKSHMANAN–CHUA CIRCUITS
Authors: MURUGANANDAM P. , MURALI K. , LAKSHMANAN M.
Published: July 2002

The circuit recently proposed by Murali, Lakshmanan and Chua (MLC) is one of the simplest nonautonomous nonlinear electronic circuits which show a variety of dynamical phenomena including various bifurcations, chaos and so on. In this paper we study the spatiotemporal dynamics in one- and two-dimensional arrays of coupled MLC circuits both in the absence as well as in the presence of external periodic forces. In the absence of any external force, the propagation phenomena of traveling wavefront and its failure have been observed from numerical simulations. We have shown that the propagation of the traveling wavefront is due to the loss of stability of the steady states (stationary front) via subcritical bifurcation coupled with the presence of neccessary basin of attraction of the steady states. We also study the effect of weak coupling on the propagation phenomenon in one-dimensional array which results in the blocking of wavefront due to the existence of a stationary front. Further we have observed the spontaneous formation of hexagonal patterns (with penta–hepta defects) due to Turing instability in the two-dimensional array. We show that a transition from hexagonal to rhombic structures occur by the influence of an external periodic force. We also show the transition from hexagons to rolls and hexagons to breathing (space-time periodic oscillations) motion in the presence of external periodic force. We further analyze the spatiotemporal chaotic dynamics of the coupled MLC circuits (in one dimension) under the influence of external periodic forcing. Here we note that the dynamics is critically dependent on the system size. Above a threshold size, a suppression of spatiotemporal chaos occurs, leading to a space-time regular (periodic) pattern eventhough the single MLC circuit itself shows a chaotic behavior. Below this critical size, however, a synchronization of spatiotemporal chaos is observed.
A COMPOSITIONAL KNOWLEDGE LEVEL PROCESS MODEL OF REQUIREMENTS ENGINEERING
Authors: HERLEA DANIELA E. , JONKER CATHOLIJN M. , TREUR JAN , WIJNGAARDS NIEK J. E.
Published: July 2002

In current literature few detailed process models for Requirements Engineering are presented: usually high-level activities are distinguished, without a more precise specification of each activity. In this paper the process of Requirements Engineering has been analyzed using knowledge-level modelling techniques, resulting in a well-specified compositional process model for the Requirements Engineering task. This process model is considered to be a generic process model: it can be refined (by instantiation or specialisation) into a process model for a specific kind of Requirements Engineering process.
TEST ELEMENTS IN DIRECT PRODUCTS OF GROUPS
Authors: O'NEILL JOHN C. , TURNER EDWARD C.
Published: July 2002

We characterize test elements in the commutator subgroup of a direct product of certain groups in terms of test elements of the factors. This provides explicit examples of test elements in direct products whose factors are free groups or surface groups and a tool for doing the same for torsion free hyperbolic factors.
HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
Authors: ALMEIDA JORGE
Published: July 2002

This note introduces the notion of a hyperdecidable pseudovariety. This notion appears naturally in trying to prove decidability of the membership problem of semi-direct products of pseudovarieties of semigroups. It turns out to be a generalization of a notion introduced by C. J. Ash in connection with his proof of the "type II" theorem.

The main results in this paper include a formulation of the definition of a hyper-decidable pseudovariety in terms of free profinite semigroups, the equivalence with Ash's property in the group case, the behaviour under the operator g of taking the associated global pseudovariety of semigroupoids, and the decidability of V*W in case gV is decidable and has a given finite vertex-rank and W is hyperdecidable. A further application of this notion which is given establishes that the join of a hyperdecidable pseudovariety with a locally finite pseudovariety with computable free objects is again hyperdecidable.
ERROR ESTIMATE FOR A SPLITTING METHOD APPLIED TO CONVECTION-REACTION EQUATIONS
Authors: PEYROUTET F. , MADAUNE-TORT M.
Published: July 2002

An operator splitting method is used to approximate solutions of initial–boundary value problems related to a hyperbolic reaction equation. In this paper, we study the order of convergence for this scheme using only bounded entropy weak solutions of the associated homogeneous problem. An L1-error estimate of order 1 is proved by means of Kruzkov's comparison techniques.
AVASCULAR TUMOUR DYNAMICS AND NECROSIS
Authors: PLEASE C. P. , PETTET G. J. , McELWAIN D. L. S.
Published: July 2002

We consider the dynamic growth of a tumour, concentrating on the possible development of a necrotic region and examine some simple tumour geometries in detail. The growth and death rates of the cells in the viable rim of the tumour are taken to be determined by the local oxygen concentration. Crucially the cell motion is determined by the forces generated by cell affinity, by cell interaction and by the need to get the waste products of cell death, primarily water, out of the tumour and products for cell growth, again primarily water, into the tumour. A consolidation type model with surface tension on the cells, slow viscous flow of the cells and porous media flow of the extracellular water is derived. The dynamic behaviour of this model is examined. Considering the very simple case where resistance to extracellular water flow dominates the problem, the model accounts naturally for the formation of a necrotic region. In regions where the extracellular water pressure gets too large, the cells are assumed to be ripped from the extracellular matrix and die. This model contrasts significantly from previous models which typically assume a necrotic region exists and that its behaviour is primarily governed directly by oxygen concentration. Here, the stress determines the necrotic region behaviour and this is affected by the oxygen only indirectly through the cell growth and death rates. The predicted time-dependent growth of one-dimensional, and spherical tumours are illustrated by numerical calculations.
ORIENTED QUANTUM ALGEBRAS, CATEGORIES AND INVARIANTS OF KNOTS AND LINKS
Authors: KAUFFMAN LOUIS , RADFORD DAVID E.
Published: July 2002

This paper defines the concept of an oriented quantum algebra and develops its application to the construction of quantum link invariants. We show, in fact, that all known quantum link invariants can be put into this framework.
ANALYTIC INVARIANTS OF BOUNDARY LINKS
Authors: GAROUFALIDIS STAVROS , LEVINE JEROME
Published: July 2002

Using basic topology and linear algebra, we define a plethora of invariants of boundary links whose values are power series with noncommuting variables. These turn out to be useful and elementary reformulations of an invariant originally defined by M. Farber [Fa2].
HIGHER ORDER SYMMETRIES AND THE KOUTRAS ALGORITHM
Authors: AMERY G. , MAHARAJ S. D.
Published: July 2002

We investigate the form of Killing tensors, constructed from conformal Killing vectors of a given spacetime (M, g), by utilizing the Koutras algorithm. As an example we find irreducible Killing tensors in Robertson–Walker spacetimes. A number of theorems are given for the existence of Killing tensors in the conformally related spacetime [Formula: see text]. The form of the conformally related Killing tensors are explicitly determined. The conditions on the conformal factor Ω relating the two spacetimes (M, g) and [Formula: see text] are determined for the existence of the tensors. Also we briefly consider the role of recurrent vectors, inheriting conformal vectors and gradient conformal vectors in building Killing tensors.
SINGULAR SHELLS OF QUARK-GLUON MATTER
Authors: ZLOSHCHASTIEV KONSTANTIN G.
Published: July 2002

The spherically symmetric thin shells of the macroscopically stable quark-gluon matter are considered within the frameworks of the bag model and theory of discontinuities in general relativity. The equation of state for the two-dimensional matter is suggested, and its features are discussed. The exact equations of motion of such shells are obtained. Distinguishing the two cases, circumstellar and microscopical shells, we calculate the parameters of equilibrium configurations, including the conditions of decay (deconfinement).
THE APPARENT FRACTAL CONJECTURE
Authors: RIBEIRO MARCELO B.
Published: July 2002

This short communication advances the hypothesis that the observed fractal structure of large-scale distribution of galaxies is due to a geometrical effect, which arises when observational quantities relevant for the characterization of a cosmological fractal structure are calculated along the past light cone. If this hypothesis proves, even partially, correct, most, if not all, objections raised against fractals in cosmology may be solved. For instance, under this view the standard cosmology has zero average density, as predicted by an infinite fractal structure, with, at the same time, the cosmological principle remaining valid. The theoretical results which suggest this conjecture are reviewed, as well as possible ways of checking its validity.
PATTERN FORMATION IN ELECTROLESS DEPOSITION
Authors: MOGI IWAO , OKUBO SUSUMU
Published: July 2002

Metal-forest patterns of electroless deposits of silver and gold in thin-layer aqueous solutions were studied in connection with their chemical reactions. While the silver metal-forest with a simple redox reaction of Cu and Ag+ showed a DLA (diffusion limited aggregation)-like pattern, the gold metal-forest with a redox reaction of Pb and [Formula: see text] showed a DBM (dense branching morphology). The reaction mechanism of the latter was investigated by means of cyclic voltammetry, and the growth condition of the DBM is discussed.
BRONZE FORMATION AND THE MOTION OF MESOSCOPIC TIN CLUSTERS ON A COPPER SURFACE
Authors: SCHMID ANDREAS K. , BARTELT NORM C. , HWANG ROBERT Q.
Published: July 2002

To study the dynamics of alloy phase transformations, we deposited submonolayer amounts of Sn onto Cu(111) surfaces. The subsequently observed formation of bronze alloy was found to be surprisingly complex. First, the Sn forms 2D clusters with a 2×2 structure and typical diameters of the order of 100 nm. Then the Sn clusters move across the Cu surface and shrink in size, leaving dilute bronze in their wake.

The curious motion of the Sn clusters can be interpreted as an example of chemomechanical energy transduction on a surprisingly small length scale. Thus the Sn clusters are microscopic engines and one can discuss their fundamental mechanical properties. A speculative comparison of the self-propelled motion of the Sn clusters with other isothermal engines, such as molecular biological machines, is considered.
NATURAL FORMATION OF NANOSTRUCTURES: FROM FUNDAMENTALS IN METAL HETEROEPITAXY TO APPLICATIONS IN OPTICS AND BIOMATERIALS SCIENCE
Authors: MÜLLER BERT
Published: July 2002

The tailoring of nanostructures by the use of vapor deposition techniques opens up new opportunities to engineer innovative materials and devices in different fields, including optoelectronics and biomaterials. This review elucidates recent advances in the understanding of heteroepitaxy exemplifying the growth of copper on Ni(100) and the growth of para-hexaphenyl on GaAs. Although copper on nickel belongs to the simplest systems, unprecedented morphologies arise, such as ramified islands on a square lattice and strain relief by internal faceting. The elongated para-hexaphenyl crystallites formed on GaAs(001) exhibit a polarized blue light emission, which is a basis for developing organic diode lasers. Anisotropic thin film morphologies are also realized by oblique incidence deposition of noncentrosymmetric organic molecules onto amorphous substrates. Using the frequency doubling of light, it has been demonstrated for the first time that the films not only are anisotropic but also exhibit a preferential orientation of the molecules. Germanium nanopyramids epitaxially grown on Si(001) provide evidence that a well-defined nanopatterned substrate alters the contact angles of water, the protein adsorption and activity, as well as the cell behavior. These results are a milestone in structural biocompatibility on the nanometer scale.
GROWTH, MORPHOLOGY, INTERFACIAL EFFECTS AND CATALYTIC PROPERTIES OF Au ON TiO2
Authors: COSANDEY F. , MADEY T. E.
Published: July 2002

We survey recent studies and present new data on the growth, interactions, structure and chemistry of gold deposited on TiO 2(110) surfaces. The noble metal Au on TiO 2(110) is a model system for weak interaction of a metal with an oxide substrate; it is also of interest because Au on TiO 2 has unusually high activity as a catalyst for CO oxidation at room temperature. In this review, we present results on the growth of ultrathin films of Au on TiO 2(110), as well as the morphology, interface formation, epitaxy, structure and electronic properties of Au on TiO 2 single crystal and planar films. The results are compared to studies of Au on high-surface-area TiO 2 catalysts in an attempt to bridge the gap between surface science experiments and the high pressure conditions of catalyst operation.
X-RAY REFLECTOMETRY AND TOTAL REFLECTION IMAGING: A NEW COMBINED X-RAY TECHNIQUE
Authors: JIBAOUI H. , ERRE D.
Published: July 2002

X-ray specular reflectivity measurement is a powerful method for investigating surfaces, and the shape analysis of the X-ray reflectivity curve provides a range of possibilities for the study of surface structure, thin layers and multilayers. The wide field applications of this technique in modern technology explains its increasing use. The typical equipment for this technique is usually a reflectometer with an angular scanning that requires a long time for studying a surface size of a few mm 2. This article proposes a new method for simultaneous detection of several experimental reflectivity curves without incidence angle scanning and thus with a shorter aquisition time, typically 2–60 s. The method is illustrated with a first experiment using a divergent X-ray beam and a 2D detector. Furthermore, such an approach provides a new imaging technique for the surface and interface. The images obtained that way can concern the direct visualization of isolated defects sited on a very flat surface or buried interface; a domain where the X-ray reflectivity cannot be used. The feasibility of X-ray images at grazing incidence has also been demonstrated. The technique will hereafter be noted as total reflection X-ray microscopy (TRXRM).
TEMPERATURE-ACTIVATED REACTIONS OF H2O AND NH3 WITH H-PASSIVATED Si(111) SURFACES
Authors: ZAÏBI M. A. , SÉBENNE C. A. , LACHARME J. P.
Published: July 2002

Chemically hydrogenated surfaces Si(111)(1×1)–H were exposed sequentially, at temperatures of up to 600°C, and to low pressures of H 2 O or NH 3. The interaction processes have been studied by low energy electron diffraction and by photoemission yield and Auger electron spectrometries. The temperature threshold for H 2 O reaction is 350°C, at which, in a first stage, OH dipoles replace adsorbed H. OH dipole density is limited below 1/3 monolayer by the Si–O–Si formation, which brings disorder and restores H passivation. For NH 3, the reaction threshold is 370°C, at which only a small density of NH 2 dipoles is stabilized at saturation. Beyond 370°C, the saturated NH 3/Si(111)–H reaction is characterised by an increasing substitution of NH 2 dipoles to H atoms. At higher temperatures, the loss of hydrogen leads to surface disorder, which induces a loss of the N-related dipole moment normal to the surface.
SURFACE MAGNETIC ORDERING OF Fe-O and Ti-O GROUPS DISPOSED ON DIAMAGNETIC SUPPORT
Authors: SMIRNOV V. M. , BOBRYSHEVA N. P. , OSMOLOWSKY M. G. , SEMENOV V. G. , MURIN I. V.
Published: July 2002

Multiplex dependence of the magnetic susceptibility of iron and titanium-oxygen two-dimensional nanostructures on the amount of metal–oxygen groups deposited on a silica surface was found. The effect of two-dimensional ferrimagnetism was observed. Its appearance is explained by the existence of magnetization areas arising only for certain amounts of Fe–O groups in the surface layer of silica. In the case of samples containing surface Ti–O groups, the structure-induced magnetic effect was observed. Such an effect is caused by an increase of the diamagnetism polarizing component and by the ordering action of silica support on Ti–O bonds.
A STUDY FOR ANODIC OXIDE FILMS OF GaAs BY RADIOACTIVATION ANALYSIS
Authors: YOKOTA K. , NAKAMURA K. , TAMURA S. , ISHIHARA S. , KIMURA I.
Published: July 2002

Gallium arsenide was anodically oxidized in a mixture of ethylene glycol and tartaric acid as an electrolyte. The numbers of Ga and As atoms in the anodic oxide films and in the used electrolytes were measured by radioactivation analysis. During the anodic oxidation, GaAs dissolved into the electrolyte. The numbers of Ga and As atoms that dissolved into the electrolytes was proportional to the anodic voltage, and the number of Ga atoms in the electrolyte was about five times more than that of As atoms. The composition of the anodic oxide films varied with depth. However, the atomic profiles measured by Auger electron spectroscopy displayed As atoms much less than Ga atoms throughout the anodic oxide films, because Ga oxides were lost from the anodic oxide films into the vacuum during the Auger electron spectroscopy, accompanying sputtered thin film removal.
DYNAMIC SCALING PHENOMENA IN DIAMOND FILM GROWTH
Authors: CATTANI M. , SALVADORI M. C.
Published: July 2002

In this paper we investigate how the growth dynamics of diamond films, synthesized by plasma-enhanced chemical vapor deposition, can be explained within the framework of the Edwards–Wilkinson and Kardar–Parisi–Zhang stochastic differential equations.
STRESS FRACTURE OF THE ULNAR STYLOID PROCESS IN KENDO PLAYER — A CASE REPORT
Authors: Itadera E. , Ichikawa N. , Hashizume H. , Inoue H
Published: July 2002

We present a case report of a 15-year-old kendo (Japanese fencing) player who suffered a stress fracture of the ulnar styloid process. Exercise of the kendo requires the athlete to flex his non-dominant wrist repeatedly in an ulnar direction, and causes the disorder. Excision of the osteochondral fragment relieved the symptoms. This lesion is likely to occur with other sports or activities which demand similar motion of the wrists.
PEAK HIP-JOINT CONTACT STRESS IN MALE AND FEMALE POPULATIONS
Authors: Iglič Aleš , Daniel Matej , Kralj-Iglič Veronika , Antolič Vane , Jaklič Anton
Published: July 2002

Increased contact hip-joint stress could be one of the reasons for the higher incidence of coxarthrosis in the female population. Therefore, in this work, the normalized peak contact stress in the articular surface of the hip joint was determined for 33 male and 113 female healthy hips. Stress was determined by the mathematical model describing one-legged stance, where hip geometry was taken into account for each individual. The hip geometry was determined from standard anteroposterior radiographs using the computer aided system. Our results show that the peak contact stress normalized with respect to the body weight is considerably higher (cca 20%) in the female population than in the male population. The difference is statistically significant (P<0.00005) and is mainly attributed to the smaller radius of the articular surface in the female population. The results are in favor of the hypothesis that the increased hip joint contact stress in the female population could contribute to greater incidence of arthrosis in the female population relative to the male population.
OPTION PRICING FOR TRUNCATED LÉVY PROCESSES
Authors: BOYARCHENKO SVETLANA I. , LEVENDORSKIǏ SERGEI Z.
Published: July 2002

A general class of truncated Lévy processes is introduced, and possible ways of fitting parameters of the constructed family of truncated Lévy processes to data are discussed. For a market of a riskless bond and a stock whose log-price follows a truncated Lévy process, TLP-analogs of the Black–Scholes equation, the Black–Scholes formula, the Dynkin derivative and the Leland's model are obtained, a locally risk-minimizing portfolio is constructed, and an optimal exercise price for a perpetual American put is computed.
CORRELATION ANALYSIS IN THE LIBOR AND SWAP MARKET MODEL
Authors: DE MALHERBE ETIENNE
Published: July 2002

In the general framework that is offered by the market model, each LIBOR interest rate is a lognormal martingale under its own probability measure. The advantage is that the approach is consistent with the way cap, floor and swaption volatilities are quoted. The joint distribution of several LIBOR or swap rates under a common probability measure is somehow more complicated because it requires the specification of a drift term structure and the specification of a correlation term structure. In this paper, the correlation between the LIBORs is represented by a function of the LIBOR maturities. The form of this function is inspired by the stochastic string theory that was recently introduced in finance for the modelling of yield curves. The function is fitted to the volatilities of the LIBOR and swap rates so that it is consistent with market observations and does not rely on statistical analysis of any historical data.
A NOTE ON REGULAR SEMIVALUES
Authors: CARRERAS FRANCESC , FREIXAS JOSEP
Published: July 2002

Using the characterisation of semivalues by means of weighting coefficients, we study the possibility of extending to them several interesting properties common to the Shapley and Banzhaf values. We conclude that most of the main characteristics of these two classical values are shared by regular semivalues, and this fact provides a theoretical basis for using them as alternatives in future applications — due to their versatility.
UNIFIED APPROACH FOR NOISY NONLINEAR MATHIEU-TYPE SYSTEMS
Authors: NAMACHCHIVAYA N. SRI , SOWERS RICHARD B.
Published: July 2002

The purpose of this work is to develop a unified approach to study the dynamics of a single-degree-of-freedom system excited by both periodic and random perturbations. As a prototype, we consider the noisy Duffing–van der Pol–Mathieu equation and achieve a reduction by developing rigorous methods to replace, in a limiting regime, the original complicated system by a simpler, constructive, and rational approximation — a lower-dimensional model of the dynamical system. To this end, we study the equations as a random perturbation of a two-dimensional weakly dissipative time-periodic Hamiltonian system. We achieve the model-reduction through stochastic averaging and the reduced Markov process takes its values on a graph with certain glueing conditions at the vertex of the graph. Examination of the reduced Markov process on the graph yields many important results, namely, mean exit times, probability density functions, and stochastic bifurcations.
The average time until bucket overflow
Authors: Cooper Robert B. , Solomon Martin K.
Published: July 2002

It is common for file structures to be divided into equal-length partitions, called buckets, into which records arrive for insertion and from which records are physically deleted. We give a simple algorithm which permits calculation of the average time until overflow for a bucket of capacity
n
records, assuming that record insertions and deletions can be modeled as a stochastic process in the usual manner of queueing theory. We present some numerical examples, from which we make some general observations about the relationships among insertion and deletion rates, bucket capacity, initial fill, and average time until overflow. In particular, we observe that it makes sense to define the
stable point
as the product of the arrival rate and the average residence time of the records; then a bucket tends to fill up to its stable point quickly, in an amount of time almost independent of the stable point, but the average time until overflow increases rapidly with the difference between the bucket capacity and the stable point.
Taxonomic syntax for first order inference
Authors: McAllester David , Givan Robert
Published: July 2002

A new polynomial time decidable fragment of first order logic is identified, and a general method for using polynomial time inference procedures in knowledge representation systems is presented. The results shown in this paper indicate that a nonstandard “taxonomic” syntax is essential in constructing natural and powerful polynomial time inference procedures. The central role of taxonomic syntax in the polynomial time inference procedures provides technical support for the often-expressed intuition that knowledge is better represented in terms of taxonomic relationships than classical first order formulas. To use the procedures in a knowledge representation system, a “Socratic proof system” is defined, which is complete for first order inference and which can be used as a semi-automated interface to a first order knowledge base.
Fishspear: a priority queue algorithm
Authors: Fischer Michael J. , Paterson Michael S.
Published: July 2002

The Fishspear priority queue algorithm is presented and analyzed. Fishspear is comparable to the usual heap algorithm in its worst-case running time, and its relative performance is much better in many common situations. Fishspear also differs from the heap method in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it potentially attractive for implementation of very large queues on paged memory systems.
Exact integer hybrid subdivision and forward differencing of cubics
Authors: Klassen R. Victor
Published: July 2002

Forward differencing is widely used to generate rapidly large numbers of points at equally space parameter values along a curve. A failing of forward differencing is the tendency to generate many extraneous points for curves with highly nonuniform parameterizations. A key result is presented and proven, namely, that a few levels of subdivision, prior to initialization for forward differencing, can improve substantially the quality of the step size estimate, resulting in very few extra points. The initial subdivisions can be done without loss of the exact integer precision available in forward differencing. For small numbers of points—a common occurrence in fonts—exact subdivision is even faster than exact forward differencing. When exact subdivision is used in conjunction with a previously presented exact forward-differencing algorithm, arbitrary cubic curves may be rendered with 32-bit arithmetic and guaranteed single-pixel accuracy, in a grid with an address space as large as 0…7281, with no two generated points greater than one pixel apart. This is more steps than previously possible. Previous discussions of rendering using subdivision have concentrated not on distance but on straightness estimates, whereby subdivision can be stopped once a subcurve can be drawn safely using its polygonal approximation. In this article, bounds are also derived on the size of the control polygon after multiple levels of subdivision: these are used to determine bounds on the number of steps required for differencing. It is shown that any curve whose rasterization fits in a space of ω pixels requires no more than 9ω steps.
Software distribution using Xnetlib
Authors: Dongarra Jack , Rowan Tom , Wade Reed
Published: July 2002

Xnetlib is a new tool for software distribution. Whereas its predecessor netlib uses email as the user interface to its large collection of public-domain mathematical software, Xnetlib uses an X Window interface and socket-based communication. Xnetlib makes it easy to search through a large distributed collection of software and to retrieve requested software in seconds.
Chaos engineering in Japan
Authors: Aihara Kazuyuki , Katayama Ryu
Published: July 2002

Since deterministic chaos is not only a profound concept in science but also a ubiquitous phenomenon in real-world nonlinear systems, extending to a variety of temporal and spatial scales, it can be naturally related to applications in science and technology [4]. In fact, it is not difficult to find the buds of such possible applications in historical papers by Van der Pol and Van der Mark [22], Ulam and von Neumann [21], and Kalman [12], although the term
deterministic chaos
was not used in those days.
Intelligent information-sharing systems
Authors: Malone Thomas W , Grant Kenneth R , Turbak Franklyn A , Brobst Stephen A , Cohen Michael D
Published: July 2002

The Information Lens system is a prototype intelligent information-sharing system that is designed to include not only good user interfaces for supporting the problem-solving activity of individuals, but also good organizational interfaces for supporting the problem-solving activities of groups.
Algorithm 763: INTERVAL_ARITHMETIC
Authors: Kearfott R. Baker
Published: July 2002

Interval arithmetic is useful in
automatically verified computations
, that is, in computations in which the algorithm itself rigorously proves that the answer must lie within certain bounds. In addition to rigor, interval arithmetic also provides a simple and sometimes sharp method of bounding ranges of functions for global optimization and other tasks. Convenient use of interval arithmetic requires an interval data type in the programming language. Although various packages supply such a data type, previous ones are machine specific, obsolete, and unsupported, for languages other than Fortran, or commercial. The Fortran 90 module INTERVAL_ARITHMETIC provides a portable interval data type in Fortran 90. This data type is based on two double-precision real Fortran storage units. Module INTERVAL_ARTHMETIC uses the Fortran 77 library INTLIB (ACM TOMS Algorithm 737) as a supporting library. The module has been employed extensively in the author's own research.
Optimal wiresizing for interconnects with multiple sources
Authors: Cong Jason , He Lei
Published: July 2002

In this paper, we study the optimal wiresizing problem for nets with multiple sources under the RC tree model and the Elmore delay model. We decompose the routing tree for a multisource net into the source subtree (SST) and a set of loading subtrees (LSTs), and show that the optimal wiresizing solution satisfies a number of interesting properties, including: LST separability, the LST monotone property, the SST local monotone property, and the dominance property. Furthermore, we study the optimal wiresizing problem using a variable segment-division rather than an a priori fixed segment-division as in all previous works and reveal the bundled refinement property. These properties lead to efficient algorithms to compute the optimal solutions. We have tested our algorithm on nets extracted from the multilayer layout for a high-performance Intel microprocessor. Accurate SPICE simulation shows that our methods reduce the average delay by up to 23.5% and the maximum delay by up to 37.8%, respectively, for the submicron CMOS technology when compared to the minimal wire width solution. In addition, the algorithm based on the variable segment-division yields a speedup of over 100× time and does not lose any accuracy, when compared with the algorithm based on the a priori fixed segment-division.
Aggregation with an error of
O
(ε
2
)
Authors: Vantilborgh Hendrik
Published: July 2002

An aggregative technique to obtain an improved approximation of the equilibrium vector of a Markov chain with a nearly completely decomposable transition matrix is presented. The technique is demonstrated on a model of a multiprogrammed computer system.
Recursive hashing functions for
n
-grams
Authors: Cohen Jonathan D.
Published: July 2002

Many indexing, retrieval, and comparison methods are based on counting or cataloguing
n
-grams in streams of symbols. The fastest method of implementing such operations is through the use of hash tables. Rapid hashing of consecutive
n
-grams is best done using a recursive hash function, in which the hash value of the current
n
-gram is drived from the hash value of its predecessor. This article generalizes recursive hash functions found in the literature and proposes new methods offering superior performance. Experimental results demonstrate substantial speed improvement over conventional approaches, while retaining near-ideal hash value distribution.
On the power and limitations of strictness analysis
Authors: Sekar R. , Ramakrishnan I. V. , Mishra P.
Published: July 2002

Strictness analysis is an important technique for optimization of lazy functional languages. It is well known that all strictness analysis methods are
incomplete
, i.e., fail to report some strictness properties. In this paper, we provide a precise and formal characterization of the loss of information that leads to this incompletenss. Specifically, we establish the following characterization theorem for Mycroft's strictness analysis method and a generalization of this method, called
ee-analysis
, that reasons about exhaustive evaluation in nonflat domains:
Mycroft's method will deduce a strictness property for program P iff the property is independent of any constant appearing in any evaluation of P.
To prove this, we specify a small set of equations, called
E-axioms
, that capture the information loss in Mycroft's method and develop a new proof technique called
E-rewriting
.
E
-rewriting extends the standard notion of rewriting to permit the use of reductions using
E
-axioms interspersed with standard reduction steps.
E
-axioms are a syntactic characterization of information loss and
E
-rewriting provides and
algorithm-independent
proof technique for characterizing the power of analysis methods. It can be used to answer questions on completeness and incompleteness of Mycroft's method on certain natural classes of programs. Finally, the techniques developed in this paper provide a general principle for establishing similar results for other analysis methods such as those based on abstract interpretation. As a demonstration of the generality of our technique, we give a characterization theorem for another variation of Mycroft's method called
dd
-analysis.
A codesign experiment in acoustic echo cancellation
Authors: Freund L. , Israel M. , Rousseau F. , Bergé J. M. , Auguin M. , Belleudy C. , Gogniat G.
Published: July 2002

Continuous advances in processor and ASIC technologies enable the integration of more and more complex embedded systems. Embedded systems have become commonplace in recent years. Since their implementations generally require the use of heterogeneous resources (e.g., processor cores, ASICs) in one system with hard design constraints, the importance of hardware/software codesign methodologies increases steadily. HW/SW codesign approaches consist generally of HW/SW partitioning and scheduling, constrained code generation, and hardware and interface synthesis. This article presents the codesign of an industrial experiment in acoustic echo cancellation (GMDFα algorithm); and emphasizes the partitioning and communication synthesis steps. This experiment brings to light interesting problems such as data and program distribution between system memories and the modeling of communications in the partitioning process
Noise-tolerant distribution-free learning of general geometric concepts
Authors: Bshouty Nader H. , Goldman Sally A. , Mathias H. David , Suri Subhash , Tamaki Hisao
Published: July 2002

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ
d
for fixed
d
. More specifically, let 𝒯 be any set of
s
halfspaces. Let
x
=(x
1
, …,
x
d
) be an arbitrary point in ℛ
d
. With each
t
∈ 𝒯 we associate a boolean indicator function

I
t
(x)

which is 1 if and only if
x
is in the halfspace
t
. The concept class, 𝒞
d
s
, that we study consists of all concepts formed by any Boolean function over

I
t1
, …, I
ts

for

t
i

∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ
d
given that the VC-dimension of 𝒞 has dependence only on
d
and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for
d
= 2 based on geometric subdivisions.
ICOS
Authors: Hsiung Pao-Ann , Chen Chung-Hwang , Lee Trong-Yen , Chen Sao-Jie
Published: July 2002

The design of multiprocessor architectures differs from uniprocessor systems in that the number of processors and their interconnection must be considered. This leads to an enormous increase in the design-space exploration time, which is exponential in the total number of system components. The methodology proposed here, called
Intelligent Concurrent Object-Oriented Synthesis
(ICOS) methodology, makes feasible the synthesis of complex multiprocessor systems through the application of several techiques that speed up the design process. ICOS is based on
Performance Synthesis Methodology
(PSM), a recently proposed object-oriented system-level design methodology. Four major techniques: object-oriented design, fuzzy design-space exploration, concurrent design, and intelligent reuse of complete subsystems are integrated in ICOS. First, object-oriented modeling and design, through the use of object-oriented relationships and operators, make the whole design process manageable and maintainable in ICOS. Second, fuzzy comparison applied to the specializations or instances of components reduces the exponential growth of design-space exploration in ICOS. Third, independent components from different design alternatives are synthesized in parallel; this design concurrency shortens the overall design time. Lastly, the resynthesis of complete subsystems can be avoided through the application of learning, thus making the methodology intelligent enough to reuse previous design configurations. Experiments show that all these applied techniques contribute to the synthesis efficiency and the degree of automation in ICOS.
Implementation of Hopf and double-Hopf continuation using bordering methods
Authors: Govaerts W. , Kuznetsov Yu. A. , Sijnave B.
Published: July 2002

We discuss the computational study of curves of Hopf and double-Hopf points in the software package CONTENT developed at CWI, Amsterdam. These are important points in the numerical study of dynamical systems characterized by the occurrence of one or two conjugate pairs of pure imaginary eigenvalues in the spectrum of the Jacobian matrix. The bialternate product of matrices is extensively used in three codes for the numerical continuation of curves of Hopf points and in one for the continuation of curves of double-Hopf points. In the double-Hopf and two of the single-Hopf cases this is combined with a bordered matrix method. We use this software to find special points on a Hopf curve in a model of chemical oscillations and by computing a Hopf and a double-Hopf curve in a realistic model of a neuron.
Analysis of dynamic hashing with deferred splitting
Authors: Veklerov Eugene
Published: July 2002

Dynamic hashing with deferred splitting is a file organization scheme which increases storage utilization, as compared to standard dynamic hashing. In this scheme, splitting of a bucket is deferred if the bucket is full but its brother can accommodate new records. The performance of the scheme is analyzed. In a typical case the expected storage utilization increases from 69 to 76 percent.
Joined normal form
Authors: Babb E.
Published: July 2002

A new on-line query language and storage structure for a database machine is presented. By including a mathematical model in the interpreter the query language has been substantially simplified so that no reference to relation names is necessary. By storing the model as a single joined normal form (JNF) file, it has been possible to exploit the powerful search capability of the Content Addressable File Store (CAFS®; CAFS is a registered trademark of International Computers Limited) database machine.
Hierarchical file organization and its application to similar-string matching
Authors: Ito Tetsuro , Kizawa Makoto
Published: July 2002

The automatic correction of misspelled inputs is discussed from a viewpoint of similar-string matching. First a hierarchical file organization based on a linear ordering of records is presented for retrieving records highly similar to any input query. Then the spelling problem is attacked by constructing a hierarchical file for a set of strings in a dictionary of English words. The spelling correction steps proceed as follows: (1) find one of the best-match strings which are most similar to a query, (2) expand the search area for obtaining the good-match strings, and (3) interrupt the file search as soon as the required string is displayed. Computational experiments verify the performance of the proposed methods for similar-string matching under the UNIX™ time-sharing system.
Analysis of Nets by Numerical Methods
Authors: Gill Arthur
Published: July 2002

The assignment of prime numbers to the branches of directed or non-directed nets, enables one to construct transition matrices in a numerical, rather than a symbolic, form. The numerical form greatly facilitates the construction of higher-order transition matrices, needed for the topological analysis of a given net. The proposed method is especially useful for the mechanical determination of the non-repeating paths and cycles in the net.
Estimation of Power Spectral Density by Filters
Authors: Gauss E. J.
Published: July 2002

An algorithm is presented which differs from previous methods by being more adapted for searching over wide frequency ranges and which permits the estimation of spectral density as a function of time as well as of frequency. The algorithm may offer economy, especially on smaller computers. The algorithm is based on the analogy between a broadly tuned filter and a truncated cross correlation.
Structure and Transition-Preserving Functions of Finite Automata
Authors: Bavel Zamir
Published: July 2002

Arbitrary finite automata are decomposed into their major substructures, the primaries. Several characterizations of homomorphisms, endomorphisms, isomorphisms, and automorphisms of arbitrary finite automata are presented via reduction to the primaries of the automata. Various characterizations of these transition-preserving functions on singly generated automata are presented and are used as a basis for the reduction. Estimates on the number of functions of each type are given.
Analysis in the Computable Number Field
Authors: Aberth Oliver
Published: July 2002

It is well known that real variable analysis is nonconstructive. For example, although it is asserted that every bounded monotone sequence converges to a limit, there is no algorithm for obtaining this limit.

This paper presents a constructive analysis which is restricted to a countable set of numbers, the field of computable numbers. These numbers are defined in a new way by employing the concept of “programmable functions.” The resultant analysis differs from real analysis in many important respects.
Resolution With Merging
Authors: Andrews Peter B.
Published: July 2002

A refinement of the resolution method for mechanical theorem proving is presented. A resolvent
C
of clauses
A
and
B
is called a
merge
if literals from
A
and
B
merge together to form some literal of
C
. It is shown that the resolution method remains complete if it is required that two noninitial clauses which are not merges never be resolved with one another. It is also shown that this strategy can be combined with the set-of-support strategy.
Efficiency of a Procedure for Near-Minimax Approximation
Authors: Shampine L. F.
Published: July 2002

A procedure using the minimax polynomial fit of degree
n
on the set of extrema of the Chebyshev polynomial
T
n+1
is examined for its effectiveness in generating near-minimax fits on [-1, 1]. It is compared to Powell's results for interpolation at the zeros of
T
n
.
PIC matrices
Authors: Greiff Warren R. , Croft W. Bruce , Turtle Howard
Published: July 2002

The inference network model of information retrieval allows a
probabilistic interpretation of query operators. In particular, Boolean query operators are conveniently modeled as link matrices of the Bayesian Network. Prior work has shown, however, that these operators do not perform as well as the
pnorm
operators used for modeling query operators in the context of the vector space model. This motivates the search for alternative probabilistic formulations for these operators. The design of such alternatives must contend with the issue of computational tractability, since the evaluation of an arbitrary operator requires exponential time. We define a flexible class of link matrices that are natural candidates for the implementation of query operators and an
O
(
n
2
) algorithm (
n
= the number of parent nodes) for the computation of probabilities involving link matrices of this class. We present experimental results indicating that Boolean operators implemented in terms of link matrices from this class perform as well as
pnorm
operators in the context of the INQUERY inference network.