bluuebunny/crossref_metadata_2025 huggingface dataset:
Molecular characterization of a 2.7-kb, 12q13-specific, retroviral-related sequence isolated by RDA from monozygotic twin pairs discordant for schizophrenia
Authors: Deb-Rinker Paromita , O'Reilly Richard L , Torrey E Fuller , Singh Shiva M
Published: July 2002

This report deals with the molecular characterization of a representational difference analysis (RDA)-derived sequence (SZRV-2, GenBank accession No. AF135486; Genome Database accession Nos. 7692183 and 7501402) from three monozygotic twin pairs discordant for schizophrenia (MZD). The results suggest that it is a primate-specific, heavily methylated, and placentally expressed (~7-kb mRNA) endogenous retroviral-related (ERV) sequence of the human genome. We have mapped this sequence to 12q13 using two SZRV-2 positive BAC clones (4K11 (Genome Survey Sequence Database No. 1752076; GenBank accession No. AZ301773) and 501H16) by fluorescence in situ hybridization. End sequencing of the 4K11 BAC clone has allowed identification of nearby genes from the human genome database at NCBI that may be of interest in schizophrenia research. These include viral-related sequences (potential hot spots for insertions), developmental, channel, and signal transduction genes, as well as genes affecting expression of certain receptors in neurons. Furthermore, when used as a probe on Southern blots, SZRV-2 detected no difference between schizophrenia patients from southwestern Ontario and their matched controls. However, it identified aberrant methylation in one of the eight patients and none of the 21 unaffected controls. Although additional experiments will be required to establish the significance, if any, of SZRV-2 methylation in the complex etiology of schizophrenia, molecular results included offer a novel insight into the role of retroviral-related sequences in the origin, organization, and regulation of the human genome.Key words: ERV, methylation, retroviral integration, 12q13, neurodevelopment, schizophrenia.
Size dependence of the solubility of nonpolar compounds in different solvents
Authors: Graziano Giuseppe
Published: July 2002

At 25°C, plots of the standard Gibbs energy change associated with the solvation of noble gases and aliphatic hydrocarbons vs. the size of the solutes prove to be approximately linear with a negative slope for common organic solvents but not for water. In the latter case, the plot has a characteristic V-shape. The slope is negative for noble gases, methane, and ethane, but is positive for larger alkanes. This means that the solubility of nonpolar solutes increases with solute size in every solvent except water. The solvation thermodynamics of noble gases and aliphatic hydrocarbons in five solvents (water, ethanol, benzene, c-hexane, and n-hexane) are analyzed in detail by a general theory, which is rederived to avoid risky misunderstandings. The calculations are performed in the same manner for all solvents, using simple formulas where the physical reliability is well established and the results are consistent. The work of cavity creation increases with solute size in every solvent, but to a far greater extent in water. Additionally, the work to turn on the solutesolvent attractive interactions increases in magnitude with solute size in every solvent, but to a lesser extent in water. By combining these two factors a satisfactory explanation for experimental data obtained emerges. The microscopic origins of the difference between water and common organic solvents are discussed.Key words: solvation, excluded-volume effect, solutesolvent interactions, enthalpyentropy compensation, molecular size.
CONFORMAL COVARIANCE OF MASSLESS FREE NETS
Authors: LLEDÓ FERNANDO
Published: July 2002

In the present paper we review in a fiber bundle context the covariant and massless canonical representations of the Poincaré group as well as certain unitary representations of the conformal group (in 4-dimensions). We give a simplified proof of the well-known fact that massless canonical representations with discrete helicity extend to unitary and irreducible representations of the conformal group mentioned before. Further we give a simple new proof that massless free nets for any helicity value are covariant under the conformal group. Free nets are the result of a direct (i.e. independent of any explicit use of quantum fields) and natural way of constructing nets of abstract C *-algebras indexed by open and bounded regions in Minkowski space that satisfy standard axioms of local quantum physics. We also give a group theoretical interpretation of the embedding ℐ. that completely characterizes the free net: it reduces the (algebraically) reducible covariant representation in terms of the unitary canonical ones. Finally, we also mention some of the expected algebraic properties of these models that are a direct consequence of the conformal covariance (essential duality, PCT-symmetry etc.).
QUANTUM GROUPS AND DUALITY
Authors: GOOTMAN ELLIOT C. , LAZAR ALDO J.
Published: July 2002

We present an approach to the duality theory for quantum groups which is explicitly modelled on the construction of the group C*-algebra C* (G) from C0 (G), namely: in the dual of C0 (G), single out the ideal of all elements absolutely continuous with respect to Haar measure, renorm with a C*-norm determined by the representations of this ideal, and complete. We thus obtain a C*-algebra whose *-representations are in one-to-one correspondence with the representations of the quantum group. This C*-algebra is itself a (non-compact) quantum group, and we verify a duality theorem for it.
A DETAILED ACCOUNT OF ALAIN CONNES' VERSION OF THE STANDARD MODEL IN NON-COMMUTATIVE GEOMETRY: I AND II.
Authors: KASTLER DANIEL
Published: July 2002

We present a detailed calculation of the Lagrangian of the standard model prescribed in the paper [4] of Connes and Lott, first for the electroweak interactions alone, and then (as is necessary to achieve the correct weak hypercharge assignments) for the coupling of electroweak interactions with chromodynamics. In its most symmetrical form (with free parameters the fermion mass-matrices plus one universal coupling constant), the Connes theory in tree-approximation yields equality of the strong and electroweak coupling constants, and fixes the value sin 2 θw = 3/8, and the ratios mt/mw and mH/mt.
Continuous Quantum Measurement: Local and Global Approaches
Authors: Albeverio S. , Kolokol'tsov V. N. , Smolyanov O. G.
Published: July 2002

In 1979 B. Menski suggested a formula for the linear propagator of a quantum system with continuously observed position in terms of a heuristic Feynman path integral. In 1989 the aposterior linear stochastic Schrödinger equation was derived by V. P. Belavkin describing the evolution of a quantum system under continuous (nondemolition) measurement. In the present paper, these two approaches to the description of continuous quantum measurement are brought together from the point of view of physics as well as mathematics. A self-contained deductions of both Menski's formula and the Belavkin equation is given, and the new insights in the problem provided by the local (stochastic equation) approach to the problem are described. Furthermore, a mathematically well-defined representations of the solution of the aposterior Schrödinger equation in terms of the path integral is constructed and shown to be heuristically equivalent to the Menski propagator.
MOLECULAR PROPAGATION THROUGH SMALL AVOIDED CROSSINGS OF ELECTRON ENERGY LEVELS
Authors: HAGEDORN GEORGE A. , JOYE ALAIN
Published: July 2002

This is the second of two papers on the propagation of molecular wave packets through avoided crossings of electronic energy levels in a limit where the gap between the levels shrinks as the nuclear masses are increased. An earlier paper deals with the simplest two types of generic, minimal multiplicity avoided crossings, in which the levels essentially depend on only one of the nuclear configuration parameters. The present paper deals with propagation through the remaining four types of generic, minimal multiplicity avoided crossings, in which the levels depend on more than one nuclear configuration parameter.
SCATTERING THEORY APPROACH TO RANDOM SCHRÖDINGER OPERATORS IN ONE DIMENSION
Authors: KOSTRYKIN V. , SCHRADER R.
Published: July 2002

Methods from scattering theory are introduced to analyze random Schrödinger operators in one dimension by applying a volume cutoff to the potential. The key ingredient is the Lifshitz–Krein spectral shift function, which is related to the scattering phase by the theorem of Birman and Krein. The spectral shift density is defined as the "thermodynamic limit" of the spectral shift function per unit length of the interaction region. This density is shown to be equal to the difference of the densities of states for the free and the interacting Hamiltonians. Based on this construction, we give a new proof of the Thouless formula. We provide a prescription how to obtain the Lyapunov exponent from the scattering matrix, which suggest a way how to extend this notion to the higher dimensional case. This prescription also allows a characterization of those energies which have vanishing Lyapunov exponent.
MELTING AND FRAGMENTATION OF NICKEL NANOPARTICLES: MOLECULAR–DYNAMICS SIMULATIONS
Authors: GÜNEŞ BILAL , ERKOÇ ŞAKIR
Published: July 2002

Melting and fragmentation behaviors of Ni 429 cluster have been studied with molecular-dynamics simulations using a size-dependent empirical model potential energy function. To monitor thermal behaviors of the cluster, we calculated some physical quantities such as average potential energy per atom, specific heat, radial atomic distribution, bond length distribution, average interatomic distance, nearest neighbor distance and average coordination number as a function of temperature. The roles of the surface and core atoms in the melting and fragmentation process of the cluster are also investigated by considering the surface and the bulk coordination numbers of the cluster.
THE AREA LAW IN MATRIX MODELS FOR LARGE N QCD STRINGS
Authors: ANAGNOSTOPOULOS K. N. , BIETENHOLZ W. , NISHIMURA J.
Published: July 2002

We study the question whether matrix models obtained in the zero volume limit of 4d Yang–Mills theories can describe large N QCD strings. The matrix model we use is a variant of the Eguchi–Kawai model in terms of Hermitian matrices, but without any twists or quenching. This model was originally proposed as a toy model of the IIB matrix model. In contrast to common expectations, we do observe the area law for Wilson loops in a significant range of scale of the loop area. Numerical simulations show that this range is stable as N increases up to 768, which strongly suggests that it persists in the large N limit. Hence the equivalence to QCD strings may hold for length scales inside a finite regime.
DISCRETE SPECTRA OF SEMIRELATIVISTIC HAMILTONIANS FROM ENVELOPE THEORY
Authors: HALL RICHARD L. , LUCHA WOLFGANG , SCHÖBERL FRANZ F.
Published: July 2002

We analyze the (discrete) spectrum of the semirelativistic "spinless-Salpeter" Hamiltonian [Formula: see text] where V(r) is an attractive, spherically symmetric potential in three dimensions. In order to locate the eigenvalues of H, we extend the "envelope theory", originally formulated only for nonrelativistic Schrödinger operators, to the case of Hamiltonians involving the relativistic kinetic-energy operator. If V(r) is a convex transformation of the Coulomb potential -1/r and a concave transformation of the harmonic-oscillator potential r2, both upper and lower bounds on the discrete eigenvalues of H can be constructed, which may all be expressed in the form [Formula: see text] for suitable values of the numbers P here provided. At the critical point, the relative growth to the Coulomb potential h(r)=-1/r must be bounded by d V/ d h < 2β/π.
SURFACE DIFFUSION IN SYSTEMS OF INTERACTING BROWNIAN PARTICLES
Authors: MAZROUI M'HAMMED , BOUGHALEB YAHIA
Published: July 2002

The paper reviews recent results on diffusive phenomena in two-dimensional periodic potential. Specifically, static and dynamic properties are investigated by calculating different correlation functions. Diffusion process is first studied for one-dimensional system by using the Fokker–Planck equation which is solved numerically by the matrix continued fraction method in the case of bistable potential. The transition from hopping to liquid-like diffusion induced by variation of some parameters is discussed. This study will therefore serve to demonstrate the influence of this form of potential. Further, an analytical approximation for the dc-conductivity is derived for a wide damping range in the framework of the Linear Response Theory. On the basis of this expression, calculations of the ac conductivity of two-dimensional system with Frenkel–Kontorova pair interaction in the intermediate friction regime is performed by using the continued fraction expansion method. The dc-conductivity expression is used to determine the rest of the development. By varying the density of mobile ions we discuss commensurability effects. To get information about the diffusion mechanism, the full width at half maximum λω(q), of the quasi-elastic line of the dynamical structure factor S(q,ω) is computed. The calculations are extended up to large values of q covering several Brillouin zones. The analysis of λω(q) with different parameters shows that the most probable diffusion process in good two-dimensional superionic conductors consists of a competition between a back correlated hopping in one direction and forward correlated hopping in addition to liquid-like motions in the other direction.
DIMENSIONAL CROSSOVERS AND PHASE TRANSITIONS IN STRONGLY CORRELATED LOW-DIMENSIONAL ELECTRON SYSTEMS: RENORMALIZATION-GROUP STUDY
Authors: KISHINE JUN-ICHIRO , YONEMITSU KENJI
Published: July 2002

Based on the perturbative renormalization-group (PRG) approach, we have examined interplay or competition between one-particle (1P) and two-particle (2P) processes in strongly correlated low-dimensional electron systems. Throughout the article, we use the Grassmann functional integral approach, since it has an advantage that the 1P degrees of freedom are incorporated in an explicit manner. We mainly discuss an array of chains weakly-coupled via interchain one-particle hopping, where the constituent chains, if isolated, have a strong-coupling fixed point, such as the Mott-insulator, spin-gap-metal, or Anderson-insulator fixed point. In such cases, quantum fluctuations evolving toward the low-energy limit strongly suppress the interchain 1P coherence, and consequently a phase transition from the incoherent metallic (ICM) phase becomes possible. This kind of competition plays a key role to elucidate the interplay of correlation and dimensionality effects in real quasi-one-dimensional (Q1D) materials in nature. As examples, we take up spin-density-wave (SDW) phase transitions in dimerized quarter-filled Hubbard chains to elucidate the nature of the magnetic phase transitions in the Q1D organic conductors, (TMTTF)2X and (TMTSF)2X. Dimensional crossover problems in Q1D Hubbard ladders are also discussed to describe the pressure-induced superconductivity in the doped ladder systems. Interplay of randomness, electron correlation, and dimensionality effects in weakly-coupled half-filled Hubbard chains with weak quenched random potentials is also studied. We also discuss some 2D electron systems where the two-loop renormalization-group procedure is well defined and works.
ELLIPTIC ALGEBRA AND INTEGRABLE MODELS FOR SOLITONS ON NONCOMMUTATIVE TORUS $\mathcal T$
Authors: HOU BO-YU , PENG DAN-TAO
Published: July 2002

We study the algebra [Formula: see text], the basis of the Hilbert space ℋn in terms of θ functions of the positions of n solitons. Then we embed the Heisenberg group as the quantum operator factors in the representation of the transfer matrices of various integrable models. Finally we generalize our result to the generic θ case.
XANES STUDY OF THE VALENCE OF Pb IN (Tl0.5Pb0.5)Sr2Ca1-xYxCu2O7-δ
Authors: LIANG G. , LIU R. S. , WANG L. V.
Published: July 2002

Near edge x-ray-absorption spectra at Pb L3-edges have been measured for ( Tl 0.5 Pb 0.5) Sr 2 Ca 1-x Y x Cu 2 O 7-δ compound series. It is found that the intensity of the 2p→6s transition feature decreases with the substitution of Ca +2 by Y +3. This result indicates that some electronic charges have been transferred into the Pb(Tl)-O layers by this substitution. Detailed analysis suggests that the valence value of Pb in this compound series is close to +4 and it decreases with the increase of the Y-doping level x.
ON SOME SEMIGROUPS OF INTERMEDIATE GROWTH
Authors: LAVRIK-MÄNNLIN ALLA A.
Published: July 2002

Asymptotic estimates for growth functions of Belyaev–Sesekin–Trofimov's and Okniński's semigroups are obtained. In particular, a question of R. Grigorchuk about the existence of matrix semigroups with growth rate between polynomial and [Formula: see text], is positively answered.
SURVIVAL OF THE FITTEST IN A GENERALIZED LOGISTIC MODEL
Authors: ACKLEH AZMY S. , MARSHALL DAVID F. , HEATHERLY HENRY E. , FITZPATRICK BEN G.
Published: July 2002

In this paper we discuss the asymptotic behavior of a logistic model with distributed growth and mortality rates. In particular, we prove that the entire population becomes concentrated within the subpopulation with highest growth to mortality ratio, and converges to the equilibrium defined by this ratio. Finally, we present a numerical example illustrating the theoretical results.
COLORING SPATIAL GRAPHS
Authors: McATEE JENELLE , SILVER DANIEL S. , WILLIAMS SUSAN G.
Published: July 2002

Coloring invariants for spatial graphs are defined, inspired by Fox colorings of knots and links. A new proof of a the nontriviality of Suzuki's n-theta curves is given. Necessary and sufficient conditions for colorings of θn-curves are described in terms of an Alexander polynomial defined by Litherland.
ISOMINKOWSKIAN GEOMETRY FOR THE GRAVITATIONAL TREATMENT OF MATTER AND ITS ISODUAL FOR ANTIMATTER
Authors: SANTILLI RUGGERO MARIA
Published: July 2002

In a preceding paper at Foundations of Physics Letters,11 we have submitted the apparently first, axiomatically consistent inclusion of gravitation in unified gauge theories of electroweak interactions under the name of isotopic grand unification. The result was submitted via an apparent resolution of the structural incompatibilities between electroweak and gravitational interactions due to: (1) curvature, because the former are defined on a flat spacetime, while the latter are instead defined on a curved spacetime; (2) antimatter, because the former characterize antimatter via negative-energy solutions, while the latter use instead positive-definite energy-momentum tensors; and (3) basic spacetime symmetries, because the former satisfy the fundamental Poincaré symmetry, which is instead absent for the latter. The main purpose of this paper is to present the methods underlying the isotopic grand unification. We begin with a study of the new mathematics, called isomathematics, and of the related new geometry, called isominkowskian geometry, which permit an apparent resolution of the first incompatibility due to curvature. We then pass to a study of the second novel mathematics, called isodual isomathematics, and related geometry, called isodual isominkowskian geometry, which permit an apparent resolution of the second incompatibility due to antimatter. We then pass to a study of the novel realizations of the conventional Poincaré symmetry, known as Poincaré–Santilli isosymmetry and its isodual, which provide a universal symmetry of gravitation for matter and antimatter, respectively, and permit an apparent resolution of the third incompatibility due to spacetime symmetries. This paper has been made possible by the preceding: memoir5g recently appeared in Rendiconti Circolo Matematico Palermo, which achieves sufficient maturity in the new mathematics; memoir4h recently appeared in Foundations of Physics, which achieves sufficient maturity in the physical realizations of the new mathematics; and memoir8c recently appeared in Mathematical Methods in Applied Sciences, which achieves sufficient maturity in the formulation of the generalized symmetries. Regrettably, in addition to the study of the methods, we cannot study the novel applications and verifications to prevent a prohibitive length. Nevertheless, the reader should be aware that the isominkowskian geometry and its isodual already possess a number of novel applications and experimental verifications in classical physics, particle physics, nuclear physics, astrophysics, gravitation, superconductivity, chemistry, antimatter, and biology, which are indicated in the text with related references without a review.
CHIRAL ANOMALY IN ASHTEKAR'S APPROACH TO CANONICAL GRAVITY
Authors: MIELKE ECKEHARD W. , KREIMER DIRK
Published: July 2002

The Dirac equation in Riemann–Cartan spacetimes with torsion is reconsidered. As is well-known, only the axial covector torsion A, a one-form, couples to massive Dirac fields. Using diagrammatic techniques, we show that besides the familiar Riemannian term only the Pontrjagin type four-form dA ∧ dA does arise additionally in the chiral anomaly, but not the Nieh–Yan term d* A, as has been claimed recently. Implications for cosmic strings in Einstein–Cartan theory as well as for Ashtekar's canonical approach to quantum gravity are discussed.
DRIVING FORCE AND BOND STRAIN FOR THE C–Ni(100) SURFACE REACTION
Authors: SUN CHANG Q. , HING PETER
Published: July 2002

It is shown that the atomic states, bonding dynamics, driving force and bond strain for the C–Ni(100) surface reaction can be consistently understood by considering the sp orbital hybridization of carbon. It is proposed that, at the initial stage, C sinks into the hollow site and bonds to one Ni atom underneath. The C -1 polarizes and pushes its surface neighbors radially away from the site center, and hence a Ni 5 C cluster forms. Then, sp hybridization of the C happens, leading to a Ni 4 C tetrahedron. Besides the Ni + underneath the C adsorbate, three of the four surface Ni neighbors donate electrons to the adsorbate. The half-monolayer coverage of C defines therefore half of the surface Ni atoms to be Ni + ions and the other half to be Ni 2+ ions. As a result, one-dimensional nonuniform "- (+) - (2+) – (2+) - (+) – (+) -" chains form along the < 11> direction. It is suggested that the forces arising from charge redistribution drive the reconstruction. Calculation reveals that an increase of ~ 90 dyne electrostatic repulsion along the < 11> direction and a responding ~ 130 dyne bond compression stabilize the network of (2× 2)p4g clock rotation.
Optimizing equijoin queries in distributed databases where relations are hash partitioned
Authors: Shasha Dennis , Wang Tsong-Li
Published: July 2002

Consider the class of distributed database systems consisting of a set of nodes connected by a high bandwidth network. Each node consists of a processor, a random access memory, and a slower but much larger memory such as a disk. There is no shared memory among the nodes. The data are horizontally partitioned often using a hash function. Such a description characterizes many parallel or distributed database systems that have recently been proposed, both commercial and academic. We study the optimization problem that arises when the query processor must repartition the relations and intermediate results participating in a multijoin query. Using estimates of the sizes of intermediate relations, we show (1) optimum solutions for closed chain queries; (2) the NP-completeness of the optimization problem for star, tree, and general graph queries; and (3) effective heuristics for these hard cases.

Our general approach and many of our results extend to other attribute partitioning schemes, for example, sort-partitioning on attributes, and to partitioned object databases.
Limits to low-latency communication on high-speed networks
Authors: Thekkath Chandramohan A. , Levy Henry M.
Published: July 2002

The throughput of local area networks is rapidly increasing. For example, the bandwidth of new ATM networks and FDDI token rings is an order of magnitude greater than that of Ethernets. Other network technologies promise a bandwidth increase of yet another order of magnitude in several years. However, in distributed systems, lowered latency rather than increased throughput is often of primary concern. This paper examines the system-level effects of newer high-speed network technologies on low-latency, cross-machine communications.

To evaluate a number of influences, both hardware and software, we designed and implemented a new remote procedure call system targeted at providing low latency. We then ported this system to several hardware platforms (DECstation and SPARCstation) with several different networks and controllers (ATM, FDDI, and Ethernet). Comparing these systems allows us to explore the performance impact of alternative designs in the communication system with respect to achieving low latency, e.g., the network, the network controller, the hose architecture and cache system, and the kernel and user-level runtime software.

Our RPC system, which achieves substantially reduced call times (170 μseconds on an ATM network using DECstation 5000/200 hosts), allows us to isolate those components of next-generation networks and controllers that still stand in the way of low-latency communication. We demonstrate that new-generation processor technology and software design can reduce small-packet RPC times to near network-imposed limits, making network and controller design more crucial than ever to achieving truly low-latency communication.
Algorithm 719: Multiprecision translation and execution of FORTRAN programs
Authors: Bailey David H.
Published: July 2002

This paper describes two Fortran utilities for multiprecision computation. The first is a package of Fortran subroutines that perform a variety of arithmetic operations and transcendental functions on floating point numbers of arbitrarily high precision. This package is in some cases over 200 times faster than that of certain other packages that have been developed for this purpose.

The second utility is a translator program, which facilitates the conversion of ordinary Fortran programs to use this package. By means of source directives (special comments) in the original Fortran program, the user declares the precision level and specifies which variables in each subprogram are to be treated as multiprecision. The translator program reads this source program and outputs a program with the appropriate multiprecision subroutine calls.

This translator supports multiprecision integer, real, and complex datatypes. The required array space for multiprecision data types is automatically allocated. In the evaluation of computational expressions, all of the usual conventions for operator precedence and mixed mode operations are upheld. Furthermore, most of the Fortran-77 intrinsics, such as ABS, MOD, NINT, COS, EXP are supported and produce true multiprecision values.
Precise and efficient groundness analysis for logic programs
Authors: Marriott Kim , Søndergaard Harald
Published: July 2002

We show how precise groundness information can be extracted from logic programs. The idea is to use abstract interpretation with Boolean functions as “approximations” to groundness dependencies between variables. This idea is not new, and different classes of Boolean functions have been used. We argue, however, that one class, the
positive
functions, is more suitable than others. Positive Boolean functions have a certain property which we (inspired by A. Langen) call “condensation.” This property allows for rapid computation of groundness information.
Geometric programming
Authors: Paoluzzi Alberto , Pascucci Valerio , Vicentino Michele
Published: July 2002

This article presents a functional programming approach to geometric design with embedded polyhedral complexes. Its main goals are to show the expressive power of the language as well as its usefulness for geometric design. The language, named PLASM (the Programming LAnguage for Solid Modeling), introduces a very high level approach to “constructive” or “generative” modeling. Geometrical objects are generated by evaluating some suitable language expressions. Because generating expressions can be easily combined, the language also extends the standard variational geometry approach by supporting classes of geometric objects with varying topology and shape. The design language PLASM can be roughly considered as a geometry-oriented extension of a subset of the functional language FL. The language takes a dimension-independent approach to geometry representation and algorithms. In particular it implements an algebraic calculus over embedded polyhedra of any dimension. The generated objects are always geometrically consistent because the validity of geometry is guaranteed at a syntactical level. Such an approach allows one to use a representation scheme which is weaker than those usually adopted in solid modelers, thus encompassing a broader geometric domain, which contains solids, surfaces, and wire-frames, as well as higher-dimensional objects.
Customized information extraction as a basis for resource discovery
Authors: Hardy Darren R. , Schwartz Michael F.
Published: July 2002

Indexing file contents is a powerful means of helping users locate documents, software, and other types of data among large repositories. In environments that contain many different types of data, content indexing requires type-specific processing to extract information effectively. We present a model for type-specific, user-customizable information extraction, and a system implementation calledEssence. This software structure allows users to associate specialized extraction methods with ordinary files, providing the illusion of an object-oriented file system that encapsulates indexing methods within files. By exploiting the semantics of common file types, Essence generates compact yet representative file summaries that can be used to improve both browsing and indexing in resource discovery systems. Essence can extract information from most of the types of files found in common file systems, including files with nested structure (such as compressed “tar” files). Essence interoperates with a number of different search/index systems (such as WAIS and Glimpse), as part of the Harvest system.
Diffracting trees
Authors: Shavit Nir , Zemach Asaph
Published: July 2002

Shared counters are among the most basic coordination structures in multiprocessor conputation, with applications ranging from barrier synchronization to concurrent-data-structure design. This article introduces diffracting trees, novel data structures for share counting and load balancing in a distributed/parallel environment. Empirical evidence, collected on a simulated distributed shared-memory machine and several simulated message-passing architectures, shows that diffracting trees scale better and are more robust than both combining trees and counting networks, currently the most effective known methods for implementing concurrent counters in software. The use of a randomized coordination method together with a combinatorial data structure overcomes the resiliency drawbacks of combining trees. Our simulations show that to handle the same load, diffracting trees and counting networks should have a similar widthw, yet the depth of a diffracting tree isO(logw), whereas counting networks have depthO(log2w). Diffracting trees have already been used to implement highly efficient producer/consumer queues, and we believe diffraction will prove to be an effective alternative paradigm to combining and queue-locking in the design of many concurrent data structures.
Analysis of bounded time warp and comparison with YAWNS
Authors: Dickens Phillip M. , Nicol David M. , Reynolds Paul F. , Duva J. M.
Published: July 2002

This article studies an analytic model of parallel discrete-event simulation, comparing the YAWNS conservative synchronization protocol with Bounded Time Warp. The assumed simulation problem is a heavily loaded queuing network where the probability of an idle server is closed to zero. We model workload and job routing in standard ways, then develop and validate methods for computing approximated performance measures as a function of the degree of optimism allowed, overhead costs of state-saving, rollback, and barrier synchronization, and workload aggregation. We find that Bounded Time Warp is superior when the number of servers per physical processor is low (i.e., sparse load), but that aggregating workload improves YAWNS relative performance.
A complexity theory based on Boolean algebra
Authors: Skyum S. , Valiant L. G.
Published: July 2002

A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Finer distinctions about the computational relationships among natural problems can be made than in previous formulations and some negative results are proved.
Search strategy and selection function for an inferential relational system
Authors: Minker Jack
Published: July 2002

An inferential relational system is one in which data in the system consists of both explicit facts and general axioms (or “views”). The general axioms are used together with the explicit facts to derive the facts that are implicit (virtual relations) within the system. A top-down algorithm, as used in artificial intelligence work, is described to develop inferences within the system. The top-down approach starts with the query, a conjunction of relations, to be answered. Either a relational fact solves a given relation in a conjunct, or the relation is replaced by a conjunct of relations which must be solved to solve the given relation. The approach requires that one and only one relation in a conjunction be replaced (or expanded) by the given facts and general axioms. The decision to expand only a single relation is termed a selection function. It is shown for relational systems that such a restriction still guarantees that a solution to the problem will be found if one exists.

The algorithm provides for heuristic direction in the search process. Experimental results are presented which illustrate the techniques. A bookkeeping mechanism is described which permits one to know when subproblems are solved. It further facilitates the outputting of reasons for the deductively found answer in a coherent fashion.
Unnormalized Floating Point Arithmetic
Authors: Ashenhurst R. L. , Metropolis N.
Published: July 2002

Algorithms for floating point computer arithmetic are described, in which fractional parts are not subject to the usual normalization convention. These algorithms give results in a form which furnishes some indication of their degree of precision. An analysis of one-stage error propagation is developed for each operation; a suggested statistical model for long-run error propagation is also set forth.
Some Completeness Results in the Mathematical Theory of Computation
Authors: Kaplan Donald M.
Published: July 2002

A formal theory is described which incorporates the “assignment” function
a
(
i
,
k
,
ξ
) and the “contents” function
c
(
i
,
ξ
). The axioms of the theory are shown to comprise a complete and consistent set.
Recursive Formulas for the Evaluation of the Convolutions Integral
Authors: Trauboth H. H.
Published: July 2002

Recursive formulas for the numerical evaluation of the real convolution integral are derived for the case in which the impulse response is given analytically. These formulas require considerably less computation time and memory space than the general time series formulas and can be effectively applied for digital simulation of continuous physical systems.
An Initial-Value Theory for Fredholm Integral Equations With Semidegenerate Kernels
Authors: Kagiwada H. H. , Kalaba R.
Published: July 2002

The Fredholm integral equation where the kernel is semidegenerate has many applications. The solution of this integral equation may be studied as a function of the upper limit of integration
x
, while
t
remains fixed. It is shown that the solution satisfies an initial-value problem. This reformulation is well suited to numerical solution by analog and digital computers.

The present paper is one of a series on initial-value methods for Fredholm integral equations. Its considerations are of practical significance since an arbitrary kernel may be approximated by a degenerate kernel to a desired degree of accuracy using standard techniques. Furthermore, the important cases in which the kernel is a Green's function and in which the integral equation is a Volterra equation are both covered by this treatment.
Learning functions represented as multiplicity automata
Authors: Beimel Amos , Bergadano Francesco , Bshouty Nader H. , Kushilevitz Eyal , Varricchio Stefano
Published: July 2002

We study the learnability of multiplicity automata in Angluin's
exact learning model
, and we investigate its applications. Our starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function to the rank of its Hankel matrix. With this theorem in hand, we present a new simple algorithm for learning multiplicity automata with improved time and query complexity, and we prove the learnability of various concept classes. These include (among others):
-The class of disjoint DNF, and more generally satisfy-
O
(1) DNF.
-The class of polynomials over finite fields.
-The class of bounded-degree polynomials over infinite fields.
-The class of XOR of terms.
-Certain classes of boxes in high
dimensions.
In addition, we obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2).

While multiplicity automata are shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, we study the limitations of this method. We prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulas or even
k
-term DNF for
k
= ω(log
n
) or satisfy-
s
DNF formulas for
s
= ω(1). These results are proven by exhibiting functions in the above classes that require multiplicity automata with super-polynomial number of states.
Software considerations for the “black box” solver FIDISOL for partial differential equations
Authors: Schönauer Willi , Schnepf Eric
Published: July 2002

FIDISOL is a program package for the solution of nonlinear systems of two-dimensional and three-dimensional elliptic and parabolic partial differential equations (PDEs) with nonlinear boundary conditions (BCs) on the boundaries of a rectangular domain. A finite difference method (FDM) with an arbitrary grid and arbitrary consistency order is used, these are either prescribed by the user or are self-adapted for a given relative tolerance. FIDISOL has been designed to be fully vectorizable on vector computers. In this paper we discuss several problems from the viewpoint of software development and user interface, for example, how to deliver the PDEs and BCs to FIDISOL and how to allow a flexible use by a suitable parameter list.
A highly parallel algorithm for approximating all zeros of a polynomial with only real zeros
Authors: Patrick Merrell L.
Published: July 2002

An algorithm is described based on Newton's method which simultaneously approximates all zeros of a polynomial with only real zeros. The algorithm, which is conceptually suitable for parallel computation, determines its own starting values so that convergence to the zeros is guaranteed. Multiple zeros and their multiplicity are readily determined. At no point in the method is polynomial deflation used.
Implementations for coalesced hashing
Authors: Vitter Jeffrey Scott
Published: July 2002

The coalesced hashing method is one of the faster searching methods known today. This paper is a practical study of coalesced hashing for use by those who intend to implement or further study the algorithm. Techniques are developed for tuning an important parameter that relates the sizes of the address region and the cellar in order to optimize the average running times of different implementations. A value for the parameter is reported that works well in most cases. Detailed graphs explain how the parameter can be tuned further to meet specific needs. The resulting tuned algorithm outperforms several well-known methods including standard coalesced hashing, separate (or direct) chaining, linear probing, and double hashing. A variety of related methods are also analyzed including deletion algorithms, a new and improved insertion strategy called varied-insertion, and applications to external searching on secondary storage devices.
The synthetic approach to decision table conversion
Authors: Schumacher Helmut , Sevcik Kenneth C.
Published: July 2002

Previous approaches to the problem of automatically converting decision tables to computer programs have been based on decomposition. At any stage, one condition is selected for testing, and two smaller problems (decision tables with one less condition) are created. An optimal program (with respect to average execution time or storage space, for example) is located only through implicit enumeration of all possible decision trees using a technique such as branch-and-bound. The new approach described in this paper uses dynamic programming to synthesize an optimal decision tree from which a program can be created. Using this approach, the efficiency of creating an optimal program is increased substantially, permitting generation of optimal programs for decision tables with as many as ten to twelve conditions.
Anaysis of interleaved memory systems using blockage buffers
Authors: Burnett G. J. , Coffman E. G.
Published: July 2002

A model of interleaved memory systems is presented, and the analysis of the model by Monte Carlo simulation is discussed. The simulations investigate the performance of various system structures, i.e. schemes for sending instruction and data requests to the memory system. Performance is measured by determining the distribution of the number of memory modules in operation during a memory cycle.

An important observation from these investigations is that separately grouping instruction and data requests for memory can substantially increase the average number of memory modules in operation during a memory cycle. Results of the simulations and an analytical study are displayed for various system structures.
The algorithm sequential access method
Authors: Whitt Jerry D. , Sullenberger A. Gale
Published: July 2002

A requirement of many computer file processing systems is the ability to access data stored on a direct access storage device (DASD) both sequentially and randomly. A popular method which provides both types of access is the index sequential organization. The purpose of this study is to propose and analyze a file organization method which should be appropriate for the same type of environment as index sequential but would be more efficient at the two types of access. This proposed method is designated the Algorithm Sequential Access Method (ASAM).
Comments on the algorithms of Verhelst for the conversion of limited-entry decision tables to flowcharts
Authors: King P. J. H. , Johnson R. G.
Published: July 2002

In his interesting contribution to the study of the conversion of limited-entry decision tables to flowcharts or sequential testing procedures, Verhelst [1] presents two algorithms, one of which is claimed to produce the optimal flowchart with respect to run-time. Unfortunately this minimum run-time algorithm does not always produce the result claimed, as we illustrate by example below.
On the external storage fragmentation produced by first-fit and best-fit allocation strategies
Authors: Shore John E.
Published: July 2002

Published comparisons of the external fragmentation produced by first-fit and best-fit memory allocation have not been consistent. Through simulation, a series of experiments were performed in order to obtain better data on the relative performance of first-fit and best-fit and a better understanding of the reasons underlying observed differences. The time-memory-product efficiencies of first-fit and best-fit were generally within 1 to 3 percent of each other. Except for small populations, the size of the request population had little effect on allocation efficiency. For exponential and hyperexponential distributions of requests, first-fit outperformed best-fit; but for normal and uniform distributions, and for exponential distributions distorted in various ways, best-fit out-performed first-fit. It is hypothesized that when first-fit outperforms best-fit, it does so because first-fit, by preferentially allocating toward one end of memory, encourages large blocks to grow at the other end. Sufficient contiguous space is thereby more likely to be available for relatively large requests. Results of simulation experiments supported this hypothesis and showed that the relative performance of first-fit and best-fit depends on the frequency of requests that are large compared to the average request. When the coefficient of variation of the request distribution is greater than or approximately equal to unity, first-fit outperformed best-fit.
Remark on Algorithm 343 [F2]: Eigenvalues and Eigenvectors of a Real Generator Matrix
Authors: Niessner Herbert
Published: July 2002

We had at our disposal a double precision version (all real variables are declared to be of type double precision) for the IBM 360/50 of the algorithm 343 [1] with logical
IF
statements converted to arithmetical ones. In the following three modifications which we found to be of practical value are to be discussed.
Archaelogy of computers
Authors: Alt Franz L.
Published: July 2002

The period preceding the founding of ACM was dominated by the first large computer ENIAC. Its characteristics, described here, foreshadow later developments.
A bonus from van Wijngaarden's device
Authors: Morris James H.
Published: July 2002

In [1] van Wijngaarden presented a rather remarkable technique for rewriting ALGOL 60 programs to eliminate all labels. The purpose of this note is to point out that the rewriting would also eliminate the use of array returning (procedure returning, label returning, etc.) procedures had they been legal constructs of ALGOL 60. Hence, the many languages which allow such things to be returned as procedure values are not such large extensions of ALGOL 60 as one might think [2, 3, 4, 5].
Automatic error analysis for determining precision
Authors: Richman Paul L.
Published: July 2002

The problem considered is that of evaluating a rational expression to within any desired tolerance on a computer which performs variable-precision floating-point arithmetic operations. For example, the expression might be π/(π + 1/2 - e) √2), which is rational in the data π, e, √2. An automatic error analysis technique is given for determining, directly from the results of a trial low-precision interval arithmetic calculation, just how much precision and data accuracy are required to achieve a desired final accuracy. The techniques given generalize easily to the evaluation of many nonrational expressions.
Mutual recursion in Algol 60 using restricted compilers
Authors: Atkins M. Stella
Published: July 2002

The Elliott (I.C.L.) Algol 60 compiler contains a restriction on the sequence of declarations such that no identifier may be used before it is declared. This means that direct mutual recursion between procedures declared in the same blockhead is not possible.