bluuebunny/crossref_metadata_2025 huggingface dataset:
THE COMPLEX INDECOMPOSABLE REPRESENTATIONS OF Aut(F2) OF DEGREE LESS THAN SIX
Authors: ĐOKOVIĆ D. Ž. , DONIZ D.
Published: July 2002

Denote by Φ2 the automorphism group of the free group on two generators. We classify the indecomposable complex linear representations of Φ2 of degree at most 5, and determine which ones have an infinite image. As a side-effect, our classification incorporates all the indecomposable representations of GL2(Z) in these degrees.
THE SEMIDIRECTLY CLOSED PSEUDOVARIETY GENERATED BY APERIODIC BRANDT SEMIGROUPS
Authors: TEIXEIRA M. LURDES
Published: July 2002

This paper presents a study of the semidirectly closed pseudovariety generated by the aperiodic Brandt semigroup B2, denoted V*(B2). We construct a basis of pseudoidentities for the semidirect powers of the pseudovariety generated by B2 which leads to the main result, which states that V*(B2) is decidable.

Independently, using some suggestions given by J. Almeida in his book "Finite Semigroups and Universal Algebra", we constructed an algorithm to solve the membership problem in V* (B2).
STABLE EQUIVALENCE PROBLEMS FOR FREE ALGEBRAS WITH THE NIELSEN-SCHREIER PROPERTY
Authors: MIKHALEV ALEXANDER A. , YU JIE-TAI
Published: July 2002

A variety of algebras is said to be Schreier if any subalgebra of a free algebra of this variety is free in the same variety of algebras. For free algebras of finite ranks of Schreier varieties we prove that if two systems of elements are stably equivalent, then they are equivalent. We define the rank of an endomorphism of a free algebra of a Schreier variety and prove that an injective endomorphism of maximal rank does not change the rank of elements of maximal rank.
COFRAME TELEPARALLEL MODELS OF GRAVITY: EXACT SOLUTIONS
Authors: ITIN YAKOV
Published: July 2002

The superstring and superbrane theories include gravity as a necessary and fundamental part of a (future) unified field theory. Thus it is important to consider the alternative representations of general relativity as well as the alternative models of gravity.

We study the coframe teleparallel theory of gravity with a most general quadratic Lagrangian. The coframe field on a differentiable manifold is a basic dynamical variable. A metric tensor as well as a metric compatible connection is generated by a coframe in a unique manner.

The Lagrangian is a general linear combination of Weitzenböck's quadratic invariants with free dimensionless parameters ρ1, ρ2, ρ3. Every independent term of the Lagrangian is a global SO(1,3)-invariant 4-form. For a special choice of parameters which confirms with the local SO(1,3) invariance this theory gives an alternative description of Einsteinian gravity — teleparallel equivalent of GR.

The field equations of the theory is studied by a "diagonal" coframe ansatz which is a subclass of a most general spherical-nsymmetric Einstein–Mayer ansatz. The restricted Lagrangian depends only on two free parameters ρ1, ρ3.

We obtain a formula for scalar curvature of a pseudo-Riemannian manifold with a metric constructed from the static "diagonal" solution of the field equation. It is proved that the sign of the scalar curvature depends only on a relation between the parameters ρ1and ρ3. Thus by a specific choice of free parameters a manifold of positive or negative curvature can be obtained. The scalar curvature vanishes only for a subclass of models with ρ1=0. This subclass includes the teleparallel equivalent of GR.

We obtain the explicit form of all spherically symmetric static solutions of the "diagonal" type to the field equations for an arbitrary choice of free parameters. We prove that the unique asymptotic-flat solution with Newtonian limit is the Schwarzschild solution that holds for a subclass of teleparallel models with ρ1=0. Thus the Yang–Mills-type term of the general quadratic coframe Lagrangian should be rejected.
SLOWLY ROTATING BOSON-FERMION STAR
Authors: DE SOUSA CLAUDIO M. G. , SILVEIRA VANDA
Published: July 2002

Relativistic prescription is used to study the slow rotation of stars composed by self-gravitating bosons and fermions (fermions may be considered as neutrons). Previous results demand that purely boson stars are unable to display slow rotation, if one uses relativistic prescription with classical scalar fields. In contrast to this, the present work shows that a combined boson-fermion star in its ground-state can rotate. Its structure and stability are analysed under slow rotation approximations.
TORSION AND THE ELECTROMAGNETIC FIELD
Authors: DE ANDRADE V. C. , PEREIRA J. G.
Published: July 2002

In the framework of the teleparallel equivalent of general relativity, we study the dynamics of a gravitationally coupled electromagnetic field. It is shown that the electromagnetic field is able not only to couple to torsion, but also, through its energy–momentum tensor, produce torsion. Furthermore, it is shown that the coupling of the electromagnetic field with torsion preserves the local gauge invariance of Maxwell's theory.
COSMOLOGICAL SOLUTION IN M-THEORY ON S1/Z2
Authors: BENAKLI KARIM
Published: July 2002

We provide the first example of a cosmological solution of the Horava–Witten supergravity. This solution is obtained by exchanging the role of time with the radial coordinate of the transverse space to the five-brane soliton. On the boundary, this corresponds to rotating an instanton solution into a tunneling process in a space with Lorentzian signature, leading to an expanding universe. Due to the freedom to choose different nontrivial Yang–Mills backgrounds on the boundaries, the two walls of the universe (visible and hidden worlds) expand differently. However at late times the anisotropy is washed away by gravitational interactions.
HAMILTONIAN ANALYSIS OF POINCARÉ GAUGE THEORY SCALAR MODES
Authors: YO HWEI-JANG , NESTER JAMES M.
Published: July 2002

The Hamiltonian constraint formalism is used to obtain the first explicit complete analysis of nontrivial viable dynamic modes for the Poincaré gauge theory of gravity. Two modes with propagating spin-zero torsion are analyzed. The explicit form of the Hamiltonian is presented. All constraints are obtained and classified. The Lagrange multipliers are derived. It is shown that a massive spin -0- mode has normal dynamical propagation but the associated massless 0- is pure gauge. The spin -0+ mode investigated here is also viable in general. Both modes exhibit a simple type of "constraint bifurcation" for certain special field/parameter values.
NANOSCALE MODIFICATION OF THIN PALLADIUM ACETATE FILMS WITH SCANNING TUNNELING MICROSCOPY
Authors: GURIN V. S.
Published: July 2002

Thin films on solid surface prepared from palladium acetate are studied with respect to the formation of nanometer scale structures after the voltage pulses in scanning tunneling microscopy (STM). Explicit relief changes are observed. They correlate with the work function variation measured with the same STM in the tip-oscillating mode. The possible nature of STM-stimulated effects is discussed from the point of view of the tip-induced electrical field action upon chemical processes on the surface and in the solid phase.
PREPARATION OF HIGHLY ORDERED GdFe2 ALLOYS
Authors: GETZLAFF M. , PASCAL R. , TÖDTER H. , BODE M. , WIESENDANGER R.
Published: July 2002

The monolayer of the highly ordered GdFe 2 alloy was prepared on top of a W(110) substrate and characterized by using scanning tunneling microscopy (STM) and low energy electron diffraction (LEED). The crystallographic arrangement of the ultrathin films does not coincide with the bulk structure (C15 Laves phase). This is due to the large misfit between the lattice constant of the Laves phase and the W(110) substrate. A structure model for the ultrathin GdFe 2 films on W(110) is proposed basing on atomically resolved STM images and LEED studies.
CUBITAL TUNNEL RELEASE WITH LIFT-TYPE ENDOSCOPIC SURGERY
Authors: Nakao Yasushi , Takayama Shinichiro , Toyama Yoshiaki
Published: July 2002

A new technique of endoscopic release of the ulnar nerve at the elbow was designed for cubital tunnel syndrome. After three 5 mm incisions were made along the line of the ulnar nerve, the skin and subcutaneous tissue were lifted up using a fine tape to produce a provisional space. An endoscope was inserted through the one incision, and the constricting ligaments and fascia were released using a retrograde knife inserted through the other incision under endoscopic vision. Eight patients were treated using this method, and successful results were achieved. No neurovascular complications occurred, and all pre-operative complaints were resolved within three weeks. Our surgical series indicated an earlier return to work and daily activity due to early healing of incisions and minimal post-operative pain.
A Comparative Study of Nerve Reconstruction Techniques in Phrenic Nerve Tranfer for Treatment of Brachial Plexus Root Avulsion Injuries
Authors: Gu Yu-Dong , Ma Jian-Jun
Published: July 2002

This experimental study investigated the effectiveness of three methods of neurorrhaphy, nerve grafting and nerve implantation in phrenic nerve transfer for treatment of brachial plexus root avulsion injuries. 180 Sprague-Dawley rats were used. The electrophysiological, histological and muscle functional evaluations were performed at 1, 2, 3, 4, 5 and 6-month postoperatively. Variable recovery in each group was found at different postoperative intervals. At six months after operation, the following results were observed in descending order of superiority: neurorrhaphy, nerve grafting, nerve implantation. Nerve implantation demonstrated a recovery of function of 75.76% and the characteristic electrical activity of the phrenic nerve might contribute to the motor endplate regeneration. Our experimental results will serve as the basis for our clinical practice.
METADATA MANAGEMENT FOR DATA WAREHOUSING: AN OVERVIEW
Authors: VADUVA ANCA , VETTERLI THOMAS
Published: July 2002

Metadata has been identified as a key success factor in data warehouse projects. It captures all kinds of information necessary to design, build, use and interpret the data warehouse contents. This paper gives an overview about the role metadata plays for data warehousing and reviews existing standards, commercial solutions and research actions relevant to metadata management. It turns out that an overall solution for managing all metadata in a central or federated repository is still missing regarding a global metadata schema as well as system aspects and interoperability among involved tools producing metadata. The divergence of proposed standards will probably prevent a breakthrough within the near future.
A GENERAL METHODOLOGY TO PRICE AND HEDGE DERIVATIVES IN INCOMPLETE MARKETS
Authors: AURELL ERIK , BAVIERA ROBERTO , HAMMARLID OLA , SERVA MAURIZIO , VULPIANI ANGELO
Published: July 2002

We introduce and discuss a general criterion for the derivative pricing in the general situation of incomplete markets, we refer to it as the No Almost Sure Arbitrage Principle. This approach is based on the theory of optimal strategy in repeated multiplicative games originally introduced by Kelly. As particular cases we obtain the Cox–Ross–Rubinstein and Black–Scholes in the complete markets case and the Schweizer and Bouchaud–Sornette as a quadratic approximation of our prescription. Technical and numerical aspects for the practical option pricing, as large deviation theory approximation and Monte Carlo computation are discussed in detail.
WHITNEY'S TYPE THEOREMS FOR INFINITE DIMENSIONAL SPACES
Authors: SHKARIN S. A.
Published: July 2002

It is proved that for any f ∈ Ck(L,ℝ), where k ∈ ℕ and L is a closed linear subspace of a nuclear Frechét space X, the function f can be extended to a function of class Ck-1 defined on the entire space X. It is also proved that for any f ∈ Ck (L, ℝ), where k ∈ℕ∪{∞} and L is a closed linear subspace of a conjugate X of a nuclear Frechét space, the function f can be extended to a function of class Ck defined on the entire space X. In addition, it is proved that under these conditions, the existence of a linear extension operator is equivalent to the complementability of the subspace.
OPEN SETS SATISFYING SYSTEMS OF CONGRUENCES
Authors: DOUGHERTY RANDALL
Published: July 2002

A famous result of Hausdorff states that a sphere with countably many points removed can be partitioned into three pieces A, B, C such that A is congruent to B (i.e. there is an isometry of the sphere which sends A to B), B is congruent to C, and A is congruent to B ∪ C; this result was the precursor of the Banach–Tarski paradox. Later, R. Robinson characterized the systems of congruences like this which could be realized by partitions of the (entire) sphere with rotations witnessing the congruences. The pieces involved were nonmeasurable.

In the present paper, we consider the problem of which systems of congruences can be satisfied using open subsets of the sphere (or related spaces); of course, these open sets cannot form a partition of the sphere, but they can be required to cover "most of" the sphere in the sense that their union is dense. Various versions of the problem arise, depending on whether one uses all isometries of the sphere or restricts oneself to a free group of rotations (the latter version generalizes to many other suitable spaces), or whether one omits the requirement that the open sets have dense union, and so on. While some cases of these problems are solved by simple geometrical dissections, others involve complicated iterative constructions and/or results from the theory of free groups. Many interesting questions remain open.
PIVOTING ALGORITHMS FOR SOME CLASSES OF STOCHASTIC GAMES: A SURVEY
Authors: MOHAN S. R. , NEOGY S. K. , PARTHASARATHY T.
Published: July 2002

In this paper, we survey the recent literature on computing the value vector and the associated optimal strategies of the players for special cases of zero-sum stochastic games, or in computing a Nash equilibrium point and the corresponding stationary strategies of the players for special cases of nonzero-sum stochastic games, using finite-step algorithms based on pivoting. Examples of finite-step pivoting algorithms are the various simplex-type algorithms, such as the primal simplex or dual simplex method for solving the linear programming problem or Lemke's or Lemke-Howson's algorithm for solving the linear complementarity problem. Also included are Lemke-type algorithms for solving various generalisations of the linear complementarity problem. The survey also includes a few new results and observations.
PLASMA-ENHANCED SURFACE MODIFICATION OF LOW LINEAR-DENSITY POLYETHYLENE CATHETERS
Authors: KOMVOPOULOS K.
Published: July 2002

Modification of the surface chemistry, topography, and frictional characteristics of medical-grade low linear-density polyethylene catheters with various plasma chemistries was accomplished in a radio-frequency (RF) vacuum chamber. Two different types of plasma treatments were examined. For surface texturing and chemistry modification, the catheters were treated with either He or CF 4 gases for 0.5–60 min at RF power in the range of 30–1000 W and working pressure between 0.2 and 2 Torr. For grafting of a low friction film, the catheters were exposed to pure Ar plasma at 400 W for 2 min (surface cleaning) and then to CH 4, CH 4/ CF 4, or H 2/ CF 4 plasmas at power of 250–550 W and working pressure of 0.2–0.8 Torr for 10–60 min (surface modification). The effects of the different plasma treatments on the surface texture, chemical behavior, and friction characteristics of the catheters are discussed in light of results obtained from contact surface profilometry, scanning electron microscopy, atomic force microscopy, contact angle measurements, infrared spectroscopy, and friction experiments. The findings of this study demonstrate that surface crosslinking and grafting of desirable functional groups by RF plasma treatment is an effective low-temperature surface modification technique for polymeric medical devices.
NONINVASIVE ASSESSMENT OF LEFT VENTRICULAR DIASTOLIC FUNCTION BY COLOR M-MODE DOPPLER ECHOCARDIOGRAPHY
Authors: KITABATAKE AKIRA , NISHIHARA KEIKO , ONOZUKA HISAO , URASAWA KAZUSHI , MIKAMI TAISEI
Published: July 2002

Transmitral flow velocity pattern obtained by pulsed Doppler technique reflects left ventricular (LV)diastolic function, but an increase in left atrial pressure pseudo-normalizes the flow pattern and masks diastolic dysfunction. Flow propagation velocity (FPV) measured, using color M-mode Doppler and baseline-shift technique, represents an average velocity of early diastolic LV filling flow from mitral orifice to mid-ventricle. In patients with ischemic heart disease and dilated cardiomyopathy, including those with pseudonormalized transmitral flow pattern, FPV had good correlation with the time constant of early diastolic LV pressure decay (Tau), indicating that FPV is a useful noninvasive diastolic-function parameter which does not pseudo-normalize. Unlike the conventional Doppler parameters, FPV was well correlated with Tau in patients with hypertrophic cardiomyopathy, and was distinctly decreased even in hypertensive patents without LV hypertrophy. Thus, FPV is a unique noninvasive diastolic parameter, which can sensitively and accurately detect LV diastolic impairment.
Amplitude Spectra of Fitness Landscapes
Authors: Hordijk Wim , Stadler Peter F.
Published: July 2002

Fitness landscapes can be decomposed into elementary landscapes using a Fourier transform that is determined by the structure of the underlying configuration space. The amplitude spectrum obtained from the Fourier transform contains information about the ruggedness of the landscape. It can be used for classification and comparison purposes. We consider here three very different types of landscapes using both mutation and recombination to define the topological structure of the configuration spaces. A reliable procedure for estimating the amplitude spectra is presented. The method is based on certain correlation functions that are easily obtained from empirical studies of the landscapes.
Subtle nonlinearity in popular album charts
Authors: Alexander Bentley R. , Maschner Herbert D. G.
Published: July 2002

Large-scale patterns of culture change may be explained by models of self organized criticality, or alternatively, by multiplicative processes. We speculate that popular album activity may be similar to critical models of extinction in that interconnected agents compete to survive within a limited space. Here we investigate whether popular music albums as listed on popular album charts display evidence of self-organized criticality, including a self-affine time series of activity and power-law distributions of lifetimes and exit activity in the chart. We find it difficult to distinguish between multiplicative growth and critical model hypotheses for these data. However, aspects of criticality may be masked by the selective sampling that a "Top 200" listing necessarily implies.
LEARNING NAIVE PHYSICS BY VISUAL OBSERVATION: USING QUALITATIVE SPATIAL REPRESENTATIONS AND PROBABILISTIC REASONING
Authors: BOXER PAUL A.
Published: July 2002

Autonomous robots are unsuccessful at operating in complex, unconstrained environments. They lack the ability to learn about the physical behavior of different objects through the use of vision. We combine Bayesian networks and qualitative spatial representation to learn general physical behavior by visual observation. We input training scenarios that allow the system to observe and learn normal physical behavior. The position and velocity of the visible objects are represented as qualitative states. Transitions between these states over time are entered as evidence into a Bayesian network. The network provides probabilities of future transitions to produce predictions of future physical behavior. We use test scenarios to determine how well the approach discriminates between normal and abnormal physical behavior and actively predicts future behavior. We examine the ability of the system to learn three naive physical concepts, "no action at a distance", "solidity" and "movement on continuous paths". We conclude that the combination of qualitative spatial representations and Bayesian network techniques is capable of learning these three rules of naive physics.
Planar graph decomposition and all pairs shortest paths
Authors: Frederickson Greg N.
Published: July 2002

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph
G
with real-valued edge costs but no negative cycles. The algorithm runs in
O
(
pn
) time, where
n
is the number of vertices in
G
, and
p
is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of
G
. The algorithm is based on a decomposition of the graph into
O
(
pn
) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of
G
and a corresponding face-on-vertex covering of cardinality
O
(
p
), and of generating all pairs shortest path information in a directed outerplannar graph.
Partial expansions for file organizations with an index
Authors: Lomet David B.
Published: July 2002

A new way to increase file space in dynamically growing files is introduced in which substantial improvement in file utilization can be achieved. It makes use of partial expansions in which, instead of doubling the space associated with some part of the file, the space grows at a slower rate. Unlike previous versions of partial expansion in which the number of buckets involved in file growth is increased by less than a factor of two, the new method expands file space by increasing bucket size via “elastic buckets.” This permits partial expansions to be used with a wide range of indexed files, including B-trees. The results of using partial expansions are analyzed, and the analysis confirmed by a simulation study. The analysis and simulation demonstrate that the file utilization gains are substantial and that fears of excessive insertion cost resulting from more frequent file growth are unfounded.
Systolic algorithms to examine all pairs of elements
Authors: Shih Zen-Cheung , Chen Gen-Huey , Lee R. C. T.
Published: July 2002

Four methods to solve the all pairs examination problem are presented. The first two methods are based on the fold-over scheme. The remaining two methods are adopted from some parallel sorting algorithms. All of these approaches can be implemented on a linear systolic array.
Finite state verifiers I
Authors: Dwork Cynthia , Stockmeyer Larry
Published: July 2002

An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown:

Additional results concern two other classes of verifiers: 2pfa's that halt in polynomial expected time, and 2-way probabilistic pushdown automata that halt in polynomial time. In particular, IPSs with verifiers in the latter class are as powerful as IPSs where verifiers are polynomial-time probabilistic Turing machines. In a companion paper [7], zero knowledge IPSs with 2pfa verifiers are investigated.
On the correctness of orphan management algorithms
Authors: Herlihy Maurice , Lynch Nancy , Merritt Michael , Weihl William
Published: July 2002

In a distributed system, node failures, network delays, and other unpredictable occurences can result in
orphan
computations—subcomputations that continue to run but whose results are no longer needed. Several algorithms have been proposed to prevent such computations from seeing inconsistent states of the shared data. In this paper, two such orphan management algorithms are analyzed. The first is an algorithm implemented in the Argus distributed-computing system at MIT, and the second is an algorithm proposed at Carnegie-Mellon. The algorithms are described formally, and complete proofs of their correctness are given.

The proofs show that the fundamental concepts underlying the two algorithms are very similar in that each can be regarded as an implementation of the same high-level algorithm. By exploiting properties of information flow within transaction management systems, the algorithms ensure that orphans only see states of the shared data that they could also see if they were not orphans. When the algorithms are used in combination with any correct concurrency control algorithm, they guarantee that all computations, orphan as well as nonorphan, see consistent states of the shared data.
The generalized Schur decomposition of an arbitrary pencil A–λB—robust software with error bounds and applications. Part I
Authors: Demmel James , Kågström Bo
Published: July 2002

Robust software with error bounds for computing the generalized Schur decomposition of an arbitrary matrix pencil A – λB (regular or singular) is presented. The decomposition is a generalization of the Schur canonical form of A – λI to matrix pencils and reveals the Kronecker structure of a singular pencil. Since computing the Kronecker structure of a singular pencil is a potentially ill-posed problem, it is important to be able to compute rigorous and reliable error bounds for the computed features. The error bounds rely on perturbation theory for reducing subspaces and generalized eigenvalues of singular matrix pencils. The first part of this two-part paper presents the theory and algorithms for the decomposition and its error bounds, while the second part describes the computed generalized Schur decomposition and the software, and presents applications and an example of its use.
Mathematical software for Sturm-Liouville problems
Authors: Pruess Steven , Fulton Charles T.
Published: July 2002

Software is described for the Sturm-Liouville eigenproblem. Eigenvalues, eigenfunctions, and spectral density functions can be estimated with global error control. The method of approximating the coefficients forms the mathematical basis. The underlying algorithms are briefly described, and several examples are presented.
Parallel logic programming systems
Authors: de Kergommeaux Jacques Chassin , Codognet Philippe
Published: July 2002

Parallelizing logic programming has attracted much interest in the research community, because of the intrinsic OR- and AND-parallelisms of logic programs. One research stream aims at transparent exploitation of parallelism in existing logic programming languages such as Prolog, while the family of concurrent logic languages develops language constructs allowing programmers to express the concurrency—that is, the communication and synchronization between parallel processes—within their algorithms. This article concentrates mainly on transparent exploitation of parallelism and surveys the most mature solutions to the problems to be solved in order to obtain efficient implementations. These solutions have been implemented, and the most efficient parallel logic programming systems reach effective speedups over state-of-the-art sequential Prolog implementations. The article also addresses current and prospective research issues in extending the applicability and the efficiency of existing systems, such as models merging the transparent parallelism and the concurrent logic languages approaches, combination of constraint logic programming with parallelism, and use of highly parallel architectures.
An object-oriented approach to graphical interfaces
Authors: Barth Paul S.
Published: July 2002

An object-oriented system for building graphical interfaces to programs is discussed. The system, called GROW, facilitates the process of creating interfaces that are highly interactive (including direct manipulation and animation), rich in layout structure, and effectively reusable across applications. These properties are achieved through three techniques: object-based graphics with taxonomic inheritance, interobject relationships such as composition and graphical dependency, and separation of the interface and application. Experience with interfaces for several applications has provided insights on the effectiveness of these techniques. First, object-oriented programming yields significant leverage on specializing and reusing interfaces. Second, layout constraints (such as maintaining the connectivity of a graph) can be managed with simple data dependencies among the attributes of the graphical objects. Finally, separating the interface and application is essential to reusing interface components. This paper describes the techniques in detail, gives examples of interfaces built with GROW, and summarizes experiences using GROW with a variety of applications.
Answering queries on embedded-complete database schemes
Authors: Chan Edward P. F. , Mendelzon Alberto O.
Published: July 2002

It has been observed that, for some database schemes, users may have difficulties retrieving correct information, even for simple queries. The problem occurs when some implicit “piece” of information, defined on some subset of a relation scheme, is not explicitly represented in the database state. In this situation, users may be required to know how the state and the constraints interact before they can retrieve the information correctly.

In this paper, the formal notion ofembedded-completenessis proposed, and it is shown that schemes with this property avoid the problem described above. A polynomial-time algorithm is given to test whether a database scheme is independent and embedded-complete. Under the assumption of independence, it is shown that embedded-complete schemes allow efficient computation of optimal relational algebra expressions equivalent to theX-total projection, for any set of attributesX.
The Vesta parallel file system
Authors: Corbett Peter F. , Feitelson Dror G.
Published: July 2002

The Vesta parallel file system is designed to provide parallel file access to application programs running on multicomputers with parallel I/O subsystems. Vesta uses a new abstraction of files: a file is not a sequence of bytes, but rather it can be partitioned into multiple disjoint sequences that are accessed in parallel. The partitioning—which can also be changed dynamically—reduces the need for synchronization and coordination during the access. Some control over the layout of data is also provided, so the layout can be matched with the anticipated access patterns. The system is fully implemented and forms the basis for the AIX Parallel I/O File System on the IBM SP2. The implementation does not compromise scalability or parallelism. In fact, all data accesses are done directly to the I/O node that contains the requested data, without any indirection or access to shared metadata. Disk mapping and caching functions are confined to each I/O node, so there is no need to keep data coherent across nodes. Performance measurements shown good scalability with increased resources. Moreover, different access patterns are show to achieve similar performance.
Analysis of an efficient algorithm for the hard-sphere problem
Authors: Krantz Alan T.
Published: July 2002

Many similar algorithms for performing simulations of hard-sphere have been presented. Among these algorithms are those designed by Rapaport (RAP), Lubachevsky (LUB), Krantz (HAD), and Marin (HYBRID). These algorithms exhibit a similar design in that they each use an
O
(log
n
) event queue which becomes the overwhelming bottleneck when simulating large systems. In this paper the design of HAD is presented and contrasted to RAP, LUB and HYBRID. Next, both an empirical and analytic analysis of HAD's performance are presented which show that HAD scales well. Finally, using the design differences of these algorithms, the performance of HAD is compared to RAP, LUB and HYBRID.
Using GOMS for user interface design and evaluation
Authors: John Bonnie E. , Kieras David E.
Published: July 2002

Since the seminal book,
The Psychology of Human-Computer Interaction
, the GOMS model has been one of the few widely known theoretical concepts in human-computer interaction. This concept has spawned much research to verify and extend the original work and has been used in real-world design and evaluation situations. This article synthesizes the previous work on GOMS to provide an integrated view of GOMS models and how they can be used in design. We briefly describe the major variants of GOMS that have matured sufficiently to be used in actual design. We then provide guidance to practitioners about which GOMS variant to use for different design situations. Finally, we present examples of the application of GOMS to practical design problems and then summarize the lessons learned.
Datapath scheduling with multiple supply voltages and level converters
Authors: Johnson Mark C. , Roy Kaushik
Published: July 2002

We present an algorithm called MOVER (Multiple Operating Voltage Energy Reduction) to minimize datapath energy dissipation through use of multiple supply voltages. In a single voltage design, the critical path length, clock period, and number of control steps limit minimization of voltage and power. Multiple supply voltages permit localized voltage reductions to take up remaining schedule slack. MOVER initially finds one minimum voltage for an entire datapath. It then determines a second voltage for operations where there is still schedule slack. New voltages con be introduced and minimized until no schedule slack remains. MOVER was exercised for a variety of DSP datapath examples. Energy savings ranged from 0% to 50% when comparing dual to single voltage results. The benefit of going from two to three voltages never exceeded 15%. Power supply costs are not reflected in these savings, but a simple analysis shows that energy savings can be achieved even with relatively inefficient DC-DC converters. Datapath resource requirements were found to vary greatly with respect to number of supplies. Area penalties ranged from 0% to 170%. Implications of multiple voltage design for IC layout and power supply requirements are discussed.
Elimination algorithms for data flow analysis
Authors: Ryder Barbara G. , Paull Marvin C.
Published: July 2002

A unified model of a family of data flow algorithms, called elimination methods, is presented. The algorithms, which gather information about the definition and use of data in a program or a set of programs, are characterized by the manner in which they solve the systems of equations that describe data flow problems of interest. The unified model provides implementation-independent descriptions of the algorithms to facilitate comparisons among them and illustrate the sources of improvement in worst case complexity bounds. This tutorial provides a study in algorithm design, as well as a new view of these algorithms and their interrelationships.
Safe stratified Datalog with integer order does not have syntax
Authors: Stolboushkin Alexei P. , Taitslin Michael A.
Published: July 2002

Stratified Datalog with integer (gap)-order (orDatalog¬,<z) is considered. ADatalog¬,<z-program is said to be safe if its bottom-up processing terminates on all valid inputs. We prove that safeDatalog¬,<zprograms do not have effective syntax in the sense that there is no recursively enumerable setSof safe Datalog¬,<zprograms such that every safe Datalog¬,<zprogram is equivalent to a program inS.
A quantitative comparison of parallel computation models
Authors: Juurlink Ben H. H. , Wijshoff Harry A. G.
Published: July 2002

In recent years, a large number of parallel computation models have been proposed to replace the PRAM as the parallel computation model presented to the algorithm designer. Although mostly the theoretical justifications for these models are sound, and many algorithmic results where obtained through these models, little experimentation has been conducted to validate the effectiveness of these models for developing cost-effective algorithms and applications on existing hardware platforms. In this article a first attempt is made to perform a detailed experimental account on the preciseness of these models. The achieve this, three models (BSP, E-BSP, and BPRAM) were selected and validated on five parallel platforms (Cray T3E, Thinking Machines CM-5, Intel Paragon, MasPar MP-1, and Parsytec GCel). The work described in this article consists of three parts. First, the predictive capabilities of the models are investigated. Unlike previous experimental work, which mostly demonstrated a close match between the measuredd and predicted execution times, this article shows that there are several situations in which the models do not precisely predict the actual runtime behavior of an algorithm implementation. Second, a comparison between the models is provided in order to determine the model that induces that most efficient algorithms. Lastly, the performance achieved by the model-derived algorithms is compared with the performace attained by machine-specific algorithms in order to examine the effectiveness of deriving fast algorithms through the formalisms of the models.
Algorithm 652
Authors: Watson Layne T. , Billups Stephen C. , Morgan Alexander P.
Published: July 2002

There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK provides three qualitatively different algorithms for tracking the homotopy zero curve: ordinary differential equation-based, normal flow, and augmented Jacobian matrix. Separate routines are also provided for dense and sparse Jacobian matrices. A high-level driver is included for the special case of polynomial systems.
A text-compression-based method for code size minimization in embedded systems
Authors: Liao Stan , Devadas Srinivas , Keutzer Kurt
Published: July 2002

We address the problem of code-size minimization in VLSI systems with embedded DSP processors. Reducing code size reduces the production cost of embedded systems

we use data-compression methods to develop code-size minimization strategies. In our framework, the compressed program consists of a skeleton and a dictionary. We show that the dictionary can be computed by solving a set-covering problem derived from the original program. To execute the compressed code, we describe two methods that have different performance characteristics and different degrees of freedom in compressing the code. We also address performance considerations, and show that they can be incorporated easily into the set-covering formulation, and present experimental results obtained with Texas Instruments' optimizing TMS3220C25 compiler.
Fast simulation of networks of queues with effective and decoupling bandwidths
Authors: Falkner Matthias , Devetsikiotis Michael , Lambadaris Ioannis
Published: July 2002

A significant difficulty when using Monte Carlo simulation for the
performance analysis of communication networks is the long runtime required to obtain accurate statistical estimates. Under the proper conditions, importance sampling (IS) is a technique that can speed up simulations involving rare events in network (queuing) systems. Large speed-up factors in simulation runtime can be obtained with IS if the modification or bias of the underlying probability measures of certain random processes is carefully chosen. Fast simulation methods based on large deviation theory (LTD) have been successfully applied in many cases.

In this paper, we set up an IS-based simulation of various elementary network topologies. These configurations are frequenly encountered in broadband ATM-based network components such as switches and multiplexers. Our objective in this study is to obtain the optimal or near-optimal biasing parameter values of the arrival processes for the importance sampling simulation. For this purpose we appropriately apply a technique presented by Chang et al. for certain portions of the networks (intree) while we develop a new algorithm, inspired by the work of De Veciana et al. on decoupling bandwidths, for the non-intree portion of the network.
Database partitioning in a cluster of processors
Authors: Sacca Domenico , Wiederhold Gio
Published: July 2002

In a distributed database system the partitioning and allocation of the database over the processor nodes of the network can be a critical aspect of the database design effort. In this paper we develop and evaluate algorithms that perform this task in a computationally feasible manner. The network we consider is characterized by a relatively high communication bandwidth, considering the processing and input output capacities in its processors. Such a balance is typical if the processors are connected via busses or local networks. The common constraint that transactions have a specific root node no longer exists, so that there are more distribution choices. However, a poor distribution leads to less efficient computation, higher costs, and higher loads in the nodes or in the communication network so that the system may not be able to handle the required set of transactions.

Our approach is to first split the database into fragments which constitute appropriate units for allocation. The fragments to be allocated are selected based on maximal benefit criteria using a greedy heuristic. The assignment to processor nodes uses a first-fit algorithm. The complete algorithm, called GFF, is stated in a procedural form.

The complexity of the problem and of its candidate solutions are analyzed and several interesting relationships are proven. Alternate benefit metrics are considered, since the execution cost of the allocation procedure varies by orders of magnitude with the alternatives of benefit evaluation. A mixed benefit evaluation strategy is eventually proposed.

A model for evaluation is presented. Two of the strategies are experimentally evaluated, and the reported results support the discussion. The approach should be suitable for other cases where resources have to be allocated subject to resource constraints.
Time- and space-optimality in B-trees
Authors: Rosenberg Arnold L. , Snyder Lawrence
Published: July 2002

A B-tree is
compact
if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious B-trees of the same order. The space utilization of compact B-trees is analyzed and compared with that of noncompact B-trees and with (node)-visit-optimal B-trees, which minimize the expected number of nodes visited per key access. Compact B-trees can be as much as a
factor
of 2.5 more space efficient than visit-optimal B-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. The utility of initializing a B-tree to be compact (which initialization can be done in time linear in the number of keys if the keys are presorted) is demonstrated by comparing the space utilization of a compact tree that has been augmented by random insertions with that of a tree that has been grown entirely by random insertions. Even after increasing the number of keys by a modest amount, the effects of compact initialization are still felt. Once the tree has grown so large that these effects are no longer discernible, the tree can be expeditiously compacted in place using an algorithm presented here; and the benefits of compactness resume.
Partial-match retrieval using hashing and descriptors
Authors: Ramamohanarao K. , Thom James A. , Lloyd John W.
Published: July 2002

This paper studies a partial-match retrieval scheme based on hash functions and descriptors. The emphasis is placed on showing how the use of a descriptor file can improve the performance of the scheme. Records in the file are given addresses according to hash functions for each field in the record. Furthermore, each page of the file has associated with it a descriptor, which is a fixed-length bit string, determined by the records actually present in the page. Before a page is accessed to see if it contains records in the answer to a query, the descriptor for the page is checked. This check may show that no relevant records are on the page and, hence, that the page does not have to be accessed. The method is shown to have a very substantial performance advantage over pure hashing schemes, when some fields in the records have large key spaces. A mathematical model of the scheme, plus an algorithm for optimizing performance, is given.
A note on associative processors for data management
Authors: Langdon Glen G.
Published: July 2002

Associative “logic-per-track” processors for data management are examined from a technological and engineering point of view. Architectural and design decisions are discussed. Some alternatives to the design of comparators, garbage collection, and domain extraction for architectures like the Relational Associative Processor (RAP) are offered.
On an authorization mechanism
Authors: Fagin Ronald
Published: July 2002

Griffiths and Wade (
ACM Trans. Database Syst. 1,3,
(Sept. 1976), 242-255) have defined a dynamic authorization mechanism that goes beyond the traditional password approach. A database user can grant or revoke privileges (such as to read, insert, or delete) on a file that he has created. Furthermore, he can authorize others to grant these same privileges. The database management system keeps track of a directed graph, emanating from the creator, of granted privileges. The nodes of the graph correspond to users, and the edges (each of which is labeled with a timestamp) correspond to grants. The edges are of two types, corresponding to whether or not the recipient of the grant has been given the option to make further grants of this privilege. Furthermore, for each pair
A, B
of nodes, there can be no more than one edge of each type from
A
to
B
. We modify this approach by allowing graphs in which there can be multiple edges of each type from one node to another. We prove correctness (in a certain strong sense) for our modified authorization mechanism. Further, we show by example that under the original mechanism, the system might forbid some user from exercising or granting a privilege that he “should” be allowed to exercise or grant.
A model of statistical database their security
Authors: Kam John B. , Ullman Jeffrey D.
Published: July 2002

Considered here, for a particular model of databases in which only information about relatively large sets of records can be obtained, is the question of whether one can from statistical information obtain information about individuals. Under the assumption that the data in the database is taken from arbitrary integers, it is shown that essentially nothing can be inferred. It is also shown that when the values are known to be imprecise in some fixed range, one can often deduce the values of individual records.
Calculating constraints on relational expression
Authors: Klug A.
Published: July 2002

This paper deals with the problem of determining which of a certain class of constraints hold on a given relational algebra expression where the base relations come from a given schema. The class of constraints includes functional dependencies, equality of domains, and constancy of domains. The relational algebra consists of projection, selection, restriction, cross product, union, and difference. The problem as given is undecidable, but if set difference is removed from the algebra, there is a solution. Operators specifying a closure function (similar to functional dependency closure on one relation) are defined; these will generate exactly the set of constraints valid on the given relational algebra expression. We prove that the operators are sound and complete.
Mappings of languages by two-tape devices
Authors: Ginsburg Seymour , Spanier Edwin H.
Published: July 2002

Several devices with two input lines and one output line are introduced. These devices are viewed as transformations which operate on pairs of (ALGOL-like) languages. Among the results proved are the following: (i) a pair consisting of a language and a regular set is transformed into a language; (ii) let (
V, W
) be a pair consisting of a language and a regular set. Then the set of those words
w
1
, for which there exists a word
w
2
in
V
so that (
w
1
,
w
2
) is mapped into
W
, is a language.