bluuebunny/crossref_metadata_2025 huggingface dataset:
EXTENDED HUBBARD HAMILTONIAN WITH (SUPER)SYMMETRIES: ADDITIVE POLYNOMIAL R-MATRIX FOR SOME INTEGRABLE CASES
Authors: DOLCINI FABRIZIO , MONTORSI ARIANNA
Published: July 2002

We propose a constructive method to prove the integrability of a given physical Hamiltonian in one dimension, which amounts to looking for appropriate polynomial R-matrices, solutions of GYBE, whose first coefficient in the power expansion with respect to the spectral parameter is the Hamiltonian itself. The method is applied to the extended Hubbard Hamiltonian, in particular to the cases in which it exhibits so(4) or gl(2,1) symmetries. We show that in the latter case the R-matrices are at most polynomial of second degree, whose coefficients are nothing but the Hamiltonian, the identity and the permutation operator. In this way, all known completely integrable cases are recovered. Also, the method allows to recognize that the possible integrability of the most general gl(2,1) invariant Hamiltonian depends on the existence of a non-additive R-matrix.
QUANTUM OPTICS: GROUP AND NON-GROUP METHODS
Authors: SOLOMON ALLAN I.
Published: July 2002

We give a brief review of some group and quantum group theoretical methods used for the construction of photon states, generalisations of coherent and squeezed states. We finally describe a more general approach, exemplified by a new generalized coherent state, a generalization of the Kerr state.
THE KRAMERS PROBLEM REVISITED: A MINIMAL PATH APPROXIMATION TO THE LANGEVIN EQUATION
Authors: CHEN L. Y.
Published: July 2002

Applying the minimal path approximation to the Langevin equation, we revisit the well-known Kramers problem, noise-activated escape of a particle out of a meta-stable well and present a new technique to evaluate the activation rate. This new technique is valid for low to intermediate friction and is accurate for low temperatures. For low friction, analytical solution is derived. For intermediate friction, numerical results are obtained with minimal computational effort and the numerical effort required does not increase going for lower temperature.
BINDING ENERGY OF A BOUND POLARON IN THE FINITE PARABOLIC QUANTUM WELL
Authors: ZHAO FENG-QI , LIANG XI XIA
Published: July 2002

We have studied the effect of the electron–phonon interaction on the energy levels of the bound polaron and calculated the ground-state energy, the binding energy of the ground state, and the 1 s → 2 p ± transition energy in the GaAs/Al x Ga 1-x As parabolic quantum well (PQW) structure by using a modified Lee–Low–Pines (LLP) variational method. The numerical results are given and discussed. It is found that the contribution of electron–phonon interaction to the ground-state energy and the binding energy is obvious, especially in large well-width PQWs. The electron–phonon interaction should not be neglected.
A NEW SYNCHRONIZATION PRINCIPLE AND APPLICATION TO CHUA'S CIRCUITS
Authors: ZHENG YONGAI , LIU ZENGRONG , ZHOU JIN
Published: July 2002

In the paper we propose a new synchronization principle. To guarantee synchronization between coupled chaotic oscillators, proper coupling constants are selected by the Liapunov stability theory and Hurwitz Theorem. As an example and application, we prove the conjecture [Wu & Chua, 1994] that synchronization between two chaotic Chua's circuits can be achieved by using the second state as feedback variable for sufficiently large coupling constant.
ABSOLUTELY CONTINUOUS INVARIANT MEASURES FOR GENERIC MULTI-DIMENSIONAL PIECEWISE AFFINE EXPANDING MAPS
Authors: BUZZI J.
Published: July 2002

By a well-known result of Lasota and Yorke, any self-map f of the interval which is piecewise smooth and uniformly expanding, i.e. such that inf |f′|>1, admits absolutely continuous invariant probability measures (or a.c.i.m.'s for short). The generalization of this statement to higher dimension remains an open problem. Currently known results only apply to "sufficiently expanding maps". Here we present a different approach which can deal with almost all piecewise expanding maps. Here, we consider both continuous and discontinuous piecewise affine expanding maps.
SLABS: A FORMAL SPECIFICATION LANGUAGE FOR AGENT-BASED SYSTEMS
Authors: ZHU HONG
Published: July 2002

Being autonomous, proactive and adaptive, an agent-based system may demonstrate emergent behaviours, which are neither designed by the developers nor expected by the users of the system. Whether or not such emergent behaviours are advantageous, methods for the specification of agent behaviours must be developed to enable software engineers to analyse agent-based systems before they are implemented. This paper presents a formal specification language SLABS for agent-based systems. It is a model-based specification language defined based on the notion of agents as encapsulations of data, operations and behaviours. The behaviour of an agent is defined by a set of rules that describe the action/reaction of the agent in certain environment scenarios. The style and expressiveness of the language is demonstrated by examples like ants, personal assistants and speech-act style of agent communications.
ANCHOR — A CONNECTIONIST ARCHITECTURE FOR PARTITIONING FEATURE SPACES AND HIERARCHICAL NESTING OF NEURAL NETS
Authors: KUMAR RAJEEV
Published: July 2002

We present a novel connectionist architecture for handling arbitrarily complex neural computations. The architecture — which we call an Artificial Neural Network Compiler for Hierarchical ORganisation (ANCHOR) — facilitates network hierarchy and the partitioning of the input space into a number of small, simpler sub-mappings. This strategy is a mix of both a modular approach for reduction of the problem complexity, and an ensemble-based approach for increasing prediction accuracy. ANCHOR is implemented around the concept of a Superneuron which is a generalised view of a neuron-processing element; a superneuron is a single (or higher-order) perceptron which can be trained individually with the support of multiple learning algorithms. The indistinguishability between a superneuron, and a neuron is employed in hierarchical nesting of superneurons, up to (theoretically) infinite depth, within other superneurons as well as linear or tree-structured cascading. Hierarchical decomposition of simple boolean functions has been demonstrated as proof-of-concept. It is argued that this strategy of data-partitioning for subsequent mapping onto a hierarchical classifier reduces the learning complexity and offers better generalisation.
AN INTRODUCTION TO THE SUPERCROSSING INDEX OF KNOTS AND THE CROSSING MAP
Authors: ADAMS COLIN , OTHMER JONATHAN , STIER ANDREA , LEFEVER CARMEN , PAHK SANG , TRIPP JAMES
Published: July 2002

This paper is an introduction to supercrossing index for knots and links, which is related to crossing index in the same way that N. Kuiper's superbridge index is related to bridge index. A variety of results on supercrossing index and the associated crossing map are given.
RESPONSE OF VIRGO DETECTORS TO PRE-BIG-BANG GRAVITONS
Authors: BABUSCI D. , GIOVANNINI M.
Published: July 2002

The sensitivity achievable by a pair of VIRGO detectors to stochastic and isotropic gravitational wave backgrounds produced in pre-big-bang models is discussed in view of the development of a second VIRGO interferometer. We describe a semi-analytical technique allowing to compute the signal-to-noise ratio for (monotonic or non-monotonic) logarithmic energy spectra of relic gravitons of arbitrary slope. We apply our results to the case of two correlated and coaligned VIRGO detectors and we compute their achievable sensitivities. We perform our calculations both for the usual case of minimal string cosmological scenario and in the case of a non-minimal scenario (originally suggested by Gasperini) where a long dilaton dominated phase is present prior to the onset of the ordinary radiation dominated phase. In this framework, we investigate possible improvements of the achievable sensitivities by selective reduction of the thermal contributions (pendulum and pendulum's internal modes) to the noise power spectra of the detectors. Since a reduction of the shot noise does not increase significantly the expected sensitivity of a VIRGO pair (in spite of the relative spatial location of the two detectors) our findings support the experimental efforts directed towards a substantial reduction of thermal noise.
COLLAPSING AND EXPANDING CYLINDRICALLY SYMMETRIC FIELDS WITH LIGHTLIKE WAVE-FRONTS IN GENERAL RELATIVITY
Authors: PEREIRA PAULO R. C. T. , WANG A. Z.
Published: July 2002

The dynamics of collapsing and expanding cylindrically symmetric gravitational and matter fields with lightlike wave-fronts is studied in General Relativity, using the Barrabés–Israel method. As an application of the general formulae developed, the collapse of a matter field that satisfies the condition RABgAB =0, (A,B = z, φ), in an otherwise flat spacetime background is studied. In particular, it is found that the gravitational collapse of a purely gravitational wave or a null dust fluid cannot be realized in a flat spacetime background. The studies are further specified to the collapse of purely gravitational waves and the general conditions for such collapse are found. It is shown that after the waves arrive at the axis, in general, part of them is reflected to spacelike infinity along the future light cone, and part of it is focused to form spacetime singularities on the symmetry axis. The cases where the collapse does not result in the formation of spacetime singularities are also identified.
A NUCLEAR MANY-BODY THEORY AT FINITE TEMPERATURE APPLIED TO A PROTONEUTRON STAR
Authors: MARRANGHELLO GUILHERME F. , VASCONCELLOS CESAR A. Z. , DILLIG MANFRED , DE FREITAS PACHECO J. A.
Published: July 2002

Thermodynamical properties of nuclear matter are studied in the framework of an effective many-body field theory at finite temperature, considering the Sommerfeld approximation. We perform the calculations by using the nonlinear Boguta and Bodmer model, extended by the inclusion of the fundamental baryon octet and leptonic degrees of freedom. Trapped neutrinos are also included in order to describe protoneutron star properties through the integration of the Tolman–Oppenheimer–Volkoff equations, from which we obtain, beyond the standard relations for the masses and radii of protoneutron stars as functions of the central density, new results of these quantities as functions of temperature. Our predictions include: the determination of an absolute value for the limiting mass of protoneutron stars; new structural aspects on the nuclear matter phase transition via the behavior of the specific heat and, through the inclusion of quark degrees of freedom, the properties of a hadron-quark phase transition and hybrid protoneutron stars
FAILURE TIME DISTRIBUTION UNDER A δ-SHOCK MODEL AND ITS APPLICATION TO ECONOMIC DESIGN OF SYSTEMS
Authors: LI ZEHUI , CHAN LING-YAU , YUAN ZHIXIN
Published: July 2002

Suppose that shocks arrive and act on a system according to a Poisson distribution with mean rate of arrival equal to λ shock(s) per unit time. A δ-shock failure model is proposed in this paper, which assumes that when a system is acted on by a shock, it will recover fully in time δ(>0), and after that it will function as if no shock had occurred before. If the time lag between two successive shocks is less than δ, the second shock will cause failure of the system. Theoretical expressions related to the distribution of the failure time of the system are derived. These results can be used to optimize the design of a system from a costing point of view.
STEP–STEP INTERACTION ENERGY ON Cu(111) VICINAL SURFACES
Authors: GIESEN MARGRET , ICKING-KONERT GEORG SCHULZE
Published: July 2002

We have measured the terrace width distribution on copper (111) vicinal surfaces with (100) steps. For all surfaces, the distribution is well fitted by a Gaussian. The width of the Gaussian scales with the mean terrace width L, which is indicative of a repulsive 1/L2 interaction potential between steps. We determine an interaction strength of the potential of 3.2± 0.2 meV per atom length. From the temperature-dependent analysis of the step–step distance distribution, we find a kink formation energy for (100) steps of 0.12± 0.03 eV, which is consistent with previous measurements of the kink energy on copper (100) vicinal surfaces.
SURFACE RESTRUCTURING OF W(111) INDUCED BY SULFUR OVERLAYERS
Authors: NIEN C.-H. , ABDELREHIM I. M. , MADEY T. E.
Published: July 2002

The restructuring of S/W(111) surfaces has been studied using low-energy electron diffraction (LEED), Auger electron spectroscopy (AES) and scanning tunneling microscopy (STM). Dosing W(111) with a saturation coverage of H 2 S followed by annealing to >800 K causes the substrate to reconstruct, forming a structure with (4× 4) periodicity. In addition, the terrace-step configurations restructure and form triangular domains with a preferential orientation. These domains coalesce and enlarge, and also form multiple steps when the surface is heated to T>1000 K. The low reactivity of sulfided W(111) to high exposures of oxygen demonstrates that the surface is passivated by sulfur. Adsorption of S onto a faceted Pd/W(111) surface causes the facets to disappear, restoring the surface's planar form upon annealing. The resulting features are dominated by a (2× 2) structure. A size-mismatch mechanism, based on charge transfer between S/W and coadsorbed Pd/S on W, has been proposed to explain the formation of (4× 4) and (2× 2) structures, as well as the transition between these structures.
FLEXOR TENOLYSIS: A WORTHWHILE PROCEDURE IN A SELECT PATIENT POPULATION
Authors: Baker M.K. , Dunn S.J. , Tonkin M.A. , Eakins D.F.
Published: July 2002

This paper is a retrospective clinical review of flexor tenolysis performed on 23 digits for restricted active flexion following open and closed hand injuries. Based on Strickland’s13 grading scale, over 90% of digits had an excellent or good result at three months. No digits lost range of motion and there were no tendon ruptures. Importantly the active range of motion was much improved at three months compared with the initial postoperative assessment. This review reinforces the benefits of continuing dedicated hand therapy for at least three months and confirms the usefulness of flexor tenolysis as a salvage procedure in a carefully selected patient population.
UNCERTAINTY VERSUS RANDOMNESS: MINIMIZING MODEL DEPENDENCE
Authors: WILMOTT PAUL
Published: July 2002

I describe some recent advances in the pricing and hedging of derivative instruments. The theme is the reduction of model risk using non-probabilistic models. We see how the nonlinearity in the models leads to natural and optimal choices for static hedges for the reduction of market risk.
DECOMPOSITION OF STOCHASTIC FLOWS AND ROTATION MATRIX
Authors: RUFFINO PAULO R. C.
Published: July 2002

We provide geometrical conditions on the manifold for the existence of the Liao's factorization of stochastic flows [10]. If M is simply connected and has constant curvature, then this decomposition holds for any stochastic flow, conversely, if every flow on M has this decomposition, then M has constant curvature. Under certain conditions, it is possible to go further on the factorization: φt = ξt°Ψt° Θt, where ξt and Ψt have the same properties of Liao's decomposition and (ξt°Ψt) are affine transformations on M. We study the asymptotic behaviour of the isometric component ξt via rotation matrix, providing a Furstenberg–Khasminskii formula for this skew-symmetric matrix.
ROTATION OF PARTICLES IN POLARIZED BROWNIAN FLOWS
Authors: ZIRBEL CRAIG L. , WOYCZYŃSKI WOJBOR A.
Published: July 2002

We consider the rotation of tangent vectors and the mutual rotation of two particles undergoing motion in a random two-dimensional velocity field. We look at random fields whose laws are invariant under translations and rotations, but not reflections. These polarized fields are intermediate between homogeneous and isotropic fields, and may possess a preferred sense of rotation. The covariance of such a field must have a certain form which we describe. In a Brownian flow based on a polarized random field, we show that tangent vectors can rotate at a constant asymptotic rate, and that under certain conditions, two particles will rotate about each other at the same asymptotic rate. For illustration we present simulations of a polarized Gaussian field and of particles moving in a polarized Brownian flow.
Practical programmer
Authors: Rettig Marc
Published: July 2002

How one team made software testing an integral part of the development process.
Precision requirements for digital color reproduction
Authors: Stokes Mike , Fairchild Mark D. , Berns Roy S.
Published: July 2002

An environment was established to perform device-independent color reproduction of full-color pictorial images. In order to determine the required precision for this environment, an experiment was performed to psychophysically measure colorimetric tolerances for six images using paired comparison techniques. These images were manipulated using 10 linear and nonlinear functions in the CIELAB dimensions of lightness, chroma, and hue angle. Perceptibility tolerances were determined using probit analysis. From these results, the necessary precision in number of bits per color channel was determined for both the CIELAB and the CRT rgb device color spaces. For both the CIELAB color space and the CRT rgb device space, approximately eight color bits per channel were required for imperceptible color differences for pictorial images, and 10 bits per channel were required for computational precision.
EmbeddedButtons
Authors: Bier Eric A.
Published: July 2002

EmbeddedButtons is a library of routines and a runtime kernel that support the integration of buttons into document media, including text and graphics. Existing document editors can be modified to participate in this open architecture with the addition of a few simple routines. Unlike many button systems that insert special button objects into document media, this system supports turning existing document objectsinto buttons. As a consequence, buttons inherit all of the attributes of normal document objects, and the appearance of buttons can be edited using operations already familiar to users. Facilities are provided for linking buttons to application windows so that documents can serve as application control panels. Hence, user interface designers can lay out control panels using familiar document editors rather than special-purpose tools. Three classes of buttons have been implemented, including buttons that pop up a menu and buttons that store and display the value of a variable. New button classes, editors, and applications can be added at run time. Two editors, one for text and one for graphics, currently participate in the architecture.
The transitive closure of control dependence
Authors: Weiss Michael
Published: July 2002

We characterize the transitive closure of the control dependence relation and give an application to the theory of control fow guards. We relate our result to characterizations by Beck et al., by Sarkar, and by Cytron et al., and strengthen a result of the latter concerning dominance frontiers and join sets.
Using static single assignment form in a code optimizer
Authors: McConnell Carl , Johnson Ralph E.
Published: July 2002

Static single assignment form represents data dependences elegantly and provides a basis for powerful optimizations. Table-driven techniques for peephole optimization and code generation are straightforward and effective. it is natural to want to use both together in a code optimizer. However, doing so reveals that static single assignment form does not remove all antidependences, and that it conflicts with table-driven code generation for 2-address machines. This paper describes these problems and how to solve them.
Abstract description of pointer data structures
Authors: Hummel Joseph , Hendren Laurie J. , Nicolau Alexandru
Published: July 2002

Even though impressive progress has been made in the area of optimizing and parallelizing array-based programs, the application of similar techniques to programs using pointer data structures has remained difficult. Unlike arrays which have a small number of well-defined properties, pointers can be used to implement a wide variety of structures which exhibit a much larger set of properties. The diversity of these structures implies that programs with pointer data structures cannot be effectively analyzed by traditional optimizing and parallelizing compilers.

In this paper we present a new approach that leads to the improved analysis and transformation of programs with recursively defined pointer data structures. Our approach is based on a mechanism for the Abstract Description of Data Structures (ADDS). ADDS is a simple extension to existing imperative languages that allows the programmer to explicitly describe the important properties of a large class of data structures. These abstract descriptions may be used by the compiler to achieve more accurate program analysis in the presence of pointers, which in turn enables and improves the application of numerous optimizing and parallelizing transformations. We present ADDS by describing various data structures; we discuss how such descriptions can be used to improve analysis and debugging; and we supply three important transformations enabled by ADDS.
Waiting algorithms for synchronization in large-scale multiprocessors
Authors: Lim Beng-Hong , Agarwal Anant
Published: July 2002

Through analysis and experiments, this paper investigates two-phase waiting algorithms to minimize the cost of waiting for synchronization in large-scale multiprocessors. In a two-phase algorithm, a thread first waits by polling a synchronization variable. If the cost of polling reaches a limit

L
poll

and further waiting is necessary, the thread is blocked, incurring an additional fixed cost,
B
. The choice of

L
poll

is a critical determinant of the performance of two-phase algorithms. We focus on methods for statically determining

L
poll

because the run-time overhead of dynamically determining

L
poll

can be comparable to the cost of blocking in large-scale multiprocessor systems with lightweight threads.

Our experiments show that
always-block
(

L
poll

= 0) is a good waiting algorithm with performance that is usually close to the best of the algorithms compared. We show that even better performance can be achieved with a static choice of

L
poll

based on knowledge of likely wait-time distributions. Motivated by the observation that different synchronization types exhibit different wait-time distributions, we prove that a static choice of

L
poll

can yield close to optimal on-line performance against an adversary that is restricted to choosing wait times from a fixed family of probability distributions. This result allows us to make an optimal static choice of

L
poll

based on synchronization type. For exponentially distributed wait times, we prove that setting

L
poll

= 1n(e-1)
B
results in a waiting cost that is no more than
e/(e-1)
times the cost of an optimal off-line algorithm. For uniformly distributed wait times, we prove that setting
L
poll
=1/2(square root of 5 -1)
B
results in a waiting cost that is no more than (square root of 5 + 1)/2 (the golden ratio) times the cost of an optimal off-line algorithm. Experimental measurements of several parallel applications on the Alewife multiprocessor simulator corroborate our theoretical findings.
An analysis of ML typability
Authors: Kfoury A. J. , Tiuryn J. , Urzyczyn P.
Published: July 2002

We carry out an analysis of typability of terms in ML. Our main result is that this problem is DEXPTIME-hard, where by DEXPTIME we mean DTIME(2
n
0(1)
). This, together with the known exponential-time algorithm that solves the problem, yields the DEXPTIME-completeness result. This settles an open problem of P. Kanellakis and J. C. Mitchell.

Part of our analysis is an algebraic characterization of ML typability in terms of a restricted form of semi-unification, which we identify as
acyclic semi-unification
. We prove that ML typability and acyclic semi-unification can be reduced to each other in polynomial time. We believe this result is of independent interest.
A parallel block implementation of Level-3 BLAS for MIMD vector processors
Authors: Daydé Michel J. , Duff Iain S. , Petitet Antoine
Published: July 2002

We describe an implementation of Level-3 BLAS (Basic Linear Algebra Subprograms) based on the use of the matrix-matrix multiplication kernel (GEMM). Blocking techniques are used to express the BLAS in terms of operations involving triangular blocks and calls to GEMM. A principal advantage of this approach is that most manufacturers provide at least an efficient serial version of GEMM so that our implementation can capture a significant percentage of the computer performance. A parameter which controls the blocking allows an efficient exploitation of the memory hierarchy of the various target computers. Furthermore, this blocked version of Level-3 BLAS is naturally parallel. We present results on the ALLIANT FX/80, the CONVEX C220, the CRAY-2, and the IBM 3090/VF. For GEMM, we always use the manufacturer-supplied versions. For the operations dealing with triangular blocks, we use assembler or tuned Fortran (using loop-unrolling) codes, depending on the efficiency of the available libraries.
Provably correct theories of action
Authors: Lin Fangzhen , Shoham Yoav
Published: July 2002

We investigate logical formalization of the effects of actions in the situation calculus. We propose a formal criterion against which to evaluate theories of deterministic actions. We show how the criterion provides us a formal foundation upon which to tackle the frame problem, as well as its variant in the context of concurrent actions. Our main technical contributions are in formulating a wide class of monotonic causal theories that satisfy the criterion, and showing that each such theory can be reformulated succinctly in circumscription.
Determining the last process to fail
Authors: Skeen Dale
Published: July 2002

A
total failure
occurs whenever all processes cooperatively executing a distributed task fail before the task completes. A frequent prerequisite for recovery from a total failure is identification of the last set (LAST) of processes to fail. Necessary and sufficient conditions are derived here for computing LAST from the local failure data of recovered processes. These conditions are then translated into procedures for deciding LAST membership, using either complete or incomplete failure data. The choice of failure data is itself dictated by two requirements: (1) it can be cheaply maintained, and (2) it must afford maximum fault-tolerance in the sense that the expected number of recoveries required for identifying LAST is minimized.
QMRPACK
Authors: Freund Roland W. , Nachtigal Noël M.
Published: July 2002

The quasi-minimal residual (QMR) algorithm is a Krylov-subspace method for the iterative solution of large non-Hermitian linear systems. QMR is based on the look-ahead Lanczos algorithm that, by itself, can also be used to obtain approximate eigenvalues of large non-Hermitian matrices. QMRPACK is a software package with Fortran 77 implementations of the QMR algorithm and variants thereof, and of the three-term and coupled two-term look-ahead Lanczos algorithms. In this article, we discuss some of the features of the algorithms in the package, with emphasis on the issues related to using the codes. We describe in some detail two routines from the package, one for the solution of linear systems and the other for the computation of eigenvalue approximations. We present some numerical examples from applications where QMRPACK was used.
Recovery in the Calypso file system
Authors: Devarakonda Murthy , Kish Bill , Mohindra Ajay
Published: July 2002

This article presents the deign and implementation of the recovery scheme in Calypso. Calypso is a cluster-optimized, distributed file system for UNIX clusters. As in Sprite and AFS, Calypso servers are stateful and scale well to a large number of clients. The recovery scheme in Calypso is nondisruptive, meaning that open files remain open, client modified data are saved, and in-flight operations are properly handled across server recover. The scheme uses distributed state amount the clients to reconstruct the server state on a backup node if disks are multiported or on the rebooted server node. It guarantees data consistency during recovery and provides congestion control. Measurements show that the state reconstruction can be quite fast: for example, in a 32-node cluster, when an average node contains state for about 420 files, the reconstruction time is about 3.3 seconds. However, the time to update a file system after a failure can be a major factor in the overall recovery time, even when using journaling techniques.
DESI methods for stiff initial-value problems
Authors: Butcher J. C. , Cash J. R. , Diamantakis M. T.
Published: July 2002

Recently, the so-called DESI (diagonally extended singly implicit) Runge-Kutta methods were introduced to overcome some of the limitations of singly implicit methods. Preliminary experiments have shown that these methods are usually more efficient than the standard singly implicit Runge-Kutta (SIRK) methods and, in many cases, are competitive with backward differentiation formulae (BDF). This article presents an algorithm for determining the full coefficient matrix from the stability function, which is already chosen to make the method A-stable. Because of their unconventional nature, DESI methods have to be implemented in a special way. In particular, the effectiveness of these methods depends heavily on how starting values are chosen for the stage iterations. These and other implementation questions are descussed in detail, and design choices we have made form the basis of an experimental coe for the solution of stiff problems by DESI methods. We present here a small subset of the numerical results obtained with our code. Many of these results are quite satisfactory and suggest that DESI methods have a useful role in the solution of this type of problem.
Instability and performance limits of distributed simulators of feedforward queueing networks
Authors: Shorey Rajeev , Kumar Anurag , Rege Kiran M.
Published: July 2002

In this article we study the performance of distributed simulation of open feedforward queueing networks, by analyzing queueing models of message flows in distributed discrete event simulators. We view each logical process in a distributed simulation as comprising a message sequencer with associated message queues, followed aby an event processor. We introduce the idealized, but analytically useful, comcept of
maximum lookahead.
We show that, with quite general stochatstic assumptions for message arrival and time-stamp processes, the meassage queues are
unstable
for conservative sequencing, and for conservative sequencing with maximum lookahead and hence for optimistic resequencing, and for any resequenceing algorithm that does not employ interprocessor
flow control
. Finally, we provide formulas for the throughput of distributed simulators of feedforward queueing networks.
Hybrid slicing
Authors: Gupta Rajiv , Soffa Mary Lou , Howard John
Published: July 2002

Program slicing is an effective techniqe for narrowing the focus of attention to the relevant parts of a program during the debugging process. However, imprecision is a problem in static slices, since they are based on all possible executions that reach a given program point rather than the specific execution under which the program is being debugged. Dynamic slices, based on the specific execution being debugged, are precise but incur high run-time overhead due to the tracing information that is collected during the program's execution. We present a hybrid slicing technique that integrates dynamic information from a specific execution into a static slice analysis. The
hybrid slice
produced is more precise that the static slice and less costly that the dynamic slice. The technique exploits dynamic information that is readily available during debugging—namely, breakpoint information and the dynamic call graph. This information is integrated into a static slicing analysis to more accurately estimate the potential paths taken by the program. The breakpoints and call/return points, used as reference points, divide the execution path into intervals. By associating each statement in the slice with an execution interval, hybrid slicing provides information as to when a statement was encountered during execution. Another attractive feature of our approach is that it allows the user to control the cost of hybrid slicing by limiting the amount of dynamic information used in computing the slice. We implemented the hybrid slicing technique to demonstrate the feasibility of our approach.
The overhead of locking (and commit) protocols in distributed databases
Authors: Wolfson Ouri
Published: July 2002

The main purpose of a locking protocol is to ensure correct interleaving of actions executed by concurrent transactions. The locking protocol consists of a set of rules dictating how accessed entities should be locked and unlocked. As a result of obeying the rules, transactions in a distributed database incur an overhead. We propose three measures of evaluating this overhead, each most suitable to a different type of underlying communication network. Then, using a graph theoretic model, we analyze and compare three protocols according to each measure: two-phase locking, two-phase locking with a fixed order imposed on the database entities (ensuring deadlock freedom), and the tree protocol. In practice, a transaction also executes the two-phase commit protocol in order to guarantee atomicity. Therefore, the combined overhead of each locking protocol and the two-phase commit protocol is also determined.
Formal models of stepwise refinements of programs
Authors: Mili Ali , Desharnais Jules , Gagné Jean Raynomd
Published: July 2002

Of the many ways to express program specifications, three of the most common are: as a pair of assertions, an input assertion and an output assertion; as a function mapping legal inputs to correct outputs; or as a relation containing the input/output pairs that are considered correct. The construction of programs consists of mapping a potentially complex specification into a program by recursively decomposing complex specifications into simpler ones. We show how this decomposition takes place in all three modes of specification and draw some conclusions on the nature of programming.
Algorithm 780: exponential pseudorandom distribution
Authors: Hamilton Kenneth G.
Published: July 2002

An algorithm is presented for the calculation of exponentially distributed random numbers. It is based on mathematics that was published by Ahrend and Dieter, but some errors have been corrected.
Eliminating false loops caused by sharing in control path
Authors: Su Alan , Hsu Yu-Chin , Liu Ta-Yung , Lee Mike Tien-Chien
Published: July 2002

In high-level synthesis, resource sharing may result in a circuit containing false loops that create great difficulty in timing validation during the design sign-off phase. It is hence desirable to avoid generating any false loops in a synthesized circuit. Previous work [Stok 1992; Huang et al. 1995] considered mainly data path sharing for false loop elimination. However, for a complete circuit with both data path and control path, false loops can be created due to control logic sharing. In this article, we present a novel approach to detect and eleminate the false loops caused by control logic sharing. An effective filter is devised to reduce the computational complexity of false loop detection, which is based on checking the level numbers that are propagated from data path operators to imputs and outputs of the control path. Only the input/output pairs of the control path identified by the filter are further investigated by traversing into the data path for false loop detection. A removal algorithm is then applied to eliminate the detected false loops, followed by logic minimization to further optimize the circuit. Experimental results show that for the nine example circuits we tested, the final designs after false loop removal and logic minimization give only slightly larger area than the original ones that contain false loops.
Optimal river routing with crosstalk constraints
Authors: Zhou Hai , Wong D. F.
Published: July 2002

With the increasing density of VLSI circuits, the interconnection wires are being packed even closer. This has increased the effect of interaction among these wires on circuit performance and hence, the importance of controlling crosstalk. In this article, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of neighboring nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk when it is feasible.
Algorithm 788: automatic boundary integral equation programs for the planar Laplace equation
Authors: Atkinson Kendall , Jeon Youngmok
Published: July 2002

Algorithms with automatic error control are described for the solution of Laplace's equation on both interior and exterior regions, with both Dirichlet and Neumann boundary conditions. The algorithms are based on standard reformulations of each boundary value problem as a boundary integral equation of the second kind. The Nyström method is used to solve the integral equations, and convergence of arbitrary high order is observed when the boundary data are analytic. The Kelvin transformation is introduced to allow a simple conversion between internal and external problems. Two Fortran program implementations, DRCHLT and NEUMAN, are defined, analyzed, and illustrated.
Processor allocation strategies for multiprocessor database machines
Authors: Boral Haran , DeWitt David J.
Published: July 2002

In this paper four alternative strategies for assigning processors to queries in multiprocessor database machines are described and evaluated. The results demonstrate that SIMD database machines are indeed a poor design when their performance is compared with that of the three MIMD strategies presented.

Also introduced is the application of data-flow machine techniques to the processing of relational algebra queries. A strategy that employs data-flow techniques is shown to be superior to the other strategies described by several experiments. Furthermore, if the data-flow query processing strategy is employed, the results indicate that a two-level storage hierarchy (in which relations are paged between a shared data cache and mass storage) does not have a significant impact on performance.
Analysis of index-sequential files with overflow chaining
Authors: Larson Per-Åke
Published: July 2002

The gradual performance deterioration caused by deletions from and insertions into an index-sequential file after loading is analyzed. The model developed assumes that overflow records are handled by chaining. Formulas for computing the expected number of overflow records and the expected number of additional accesses caused by the overflow records for both successful and unsuccessful searches are derived.
Performance evaluation of attribute-based tree organization
Authors: Gopalakrishna V. , Veni Madhavan C. E.
Published: July 2002

A modified version of the multiple attribute tree (MAT) database organization, which uses a compact directory, is discussed. An efficient algorithm to process the directory for carrying out the node searches is presented. Statistical procedures are developed to estimate the number of nodes searched and the number of data blocks retrieved for most general and complex queries. The performance of inverted file and modified MAT organizations are compared using six real-life databases and four types of query complexities. Careful tradeoffs are established in terms of storage and access times for directory and data, query complexities, and database characteristics.
Optimal policy for batch operations
Authors: Lohman Guy M. , Muckstadt John A.
Published: July 2002

Many database maintenance operations are performed periodically in batches, even in realtime systems. The purpose of this paper is to present a general model for determining the optimal frequency of these batch operations. Specifically, optimal backup, checkpointing, batch updating, and reorganization policies are derived. The approach used exploits inventory parallels by seeking the optimal number of items—rather than a time interval—to trigger a batch. The Renewal Reward Theorem is used to find the average long run costs for backup, recovery, and item storage, per unit time, which is then minimized to find the optimal backup policy. This approach permits far less restrictive assumptions about the update arrival process than did previous models, as well as inclusion of storage costs for the updates. The optimal checkpointing, batch updating, and reorganization policies are shown to be special cases of this optimal backup policy. The derivation of previous results as special cases of this model, and an example, demonstrate the generality of the methodology developed.
A transformational grammar-based query processor for access control in a planning system
Authors: Bonczek Robert H. , Cash James I. , Whinston Andrew B.
Published: July 2002

Providing computer facilities and data availability to larger numbers of users generates increased system vulnerability which is partially offset by software security systems. Much too often these systems are presented as ad hoc additions to the basic data management system. One very important constituent of software security systems is the access control mechanism which may be the last resource available to prohibit unauthorized data retrieval. This paper presents a specification for an access control mechanism. The mechanism is specified in a context for use with the GPLAN decision support system by a theoretical description consistent with the formal definition of GPLAN's query language. Incorporation of the mechanism into the language guarantees it will not be an ad hoc addition. Furthermore, it provides a facile introduction of data security dictates into the language processor.
Garbage collection for a client-server persistent object store
Authors: Amsaleg Laurent , Franklin Michael J. , Gruber Olivier
Published: July 2002

We describe an efficient server-based algorithm for garbage collecting persistent object stores in a client-server environmnet. The algorithm is incremental and runs concurrently with client transactions. Unlike previous algorithms, it does not hold any transactional locks on data and does non require callbacks to clients. It is fault-tolerant, but performs very little logging. The algorithm has been designed to be integrated into existing systems, and therefore it works with standard implementation techniques such as Two-Phase Locking and Write-Ahead-Logging. In addition, it supports client-server performance optimizations such as client caching and flexible management of client buffers. We describe an implementation of the algorithm in the EXODUS storage manager and present the results of a performance study of the implementation.
Asymptotic Behavior of the Best Polynomial Approximation
Authors: Blum E. K. , Curtis P. C.
Published: July 2002

Let ƒ (
x
) be a real-valued function defined and continuous on [- 1, +1] and let
T
(
x
) =
a
0
/2 + Σ
∞

k
=1

a
k
T
k

(
x
) be the Fourier-Tschebycheff expansion for ƒ (
x
), that is,

T
k

(
x
) = cos
klθ
,

a
k

= 2/π ∫
π
0
ƒ (cos
θ
) cos
kθ dθ
where
x
= cos
θ
. If

P
n

is the class of real polynomials in
x
of degree less than or equal to
n
, we let

M
n

= inf

pϵPn

sup

-1≤
x
≤1

| ƒ (
x
) -
p
(
x
) |.

M
n

is called the best Tschebycheff approximation to ƒ (
x
) by a polynomial of degree less than or equal to
n
.
Digital Computer System for Dynamic Analysis of Speech and Sound Feedback Mechanisms
Authors: Smith K. U. , Ansell S. D. , Koehler J. , Servos G. H.
Published: July 2002

The aim of the research reported is to put the laboratory application of closed-loop digital computer systems to experimental control and analysis in biology and behavioral science on a formal basis, using special concepts of programming to quantitatively control different parameters of variation in sensory feedback of specific response systems. The theory is unconventional in that the computer and the techniques of closed-loop programming are designed to control time delays, space displacements, kinetic modulations, and informational and symbolic transformations in the sensory feedback that is generated by movements and/or physiological actions of the living subject.

The present experiment illustrates application of the system and the methods of closed-loop perturbation programming to study of delayed auditory feedback of speech. The subject's speech is transduced, amplified, converted by an analog-to-digital converter, programmed for delays, deconverted by a digital-to-analog converter, filtered, amplified, and then used to activate protected earphones on the speaker's ears. The computer is also used to introduce many special perturbation of the auditory feedback of speech in real time.
One View of Man-Machine Interaction
Authors: Yershóv A. P.
Published: July 2002

For the computer to be a tool of the general scientist rather than of the computer specialist it will have to conform to the characteristics of interpersonal communications, since these are rooted in the characteristics of human intelligence. It must not require the scientist to use a language which is formal or which requires special study. It must, like a human assistant, share with each particular employer the labor of establishing a common language and of formulating clear instructions. This shared labor must take the form of a dialog in which the computer asks questions on obscure portions of its instructions. The computer must accept as answers either paraphrases or explanations. It should not need to repeat identical or similar questions. It should choose fundamental or revealing questions; if necessary an employer can encourage this by giving fundamental answers to superficial questions.
An Online Display for the Study of Approximating Functions
Authors: Conn Richard W. , von Holdt Richard E.
Published: July 2002

The method of least squares is often used to determine the arbitrary constants in an empirical formula or approximating function. If such a function is not linear in its unknowns, approximate values must first be obtained. Typically they are obtained graphically or as the result of physical supposition or similar experiment. This paper describes a program written to find first approximations for certain oscilloscope traces by: (1) displaying the trace on a cathode-ray tube (CRT) and, (2) imposing upon it a computer generated curve which (3) employs parameters arbitrarily supplied by an operator in a quest for visual coincidence.

While the technique proved successful in this application, a greater value may lie in its having indicated a mechanism for further automation. In its present form the method might best be utilized as a tool for studying the behavior of selected approximating functions.
Sequential Processing Machines (S.P.M) Analyzed With a Queuing Theory Model
Authors: Kleinrock Leonard
Published: July 2002

Results are obtained for a model of many processors operating in series. The results are obtained directly by recognizing that a sequential processing may be viewed as a cyclic queue. Exact results are given for two sequential processing stages with a buffer storage of arbitrary size between the stages, and approximate results for the case of 2

M

(
M
an integer) stages. The analysis is good only for exponentially distributed computation times.
Use of Multiwrite for General Programmability of Search Memories
Authors: Porter Sigmund N.
Published: July 2002

Multiwrite (selective writing in words which satisfied a previous search) is shown to permit parallel evaluation of any Boolean function (including arithmetic) in a search memory. A general method is given which expresses the Boolean function as a sum of products, searches for these products one at a time and OR8 the results of these searches. An example applying the process to arithmetic given.