bluuebunny/crossref_metadata_2025 huggingface dataset:
A TWO-DIMENSIONAL REPRESENTATION OF FOUR-DIMENSIONAL GRAVITATIONAL WAVES
Authors: SCHMIDT HANS-JÜRGEN
Published: July 2002

The Einstein equation in D dimensions, if restricted to the class of spacetimes possessing n = D - 2 commuting hypersurface-orthogonal Killing vectors, can be equivalently written as metric-dilaton gravity in two dimensions with n scalar fields.

For n = 2, this result reduces to the known reduction of certain four-dimensional metrics which include gravitational waves. Here, we give such a representation which leads to a new proof of the Birkhoff theorem for plane-symmetric spacetimes, and which leads to an explanation, in which sense two (spin zero-) scalar fields in two dimensions may incorporate the (spin two-) gravitational waves in four dimensions. (This result should not be mixed up with well–known analogous statements where, however, the four-dimensional spacetime is supposed to be spherically symmetric, and then, of course, the equivalent two-dimensional picture cannot mimic any gravitational waves.)

Finally, remarks on hidden symmetries in two dimensions are made.
ON AN ALTERNATIVE METHOD TO STUDY COLLAPSED STARS
Authors: AQUILANO ROBERTO O.
Published: July 2002

To find the motion equation of a spherically symmetric radiating shell moving in a central gravitational potential, an improved version of the post-Newtonian approximation is used.
STABLE SIZE DISTRIBUTION IN A MATHEMATICAL MODEL FOR TUMOR CELL POPULATION GROWTH DURING CHEMOTHERAPEUTICAL TREATMENT WITH TWO NON-CROSS RESISTANT DRUGS
Authors: LECKAR HAMILTON F. , VENDITE LAÉRCIO L.
Published: July 2002

A size-structured model is developed to study the growth of tumor cell populations during chemotherapeutic treatment with two non-cross resistant drugs, [Formula: see text] and [Formula: see text]. The cells reproduce by fission. Four types of cells are considered: sensitive cells to both [Formula: see text] and [Formula: see text], cells that are resistant to [Formula: see text] only, cells that are resistant to [Formula: see text] only, and cells that are resistant to both [Formula: see text] and [Formula: see text]. Resistant cells arise by spontaneous genetic mutation from sensitive cells and are selected during the growth of the mixed population. The model consists on a system of linear partial differential equations describing the size-density of each type of cells. That corresponds to chemotherapeutic treatment on a given time sequence intervals such that, we continuously apply [Formula: see text] at a first interval and next we apply [Formula: see text] at a second interval, and so forth. We obtain a stable size-distribution theorem for this case.
FRACTALS, SCALING AND THE QUESTION OF SELF-ORGANIZED CRITICALITY IN MAGNETIZATION PROCESSES
Authors: DURIN GIANFRANCO , BERTOTTI GIORGIO , MAGNI ALESSANDRO
Published: July 2002

The main physical aspects and the theoretical description of stochastic domain wall dynamics in soft magnetic materials are reviewed. The intrinsically random nature of domain wall motion results in the Barkhausen effect, which exibits scaling properties at low magnetization rates and 1/f power spectra. It is shown that the Barkhausen signal ν, as well as the size Δx and the duration Δu of jumps follow distributions of the form ν−α, Δx−β, Δu−γ, with α=1−c, β=3/2−c/2, γ=2–c, where c is a dimensionless parameter proportional to the applied field rate. These results are analytically calculated by means of a stochastic differential equation for the domain wall dynamics in a random perturbed medium with brownian properties and then compared to experiments. The Barkhausen signal is found to be related to a random Cantor dust with fractal dimension D=1−c, from which the scaling exponents are calculated using simple properties of fractal geometry. Fractal dimension Δ of the signal v is also studied using four different methods of calculation, giving Δ≈1.5, independent of the method used and of the parameter c. The stochastic model is analyzed in detail in order to clarify if the shown properties can be interpreted as manifestations of self-organized criticality in magnetic systems.
SELECTING THE MOST RELIABLE POPULATION UNDER STEP-STRESS ACCELERATED LIFE TEST
Authors: CHING TANG LOON , SUN YESHENG
Published: July 2002

We present a method for selecting the most reliable population under step-stress accelerated life testing with type II censoring. We construct a new statistic, the transitional order statistic (TOS), and derive an approximate expression for its distribution. Using the TOS, a selection rule is formulated from the test results. For planning purposes, we establish the relation between sample size and the probability of correct selection by defining a nonlinear indifference zone under the least favorable configuration. Finally, a simulation study is performed to illustrate the selection procedure and to validate the associated probability of correct selection.
GROWTH AND DISLOCATION ETCHING OF Sb0.2Bi1.8Te3 SINGLE CRYSTALS
Authors: DESAI C. F. , SONI P. H. , BHAVSAR S. R. , SHAH R. C.
Published: July 2002

Sb 0.2 Bi 1.8 Te 3 single crystals have been grown by the zone melting and Bridgman–Stockbarger methods. The freezing interface temperature gradients of 90°C/cm and 45°C/cm, respectively, have been found to yield the best quality crytals obtainable at the growth rate of 0.35 cm/h. The crystals have been characterized by the powder XRD technique. The crystals grown by the zone melting method have been observed to exhibit certain typical features on their top free surfaces. A new dislocation etchant has been developed to give reproducible etch-pitting on the cleavage surface. Tests of this dislocation etchant have been carried out successfully and the etchant has been used to obtain dislocation density in the crystals.
INTERACTION BETWEEN Li AND Na INTERCALATED INTO 1T-TaSe2 LAYER COMPOUNDS
Authors: KAMARATOS M. , PAPAGEORGOPOULOS C. A. , PAPAGEORGOPOULOS D. C. , TONTI D. , PETTENKOFER C. , JAEGERMANN W.
Published: July 2002

In this work we study the adsorption of Li on a Na-intercalated TaSe 2(0001) and, reversibly, the deposition of Na on a Li-intercalated TaSe 2(0001) surface. The intercalation occurred by deposition of the alkali elements onto the basal plane of the TaSe 2. The experiment was performed in UHV by soft X-ray photoelectron spectroscopy, using synchrotron radiation as excitation source. Lithium intercalation into 1T-TaSe 2 leads to a phase transition of the substrate from 1T to 2H polytypism. Lithium and sodium appear to compete in the intercalation process. Sodium pushes the preintercalated Li deeper into the bulk of the substrate, whereas, in the case of Li on Na-intercalated TaSe 2, an exchange reaction takes place and part of the Na deintercalates.
EMBEDDED ATOM METHOD STUDY OF SURFACE ALLOYING OF Al ON Pd(001)
Authors: BILIĆ A. , KING B. V. , O'CONNOR D. J.
Published: July 2002

We have simulated the structure and energetics of thin films created by the deposition of Al onto Pd (001). The study has been carried out within the semiempirical embedded atom method (EAM), utilizing a Pd–Al potential from the literature and two other alloy potentials generated from elemental potentials. Only one of the potentials reproduces the experimentally observed reconstruction. Problems with the construction and validity of the alloy potentials are highlighted.
SURFACE SENSITIVITY OF VERY LOW ENERGY ELECTRONS
Authors: BARTOŠ I. , SCHATTKE W.
Published: July 2002

The surface sensitivity of electron diffraction and of electron spectroscopies is determined by the imaginary component of the electron self-energy. In crystals, the energy and direction dependence of the electron attenuation and of the escape depth should be taken into account at very low energies.

Strong anisotropy of the electron attenuation has been obtained around 20 eV from peak shapes in VLEED intensity profiles from (111) transition metal surfaces. Extension of the local density approximation in the density functional formalism provides quantitative description of the electron self-energy. The one-step model of angular resolved photoemission incorporating the self-energy predicts a strong energy and angle dependence of the escape depth of low energy photoelectrons emitted from GaAs(110).
Financial Liberalization and Managerial Discretion in the Security Issue Decision: Evidence from an Emerging Economy
Authors: Bhaduri Saumitra N.
Published: July 2002

This paper investigates the Managerial Discretion Hypothesis in the context of the Indian corporate sector. The hypothesis postulates that if the interests of the managers and the other stakeholders of the firm are not perfectly aligned, then the managers tend to issue equity which might be contrary to the latter's interest. We have examined a sample of 216 manufacturing firms, which have opted for external finance during the year 1994–1995. Our findings reveal that for many firms, particularly those with poor investment opportunities, managers issue equity even when they are not expected to do so. This paper, as a policy recommendation, highlights the importance of creating appropriate institutions prior to pursuing financial liberalization in developing countries like India.
STABILITY OF THE SOLUTION SET OF NON-COERCIVE VARIATIONAL INEQUALITIES
Authors: ADLY SAMIR , THÉRA MICHEL , ERNST EMIL
Published: July 2002

In this paper, we study the stability of the solution set of a non-coercive variational inequality with respect to small perturbations of the data involved in the problem. This research is done using well-known tools of convex analysis and the concept of well-positioned convex sets (which is defined and studied).
INFLUENCE OF THE INPLANE BOUNDARY CONDITIONS ON THE VIBRATION FREQUENCIES AND BUCKLING LOAD OF RIBBED PLATES
Authors: SAPOUNTZAKIS EVANGELOS J. , KATSIKADELIS JOHN T.
Published: July 2002

In this paper, the influence of the inplane boundary conditions on the vibration frequencies and the buckling load of plates reinforced with a system of parallel beams is presented. The adopted model for the dynamic analysis of the ribbed plate takes into account the resulting inplane forces and deformations of the plate as well as the axial forces and deformations of the beam, due to combined response of the system. The analysis consists in isolating the beams from the plate by sections parallel to the lower outer surface of the plate. The analysis of the vibration problem of a ribbed plate subjected to inplane forces is based on the capability to establish a flexibility matrix with respect to a set of nodal mass points using the Analog Equation Method (AEM) for the static ribbed plate problem. Moreover, a lumped mass matrix is constructed from the tributary mass areas to the nodal mass points. The buckling load is established using the dynamic criterion. From the obtained results it is shown that both the vibration frequencies and the buckling load may be significantly influenced by the inplane boundary conditions.
ASSESMENT OF TOTAL CA2+ HANDLING FOR EXCITATION-CONTRACTION COUPLING IN BEATING LEFT VENTRICLE
Authors: ARAKI JUNICHI , SHIMIZU JUICHIRO , IRIBE GENTARO , MOHRI SATOSHI , KIYOOKA TAKAHIKO , OSIMA YU , FUJINAKA WASO , DOI YUMIKO , SUGA HIROYUKI
Published: July 2002

We have aimed to assess total Ca 2+ handling in excitation-contraction coupling in a beating left ventricle (LV). Our newly developed integrative analysis method utilizes the internal Ca 2+ recirculation fraction (RF), O2 consumption ( Vo 2) for Ca2+ handling, and O 2 cost of Emax (contractility index) of the LV. We have obtained the O 2 cost of Emax from Vo 2 measured at different contractility levels, and have combined the cost with RF calculated from the beat-constant of the exponential decay component of the postextrasystolic potentiation. Our method calculates the unknown total Ca2+ handling from the RF and the " Ca 2+ handling Vo 2". The calculated total Ca 2+ handling fell between 30 and 110 μmol/kg, depending on contractility and pathological conditions. The present method also enable's reasonable assessment of futile Ca 2+ cycling and of the Ca 2+ reactivity of Emax. Our method seems useful to better understanding of the pathophysiology of total Ca 2+ handling in a beating heart.
MODELS OF FREE COOLING GRANULAR GASES
Authors: MARCONI UMBERTO MARINI BETTOLO , BALDASSARRI ANDREA , PUGLISI ANDREA
Published: July 2002

We consider the free evolution of systems of granular particles whose dynamics is characterized by a collision rule which preserves the total momentum, but dissipates the kinetic energy. Starting from an inelastic version of a minimal model proposed by Ulam for a gas of Maxwell molecules, we introduce a new lattice model aimed at investigating the role of dynamical correlations and the onset of spatial order induced by the inelasticity of the interactions. We study, in one- and two-dimensional cases, the velocity distribution, the decay of the energy, the formation of spatial structures and topological defects. Finally, we relate our findings to other models known in other fields.
A HYBRID APPROACH TO KNOWLEDGE ACQUISITION USING NEURAL PETRI NETS AND DS THEORY
Authors: SIL JAYA , KONAR AMIT
Published: July 2002

Knowledge acquisition from multiple experts and its refinement are important issues in knowledge management of an expert system. The paper presents a novel approach to handling the above problems by combining the synergistic behavior of neural Petri nets and the Dempster–Shafer theory. The Dempster–Shafer theory has been employed here to reduce the scope of uncertainty in the supplied noisy input instances and the inferences generated therefrom by the multiple experts. The noise-free training instances thus obtained are subsequently used to train the neural Petri net model for refining the parameters of its knowledge base. A comparison of the performance of the proposed training algorithm with the classical back-propagation algorithm has also been presented in the paper.
NEURAL LOGIC NETWORK LEARNING USING GENETIC PROGRAMMING
Authors: CHIA HENRY WAI-KIT , TAN CHEW-LIM
Published: July 2002

Neural Logic Networks or Neulonets are hybrids of neural networks and expert systems capable of representing complex human logic in decision making. Each neulonet is composed of rudimentary net rules which themselves depict a wide variety of fundamental human logic rules. An early methodology employed in neulonet learning for pattern classification involved weight adjustments during back-propagation training which ultimately rendered the net rules incomprehensible. A new technique is now developed that allows the neulonet to learn by composing the net rules using genetic programming without the need to impose weight modifications, thereby maintaining the inherent logic of the net rules. Experimental results are presented to illustrate this new and exciting capability in capturing human decision logic from examples. The extraction and analysis of human logic net rules from an evolved neulonet will be discussed. These extracted net rules will be shown to provide an alternate perspective to the greater extent of knowledge that can be expressed and discovered. Comparisons will also be made to demonstrate the added advantage of using net rules, against the use of standard boolean logic of negation, disjunction and conjunction, in the realm of evolutionary computation.
Telos: representing knowledge about information systems
Authors: Mylopoulos John , Borgida Alex , Jarke Matthias , Koubarakis Manolis
Published: July 2002

We describe Telos, a language intended to support the development of information systems. The design principles for the language are based on the premise that information system development is knowledge intensive and that the primary responsibility of any language intended for the task is to be able to formally represent the relevent knowledge. Accordingly, the proposed language is founded on concepts from knowledge representations. Indeed, the language is appropriate for representing knowledge about a variety of worlds related to a particular information system, such as the subject world (application domain), the usage world (user models, environments), the system world (software requirements, design), and the development world (teams, metodologies).

We introduce the features of the language through examples, focusing on those provided for desribing metaconcepts that can then be used to describe knowledge relevant to a particular information system. Telos' fetures include an object-centered framework which supports aggregation, generalization, and classification; a novel treatment of attributes; an explicit representation of time; and facilities for specifying integrity constraints and deductive rules. We review actual applications of the language through further examples, and we sketch a formalization of the language.
A study of time warp rollback mechanisms
Authors: Lin Yi-Bing , Lazowska Edward D.
Published: July 2002

The Time Warp “optimistic” approach is one of the most important parallel simulation protocols. Time Warp synchronizes processes via
rollback
. The original rollback mechanism called
lazy cancellation
has aroused great interest. This paper studies these rollback mechanisms. The general tradeoffs between aggressive and lazy cancellation are discussed, and by a conservitive-optimal simulation is defined for comparitive purposes. Within the framework of aggressive cancellation, we offer some observations and analyze the rollback behavior of tandom systems. The lazy cancellation mechanism iss examined using a metric called the
sensitivity of output message
. Both aggressive and lazy cancellation are shown to work well for a process with a small simulated load intensity. Finally, an analytical model is given to analyze
message preemtion
, an important factor that affects the performance of rollback mechanisms. Results indicate that message preemtion has a significant effect on performance when (1) the processor is highly utilized, (2) the execution times of messages have high varience, and (3) rollbacks occur frequently.
On stability and performance of parallel processing systems
Authors: Bambos Nicholas , Walrand Jean
Published: July 2002

The general problem of parallel (concurrent) processing is investigated from a queuing theoretic point of view.

As a basic simple model, consider infinitely many processors that can work simultaneously, and a stream of arriving jobs, each carrying a processing time requirement. Upon arrival, a job is allocated to a processor and starts being executed, unless it is blocked by another one already in the system. Indeed, any job can be randomly blocked by any preceding one, in the sense that it cannot start being processed before the one that blocks it leaves. After execution, the job leaves the system. The arrival times, the processing times and the blocking structures of the jobs form a stationary and ergodic sequence.

The random precedence constraints capture the essential operational characteristic of parallel processing and allow a unified treatment of concurrent processing systems from such diverse areas as parallel computation, database concurrency control, queuing networks, flexible manufacturing systems. The above basic model includes the G/G/1 and G/G/∞ queuing systems as special extreme cases.

Although there is an infinite number of processors, the precedence constraints induce a queuing phenomenon, which, depending on the loading conditions, can lead to stability or instability of the system.

In this paper, the condition for stability of the system is first precisely specified. The asymptotic behavior, at large times, of the quantities associated with the performance of the system is then studied, and the degree of parallelism, expressed as the asymptotic average number of processors that work concurrently, is computed. Finally, various design and simulation aspects concerning parallel processing systems are considered, and the case of finite number of processors is discussed.

The results proved for the basic model are then extended to cover more complex and realistic parallel processing systems, where each job has a random internal structure of subtasks to be executed according to some internal precedence constriants.
High-speed local area networks and their performance
Authors: Abeysundara Bandula W. , Kamal Ahmed E.
Published: July 2002

At high data transmission rates, the packet transmission time of a local area network (LAN) could become comparable to or less than the medium propagation delay. The performance of many LAN schemes degrades rapidly when the packet transmission time becomes small comparative to the medium propagation delay. This paper introduces LANs and discusses the performance degradation of LANs at high speeds. It surveys recently proposed LAN schemes designed to operate at high data rates, including their performance characteristics desirable in LAN medium access protocols are identified and discussed. The paper serves as a tutorial for readers less familiar with local computer communication networks. It also serves as a survey of the state-of-the-art LANs.
Massively parallel and distributed simulation of a class of discrete event systems
Authors: Vakili Pirooz
Published: July 2002

In this paper we propose a new approach to parallel and distributed simulation of discrete event systems. Most parallel and distributed discrete event simulation algorithms are concerned with the simulation of one “large” discrete event system. In this case the computational intensity is due to the size and complexity of the simulated system. In contrast, we are interested in simulating a “large” number of “medium sized” systems. These are variants of a “nominal system” with different system parameter values or operation policies. The computational intensity in our case is due to the “large” number of simulated variants. Many simulation projects such as factor screening, performance modeling, and optimization require system performance evaluations at many parameter values; and others, we believe, could significantly benefit from them.

There is considerable work in the literature on stochastic coupling of trajectories of parametric families of stochastic processes. Our approach can be viewed as the simulation of the coupled trajectories. We use a single clock mechanism that drives all trajectories simultaneously, hence the approach is called Single Clock Multiple System (SCMS) simulation. The single clock synchronizes all trajectories such that the “same” event occurs at the “same” time at all systems. This synchronization is the basis of our parallel and distributed algorithms.

We focus on a particular implementation of the SCMS simulation using the so-called Standard Clock (SC) technique and also on the massively parallel implementation of the SC algorithms on the SIMD Connection Machine. Orders of magnitude of speedup is possible. Furthermore, the possibility of concurrent performance evaluation and comparison at many system parameter values offers new and significant opportunities for performance optimization.
A little knowledge goes a long way
Authors: Halpern Joseph Y. , Zuck Lenore D.
Published: July 2002

A high-level, knowledge-based approach for deriving a family of protocols for thesequence transmissionproblem is presented. The protocols of Aho et al. [2, 3], the Alternating Bit protocol [5], and Stenning's protocol [44] are all instances of one knowledge-based protocol that is derived. The derivation in this paper leads to transparent and uniform correctness proofs for all these protocols.
Empirical performance evaluation of concurrency and coherency control protocols for database sharing systems
Authors: Rahm Erhard
Published: July 2002

Database Sharing (DB-sharing) refers to a general approach for building a distributed high performance transaction system. The nodes of a DB-sharing system are locally coupled via a high-speed interconnect and share a common database at the disk level. This is also known as a “shared disk” approach. We compare database sharing with the database partitioning (shared nothing) approach and discuss the functional DBMS components that require new and coordinated solutions for DB-sharing. The performance of DB-sharing systems critically depends on the protocols used for concurrency and coherency control. The frequency of communication required for these functions has to be kept as low as possible in order to achieve high transation rates and short response times. A trace-driven simulation system for DB-sharing complexes has been developed that allows a realistic performance comparison of four different concurrency and coherency control protocols. We consider two locking and two optimistic schemes which operate either under central or distributed control. For coherency control, we investigate so-called on-request and broadcast invalidation schemes, and employ buffer-to-buffer communication to exchange modified pages directly between different nodes. The performance impact of random routing versus affinity-based load distribution and different communication costs is also examined. In addition, we analyze potential performance bottlenecks created by hot spot pages.
Query evaluation techniques for large databases
Authors: Graefe Goetz
Published: July 2002

Database management systems will continue to manage large data volumes. Thus, efficient algorithms for accessing and manipulating large sets and sequences will be required to provide acceptable performance. The advent of object-oriented and extensible database systems will not solve this problem. On the contrary, modern data models exacerbate the problem: In order to manipulate large sets of complex objects as efficiently as today's database systems manipulate simple records, query-processing algorithms and software will become more complex, and a solid understanding of algorithm and architectural issues is essential for the designer of database management software.

This survey provides a foundation for the design and implementation of query execution facilities in new database management systems. It describes a wide array of practical query evaluation techniques for both relational and postrelational database systems, including iterative execution of complex query evaluation plans, the duality of sort- and hash-based set-matching algorithms, types of parallel query execution and their implementation, and special operators for emerging database application domains.
Atomic snapshots of shared memory
Authors: Afek Yehuda , Attiya Hagit , Dolev Danny , Gafni Eli , Merritt Michael , Shavit Nir
Published: July 2002

This paper introduces a general formulation of
atomic snapshot memory
, a shared memory partitioned into words written (
updated
) by individual processes, or instantaneously read (
scanned
) in its entirety. This paper presents three wait-free implementations of atomic snapshot memory. The first implementation in this paper uses unbounded (integer) fields in these registers, and is particularly easy to understand. The second implementation uses bounded registers. Its correctness proof follows the ideas of the unbounded implementation. Both constructions implement a single-writer snapshot memory, in which each word may be updated by only one process, from single-writer,
n
-reader registers. The third algorithm implements a multi-writer snapshot memory from atomic
n
-writer,
n
-reader registers, again echoing key ideas from the earlier constructions. All operations require Θ(
n
2
) reads and writes to the component shared registers in the worst case. —
Authors' Abstract
Separating and intersecting spherical polygons
Authors: Chen Lin-Lin , Chou Shuo-Yan , Woo Tony C.
Published: July 2002

We consider the computation of an optimal workpiece orientation allowing the maximal number of surfaces to be machined in a single setup on a three-, four-, or five-axis numerically controlled machine. Assuming the use of a ball-end cutter, we establish the conditions under which a surface is machinable by the cutter aligned in a certain direction, without the cutter's being obstructed by portions of the same surface. The set of such directions is represented on the sphere as a convex region, called the
visibility map
of the surface. By using the Gaussian maps and the visibility maps of the surfaces on a component, we can formulate the optimal workpiece orientation problems as geometric problems on the sphere. These and related geometric problems include finding a densest hemisphere that contains the largest subset of a given set of spherical polygons, determining a great circle that separates a given set of spherical polygons, computing a great circle that bisects a given set of spherical polygons, and finding a great circle that intersects the largest or the smallest subset of a set of spherical polygons. We show how all possible ways of intersecting a set of
n
spherical polygons with
v
total number of vertices by a great circle can be computed in
O
(
vn
log
n
) time and represented as a spherical partition. By making use of this representation, we present efficient algorithms for solving the five geometric problems on the sphere.
The detection of dangling references in C++ programs
Authors: Eyre-Todd Richard A.
Published: July 2002

Thesmart pointeris a programming technique for the C++ language that extends the functionality of the simple pointer. Smart pointers have previously been used to support persistence, distributed objects, reference counting, and garbage collection. This article will show how smart pointers can provide an inexpensive method for detecting dangling pointers to dynamic objects that can be added to any standard C++ implementation.
On the power of bounded concurrency I
Authors: Drusinsky Doron , Harel David
Published: July 2002

We investigate the descriptive succinctness of three fundamental notions for modeling concurrency: nondeterminism and pure parallelism, the two facets of alternation, and
bounded cooperative concurrency
, whereby a system configuration consists of a bounded number of cooperating states. Our results are couched in the general framework of finite-state automata, but hold for appropriate versions of most concurrent models of computation, such as Petri nets, statecharts or finite-state versions of concurrent programming languages. We exhibit exhaustive sets of upper and lower bounds on the relative succinctness of these features over Σ
*
and Σ
ω
, establishing that:

For example, we prove exponential upper and lower bounds on the simulation of deterministic concurrent automata by AFAs, and triple-exponential bounds on the simulation of alternating concurrent automata by DFAs.
A survey of PRAM simulation techniques
Authors: Harris Tim J.
Published: July 2002

The Parallel Random Access Machine (PRAM) is an abstract model of parallel computation which allows researchers to focus on the essential characteristics of a parallel architecture and ignore other details. The PRAM has long been acknowledged to be a useful tool for the study of parallel computing, but unfortunately it is not physically implementable in hardware. In order to take advantage of the broad base of algorithms and results regarding this high-level abstraction one needs general methods for allowing the execution of PRAM algorithms on more realistic machines. In the following we survey these methods, which we refer to as PRAM simulation techniques. The general issues of memory management and routing are discussed, and both randomized and deterministic solutions are considered. We show that good theoretical solutions to many of the subproblems in PRAM simulation have been developed, though questions still exist as to their practical utility. This article should allow those performing research in this field to become well acquainted with the current state of the art, while allowing the novice to get an intuitive feeling for the fundamental questions being considered. The introduction should provide a concise tutorial for those unfamiliar with the problem of PRAM simulation.
Shortest paths in the plane with polygonal obstacles
Authors: Storer James A. , Reif John H.
Published: July 2002

We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required

Ω(n
2

log
n)
time and
O
(n
2
) space, where
n
denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in
O
(
n
log
n)
time), we present an
O(kn)
time algorithm, where
k
denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only
O(n)
space and, given a source point
s
, produces an
O(n)
size data structure such that the distance between
s
and any other point
x
in the plane (
x
) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in
O
(1) time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk).
Experiments with Oval
Authors: Malone Thomas W. , Lai Kum-Yew , Fry Christopher
Published: July 2002

This article describes a series of tests of the generality of a “radically tailorable” tool for cooperative work. Users of this system can create applications by combining and modifying four kinds of building blocks:
objects, views, agents,
and
links
. We found that user-level tailoring of these primitives can provide most of the functionality found in well-known cooperative work systems such as gIBIS, Coordinator, Lotus Notes, and Information Lens. These primitives, therefore, appear to provide an elementary “tailoring language” out of which a wide variety of integrated information management and collaboration applications can be constructed by end users.
Sixteen questions about software reuse
Authors: Frakes William B. , Fox Christopher J.
Published: July 2002

Software reuse is the use of existing software knowledge or artifacts to build new software artifacts. Reuse is sometimes confused with porting. The two are distinguished as follows: Reuse is using an asset in different systems; porting is moving a system across environments or platforms. For example, in Figure 1 a component in System A is shown used again in System B; this is an example of reuse. System A, developed for Environment 1, is shown moved into Environment 2; this is an example of porting.
ATM concepts, architectures, and protocols
Authors: Vetter Ronald J.
Published: July 2002

Asynchronous transfer mode (ATM) is often described as the future computer networking paradigm that will bring high-speed communications to the desktop. What is ATM? How is it different from today's networking technologies? This article is intended to acquaint readers with this emerging technology and describe some of the concepts embodied within it. In order to understand why ATM was created and how it works, we first need to review a bit of computer networking history.
Eigenvalues and expansion of regular graphs
Authors: Kahale Nabil
Published: July 2002

The spectral method is the best currently known technique to prove lower bounds on expansion. Ramanujan graphs, which have asymptotically optimal second eigenvalue, are the best-known explicit expanders. The spectral method yielded a lower bound ofk/4 on the expansion of linear-sized subsets ofk-regular Ramanujan graphs. We improve the lower bound on the expansion of Ramanujan graphs to approximatelyk/2. Moreover, we construct a family ofk-regular graphs with asymptotically optimal second eigenvalue and linear expansion equal tok/2. This shows thatk/2 is the best bound one can obtain using the second eigenvalue method. We also show an upper bound of roughly 1 + √k - 1 on the average degree of linear-sized induced subgraphs of Ramanujan graphs. This compares positively with the classical bound 2√k - 1. As a byproduct, we obtain improved results on random walks on expanders and construct selection networks (respectively, extrovert graphs) of smaller size (respectively, degree) than was previously known.
Graph models for reachability analysis of concurrent programs
Authors: Pezzè Mauro , Taylor Richard N. , Young Michal
Published: July 2002

The problem of analyzing concurrent systems has been investigated by many researchers, and several solutions have been proposed. Among the proposed techniques, reachability analysis—systematic enumeration of reachable states in a finite-state model—is attractive because it is conceptually simple and relatively straightforward to automate and can be used in conjunction with model-checking procedures to check for application-specific as well as general properties. This article shows that the nature of the translation from source code to a modeling formalism is of greater practical importance than the underlying formalism. Features identified as pragmatically important are the representation of internal choice, selection of a dynamic or static matching rule, and the ease of applying reductions. Since combinatorial explosion is the primary impediment to application of reachability analysis, a particular concern in choosing a model is facilitating divide-and-conquer analysis of large programs. Recently, much interest in finite-state verification systems has centered on algebraic theories of concurrency. Algebraic structure can be used to decompose reachability analysis based on a flowgraph model. The semantic equivalence of graph and Petri net-based models suggests that one ought to be able to apply a similar strategy for decomposing Petri nets. We describe how category-theoretic treatments of Petri nets provide a basis for decomposition of Petri net reachability analysis.
The S/Net's Linda kernel
Authors: Carriero Nicholas , Gelernter David
Published: July 2002

Linda is a parallel programming language that differs from other parallel languages in its simplicity and in its support for distributed data structures. The S/Net is a multicomputer, designed and built at AT&T Bell Laboratories, that is based on a fast, word-parallel bus interconnect. We describe the Linda-supporting communication kernel we have implemented on the S/Net. The implementation suggests that Linda's unusual shared-memory-like communication primitives can be made to run well in the absence of physically shared memory; the simplicity of the language and of our implementation's logical structure suggest that similar Linda implementations might readily be constructed on related architectures. We outline the language, and programming methodologies based on distributed data structures; we then describe the implementation, and the performance both of the Linda primitives themselves and of a simple S/Net-Linda matrix-multiplication program designed to exercise them.
Time-segmentation parallel simulation of networks of queues with loss or communication blocking
Authors: Andradóttir Sigrún , Ott Teunis J.
Published: July 2002

This article is concerned with the efficient simulation of communication systems on parallel processors. In most of the article, we assume that the communication system under study can be modeled as a system of finite exponential queues with a general topology (in particular, the system need not be acyclic) and with either loss or communication blocking. We also assume that to estimate the performance measures of interest, it is necessary to generate long sample paths of the system. This is the case in both steady-state simulations and in long transient simulations. The approach involves applying each processor to simulate the entire system for a part of the time horizon of interest. We present theory guaranteeing the validity of the proposed approach, and numerical results proving the viability of the approach. The proof of the validity of the approach uses the fact that the queueing systems considered are continuous time Markov chains. An essential part of the argument is a proof that sample paths starting from different initial states eventually will couple (i.e., become identical), and a simple method for recognizing the time when a sample path has become independent of the original starting state (i.e., when all sample paths have coupled, regardless of the initial state). Finally, we discuss how our approach can be used for parallel trace-driven simulations of certain nonMarkovian systems, and state the implications of this research for the initialization bias problem in steady-state simulation.
Adaptive memory management and optimism control in time warp
Authors: Das Samir R. , Fujimoto Richard M.
Published: July 2002

It is widely believed that the Time Warp protocol for parallel discrete event simulation is prone to two potential problems: an excessive amount of wasted, rolled back computation resulting from “rollback thrashing” behaviors, and inefficient use of memory, leading to poor performance of virtual memory and/or multiprocessor cache systems. An adaptive mechanism is proposed based on the Cancelback memory management protocol for shared-memory multiprocessors that dynamically controls the amount of memory used in the simulation in order to maximize performance. The proposed mechanism is adaptive in the sense that it monitors the execution of the Time Warp program, and using simple models,
automatically
adjusts the amount of memory used to reduce Time Warp overheads (fossil collection, Cancelback, the amount of rolled back computation, etc.) to a manageable level. We describe an implementation of this mechanism on a shared memory, Kendall Square Research KSR-1, multiprocessor and demonstrate its effectiveness in automatically maximizing performance while minimizing memory utilzation, for several synthetic and benchmark discrete event simulation applications. We also demonstrate the adaptive ability of the mechanism by showing that it “tracks” the time-varying nature of a communication network simulation.
Terrain database interoperability issues in training with distributed interactive simulation
Authors: Schiavone Guy A. , Sureshchandran S. , Hardis Kenneth C.
Published: July 2002

In Distributed Interactive Simulation (DIS), each participating node is responsible for maintaining its own model of the synthetic environment. Problems may arise if significant inconsistencies are allowed to exist between these separate world views, resulting in unrealistic simulation results or negative training, and a corresponding degradation of interoperability in a DIS simulation exercise. In the DIS community, this is known as the simulator terrain database (TDB) correlation problem. This is part of the larger synthetic environment correlation problem in DIS, which includes atmosphere, ocean, space, and a wide variety of dynamic effects, behaviors and models. In this article, we investigate the terrain database correlation problem and the resultant effects on interoperability in DIS systems. The fundamental elements of terrain databases designed for real-time distributed simulation are introduced. A generic data pipeline for terrain database generation systems is developed for the purpose of illustrating causes of the correlation problem and issues of terrain database fidelity. Implications of the problem are discussed, and testing methodologies are recommended for its mitigation. Several statistical methods have been developed to analyze consistency between various elements of the synthetic environment across DIS platforms. Correlation metrics have been formulated for terrain elevations and features. Comparisons and consistency of final rendered images have been addressed. Finally, a suite of software tools that has been developed for interoperability investigations and visual comparison of terrain databases is presented.
Proximal nodes
Authors: Navarro Gonzalo , Baeza-Yates Ricardo
Published: July 2002

A model to query document databases by both their content and structure is presented. The goal is to obtain a query language that is expressive in practice while being efficiently implementable, features not present at the same time in previous work. The key ideas of the model are a set-oriented query language based on operations on nearby structure elements of one or more hierarchies, together with content and structural indexing and bottom-up evaluation. The model is evaluated in regard to expressiveness and efficiency, showing that it provides a good trade-off between both goals. Finally, it is shown how to include in the model other media different from text.
Random variate generation for multivariate unimodal densities
Authors: Devroye Luc
Published: July 2002

A probability density on a finite-dimensional Euclidean space is orthounimodal with a given mode if within each orthant (quadrant) defined by the mode, the density is a monotone function of each of its arguments individually. Up to a linear transformation, most of the commonly used random vectors possess orthounimodal densities. To generate a random vector from a given orthounimodal density, several general-purpose algorithms are presented; and an experimental performance evaluation illustrates the potential efficiency increases that can be achieved by these algorithms versus naive rejection.
Controlling access in multiuser interfaces
Authors: Dewan Prasun , Shen Honghai
Published: July 2002

Traditionally, access control has been studied in the areas of operating systems and database management systems. With the advent of multiuser interfaces, there is a need to provide access control in the user interface. We have developed a general framework for supporting access control in multiuser interfaces. It is based on the classical notion of an access matrix, a generalized editing-based model of user-application interaction, and a flexible model of user-user coupling. It has been designed to support flexible control of all significant shared operations, high-level specification of access control policies, and automatic and efficcent implementation of access control in a multiuser interface. It supports several new kinds of protected objects including sessions, windows, and hierarchical active variables; a large set of rights including not only the traditional semantic rights but also interaction and coupling rights; a set of inference rules for deriving default permissions; and a programming interface for implementing access control in multiuser interfaces. We have implemented the framework as part of a system called Suite. This article describes and motivates the framework using the concrete example of Suite, identifies some of the difficult issues we faced in its design, describes our preliminary experience with it, and suggests directions for future work.
Algorithm 771
Authors: Brankin R. W. , Gladwell I.
Published: July 2002

The present Fortran 90 software for the initial-value problem in ordinary differential equations including the interfaces and how Fortran 90 language features afford the opportunity both to address different types and structures of variables and to provide additional functionality. A novel feature of this software is the availability of Unix scripts which enable presentation of the software for multiple problem types.