bluuebunny/crossref_metadata_2025 huggingface dataset:
H-BRANES AND CHIRAL STRINGS
Authors: KOGAN IAN I. , REIS NUNO B. B.
Published: July 2002

We add a simple boundary term to the Polyakov action and construct a new class of D-branes with a single null direction. On the string world sheet the system is described by a single quantized left-mode sector of a conformal field theory. By a Wick rotation of space–time, we map open strings attached to null branes into chiral closed strings. We suggest that these so-called H-branes describe quantum horizons — black hole, cosmological (de-Sitter), etc. We show how one can get a space/phase space transmutation near the horizon and discuss the new features of boundary states which become squeezed states.
LOOPS AND LOOP CLOUDS — A NUMERICAL APPROACH TO THE WORLDLINE FORMALISM IN QED
Authors: GIES HOLGER , LANGFELD KURT
Published: July 2002

A numerical technique for calculating effective actions of electromagnetic backgrounds is proposed, which is based on the string-inspired worldline formalism. As examples, we consider scalar electrodynamics in three and four dimensions to one-loop order. Beyond the constant-magnetic-field case, we analyze a step-function-like magnetic field exhibiting a nonlocal and nonperturbative phenomenon: "magnetic-field diffusion". Finally, generalizations to fermionic loops and systems at finite temperature are discussed.
ELECTRON CORRELATION AND PHOTO PHYSICS OF PHENYL SUBSTITUTED POLYACETYLENES
Authors: GHOSH HARANATH , MAZUMDAR S. , SHUKLA Alok
Published: July 2002

We investigate theoretically photoluminescence (PL) properties of mono and di-phenyl substituted trans-polyacetylene (t-PA), namely, poly-phenylacetylene (PPA) and poly-diphenylacetylene (PDPA), respectively. PL is a consequence of the occurrence of the two-photon state ( 2Ag ) above the optically excited state ( 1Bu ). Usually, electron correlation leads to confinement of 1Bu as well as the ground state. We show, in contrast, that in phenyl-substituted polyacetylenes electron–electron interactions cause enhanced delocalization of quasiparticles in the optically excited state from the backbone polyene chain into the phenyl groups. This coulomb enhanced delocalization in the transverse direction leads to confinement in the longitudinal direction and causes crossover between the 1Bu and 2Ag . We further show that in the absence of electron repulsion the low energy absorption is x-polarized whereas the high energy absorpion is predominantly y-polarized. In contrast, in presence of many body electron interaction both of them (low and high energy absorptions) are x-polarized. Thus photophysics of PPA/PDPA etc. are consequences of true many body effects.
COMPOSITION OF INFLATION RULES FOR APERIODIC STRUCTURES WITH NINE-FOLD SYMMETRY
Authors: ESCUDERO JUAN GARCÍa
Published: July 2002

Deterministic aperiodic planar patterns with nine-fold symmetry have been interpreted recently in terms of a class of formal grammars known as D0L systems. A wider class of patterns with the same symmetry can be generated by composing two inflation rules. They are described with the help of ET0L systems. From the formal language theory point of view this corresponds to a selective approach, due to the fact that we need to introduce nonterminal symbols in the alphabet. From the point of view of quasicrystal structures, instead of having only one pattern of a given size and shape, we now have a finite number of them. This allows to construct nondeterministic models of aperiodic structures.
ER Suspensions of Sulfonated Poly(Styrene-CO-Divinylbenzene) Particles
Authors: Kawakami Toshihiro , Aizawa Ryuji , Konishi Masayoshi , Asako Yoshinobu
Published: July 2002

Two ER suspensions (ERF1 and ERF2) containing highly sulfonated poly(styrene-co-divinylbenzene) particles (ERP) were newly prepared. The ERP concentration was 20 wt% in ERF1 and 40 wt% in ERF2. The ER properties of the suspensions were investigated in view of applications to practical devices. The investigated properties were zero-field viscosity, dispersion stability, induced shear stress, current density, response time, shear rate and temperature dependence of the induced shear stress and current density, response time, shear rate and temperature dependence of the induced shear stress and the current density. electrical durability. In the results, it was found that ERF1 and ERF2 had a very high potential for practical applicatons. The remarkable characteristic of ERF1 was the very low zero-field viscosity of 35 mPa·s at 25°C. The remarkable characteristic of ERF2 was very large induced shear stress and under applying DC 4 kV/mm at 25°C, the induced shear stress was 5.1 kPa. As an application example, the ERFs can be efficiently used for an ER Cutting Machine incorporating variable speed rodless cylinders. The machine has worked smoothly for one and a half years, although the characteristic of control slightly changed.
DETERMINATION OF THE VAPOR-LIQUID CRITICAL POINT FROM THE SHORT-TIME DYNAMICS
Authors: HUANG SHENG-YOU , ZOU XIAN-WU , TAN ZHI-JIE , JIN ZHUN-ZHI
Published: July 2002

Considering the average potential energy per particle as the parameter, we investigate the early-time dynamics of vapor-liquid transition in the critical region for 2D Lennard-Jones fluids by using NVT molecular dynamics simulations. The results verify the existence of short-time dynamic scaling in the fluid systems and show that the critical point Tc can be determined by the universal short-time behavior. The obtained value of Tc = 0.540 from the short-time dynamics is very close to the value of 0.533 from the Monte Carlo simulations in the equilibrium state of the systems.
SYMBOLIC DYNAMICS FROM HOMOCLINIC TANGLES
Authors: COLLINS PIETER
Published: July 2002

We present a method for finding symbolic dynamics for a planar diffeomorphism with a homoclinic tangle. The method only requires a finite piece of tangle, which can be computed with available numerical techniques. The symbol space is naturally given by components of the complement of the stable and unstable manifolds. The shift map defining the dynamics is a factor of a subshift of finite type, and is obtained from a graph related to the tangle. The entropy of this shift map is a lower bound for the topological entropy of the planar diffeomorphism. We give examples arising from the Hénon family.
FREE PRODUCT, PROFINITE TOPOLOGY AND FINITELY GENERATED SUBGROUPS
Authors: COULBOIS THIERRY
Published: July 2002

We consider the following property for a group G:(RZn)ifH1,…,Hnare finitely generated subgroups of G then the setH1 H2⋯ Hn= {h1 ⋯ hn| h1∈ H1, …,hn∈ Hn}is closed with respect to the profinite topology of G. It is obvious that finite groups and finitely generated commutative groups have the property ( RZ n). L. Ribes and P. Zalesskiĭ proved that any free group has ( RZ n). We show that the property ( RZ n) is stable under the free product operation. We use techniques developed by B. Herwig and D. Lascar on the one hand, R. Gitik on the other hand.
ON THE TIME-DEPENDENT HARTREE–FOCK EQUATIONS COUPLED WITH A CLASSICAL NUCLEAR DYNAMICS
Authors: CANCÈS ERIC , LE BRIS CLAUDE
Published: July 2002

We prove a global-in-time existence and uniqueness result for the Cauchy problem in the setting of some model of Molecular Quantum Chemistry. The model we are concerned with consists of a coupling between the time-dependent Hartree–Fock equations (for the electrons) and the classical Newtonian dynamics (for the nuclei). The proof combines semigroup techniques and the Schauder fixed-point theorem. We also extend our result in order to treat the case of a molecule subjected to a time-dependent electric field.
FAST AND SLOW FEEDBACK IN SYSTEMS THEORY
Authors: LOBRY CLAUDE , SARI TEWFIK , TOUHAMI SÉFIANE
Published: July 2002

Biological systems are complex systems with feedback. Very often the scales for the dynamics of the system and the dynamics of the feedback are very different. The mathematical tool used to deal with this different time scales is Tikhonov's theorem which permits to reduce the complexity of the system through suitable approximations. This paper presents a theory of two time scales feedback systems phrased in the language of Nonstandard Analysis (NSA), introduced in the sixties by A. Robinson. Our opinion is that this presentation is more understandable for a non-mathematicaly trained reader than the classical one. Th paper is entirely self contained. A short but comprehensive tutorial on NSA is provided and precise definitions for concepts from systems theory are given.
OPTIMAL ARCHIVE COPY INTERVAL FOR A FILE RECOVERY WITH GENERAL FAULT LATENCY TIME
Authors: NAKAGAWA SAYORI , ISHII NAOHIRO , FUKUMOTO SATOSHI , YAMADA SHIGERU
Published: July 2002

This paper considers the stochastic model of a file recovery mechanism: archive copies with n available generations are created periodically at constant time T. When failures have been detected, the consistent state is restored at the time just before fault occurrence by archive copies. The recovery overhead and its mean time are obtained when the fault latency time has a general distribution and a failure is detected uniformly during the copy interval. An optimal interval T* of archive copies is discussed analytically. Numerical examples are given when the fault latency time has exponential and gamma distributions.
RHEED FROM EPITAXIALLY GROWN THIN FILMS
Authors: MITURA Z.
Published: July 2002

It is shown that dynamical theory can be applied to analyze reflection high energy diffraction (RHEED) data from epitaxially grown samples. First, the theoretical description of the dynamical approach employed is presented in detail. Then examples of experimental data successfully interpreted are given. It is demonstrated that RHEED azimuthal plots may be helpful in gaining detailed information on the arrangement of atoms at the surface when the growth of samples is terminated. Furthermore, it is shown that RHEED oscillations recorded for one-beam conditions (i.e. at off-symmetry azimuths or at very low glancing angles) may be very useful in investigating growing surfaces. Finally, we discuss how the theoretical approach used in this work is related to approaches employed by other researchers, and what kind of investigations may help to develop RHEED further.
LOWEST NUMBER OF BRACHIAL PLEXUS NERVE ROOTS REQUIRED FOR MAINTAINING NORMAL LIMB FUNCTION — AN EXPERIMENTAL STUDY
Authors: Chen Liang , Gu Yu-dong
Published: July 2002

Rat models with different division of nerve roots of the brachial plexus were designed to assess whether single or two nerve roots of the contralateral normal brachial plexus can be divided as donor nerves in treatment of brachial plexus root avulsion. Two hundred and fifty-two SD rats were randomly divided into 13 groups, i.e. five groups with single nerve root division, seven groups with two nerve roots division, and one group with three nerve roots division. Post-operative evaluation by electroneurophysiology and muscular histology was performed at two weeks and two months. Results showed that in groups with single nerve root division, the experimental limb function did not show an apparent damage; in groups with non-neighbouring two nerve roots cutting, it did show a harmful repercussions on the limb at two weeks, but most of them recovered to normal at two months; in groups with neighbouring two nerve roots division and with non-neighbouring three nerve root cutting, the limb function showed a persistent damage. In conclusion, division of nerve root alone or even non-neighbouring two nerve roots of the brachial plexus did not affect the forelimb function of the rat permanently.
MELORHEOSTOSIS OF THE HAND: A COMPREHENSIVE REVIEW
Authors: Wiater J. Michael , King Jeffrey C. , Louis Dean S. , Smith James
Published: July 2002

Melorheostosis is an uncommon disorder characterized by soft tissue contractures and sclerosis of bone. The sclerosis appears to flow along the long axis of the bone, akin to candle wax dripping down one side of a candle. Numerous reports of lower extremity involvement exist, but there are few detailed reports of melorheotosis involving the hand. This condition is benign but slowly progressive and can usually be managed conservatively. Loss of function of the hand from swelling, pain, or stiffness, however, may necessitate operative intervention. Two recent cases prompted a review of the literature relating to melorheostosis and the hand.
KRAFT: AN AGENT ARCHITECTURE FOR KNOWLEDGE FUSION
Authors: PREECE ALUN , HUI KIT , GRAY ALEX , MARTI PHILIPPE , BENCH-CAPON TREVOR , CUI ZHAN , JONES DEAN
Published: July 2002

Knowledge fusion refers to the process of locating and extracting knowledge from multiple, heterogeneous on-line sources, and transforming it so that the union of the knowledge can be applied in problem-solving. The KRAFT project has defined a generic agent-based architecture to support fusion of knowledge in the form of constraints expressed against an object data model. KRAFT employs three kinds of agent: facilitators locate appropriate on-line sources of knowledge; wrappers transform heterogeneous knowledge to a homogeneous constraint interchange format; mediators fuse the constraints together with associated data to form a dynamically-composed constraint satisfaction problem, which is then passed to an existing constraint solver engine to compute solutions. The paper presents the KRAFT architecture and the three kinds of agent, and includes a description of a demonstration KRAFT application in the domain of telecommunications service provision.
BUBBLES AND ANTI-BUBBLES IN LATIN-AMERICAN, ASIAN AND WESTERN STOCK MARKETS: AN EMPIRICAL STUDY
Authors: JOHANSEN ANDERS , SORNETTE DIDIER
Published: July 2002

Twenty-one significant bubbles followed by large crashes or severe corrections in Latin-American and Asian stock markets are identified. We find that, with very few exceptions, these speculative bubbles can be quantitatively described by a rational expectation model of bubbles predicting a specific power law acceleration as well as so-called log-periodic geometric patterns. This model considerably extends the applicability of the rational expectation model of bubbles followed by crashes or severe corrections previously proposed for the major financial markets in the world, i.e. the USA and the foreign exchange markets. A comparison of the model predictions using the price and the logarithm of the price, respectively, furthermore indicates according to our model that such large downward movements in the markets are nothing but depletions of the preceding bubble thus bringing the market back towards equilibrium. In addition, a set of secondary stock markets are also shown to exhibit well-correlated "anti-bubbles" triggered by a rash of crises on emerging markets in early 1994. This suggests that smaller stock markets can weakly synchronize not only because of the over-arching influence of the US market, but also independent of the US market due to external factors such as the Asian crisis of 1994.
STOCHASTIC EVOLUTION AS A QUASICLASSICAL LIMIT OF A BOUNDARY VALUE PROBLEM FOR SCHRÖDINGER EQUATIONS
Authors: BELAVKIN V. P. , KOLOKOL'TSOV V. N.
Published: July 2002

We develop systematically a new unifying approach to the analysis of linear stochastic, quantum stochastic and even deterministic equations in Banach spaces. Solutions to a wide class of these equations (in particular those describing the processes of continuous quantum measurements) are proved to coincide with the interaction representations of the solutions to certain Dirac type equations with boundary conditions in pseudo-Fock spaces. The latter are presented as the semiclassical limit of an appropriately dressed unitary evolutions corresponding to a boundary-value problem for rather general Schrödinger equations with bounded below Hamiltonians.
DEVELOPING INNOVATION CAPABILITY IN ORGANISATIONS: A DYNAMIC CAPABILITIES APPROACH
Authors: LAWSON BENN , SAMSON DANNY
Published: July 2002

This paper draws together knowledge from a variety of fields to propose that innovation management can be viewed as a form of organisational capability. Excellent companies invest and nurture this capability, from which they execute effective innovation processes, leading to innovations in new product, services and processes, and superior business performance results. An extensive review of the literature on innovation management, along with a case study of Cisco Systems, develops a conceptual model of the firm as an innovation engine. This new operating model sees substantial investment in innovation capability as the primary engine for wealth creation, rather than the possession of physical assets. Building on the dynamic capabilities literature, an "innovation capability" construct is proposed with seven elements. These are vision and strategy, harnessing the competence base, organisational intelligence, creativity and idea management, organisational structures and systems, culture and climate, and management of technology.
THE EXTRACTION AND COMPARISON OF KNOWLEDGE FROM LOCAL FUNCTION NETWORKS
Authors: MCGARRY KENNETH , WERMTER STEFAN , MACINTYRE JOHN
Published: July 2002

Extracting rules from RBFs is not a trivial task because of nonlinear functions or high input dimensionality. In such cases, some of the hidden units of the RBF network have a tendency to be "shared" across several output classes or even may not contribute to any output class. To address this we have developed an algorithm called LREX (for Local Rule EXtraction) which tackles these issues by extracting rules at two levels: hREX extracts rules by examining the hidden unit to class assignments while mREX extracts rules based on the input space to output space mappings. The rules extracted by our algorithm are compared and contrasted against a competing local rule extraction system. The central claim of this paper is that local function networks such as radial basis function (RBF) networks have a suitable architecture based on Gaussian functions that is amenable to rule extraction.
A framework for defining logics
Authors: Harper Robert , Honsell Furio , Plotkin Gordon
Published: July 2002

The Edinburgh Logical Framework (LF) provides a means to define (or present) logics. It is based on a general treatment of syntax, rules, and proofs by means of a typed λ-calculus with dependent types. Syntax is treated in a style similar to, but more general than, Martin-Lo¨f's system of arities. The treatment of rules and proofs focuses on his notion of a
judgment
. Logics are represented in LF via a new principle, the
judgments as types
principle, whereby each judgment is identified with the type of its proofs. This allows for a smooth treatment of discharge and variable occurence conditions and leads to a uniform treatment of rules and proofs whereby rules are viewed as proofs of higher-order judgments and proof checking is reduced to type checking. The practical benefit of our treatment of formal systems is that logic-independent tools, such as proof editors and proof checkers, can be constructed.
Inferring constraints from multiple snapshots
Authors: Kurlander David , Feiner Steven
Published: July 2002

Many graphic tasks, such as the manipulation of graphical objects and the construction of user-interface widgets, can be facilitated by geometric constraints. However, the difficulty of specifying constraints by traditional methods forms a barrier to their widespread use. In order to make constraints easier to declare, we have developed a method of specifying constraints implicitly, through multiple examples. Snapshots are taken of an initial scene configuration, and one or more additional snapshots are taken after the scene has been edited into other valid configurations. The constraints that are satisfied in all of the snapshots are then applied to the scene objects. We discuss an efficient algorithm for inferring constraints from multiple snapshots. The algorithm has been incorporated into the Chimera editor, and several examples of its use are discussed.
Higher-order interpolation and least-squares approximation using implicit algebraic surfaces
Authors: Bajaj Chandrajit , Ihm Insung , Warren Joe
Published: July 2002

In this article, we characterize the solution space of low-degree, implicitly defined, algebraic surfaces which interpolate and/or least-squares approximate a collection of scattered point and curve data in three-dimensional space. The problem of higher-order interpolation and least-squares approximation with algebraic surfaces under a proper normalization reduces to a quadratic minimization problem with elegant and easily expressible solutions. We have implemented our algebraic surface-fitting algorithms, and included them in the distributed and collaborative geometric environment SHASTRA. Several examples are given to illustrate how our algorithms are applied to algebraic surface design.
Simple constrained deformations for geometric modeling and interactive design
Authors: Borrel Paul , Rappoport Ari
Published: July 2002

Deformations are a powerful tool for shape modeling and design. We present a new model for producing controlled spatial deformations, which we term
Simple Constrained Deformations (Scodef)
. The user defines a set of constraint points, giving a desired displacement and radius of influence for each. Each constraint point determines a local B-spline basis function centered at the constraint point, falling to zero for points beyond the radius. The deformed image of any point in space is a blend of these basis functions, using a projection matrix computed to satisfy the constraints. The deformation operates on the whole space regardless of the representation of the objects embedded inside the space. The constraints directly influence the final shape of the deformed objects, and this shape can be fine-tuned by adjusting the radius of influence of each constraint point. The computations required by the technique can be done very efficiently, and real-time interactive deformation editing on current workstations is possible.
Wide Area Technical Report Service
Authors: French James C. , Fox Edward A. , Maly Kurt , Selman Alan L.
Published: July 2002

Wide Area Technical Report Service (WATERS) is a distributed database of computer science technical reports. Contributors are departments of computer science that make their reports, stored locally at their sites, available through World-Wide Web and a WAIS search engine. By using WATERS, anyone with access to the Internet can, using a client such as Mosaic browse, search, obtain abstract and bibliographic information, and retrieve technical reports online. The latter assumes that the user's WWW client is set up to launch viewers such as ghostview for Postscript files, xdvi for dvi files, and xtiff for TIFF page images.
Taking steps
Authors: Slater Mel , Usoh Martin , Steed Anthony
Published: July 2002

This article presents an interactive technique for moving through an immersive virtual environment (or “virtual reality”). The technique is suitable for applications where locomotion is restricted to ground level. The technique is derived from the idea that presence in virtual environments may be enhanced the stronger the match between proprioceptive information from human body movements and sensory feedback from the computer-generated displays. The technique is an attempt to simulate body movements associated with walking. The participant “walks in place” to move through the virtual environment across distances greater than the physical limitations imposed by the electromagnetic tracking devices. A neural network is used to analyze the stream of coordinates from the head-mounted display, to determine whether or not the participant is walking on the spot. Whenever it determines the walking behavior, the participant is moved through virtual space in the direction of his or her gaze. We discuss two experimental studies to assess the impact on presence of this method in comparison to the usual hand-pointing method of navigation in virtual reality. The studies suggest that subjective rating of presence is enhanced by the walking method provided that participants associate subjectively with the virtual body provided in the environment. An application of the technique to climbing steps and ladders is also presented.
Algorithm 748: enclosing zeros of continuous functions
Authors: Alefeld G. E. , Potra F. A. , Shi Yixun
Published: July 2002

Two efficient algorithms for enclosing a zero of a continuous function are presented. They are similar to the recent methods, but together with quadratic interpolation they make essential use of inverse cubic interpolation as well. Since asymptotically the inverse cubic interpolation is always chosen by the algorithms, they achieve higher-efficiency indices: 1.6529… for the first algorithm, and 1.6686… for the second one. It is proved that the second algorithm is optimal in a certain family. Numerical experiments show that the two new methods compare well with recent methods, as well as with the efficient solvers of Dekker, Brent, Bus and Dekker, and Le. The second method from the present article has the best behavior of all 12 methods especially when the termination tolerance is small.
An efficient derivative-free method for solving nonlinear equations
Authors: Le D.
Published: July 2002

An algorithm is presented for finding a root of a real function. The algorithm combines bisection with second and third order methods using derivatives estimated from objective function values. Globaql convergence is ensured and the number of function evaluations is bounded by four times the number needed by bisection. Numerical comparisons with existing algorithms indicate the superiority of the new algorithm in all classes of problems.
Software aspects of strategic defense systems
Authors: Parnas David Lorge
Published: July 2002

A former member of the SDIO Panel on Computing in Support of Battle Management explains why he believes the “Star Wars” effort will not achieve its stated goals.
The EDR electronic dictionary
Authors: Yokoi Toshio
Published: July 2002

Natural language processing will grow into a vital industrial technology in the next five to 10 years. But this growth depends on the development of large linguistic databases that capture natural language phenomena [1, 2]. Another important theme for future work is development of large knowledge bases that are shared widely by different groups. One promising approach to such knowledge bases draws on natural language processing and linguistic knowledge. This article describes the EDR Electronic Dictionary [3], which seeks to provide a foundation for linguistic databases, and explains the relation of electronic dictionaries to very large knowledge bases.
Optimal prefetching via data compression
Authors: Vitter Jeffrey Scott , Krishnan P.
Published: July 2002

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms for caching. In this paper, we apply a form of the competitive philosophy for the first time to the problem of prefetching to develop an optimal universal prefetcher in terms of fault rate, with particular applications to large-scale databases and hypertext systems. Our prediction algorithms with particular applications to large-scale databases and hypertext systems. Our prediction algorithms for prefetching are novel in that they are based on data compression techniques that are both theoretically optimal and good in practice. Intuitively, in order to compress data effectively, you have to be able to predict future data well, and thus good data compressors should be able to predict well for purposes of prefetching. We show for powerful models such as Markov sources and
m
the order Markov sources that the page fault rate incurred by our prefetching algorithms are optimal in the limit for almost all sequences of page requests.
Understanding the sources of variation in software inspections
Authors: Porter Adam , Siy Harvey , Mockus Audris , Votta Lawrence
Published: July 2002

In a previous experiment, we determined how various changes in three structural elements of the software inspection process (team size and the number and sequencing of sessions) altered effectiveness and interval. Our results showed that such changes did not significantly influence the defect detection rate, but that certain combinations of changes dramatically increased the inspection interval. We also observed a large amount of unexplained variance in the data, indicating that other factors must be affecting inspection performance. The nature and extent of these other factors now have to be determined to ensure that they had not biased our earlier results. Also, identifying these other factors might suggest additional ways to improve the efficiency of inspections. Acting on the hypothesis that the “inputs” into the inspection process (reviewers, authors, and code units) were significant sources of variation, we modeled their effects on inspection performance. We found that they were responsible for much more variation in detect detection than was process structure. This leads us to conclude that better defect detection techniques, not better process structures, are the key to improving inspection effectiveness. The combined effects of process inputs and process structure on the inspection interval accounted for only a small percentage of the variance in inspection interval. Therefore, there must be other factors which need to be identified.
Bad subsequences of well-known linear congruential pseudorandom number generators
Authors: Entacher Karl
Published: July 2002

We present a spectral test analysis of full-period subsequences with small step sizes generated by well-known linear congruential pseudorandom number generators. Subsequences may occur in certain simulation problems or as a method to get parallel streams of pseudorandom numbers. Applying the spectral test, it is possible to find bad subsequences with small step sizes for almost all linear pseudorandom number generators currently in use.
Designing for usability: key principles and what designers think
Authors: Gould John D. , Lewis Clayton
Published: July 2002

This article is both theoretical and empirical. Theoretically, it describes three principles of system design which we believe must be followed to produce a useful and easy to use computer system. These principles are: early and continual focus on users; empirical measurement of usage; and iterative design whereby the system (simulated, prototype, and real) is modified, tested, modified again, tested again, and the cycle is repeated again and again. This approach is contrasted to other principled design approaches, for example, get it right the first time, reliance on design guidelines. Empirically, the article presents data which show that our design principles are not always intuitive to designers; identifies the arguments which designers often offer for not using these principles—and answers them; and provides an example in which our principles have been used successfully.
System level concurrency control for distributed database systems
Authors: Rosenkrantz Daniel J. , Stearns Richard E. , Lewis Philip M.
Published: July 2002

A distributed database system is one in which the database is spread among several sites and application programs “move” from site to site to access and update the data they need. The concurrency control is that portion of the system that responds to the read and write requests of the application programs. Its job is to maintain the global consistency of the distributed database while ensuring that the termination of the application programs is not prevented by phenomena such as deadlock. We assume each individual site has its own local concurrency control which responds to requests at that site and can only communicate with concurrency controls at other sites when an application program moves from site to site, terminates, or aborts.

This paper presents designs for several distributed concurrency controls and demonstrates that they work correctly. It also investigates some of the implications of global consistency of a distributed database and discusses phenomena that can prevent termination of application programs.
Mixed Congruential Random Number Generators for Binary Machines
Authors: Hull T. E. , Dobell A. R.
Published: July 2002

Random number generators of the mixed congruential type have recently been proposed. They appear to have some advantages over those of the multiplicative type, except that their statistical behavior is unsatisfactory in some cases. It is shown theoretically that a certain class of these mixed generators should be expected to fail statistical tests for randomness. Extensive testing confirms this hypothesis and makes possible a more precise definition of the unsatisfactory class. It is concluded that the advantages of mixed generators can be realized only in special circumstances. On machines with relatively short multiplication times the multiplicative generators are to be preferred.
Some New Results in Pseudo-Random Number Generation
Authors: Van Gelder A.
Published: July 2002

Pseudo-random number generators of the power residue (sometimes called congruential or multiplicative) type are discussed and results of statistical tests performed on specific examples of this type are presented. Tests were patterned after the methods of MacLaren and Marsaglia (M&M).

The main result presented is the discovery of several power residue generators which performed well in these tests. This is important because, of all the generators using standard methods (including power residue) that were tested by M&M, none gave satisfactory results.

The overall results here provide further evidence for their conclusion that the types of tests usually encountered in the literature do not provide an adequate index of the behavior of
n
-tuples of consecutively generated numbers. In any Monte Carlo or simulation problem where
n
supposedly independent random numbers are required at each step, this behavior is likely to be important.

Finally, since the tests presented here differ in certain details from those of M&M, some of their generators were retested as a check. A cross-check shows that results are compatible; in particular, if a generator failed one of their tests badly, it also failed the present author's corresponding test badly.
An Improved Bidirectional Heuristic Search Algorithm
Authors: Sint Lenie , de Champeaux Dennis
Published: July 2002

A modification of Pohl's bidirectional heuristic search algorithm is described together with a simplified implementation. Theorems are proved about conditions yielding shortest paths. The results are given of a worst-case analysis of different algorithms, suggesting a rank order of their quality. Results that Pohl had obtained with a unidirectional heuristic search algorithm on the 15-puzzle are compared with the results obtained with the new — simplified — algorithm.
CLIP
Authors: Gupta Avaneendra , Hayes John P.
Published: July 2002

A novel technique,
CLIP
, is presented for the automatic generation of optimal layouts of
CMOS
cells in the two-dimensional (2D) style.
CLIP
is based on integer-linear programming (
ILP
) and solves both the width and height minimization problems for 2D cells. Width minimization is formulated in a precise form that combines all factors influencing the 2D cell width—transistor placement, diffusion sharing, and vertical interrow connections—in a common problem space; this space is then searched in a systematic manner by the branch-and-bound algorithms used by
ILP
solvers. For height minimization, cell height is modeled accurately in terms of the horizontal wire routing density, and a minimum-height layout is found from among all layouts of minimum width. For exact width minimization alone,
CLIP
's run times are in seconds for large circuits with 30 or more transistors. For both height and width optimization,
CLIP
is practical for circuits with up to 20 transistors. To extend
CLIP
to larger circuits, hierarchical methods are necessary. Since
CLIP
is optimum under the modeling assumptions, its layouts are significantly better than those generated by other, heuristic, layout tools.
Value-based clock gating and operation packing
Authors: Brooks David , Martonosi Margaret
Published: July 2002

The large address space needs of many current applications have pushed processor designs toward 64-bit word widths. Although full 64-bit addresses and operations are indeed sometimes needed, arithmetic operations on much smaller quantities are still more common. In fact, another instruction set trend has been the introduction of instructions geared toward subword operations on 16-bit quantities. For examples, most major processors now include instruction set support for multimedia operations allowing parallel execution of several subword operations in the same ALU. This article presents our observations demonstrating that operations on “narrow-width” quantities are common not only in multimedia codes, but also in more general workloads. In fact, across the SPECint95 benchmarks, over half the integer operation executions require 16 bits or less. Based on this data, we propose two hardware mechanisms that dynamically recognize and capitalize on these narrow-width operations. The first, power-oriented optimization reduces processor power consumption by using operand-value-based clock gating to turn off portions of arithmetic units that will be unused by narrow-width operations. This optimization results in a 45%-60% reduction in the integer unit's power consumption for the SPECint95 and MediaBench benchmark suites. Applying this optimization to SPECfp95 benchmarks results in slightly smaller power reductions, but still seems warranted. These reductions in integer unit power consumption equate to a 5%-10% full-chip power savings. Our second, performance-oriented optimization improves processor performance by packing together narrow-width operations so that they share a single arithmetic unit. Conceptually similar to a dynamic form of MMX, this optimization offers speedups of 4.3%-6.2% for SPECint95 and 8.0%-10.4% for MediaBench.

Overall, these optimizations highlight an increasing opportunity for value-based optimizations to improve both power and performance in current microprocessors.
A diagnosis of beginning programmers' misconceptions of BASIC programming statements
Authors: Bayman Piraye , Mayer Richard E.
Published: July 2002

In the process of learning a computer language, beginning programmers may develop mental models for the language. A mental model refers to the user's conception of the “invisible” information processing that occurs inside the computer between input and output. In this study, 30 undergraduate students learned
BASIC
through a self-paced, mastery manual and simultaneously had hands-on access to an Apple II computer. After instruction, the students were tested on their mental models for the execution of each of nine
BASIC
statements. The results show that beginning programmers—although able to perform adequately on mastery tests in program generation—possessed a wide range of misconceptions concerning the statements they had learned. This paper catalogs beginning programmers' conceptions of “what goes on inside the computer” for each of nine
BASIC
statements.
On stopping criteria in verified nonlinear systems or optimization algorithms
Authors: Kearfott R. B. , Walster G. W.
Published: July 2002

Traditionally, iterative methods for nonlinear systems use heuristic domain and range stopping criteria to determine when accuracy tolerances have been met. However, such heuristics can cause stopping at points far from actual solutions, and can be unreliable due to the effects of round-off error or inaccuracies in data. In verified computations, rigorous determination of when a set of bounds has met a tolerance can be done analogously to the traditional approximate setting. Nonetheless, the range tolerance possibly cannot be met. If the criteria are used to determine when to stop subdivision of
n
-dimensional bounds into subregions, then failure of a range tolerance results in excessive, unnecessary subdivision, and could make the algorithm impractical. On the other hand, interval techniques can detect when inaccuracies or round-off will not permit residual bounds to be narrowed. These techniques can be incorporated into
range thickness
stopping criteria that complement the range stopping criteria. In this note, the issue is first introduced and illustrated with a simple example. The thickness stopping criterion is then formally introduced and analyzed. Third, inclusion of the criterion within a general verified global optimization algorithm is studied. An industrial example is presented. Finally, consequences and implications are discussed.
Further remark on stably updating mean and standard deviation estimates
Authors: Nelson Lloyd S.
Published: July 2002

A procedure for sequentially recomputing the mean and standard deviation of a weighted series of numbers as new values are added is given by Hanson [2]. To accommodate the most frequently occurring situation, Cotton [1] expressed Hanson's formulas in terms of unit weights. The result is accurate for updating the mean. However, for updating the standard deviation, Cotton chose to use Hanson's eq. (14), which Hanson rejected as being inaccurate when the new value is close to the mean.
Progressive acyclic digraphs—a tool for database integrity
Authors: Hansen Wilfred J.
Published: July 2002

A progressive acyclic diagraph (PAD) algorithm accepts are requests and maintains a graph in an acyclic state. When a request creates a cycle, nodes are “detached” until the new arc can be entered acyclically. This process is important in certain areas of database implementation in which there are constraints on the permissible sequences of actions.

Two PAD algorithms are presented; one uses a simple path matrix representation and the other uses a list with an “artificial gradient.” Experiments suggest that for large
N
the second is considerably faster, though both are asymptotically
O
(
NR
), where
N
is the number of nodes and
R
is the expected number of nodes reachable along paths from any given node.
How to share a secret
Authors: Shamir Adi
Published: July 2002

In this paper we show how to divide data
D
into
n
pieces in such a way that
D
is easily reconstructable from any
k
pieces, but even complete knowledge of
k
- 1 pieces reveals absolutely no information about
D
. This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.
The CRAY-1 computer system
Authors: Russell Richard M.
Published: July 2002

This paper describes the CRAY-1, discusses the evolution of its architecture, and gives an account of some of the problems that were overcome during its manufacture.

The CRAY-1 is the only computer to have been built to date that satisfies ERDA's Class VI requirement (a computer capable of processing from 20 to 60 million floating point operations per second) [1].

The CRAY-1's Fortran compiler (CFT) is designed to give the scientific user immediate access to the benefits of the CRAY-1's vector processing architecture. An optimizing compiler, CFT, “vectorizes” innermost DO loops. Compatible with the ANSI 1966 Fortran Standard and with many commonly supported Fortran extensions, CFT does not require any source program modifications or the use of additional nonstandard Fortran statements to achieve vectorization. Thus the user's investment of hundreds of man months of effort to develop Fortran programs for other contemporary computers is protected.
Representation of many-sided polygons and polygonal lines for rapid processing
Authors: Burton Warren
Published: July 2002

A representation for polygons and polygonal lines is described which allows sets of consecutive sides to be collectively examined. The set of sides are arranged in a binary tree hierarchy by inclusion. A fast algorithm for testing the inclusion of a point in a many-sided polygon is given. The speed of the algorithm is discussed for both ideal and practical examples. It is shown that the points of intersection of two polygonal lines can be located by what is essentially a binary tree search. The algorithm and a practical example are discussed. The representation overcomes many of the disadvantages associated with the various fixed-grid methods for representing curves and regions.
Stably updating mean and standard deviation of data
Authors: Hanson Richard J.
Published: July 2002

By considering the (sample) mean of a set of data as a fit to this data by a constant function, a computational method is given based on a matrix formulation and Givens transformations. The (sample) mean and standard deviation can be updated as data accumulates. The procedure is numerically stable and does not require storage of the data. Methods for dealing with weighted data and data removal are presented. When updating the mean and square of the standard deviation, the process requires no square roots.
An approximate method for generating asymmetric random variables
Authors: Ramberg John S. , Schmeiser Bruce W.
Published: July 2002

Tukey's lambda distribution is generalized to provide an algorithm for generating values of unimodal asymmetric random variables. This algorithm has the same advantages as the symmetric random variable generator previously given by the authors, except that the addition of another parameter complicates the problem of finding the parameter values to fit a distribution.
An exponential method for the solution of systems of ordinary differential equations
Authors: Chu Sherwood C. , Berman Mones
Published: July 2002

An explicit, coupled, single-step method for the numerical solution of initial value problems for systems of ordinary differential equations is presented. The method was designed to be general purpose in nature but to be especially efficient when dealing with stiff systems of differential equations. It is, in general, second order except for the case of a linear system with constant coefficients and linear forcing terms; in that case, the method is third order. It has been implemented and put to routine usage in biological applications—where stiffness frequently appears—with favorable results. When compared to a standard fourth order Runge-Kutta implementation, computation time required by this method has ranged from comparable for certain nonstiff problems to better than two orders of magnitude faster for some highly stiff systems.
Complex interval arithmetic
Authors: Rokne J. , Lancaster P.
Published: July 2002

Complex interval arithmetic is defined using real interval arithmetic. Complex interval division is defined so as to assure smallest possible resulting intervals.
An algorithm for the blocks and cutnodes of a graph
Authors: Paton Keith
Published: July 2002

An efficient method is presented for finding blocks and cutnodes of an arbitrary undirected graph. The graph may be represented either (i) as an ordered list of edges or (ii) as a packed adjacency matrix. If
w
denotes the word length of the machine employed, the storage (in machine words) required for a graph with
n
nodes and
m
edges increases essentially as 2(
m
+
n
) in case (i), or
n
2
/
w
in case (ii). A spanning tree with labeled edges is grown, two edges finally bearing different labels if and only if they belong to different blocks. For both representations the time required to analyze a graph on
n
nodes increases as

n
γ

where
γ
depends on the type of graph, 1 ≤
γ
≤ 2, and both bounds are attained. Values of
γ
are derived for each of several suitable families of test graphs, generated by an extension of the web grammar approach. The algorithm is compared in detail with that proposed by Read for which 1 ≤
γ
≤ 3.