bluuebunny/crossref_metadata_2025 huggingface dataset:
THE SEMICLASSICAL RELATIVISTIC DARWIN POTENTIAL FOR SPINNING PARTICLES IN THE REST-FRAME INSTANT FORM: TWO-BODY BOUND STATES WITH SPIN 1/2 CONSTITUENTS
Authors: ALBA DAVID , CRATER HORACE , LUSANNA LUCA
Published: July 2002

We extend previous results on the extraction of the Darwin potential to all orders in c-2 from the radiation gauge Lienard–Wiechert solution for the system of N positive-energy scalar particles plus the electromagnetic field in the Wigner-covariant rest-frame instant form of dynamics to the case of N positive-energy spinning particles. This is done in the semiclassical approximation of using Grassmann-valued electric charges for regularizing the Coulomb self-energies and extracting the unique semiclassical action-at-a-distance interaction hidden in any Green function used for the Lienard–Wiechert solution. By describing semiclassically also the spin of the particles with Grassmann variables, by means of a semiclassical Foldy–Wouthuysen transformation applied the the Dirac-like constraints of the manifestly Lorentz covariant spinning particles, we determine the coupling of positive-energy spinning particles to the electric field in the semiclassical approximation. Then we follow the same procedure developed for scalar particles and, in the sector where there is no in-radiation, we determine the effective semiclassical interparticle potential. Besides the relativistic Darwin term there are spin-orbit and spin-spin terms in the potential. Quantization of the lowest order (in c-2) part of the closed form of the effective Hamiltonian in the case N = 2 reproduces exactly the standard result of the reduction of the Bethe–Salpeter equation for the bound states of two spin 1/2 constituents of arbitrary mass (hydrogen atom, positronium, muonium).
CANCELING QUADRATIC DIVERGENCES IN A CLASS OF TWO-HIGGS-DOUBLET MODELS
Authors: MA ERNEST
Published: July 2002

The Newton–Wu conditions for the cancellation of quadratic divergences in a class of two-Higgs-doublet models are analyzed as to how they may be satisfied with a typical extension of the Standard Model of particle interactions.
DEFORMATION QUANTIZATION: QUANTUM MECHANICS LIVES AND WORKS IN PHASE-SPACE
Authors: ZACHOS COSMAS
Published: July 2002

Wigner's quasi-probability distribution function in phase-space is a special (Weyl) representation of the density matrix. It has been useful in describing quantum transport in quantum optics; nuclear physics; decoherence (e.g. quantum computing); quantum chaos; "Welcher Weg" discussions; semiclassical limits. It is also of importance in signal processing. Nevertheless, a remarkable aspect of its internal logic, pioneered by Moyal, has only emerged in the last quarter-century: It furnishes a third, alternative, formulation of Quantum Mechanics, independent of the conventional Hilbert Space, or Path Integral formulations. In this logically complete and self-standing formulation, one need not choose sides — coordinate or momentum space. It works in full phase-space, accommodating the uncertainty principle. This is an introductory overview of the formulation with simple illustrations.
THEORETICAL AND EXPERIMENTAL STATUS OF MAGNETIC MONOPOLES
Authors: MILTON KIMBALL A. , KALBFLEISCH GEORGE R. , LUO WEI , GAMBERG LEONARD
Published: July 2002

The Tevatron has inspired new interest in the subject of magnetic monopoles. First there was the 1998 D0 limit on the virtual production of monopoles, based on the theory of Ginzburg and collaborators. In 2000 the first results from an experiment (Fermilab E882) searching for real magnetically charged particles bound to elements from the CDF and D0 detectors were reported. This also required new developments in theory. The status of the experimental limits on monopole masses will be discussed, as well as the limitation of the theory of magnetic charge at present.
ANISOTROPY OF THE BOUND MAGNETIC POLARON STATES AND COLOSSAL HOPPIG MAGNETORESISTANCE IN DILUTE MAGNETIC SEMICONDUCTORS
Authors: Foygel M. , Petukhov A. G.
Published: July 2002

A theory of positive and negative colossal magnetoresistance (CMR) in dilute magnetic semiconductors (DMS) is presented. The phenomenon is described in the framework of bound magnetic polaron (BMP) hopping, driven by thermodynamic fluctuations of the local magnetization. The latter is caused by fluctuating spins of the magnetic atoms which strongly interact with the spin of a trapped electron or a hole within the localization volume. The authors' previous approach to the BMP hopping problem1,2, based on the Ginzburg-Landau effective Hamiltonian method, has been generalized in order to take into account the anisotropy of the BMP states. This effect can be attributed to the anisotropy of the local exchange field and/or to the field-induced anisotropy of the magnetic susceptibility. In DMS the latter is shown to affect the position and the shape of the maximum in the magnetic-field dependence of CMR.
FORMATION OF C54 TiSi2 ON Si(100) USING Ti/Mo AND Mo/Ti BILAYERS
Authors: ZHANG ZHIBIN , ZHANG SHILI , ZHU DEZHANG , XU HONGJIE , CHEN YI
Published: July 2002

The effect of Mo on the formation of C54 TiSi 2 on Si (100) substrates is studied using cross-section transmission electron microscopy. For a Ti/Mo bilayer on Si, the interfacial Mo film reacts with Ti and Si to form C40 (Mo,Ti)Si 2 at 550°C. Crystal grains of metastable C40 TiSi 2 and equilibrium C54 TiSi 2 are found in the region near the interfacial (Mo,Ti)Si 2 layer due to the template phenomenon. Increasing the temperature to 600°C leads to the growth of C54 TiSi 2 throughout the film. No C49 grains can be detected. The findings confirm that the usual sequence for the formation of C54 TiSi 2, i.e. the C49 TiSi 2 forms first followed by a phase transition to the C54 TiSi 2, is altered by the interposed Mo layer. For a Mo/Ti bilayer on Si , the surface Mo layer is found to be present sequentially in (Mo,Ti) 5 Si 3 at 550°C, C49 (Mo,Ti)Si 2 at 600°C and C54 (Mo,Ti)Si 2 at 650°C. The bulk Ti beneath forms the C54 TiSi 2 following the usual route through the C49-C54 phase transition. However, this transition is now enhanced, in comparison with the C54 TiSi 2 formation with pure Ti , by the C54 (Mo,Ti)Si 2 atop that plays the role as a template precisely as the interfacial C40 (Mo,Ti)Si 2.
DILUTE BOSE-EINSTEIN CONDENSATE IN A TRAP: CHARACTERISTIC LENGTHS AND CRITICAL VELOCITIES
Authors: FETTER ALEXANDER L.
Published: July 2002

The Bogoliubov approximation and the Gross-Pitaevskii equation characterize the effect of repulsive interactions on a dilute ideal Bose-Einstein gas in a spherical harmonic trap. For large N, the interactions expand the condensate relative to an ideal Bose gas; both the speed of sound and critical angular velocity Ωc1 for creation of a quantized vortex depend crucially on the interparticle repulsion through the coherence length ξ.
SECOND LAW OF THERMODYNAMICS AND ARITHMETIC-MEAN–GEOMETRIC-MEAN INEQUALITY
Authors: WANG LIQIU
Published: July 2002

The application of the second law of thermodynamics to a typical irreversible process of a thermally isolated system shows that the Arithmetic-mean–geometric-mean (AM–GM) inequality, a powerful mathematical inequality, follows logically from the second law of thermodynamics, a powerful physical law.
PLASMA SOURCE ION IMPLANTATION INTO INSULATORS
Authors: FRANKLYN C. B. , NOTHNAGEL G.
Published: July 2002

Considerable development work has taken place in the novel technique of plasma source ion implantation (PSII) for the purpose improving the tribological properties of metal surfaces. Original studies involved using nitrogen plasmas to implant nitrogen ions into irregular shaped surfaces. More recently heavy ions have also been implanted. The advantages of the process over conventional ion implantation techniques are numerous, however one distinct disadvantage was the fact that the target had to be conductive, since it acted as the cathode of the system. We report here on a technique to overcome this problem, especially when implanting heavy ions into an insulator material of small dimensions (1-3 mm across) using the PSII system. Also reported are IBA techniques employed to characterize the implantation profile.
THEORY OF TURBULENT HEAT FLUX
Authors: DEKKER H.
Published: July 2002

A first, nontrivial result from a novel systematic theory of fully-developed 3D hydrodynamic turbulence, viz. using dynamical response functions for turbulent shear flow, the thermal flux spectrum on the basis of the inertial range energy spectrum.
MIXED-MODE CHAOTIC CIRCUIT AND ITS APPLICATION TO CHAOTIC COMMUNICATION FOR TRANSMISSION OF ANALOG SIGNALS
Authors: KILIÇ RECAI , ALÇI MUSTAFA
Published: July 2002

We present a mixed-mode chaotic circuit which has both autonomous and nonautonomous chaotic circuit dynamics and we show how this mixed-mode chaotic circuit can be utilized in a chaotic communication system for transmitting analog signals. The investigation of static and dynamic analyses of the proposed circuit has been carried out and its chaotic behavior was verified by PSpice simulation experiments. For the transmission of analog signals via mixed-mode chaotic circuit, a well-known chaotic communication system introduced by Itoh et al. was chosen.
RESONANCE STRUCTURE IN A WEAKLY DETUNED LASER WITH INJECTED SIGNAL
Authors: MAYOL CATALINA , NATIELLO MARIO A. , ZIMMERMANN MARTÍN G.
Published: July 2002

We describe the qualitative dynamics and bifurcation set for a laser with injected signal for small cavity detunings. The main organizing center is the Hopf-saddle-node bifurcation from where a secondary Hopf bifurcation of a periodic orbit originates. We show that the laser's stable cw solution existing for low injections, also suffers a secondary Hopf bifurcation. The resonance structure of both tori interact, and homoclinic orbits to the "off" state are found inside each Arnold tongue. The accumulation of all the above resonances towards the Hopf-saddle-node singularity points to the occurrence of a highly degenerate global bifurcation at the codimension-2 point.
TRAVEL INSTABILITIES IN LATERAL HEATING
Authors: PELACHO M. A. , GARCIMARTÍN A. , BURGUETE J.
Published: July 2002

We study the convective motion forced by lateral heating on a liquid layer. The movement is caused by two forces: buoyancy and thermocapillarity on the free surface, which is open to the air. As soon as a temperature gradient is imposed along the liquid layer, the fluid begins to move. When a certain threshold of the temperature difference is attained, this flow destabilizes and oscillations appear. We have performed an experiment to characterize the thermocapillary waves in a rectangular container whose dimensions can be continuously changed. This way, we are able to investigate how boundaries affect the threshold for the instability, as well as their consequences on other features of the waves.
ON FEEDBACK ANTICONTROL OF DISCRETE CHAOS
Authors: WANG XIAO FAN , CHEN GUANRONG
Published: July 2002

In this Letter, we prove that the algorithm of Chen and Lai [1996, 1997, 1998] for the anticontrol of chaos leads to chaos not only in the sense of Devaney but also in the sense of Li and Yorke, for both linear and nonlinear autonomous systems of any dimensionalities.
CHAOS IN CLOSED ISOTROPIC COSMOLOGICAL MODELS WITH STEEP SCALAR FIELD POTENTIAL
Authors: TOPORENSKY A. V.
Published: July 2002

The dynamics of closed scalar field FRW cosmological models is studied for several types of exponentially and more than exponentially steep potentials. The parameters of scalar field potentials which allow a chaotic behavior are found from numerical investigations. It is argued that analytical studies of equation of motion at the Euclidean boundary can provide an important information about the properties of chaotic dynamics. Several types of transition from chaotic to regular dynamics are described.
A THEORETICAL FRAMEWORK FOR POSSIBILISTIC INDEPENDENCE IN A WEAKLY ORDERED SETTING
Authors: AMOR N. BEN , MELLOULI K. , BENFERHAT S. , DUBOIS D. , PRADE H.
Published: July 2002

The notion of independence is central in many information processing areas, such as multiple criteria decision making, databases, or uncertain reasoning. This is especially true in the later case, where the success of Bayesian networks is basically due to the graphical representation of independence they provide. This paper first studies qualitative independence relations when uncertainty is encoded by a complete pre-order between states of the world. While a lot of work has focused on the formulation of suitable definitions of independence in uncertainty theories our interest in this paper is rather to formulate a general definition of independence based on purely ordinal considerations, and that applies to all weakly ordered settings. The second part of the paper investigates the impact of the embedding of qualitative independence relations into the scale-based possibility theory. The absolute scale used in this setting enforces the commensurateness between local pre-orders (since they share the same scale). This leads to an easy decomposability property of the joint distributions into more elementary relations on the basis of the independence relations. Lastly we provide a comparative study between already known definitions of possibilistic independence and the ones proposed here.
THE INDISCERNIBLE TOPOLOGY: A MOCK ZARISKI TOPOLOGY
Authors: JUNKER MARKUS , LASCAR DANIEL
Published: July 2002

We associate with every first order structure [Formula: see text] a family of invariant, locally Noetherian topologies (one topology on each Mn). The structure is almost determined by the topologies, and properties of the structure are reflected by topological properties. We study these topologies in particular for stable structures. In nice cases, we get a behaviour similar to the Zariski topology in algebraically closed fields.
A STACKELBERG GAME OF INNOVATION DIFFUSION: PRICING, ADVERTISING AND SUBSIDY STRATEGIES
Authors: DE CESARE LUIGI , DI LIDDO ANDREA
Published: July 2002

We consider a firm that wishes to maximise the profits coming from the sale of a new product or technology by determining an optimal price and advertising strategy. A public authority wishes to accelerate and stimulate the adoption of the new product by using a budget to give price subsidies directly to the consumers. The problem is set up as a Stackelberg differential game.
THE EXPONENTIAL BEHAVIOUR OF THE GREEN FUNCTION IN A DIHEDRAL ANGLE
Authors: GARRONI M. G. , SOLONNIKOV V. A. , VIVALDI M. A.
Published: July 2002

We study the behaviour of the Green function of the heat problem in a dihedral angle with oblique (or Neumann) conditions on the faces.

The uniform estimates obtained for the Green function and its derivatives show, in particular, the exponential decay at infinity, as in the parabolic problems in regular domains.
REINFORCEMENT LEARNING IN MARKOVIAN EVOLUTIONARY GAMES
Authors: BORKAR V. S.
Published: July 2002

A population of agents plays a stochastic dynamic game wherein there is an underlying state process with a Markovian dynamics that also affects their costs. A learning mechanism is proposed which takes into account intertemporal effects and incorporates an explicit process of expectation formation. The agents use this scheme to update their mixed strategies incrementally. The asymptotic behavior of this scheme is captured by an associated ordinary differential equation. Both the formulation and the analysis of the scheme draw upon the theory of reinforcement learning in artificial intelligence.
An improved parallel thinning algorithm
Authors: Holt Christopher M. , Stewart Alan , Clint Maurice , Perrott Ronald H.
Published: July 2002

An iterative thinning algorithm reduces a two-dimensional pattern of strokes to its skeleton by removing layers of edge elements until each stroke has unit thickness. A parallel solution requires the independent calculation of new values for each iteration, using a window of nearest neighbors for each element. The traditional need for at least two subiterations can be avoided by modifying the window to permit the availability of intermediate calculations. Timings on an ICL DAP (an array processor) indicate an improvement of over 40 percent. Additional refinements are suggested to reduce noise in the final skeleton.
The parallel complexity of simple logic programs
Authors: Afrati Foto , Papadimitriou Christos H.
Published: July 2002

We consider logic programs with a single recursive rules, whose right-hand side consists of binary relations forming a chain. We give a complete characterization of all programs of this form that are computable in NC (assuming that
P
≠ NC). Our proof uses ideas from automata and language theory, and the combinatorics of strings.
A nested-graph model for the representation and manipulation of complex objects
Authors: Poulovassilis Alexandra , Levene Mark
Published: July 2002

Three recent trends in database research are object-oriented and deductive databases and graph-based user interfaces. We draw these trends together in a data model we call the Hypernode Model. The single data structure of this model is the
hypernode
, a graph whose nodes can themselves be graphs. Hypernodes are typed, and types, too, are nested graphs. We give the theoretical foundations of hypernodes and types, and we show that type checking is tractable. We show also how conventional type-forming operators can be simulated by our graph types, including cyclic types. The Hypernode Model comes equipped with a rule-based query language called Hyperlog, which is complete with respect to computation and update. We define the operational semantics of Hyperlog and show that the evaluation can be performed efficiently. We discuss also the use of Hyperlog for supporting database browsing, an essential feature of Hypertext databases. We compare our work with other graph-based data models—unlike previous graph-based models, the Hypernode Model provides inherent support for data abstraction via its nesting of graphs. Finally, we briefly discuss the implementation of a DBMS based on the Hypernode Model.
Robust sharing of secrets when the dealer is honest or cheating
Authors: Rabin Tal
Published: July 2002

The problem of Verifiable Secret Sharing (VSS) is the following: A dealer, who may be honest or cheating, can share a secret
s
, among
n
≥ 2
t
+ 1 players, where
t
players at most are cheaters. The sharing process will cause the dealer to commit himself to a secret
s
. If the dealer is honest, then, during the sharing process, the set of dishonest players will have no information about
s
. When the secret is reconstructed, at a later time, all honest players will reconstruct
s
. The solution that is given is a constant round protocol, with polynomial time local computations and polynomial message size. The protocol assumes private communication lines between every two participants, and a broadcast channel. The protocol achieves the desired properties with an exponentially small probability of error.

A new tool, called
Information Checking
, which provides authentication and is not based on any unproven assumptions, is introduced, and may have wide application elsewhere.

For the case in which it is known that the dealer is honest, a simple constant round protocol is proposed, without assuming broadcast.

A weak version of secret sharing is defined: Weak Secret Sharing (WSS). WSS has the same properties as VSS for the sharing process. But, during reconstruction, if the dealer is dishonest, then he might obstruct the reconstruction of
s
. A protocol for WSS is also introduced. This protocol has an exponentially small probability of error. WSS is an essential building block for VSS. For certain applications, the much simpler WSS protocol suffice.

All protocols introduced in this paper are secure in the Information Theoretic sense.
A decomposition of multidimensional point sets with applications to
k
-nearest-neighbors and
n
-body potential fields
Authors: Callahan Paul B. , Kosaraju S. Rao
Published: July 2002

We define the notion of a
well-separated pair decomposition
of points in
d
-dimensional space. We then develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the resulting decomposition to the efficient computation of
k
-nearest neighbors and
n
-body potential fields.
Efficient Monte-Carlo simulation of a product-form model for a cellular system with dynamic resource sharing
Authors: Fleming Philip J. , Schaeffer Dennis , Simon Burton
Published: July 2002

There are many ways for users to share the radio spectrum allocated to a cell in a cellular phone system. We analyze a commonly proposed scheme wh ere the cell is divided into
s
sectors. Each sector has exclusive access to a certain number of channels. The remaining channels reside in a “common pool” and are shared among the sectors. The smallest unit of bandwidth that can be borrowed from the common pool is a “carrier,” which consists of
c
channels. When viewed as a multidimensional birth-death process, the steady-state distribution of the number of active channels in each sector has a “product form,” but because the state space is large and has a nonlinear boundary, direct calculation of quantities of interest is usually impractical. Ross and Wang have developed a Monte-Carlo technique that applies to our problem. We significantly improve the efficiency of their technique when applied to our problem by including certain (nonlinear) control variates. The kinds of control variates we use can be applied to other loss systems as well. We also explore the effect of importance sampling for our system. In many cases the variance reduction achieved from the combination of importance sampling and control variates is far greater than from either method alone. For systems with blocking probabilities in the range 0.001 to 0.1, the variance of the system-blocking probability estimator can be reduced by several orders of magnitude.
On the existence of equilibria in noncooperative optimal flow control
Authors: Korilis Yannis A. , Lazar Aurel A.
Published: July 2002

The existence of Nash equilibria in noncooperative flow control in a general product-form network shared by
K
users is investigated. The performance objective of each user is to maximize its average throughput subject to an upper bound on its average time-delay. Previous attempts to study existence of equilibria for this flow control model were not successful, partly because the time-delay constraints couple the strategy spaces of the individual users in a way that does not allow the application of standard equilibrium existence theorems from the game theory literature. To overcome this difficulty, a more general approach to study the existence of Nash equilibria for decentralized control schemes is introduced. This approach is based on directly proving the existence of a fixed point of the best reply correspondence of the underlying game. For the investigated flow control model, the best reply correspondence is shown to be a function, implicitly defined by means of
K
interdependent linear programs. Employing an appropriate definition for continuity of the set of optimal solutions of parameterized linear programs, it is shown that, under appropriate conditions, the best reply function is continuous. Brouwer's theorem implies, then, that the best reply function has a fixed point.
On the semantics of “now” in databases
Authors: Clifford James , Dyreson Curtis , Isakowitz Tomás , Jensen Christian S. , Snodgrass Richard Thomas
Published: July 2002

Although “
now
” is expressed in SQL and CURRENT_TIMESTAMP within queries, this value cannot be stored in the database. How ever, this notion of an ever-increasing current-time value has been reflected in some temporal data models by inclusion of database-resident variables, such as “
now
” “
until-changed,
” “**,” “@,” and “-”. Time variables are very desirable, but their used also leads to a new type of database, consisting of tuples with variables, termed a
variable database.
Scale-sensitive dimensions, uniform convergence, and learnability
Authors: Alon Noga , Ben-David Shai , Cesa-Bianchi Nicolò , Haussler David
Published: July 2002

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or “agnostic”) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.
Exact analysis of Dodgson elections
Authors: Hemaspaandra Edith , Hemaspaandra Lane A. , Rothe Jörg
Published: July 2002

In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner—a candidate who beats all other candidates in pairwise majority-rule elections. Bartholdi, Tovey, and Trick provided a lower bound—NP-hardness—on the computational complexity of determining the election winner in Carroll's system. We provide a stronger lower bound and an upper bound that matches our lower bound. In particular, determining the winner in Carroll's system is complete for parallel access to NP, that is, it is complete for Theta_
2

p

for which it becomes the most natural complete problem known. It follows that determining the winner in
Carroll's elections is not NP-complete unless the polynomial hierarchy collapses.
Deductive database languages
Authors: Liu Mengchi
Published: July 2002

Deductive databases result from the integration of relational database and logic programming techniques. However, significant problems remain inherent in this simple synthesis from the language point of view. In this paper, we discuss these problems from four different aspects: complex values, object orientation, higher-orderness, and updates. In each case, we examine four typical languages that address the corresponding issues.
Comparison of access methods for time-evolving data
Authors: Salzberg Betty , Tsotras Vassilis J.
Published: July 2002

This paper compares different indexing techniques proposed for supporting efficient access to temporal data. The comparison is based on a collection of important performance criteria, including the space consumed, update processing, and query time for representative queries. The comparison is based on worst-case analysis, hence no assumptions on data distribution or query frequencies are made. When a number of methods have the same asymptotic worst-case behavior, features in the methods that affect average case behavior are discussed. Additional criteria examined are the pagination of an index, the ability to cluster related data together, and the ability to efficiently separate old from current data (so that larger archival storage media such as write-once optical disks can be used). The purpose of the paper is to identify the difficult problems in accessing temporal data and describe how the different methods aim to solve them. A general lower bound for answering basic temporal queries is also introduced.
Efficiently monitoring relational databases
Authors: Buneman O. Peter , Clemons Eric K.
Published: July 2002

An alerter is a program which monitors a database and reports to some user or program when a specified condition occurs. It may be that the condition is a complicated expression involving several entities in the database; in this case the evaluation of the expression may be computationally expensive. A scheme is presented in which alerters may be placed on a complex query involving a relational database, and a method is demonstrated for reducing the amount of computation involved in checking whether an alerter should be triggered.
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Authors: Henzinger Monika R. , King Valerie
Published: July 2002

This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor.

Let
n
denote the number of nodes in the graph. For a sequence of Ω(
m
0
) operations, where
m
0
is the number of edges in the initial graph, the expected time for
p
updates is
O
(
p
log
3
n
) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is
O
(log
n
/log log
n
). For the
k
-edge witness problem (“Does the removal of
k
given edges disconnect the graph?”) the expected time for
p
updates is
O
(
p
log
3
n
) and the expected time for
q
queries is
O
(
qk
log
3
n
). Given a graph with
k
different weights, the minimum spanning tree can be maintained during a sequence of
p
updates in expected time
O
(
pk
log
3
n
). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree
in expected time
O
((
p
log
3
n
log
U
)/ε) for
p
updates, where the weights of the edges are between 1 and
U
.
Normalization and hierarchical dependencies in the relational data model
Authors: Delobel Claude
Published: July 2002

The purpose of this paper is to present a new approach to the conceptual design of logical schemata for relational databases. One-to-one, one-to-many, and many-to-many relationships between the attributes of database relations are modeled by means of functional dependencies and multivalued dependencies. A new type of dependency is introduced: first-order hierarchical decomposition. The properties of this new type of dependency are studied and related to the normalization process of relations. The relationship between the concept of first-order hierarchical decomposition and the notion of hierarchical organization of data is discussed through the normalization process.
A Generalized Tree Circuit
Authors: Curtis H. Allen
Published: July 2002

From the very founding of switching theory by Claude E. Shannon, the tree circuit has been a useful instrument in the design of logic networks. Besides being a valuable practical addition to the designer's “tool kit”, it has been a theoretical asset in the study of circuit complexity and the establishment of general bounds on the relative costs of switching networks. The object of this paper is to expand the practical and theoretical scope of the tree circuit. The expansion is effected by the formulation of a generalized tree circuit, which in actuality is a set of circuits having basic tree circuit characteristics.
On Approximate Computer System Models
Authors: Gelenbe Erol
Published: July 2002

A new treatment of the boundary conditions of diffusion
approximations for interconnected queueing systems is presented.
The results have applications to the study of the performance of
multiple-resource computer systems. In this approximation method,
additional equations to represent the behavior of the queues when
they are empty are introduced. This reduces the dependence of the
model on heavy traffic assumptions and yields certain results which
would be expected from queueing or renewal theory. The accuracy of
the approach is evaluated by comparison with certain known exact or
numerical results.
An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
Authors: Gabow Harold N.
Published: July 2002

A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding a maximum matching. The computation time is proportional to
V
3
, where
V
is the number of vertices; previous implementations of Edmonds' algorithm have computation time proportional to
V
4
. The implementation is based on a system of labels that encodes the structure of alternating paths.
Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
Authors: Eisner Mark J. , Severance Dennis G.
Published: July 2002

It is possible to significantly reduce the average cost of information retrieval from a large shared database by partitioning data items stored within each record into a primary and a secondary record segment. An analytic model, based upon knowledge of data item lengths, transportation costs, and retrieval patterns, is developed to assist an analyst with this assignment problem. The model is generally applicable to environments in which a database resides in secondary storage, and is useful for both uniprogramming and multiprogramming systems. A computationally tractable record design algorithm has been implemented as a Fortran program and applied to numerous problems. Realistic examples are presented which demonstrate a potential for reducing total system cost by more than 65 percent.
A Level Algorithm for Preemptive Scheduling
Authors: Horvath Edward C. , Lam Shui , Sethi Ravi
Published: July 2002

Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors available. Their algorithm is adapted here to handle processors of different speeds. The new algorithm is optimal for independent tasks on any number of processors and for arbitrary task systems on two processors, but not on three or more processors, even for trees. By taking the algorithm as a heuristic onmprocessors and using the ratio of the lengths of the constructed and optimal schedules as a measure, an upper bound on its performance is derived in terms of the speeds of the processors. It is further shown that 1.23√mis an upper bound over all possible processor speeds and that the 1.23√mbound can be improved at most by a constant factor, by giving an example of a system for which the bound 0.35√mcan be approached asymptotically.
Initial Algebra Semantics and Continuous Algebras
Authors: Goguen J. A. , Thatcher J. W. , Wagner E. G. , Wright J. B.
Published: July 2002

Many apparently divergent approaches to specifying formal semantics of programming languages are applications of initial algebra semantics. In this paper an overview of initial algebra semantics is provided. The major technical feature is an initial continuous algebra which permits unified algebraic treatment of iterative and recursive semantic features in the same framework as more basic operations.
Evaluating the performance of distributed architectures for information retrieval using a variety of workloads
Authors: Cahoon Brendon , McKinley Kathryn S. , Lu Zhihong
Published: July 2002

The information explosion across the Internet and elswhere offers access to an increasing number of document collections. In order for users to effectively access these collections, information retrieval (IR) systems must provide coordinated, concurrent, and distributed access. In this article, we explore how to achieve scalable performance in a distributed system for collection sizes ranging from 1GB to 128GB. We implement a fully functional distributed IR system based on a multithreaded version of the Inquery simulation model. We measure performance as a function of system parameters such as client command rate, number of document collections, ter ms per query, query term frequency, number of answers returned, and command mixture. Our results show that it is important to model both query and document commands because the heterogeneity of commands significantly impacts performance. Based on our results, we recommend simple changes to the prototype and evaluate the changes using the simulator. Because of the significant resource demands of information retrieval, it is not difficult to generate workloads that overwhelm system resources regardless of the architecture. However under some realistic workloads, we demonstrate system organizations for which response time gracefully degrades as the workload increases and performance scales with the number of processors. This scalable architecture includes a surprisingly small number of brokers through which a large number of clients and servers communicate.
A predictive system shutdown method for energy saving of event-driven computation
Authors: Hwang Chi-Hong , Wu Allen C.-H.
Published: July 2002

This paper presents a system-level power management technique for energy savings of event-driven application. We present a new predictive system-shutdown method to exploit sleep mode operations for energy saving. We use an exponential-average approach to predict the upcoming idle period. We introduce two mechanisms, prediction-miss correction and prewake-up, to improve the hit ratio and to reduce the delay overhead. Experiments on four different event-driven applications show that our proposed method achieves high hit ratios in a wide range of delay overheads, which results in a high degree of energy with low delay penaties.
On Concurrency Control by Multiple Versions
Authors: Papadimitriou Christos H. , Kanellakis Paris C.
Published: July 2002

We examine the problem of concurrency control when the database management system supports multiple versions of the data. We characterize the limit of the parallelism achievable by the multiversion approach and demonstrate the resulting space-parallelism trade-off.
An efficient, incremental, automatic garbage collector
Authors: Deutsch L. Peter , Bobrow Daniel G.
Published: July 2002

This paper describes a new way of solving the storage reclamation problem for a system such as Lisp that allocates storage automatically from a heap, and does not require the programmer to give any indication that particular items are no longer useful or accessible. A reference count scheme for reclaiming non-self-referential structures, and a linearizing, compacting, copying scheme to reorganize all storage at the users discretion are proposed. The algorithms are designed to work well in systems which use multiple levels of storage, and large virtual address space. They depend on the fact that most cells are referenced exactly once, and that reference counts need only be accurate when storage is about to be reclaimed. A transaction file stores changes to reference counts, and a multiple reference table stores the count for items which are referenced more than once.
Error bounds for periodic quintic splines
Authors: Hall Charles Allan
Published: July 2002

Explicit error bounds for periodic quintic spline interpolation are developed. The first (third) derivative of the periodic spline is shown to be a sixth (fourth) order approximation at the mesh points to the first (third) derivative of the function being interpolated.
Optimizing object queries using an effective calculus
Authors: Fegaras Leonidas , Maier David
Published: July 2002

Object-oriented databases (OODBs) provide powerful data abstractions and modeling facilities, but they generally lack a suitable framework for query processing and optimization. The development of an effective query optimizer is one of the key factors for OODB systems to successfully compete with relational systems, as well as to meet the performance requirements of many nontraditional applications. We propose an effective framework with a solid theoretical basis for optimizing OODB query languages. Our calculus, called the monoid comprehension calculus, captures most features of ODMG OQL, and is a good basis for expressing various optimization algorithms concisely. This article concentrates on query unnesting (also known as query decorrelation), an optimization that, even though it improves performance considerably, is not treated properly (if at all) by most OODB systems. Our framework generalizes many unnesting techniques proposed recently in the literature, and is capable of removing any form of query nesting using a very simple and efficient algorithm. The simplicity of our method is due to the use of the monoid comprehension calculus as an intermediate form for OODB queries. The monoid comprehension calculus treats operations over multiple collection types, aggregates, and quantifiers in a similar way, resulting in a uniform method of unnesting queries, regardless of their type of nesting.
Flexible support for multiple access control policies
Authors: Jajodia Sushil , Samarati Pierangela , Sapino Maria Luisa , Subrahmanian V. S.
Published: July 2002

Although several access control policies can be devised for controlling access to information, all existing authorization models, and the corresponding enforcement mechanisms, are based on a specific policy (usually the closed policy). As a consequence, although different policy choices are possible in theory, in practice only a specific policy can actually be applied within a given system. In this paper, we present a unified framework that can enforce multiple access control policies within a single system. The framework is based on a language through which users can specify security policies to be enforced on specific accesses. The language allows the specification of both positive and negative authorizations and incorporates notions of authorization derivation, conflict resolution, and decision strategies. Different strategies may be applied to different users, groups, objects, or roles, based on the needs of the security policy. The overall result is a flexible and powerful, yet simple, framework that can easily capture many of the traditional access control policies as well as protection requirements that exist in real-world applications, but are seldom supported by existing systems. The major advantage of our approach is that it can be used to specify different access control policies that can all coexist in the same system and be enforced by the same security server.
Hierarchical representations of collections of small rectangles
Authors: Samet Hanan
Published: July 2002

A tutorial survey is presented of hierarchical data structures for representing collections of small rectangles. Rectangles are often used as an approximation of shapes for which they serve as the minimum rectilinear enclosing object. They arise in applications in cartography as well as very large-scale integration (VLSI) design rule checking. The different data structures are discussed in terms of how they support the execution of queries involving proximity relations. The focus is on intersection and subset queries. Several types of representations are described. Some are designed for use with the plane-sweep paradigm, which works well for static collections of rectangles. Others are oriented toward dynamic collections. In this case, one representation reduces each rectangle to a point in a higher multidimensional space and treats the problem as one involving point data. The other representation is area based—that is, it depends on the physical extent of each rectangle.
Designing documentation to compensate for delocalized plans
Authors: Soloway Elliot , Lampert Robin , Letovsky Stan , Littman David , Pinto Jeannine
Published: July 2002

Conceptual representation methods play a significant role in facilitating the software process. Recent studies explore and clarify the use of these representations and their impact on progress.
Scalable high-speed prefix matching
Authors: Waldvogel Marcel , Varghese George , Turner Jon , Plattner Bernhard
Published: July 2002

Finding the longest matching prefix from a database of keywords is an old problem with a number of applications, ranging from dictionary searches to advanced memory management to computational geometry. But perhaps today's most frequent best matching prefix lookups occur in the Internet, when forwarding packets from router to router. Internet traffic volume and link speeds are rapidly increasing; at the same time, a growing user population is increasing the size of routing tables against which packets must be matched. Both factors make router prefix matching extremely performance critical.In this paper, we introduce a taxonomy for prefix matching technologies, which we use as a basis for describing, categorizing, and comparing existing approaches. We then present in detail a fast scheme using binary search over hash tables, which is especially suited for matching long addresses, such as the 128 bit addresses proposed for use in the next generation Internet Protocol, IPv6. We also present optimizations that exploit the structure of existing databases to further improve access time and reduce storage space.
Join processing in database systems with large main memories
Authors: Shapiro Leonard D.
Published: July 2002

We study algorithms for computing the equijoin of two relations in a system with a standard architecture hut with large amounts of main memory. Our algorithms are especially efficient when the main memory available is a significant fraction of the size of one of the relations to he joined; but they can be applied whenever there is memory equal to approximately the square root of the size of one relation. We present a new algorithm which is a hybrid of two hash-based algorithms and which dominates the other algorithms we present, including sort-merge. Even in a virtual memory environment, the hybrid algorithm dominates all the others we study.

Finally, we describe how three popular tools to increase the efficiency of joins, namely filters, Babb arrays, and semijoins, can he grafted onto any of our algorithms.
Concurrent operations on extendible hashing and its performance
Authors: Kumar Vijay
Published: July 2002

Extendible hashing is a dynamic data structure which accommodates expansion and contraction of any stored data efficiently. In this article, an algorithm has been developed for managing concurrent operations on extendible hashing by achieving optimal memory utilization by supporting directly expansion and contraction, page split, and merge. The results of this study have been encouraging in the sense that it seems to provide a higher degree of concurrency compared to other algorithms on an extendible hash file.
SOLAR ACTIVE REGIONS AS DIAGNOSTICS OF SUBSURFACE CONDITIONS
Authors: Howard Robert F.
Published: July 2002

▪ Abstract  In the past decade a number of observational and theoretical studies have appeared that address the problem of how both the physical conditions in subsurface layers of the Sun and the nature of the magnetic flux tubes of active regions are reflected in the structure and behavior of these regions at the surface. This review discusses work in this area. Many characteristics of plages and sunspot groups are shown to be related to the conditions encountered by the region flux tube as it rises through the convective zone of the Sun to the surface. Size distributions, rotation and meridional flow rates and their covariances, and characteristics of growth and decay are among the factors that have been shown to depend on the nature of the source magnetic flux tube and the physical effects, such as the Coriolis force and magnetic tension, that act deep in the convection zone.