bluuebunny/crossref_metadata_2025 huggingface dataset:
Simple cellular automata as pseudorandom
m
-sequence generators for built-in self-test
Authors: Matsumoto Makoto
Published: July 2002

We propose an extremely simple and explicit construction of cellular automata (CA) generating pseudorandom
m
-sequences, which consist of only one type of cells. This construction has advantages over the previous researches in the following points. (1) There is no need to search for primitive polynomials; a simple sufficient number-theoretic condition realizes maximal periodic CA with periods 2

m

− 1,
m
=2, 3, 5, 89, 9689, 21701, 859433. (2) The configuration does not require hybrid constructions. This makes the implementation much easier. This is a modification of the Rule-90 by Wolfram. We list our CAs with maximal period, up to the size 300. We also discuss the controllability of the CA, randomness of the generated sequence, and a two-dimensional version.
GEMM-based level 3 BLAS
Authors: Kågström Bo , Ling Per , van Loan Charles
Published: July 2002

The level 3 Basic Linear Algebra Subprograms (BLAS) are designed to perform various matrix multiply and triangular system solving computations. Due to the complex hardware organization of advanced computer architectures the development of optimal level 3 BLAS code is costly and time consuming. However, it is possible to develop a portable and high-performance level 3 BLAS library mainly relying on a highly optimized GEMM, the routine for the general matrix multiply and add operation. With suitable partitioning, all the other level 3 BLAS can be defined in terms of GEMM and a small amount of level 1 and level 2 computations. Our contribution is twofold. First, the model implementations in Fortran 77 of the GEMM-based level 3 BLAS are structured to reduced effectively data traffic in a memory hierarchy. Second, the GEMM-based level 3 BLAS performance evaluation benchmark is a tool for evaluating and comparing different implementations of the level 3 BLAS with the GEMM-based model implementations.
Ordered chaining calculi for first-order theories of transitive relations
Authors: Bachmair Leo , Ganzinger Harald
Published: July 2002

We propose inference systems for binary relations that satisfy composition laws such as transitivity. Our inference mechanisms are based on standard techniques from term rewriting and represent a refinement of chaining methods as they are used in the context of resolution-type theorem proving. We establish the refutational completeness of these calculi and prove that our methods are compatible with the usual simplification techniques employed in refutational theorem provers, such as subsumption or tautology deletion. Various optimizations of the basic chaining calculus will be discussed for theories with equality and for total orderings. A key to the practicality of chaining methods is the extent to which so-called variable chaining can be avoided. We demonstrate that rewrite techniques considerably restrict variable chaining and that further restrictions are possible if the transitive relation under consideration satisfies additional properties, such as symmetry. But we also show that variable chaining cannot be completely avoided in general.
On the Recognition of Primes by Automata
Authors: Hartmanis J. , Shank H.
Published: July 2002

A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of the set of primes can be accepted by a pushdown or finite automaton.

In view of this result an interesting open problem is to determine the “weakest” automaton which can accept the set of primes. It is shown that the linearly bounded automaton can accept the set of primes, and it is conjectured that no automaton whose memory grows less rapidly can recognize the set of primes. One of the results shows that if this conjecture is true, it cannot be proved by the use of arguments about the distribution of primes, as described by the Prime Number Theorem. Some relations are established between two classical conjectures in number theory and the minimal rate of memory growth of automata which can recognize the set of primes.
New Algorithms for Bin Packing
Authors: Yao Andrew Chi-Chih
Published: July 2002

In the bin-packing problem a list
L
of
n
numbers are to be packed into unit-capacity bins. For any algorithm
S
, let
r
(
S
) be the maximum ratio
S
(
L
)/
L
*
for large
L
*
, where
S
(
L
) denotes the number of bins used by
S
and
L
*
denotes the minimum number needed. An on-line
Ο
(
n
log
n
)-time algorithm RFF with
r
(RFF) = 5/3 and an off-line polynomial-time algorithm RFFD with
r
(RFFD) ≤ 11/9 - ε for some fixed ε > 0, are given. These are strictly better, respectively, than two prominent algorithms: the First-Fit (FF), which is on-line with
r
(FF) = 17/10, and the First-Fit-Decreasing (FFD) with
r
(FFD) = 11/9. Furthermore, it is shown that any on-line algorithm
S
must have
r
(
S
) ≥ 3/2. The question, “How well can an
ο
(
n
log
n
)-time algorithm perform?” is also discussed. It is shown that in the generalized
d
-dimensional bin packing, any
ο
(
n
log
n
)-time algorithm
S
must have
r
(
S
) ≥
d
.
Fast Decision Procedures Based on Congruence Closure
Authors: Nelson Greg , Oppen Derek C.
Published: July 2002

The notion of the
congruence closure
of a relation on a graph is defined and several algorithms for computing it are surveyed. A simple proof is given that the congruence closure algorithm provides a decision procedure for the quantifier-free theory of equality. A decision procedure is then given for the quantifier-free theory of LISP list structure based on the congruence closure algorithm. Both decision procedures determine the satisfiability of a conjunction of literals of length
n
in average time
O
(
n
log
n
) using the fastest known congruence closure algorithm. It is also shown that if the axiomatization of the theory of list structure is changed slightly, the problem of determining the satisfiability of a conjunction of literals becomes NP-complete. The decision procedures have been implemented in the authors' simplifier for the Stanford Pascal Verifier.
Shadow volume reconstruction from depth maps
Authors: McCool Michael D.
Published: July 2002

Current graphics hardware can be used to generate shadows using either the shadow volume or shadow map techniques. However, the shadow volume technique requires access to a representation of the scence as a polygonal model, and handling the near plane clip correctly and efficiently is difficult; conversely, accurate shadow maps require high-precision texture map data representations, but these are not widely supported.

We present a hybird of the shadow map and shadow volume approaches which does not have these difficulties and leverages high-performance polygon rendering. The scene is rendered from the point of view of the light source and a sampled depth map is recovered. Edge detection and a template-based reconstruction technique are used to generate a global shadow volume boundary surface, after which the pixels in shadow can be marked using only a one-bit stencil buffer and a single-pass rendering of the shadow volume boundary polygons. The simple form of our template-based reconstruction scheme simplifies capping the shadow volume after the near plane clip.
Algorithm 801: POLSYS_PLP
Authors: Wise Steven M. , Sommese Andrew J. , Watson Layne T.
Published: July 2002

Globally convergent, probability-one homotopy methods have proven to be very effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based on probability-one homotopy methods are reliable and fast. Now, theoretical advances reducing the number of homotopy paths that must be tracked, and in the handling of singular solutions, have made probability-one homotopy methods even more practical. POLSYS_PLP consists of Fortran 90 modules for finding all isolated solutions of a complex coefficient polynomial system of equations. The package is intended to be used in conjunction with HOMPACK90 (Algorithm 777), and makes extensive use of Fortran 90 derived data types to support a partitioned linear product (PLP) polynomial system structure. PLP structure is a generalization of
m
-homogeneous structure, whereby each component of the system can have a different
m
-homogeneous structure. The code requires a PLP structure as input, and although finding the optimal PLP structure is a difficult combinatorial problem, generally physical or engineering intuition about a problem yields a very good structure. POLSYS_PLP employs a sophisticated power series end game for handling singular solutions, and provides support for problem definition both at a high level and via hand-crafted code. Different PLP structures and their corresponding Bezout
Static checking of system behaviors using derived component assumptions
Authors: Inverardi Paola , Wolf Alexander L. , Yankelevich Daniel
Published: July 2002

A critical challenge faced by the developer of a software system is to understand whether the system's components correctly integrate. While type theory has provided substantial help in detecting and preventing errors in mismatched static properties, much work remains in the area of dynamics. In particular, components make assumptions about their behavioral interaction with other components, but currently we have only limited ways in which to state those assumptions and to analyze those assumptions for correctness. We have formulated a method that begins to address this problem. The method operates at the architectural level so that behavioral integration errors, such as deadlock, can be revealed early and at a high level. For each component, a specification is given of its interaction behavior. Form this specification, assumptions that the component makes about the corresponding interaction behavior of the external context are automatically derived. We have defined an algorithm that performs compatibility checks between finite representations of a component's context assumptions and the actual interaction behaviors of the components with which it is intended to interact. A configuration of a system is possible if and only if a successful way of matching actual behaviors with assumptions can be found. The state-space complexity of this algorithm is significantly less than that of comparable approaches, and in the worst case, the time complexity is comparable to the worst case of standard rachability analysis.
A neuroidal architecture for cognitive computation
Authors: Valiant Leslie G.
Published: July 2002

An architecture is described for designing systems that acquire and ma nipulate large amounts of unsystematized, or so-called commonsense, knowledge. Its aim is to exploit to the full those aspects of computational learning that are known to offer powerful solutions in the acquisition and maintenance of robust knowledge bases. The architecture makes explicit the requirements on the basic computational tasks that are to be performed and is designed to make this computationally tractable even for very large databases. The main claims are that (i) the basic learning and deduction tasks are provably tractable and (ii) tractable learning offers viable approaches to a range of issues that have been previously identified as problematic for artificial intelligence systems that are programmed. Among the issues that learning offers to resolve are robustness to inconsistencies, robustness to incomplete information and resolving among alternatives. Attribute-efficient learning algorithms, which allow learning from few examples in large dimensional systems, are fundamental to the approach. Underpinning the overall architecture is a new principled approach to manipulating relations in learning systems. This approach, of independently quantified arguments, allows propositional learning algorithms to be applied systematically to learning relational concepts in polynomial time and in modular fashion.
Architecture of the space shuttle primary avionics software system
Authors: Carlow Gene D.
Published: July 2002

PASS, perhaps the most complex flight computer program ever developed, epitomizes the benefits to be gained by establishing a well-structured system architecture at the front end of the development process
Distributed computation on graphs
Authors: Chandy K. Mani , Misra J.
Published: July 2002

We use the paradigm of diffusing computation, introduced by Dijkstra and Scholten, to solve a class of graph problems. We present a detailed solution to the problem of computing shortest paths from a single vertex to all other vertices, in the presence of negative cycles.
Syntactic source to source transforms and program manipulation
Authors: Arsac Jacques J.
Published: July 2002

Syntactic transforms are the source to source program transformations which preserve the history of computation, and thus do not modify the execution time. Combined with a small number of primitive semantic transforms, they provide a powerful tool for program manipulation. A complete catalogue of syntactic transforms, and its use for solution of a system of program equations, is given. Examples of derivation of more complex source to source transformations are also presented. Two case studies illustrate the way in which syntactic and semantic source to source transformations may be used for development of clear, simple, and reasonably efficient programs.
On the complexity of computing the measure of ∪[a
i
,b
i
]
Authors: Fredman Michael L. , Weide Bruce
Published: July 2002

The decision tree complexity of computing the measure of the union of n (possibly overlapping) intervals is shown to be Ω(n log n), even if comparisons between linear functions of the interval endpoints are allowed. The existence of an Ω(n log n) lower bound to determine whether any two of n real numbers are within ∈ of each other is also demonstrated. These problems provide an excellent opportunity for discussing the effects of the computational model on the ease of analysis and on the results produced.
Fortran 77
Authors: Brainerd Walt
Published: July 2002

There is a new standard Fortran. The official title is “American National Standard Programming Language Fortran, X3.9-1978,” but it is more commonly referred to as “Fortran 77,” since its development was completed in 1977. It replaces the Fortran standard designated X3.9-1966. This paper describes many of the features of Fortran 77 and also provides some information about how and why the standard was developed.
A note on the complement of inherently ambiguous context-free languages
Authors: Maurer Herman A.
Published: July 2002

Definitions and notation used in this note are as in [1]. In particaular,
language
means
context-free language
throughout.
An approach to the optimum design of computer graphics systems
Authors: Foley James D.
Published: July 2002

Display system designers are faced with the difficult task of selecting major subsystems in an intelligent way. Each subsystem is chosen from large numbers of alternatives; the selection is based on considerations such as system response time, system cost, and the distribution of data storage and processing between the graphics processor and its supporting data processing system. The work reported here develops an objective, quantitative design procedure and helps give a better understanding of how to configure display systems. This is accomplished by means of a mathematical model of a computer driven graphics system.

The parameters of the model are functions of the capabilities of the graphics hardware and of the computational requirements of the graphics application. The model can be analyzed using numerical queueing analysis or simulation to obtain an average response time prediction. By combining the model with an optimization, the best graphics system configuration, subject to a cost constraint, is found for several applications. The optimum configurations are in turn used to find general display system design guidelines.
A stopping criterion for the Newton-Raphson method in implicit multistep integration algorithms for nonlinear systems of ordinary differential equations
Authors: Liniger W.
Published: July 2002

In the numerical solution of ordinary differential equations, certain implicit linear multistep formulas, i.e. formulas of type ∑

k

j
=0

α
j

x

n
+
j

-
h
∑

k

j
=0

β
j

x

n
+
j

= 0, (1) with

β
k

> ≠ 0, have long been favored because they exhibit strong (fixed-
h
) stability. Lately, it has been observed [1-3] that some special methods of this type are unconditionally fixed-
h
stable with respect to the step size. This property is of great importance for the efficient solution of stiff [4] systems of differential equations, i.e. systems with widely separated time constants. Such special methods make it possible to integrate stiff systems using a step size which is large relative to the rate of change of the fast-varying components of the solution.
Computer-made perspective movies as a scientific and communication tool
Authors: Zajac E. E.
Published: July 2002

It is easy to program the basic transformation required for a perspective drawing. This fact plus the advent of high speed microfilm printers such as the General Dynamics Electronics S-C 4020 makes possible perspective movies as the direct output from a computer. The programming of such a movie is briefly described for studying the angular motions of a satellite containing an attitude control system. In the movie, a domino-shaped box represents the satellite and a sphere with circles of latitude and longitude represents the earth. The cost was approximately three to eight minutes of IBM 7090 time per one minute of movie.
Note on the proof of the non-existence of a phrase structure grammar for ALGOL 60
Authors: Brown Peter J.
Published: July 2002

The proof of the non-existence of a phrase structure grammar for ALGOL 60 by Robert W. Floyd [
Comm. ACM 5
(Sept. 1962)] depends on the assumption that a syntactically correct ALGOL program must be a block. The concept of “program” is defined ambiguously in the ALGOL Report, as pointed out by Naur [1], but it is generally accepted that a program is defined as a self-contained statement. If this definition is taken, Floyd's proof becomes incomplete in that it ignores the fact that the following are syntactically correct ALGOL programs:

begin; end

begin end

〈dummy statement〉
The complexity of acyclic conjunctive queries
Authors: Gottlob Georg , Leone Nicola , Scarcello Francesco
Published: July 2002

This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational databases. By well-known results of Yannakakis[1981], this problem is solvable in polynomial time; its precise complexity, however, has not been pinpointed so far. We show that the problem of evaluating acyclic Boolean conjunctive queries is complete for LOGCFL, the class of decision problems that are logspace-reducible to a context-free language. Since LOGCFL is contained in AC1 and NC2, the evaluation problem of acyclic Boolean conjunctive queries is highly parallelizable. We present a parallel database algorithm solving this problem with alogarithmic number of parallel join operations. The algorithm is generalized to computing the output of relevant classes of non-Boolean queries. We also show that the acyclic versions of the following well-known database and AI problems are all LOGCFL-complete: The Query Output Tuple problem for conjunctive queries, Conjunctive Query Containment, Clause Subsumption, and Constraint Satisfaction. The LOGCFL-completeness result is extended to the class of queries of bounded tree width and to other relevant query classes which are more general than the acyclic queries.
A component model for standardized web-based education
Authors: Anido-Rifón L. , Fernández-Iglesias M. J. , Llamas-Nistal M. , Caeiro-Rodríguez M. , Santos-Gago J. , Rodríguez-Estévez J. S.
Published: July 2002

We present a layered component model to support Web-based collaborative applications. We show how this model lets programmers focus on the particular logic of their applications, avoiding most of the issues related to collaboration, access control, and network management. The proposed model is organized into three layers on top of a foundation composed of commercial-off-the-shelf services and standard Internet protocols. The service level provides a network-transparent communications layer, database access, and distributed data interchange. The component level offers typical collaborative services, like user management, auditing, user-oriented messaging, higher-level events, project management, and a bulletin board. The application level supports actual applications constructed using the services offered by the underlying layers. A Web-based educational application has been developed over this framework to illustrate the process. This tele-education system, which follows the recommendations of the main institutions involved in the learning technology standardization process, is the second contribution presented by the authors.
The simultaneous solution and sensitivity analysis of systems described by ordinary differential equations
Authors: Leis Jorge R. , Kramer Mark A.
Published: July 2002

The methodology for the simultaneous solution of ordinary differential equations and the associated first-order parametric sensitivity equations is presented, and a detailed description of its implementation as a modification of a widely disseminated implicit ODE solver is given. The error control strategy ensures that local error criteria are independently satisfied by both the model and sensitivity solutions. The internal logic effectuated by this implementation is detailed. Numerical testing of the algorithm is reported; results indicate that greater reliability and improved efficiency is offered over other sensitivity analysis methods.
Incremental modular decomposition
Authors: Muller John H. , Spinrad Jeremy
Published: July 2002

Modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. This paper reduces the time needed to find the modular decomposition of a graph from Ω(
n
3
) to Ο(
n
2
). Together with a new algorithm for transitive orientation given in [21], this leads to fast new algorithms for a number of problems in graph recognition and isomorphism, including recognition of comparability graphs and permutation graphs. The new algorithm works by inserting each vertex successively into the decomposition tree, using Ο(
n
) time to insert each vertex.
Efficient and portable combined random number generators
Authors: L'Ecuyer P.
Published: July 2002

In this paper we present an efficient way to combine two or more Multiplicative Linear Congruential Generators (MLCGs) and propose several new generators. The individual MLCGs, making up the proposed combined generators, satisfy stringent theoretical criteria for the quality of the sequence they produce (based on the Spectral Test) and are easy to implement in a portable way. The proposed simple combination method is new and produces a generator whose period is the least common multiple of the individual periods. Each proposed generator has been submitted to a comprehensive battery of statistical tests. We also describe portable implementations, using 16-bit or 32-bit integer arithmetic. The proposed generators have most of the beneficial properties of MLCGs. For example, each generator can be split into many independent generators and it is easy to skip a long subsequence of numbers without doing the work of generating them all.
Updating derived relations: detecting irrelevant and autonomously computable updates
Authors: Blakeley José A. , Coburn Neil , Larson Per-Åke
Published: July 2002

Consider a database containing not only base relations but also stored derived relations (also called materialized or concrete views). When a base relation is updated, it may also be necessary to update some of the derived relations. This paper gives sufficient and necessary conditions for detecting when an update of a base relation cannot affect a derived relation (an irrelevant update), and for detecting when a derived relation can be correctly updated using no data other than the derived relation itself and the given update operation (an autonomously computable update). The class of derived relations considered is restricted to those defined by
PSJ
-expressions, that is, any relational algebra expressions constructed from an arbitrary number of project, select and join operations (but containing no self-joins). The class of update operations consists of insertions, deletions, and modifications, where the set of tuples to be deleted or modified is specified by a selection condition on attributes of the relation being updated.
Investigating the effects of color
Authors: Hoadley E.
Published: July 2002

A laboratory experiment studies the effects of color on a decision maker's ability to extract information from different graphical and tabular presentations. Results indicate color improves time performance for tables, pie charts and bar graphs, and accuracy performance for pie charts and line graphs.
Cross-Cultural Comparative Approaches in Archaeology
Authors: Peregrine Peter N.
Published: July 2002

▪ Abstract  Cross-cultural comparative approaches have been used widely in archaeological research, yet to date none seem to have achieved their full potential. Synchronic cross-cultural comparisons have provided a number of material correlates of behavior, as well as a few causal and noncausal associations that allow behavior to be inferred from material remains. However, large areas of material culture, such as ceramics and lithics, have not yet been subject to extensive comparative analysis, and thus large areas of archaeological research that might be aided by synchronic comparative findings have been left unassisted. Diachronic cross-cultural comparisons have been used extensively to chart and analyze cultural evolution. However, these comparisons are typically based on grab-bag samples and only rarely employ statistics to aid in the discovery or testing of evolutionary patterns. New research tools providing a statistically valid sampling universe and information resources for coding archaeological data are being developed to facilitate cross-cultural comparisons.
FROM VACUOLAR GS-X PUMPS TO MULTISPECIFIC ABC TRANSPORTERS
Authors: Rea Philip A. , Li Ze-Sheng , Lu Yu-Ping , Drozdowicz Yolanda M. , Martinoia Enrico
Published: July 2002

▪ Abstract  While the concept of H+-coupling has dominated studies of energy-dependent organic solute transport in plants for over two decades, recent studies have demonstrated the existence of a group of organic solute transporters, belonging to the ATP-binding cassette (ABC) superfamily, that are directly energized by MgATP rather than by a transmembrane H+-electrochemical potential difference. Originally identified in microbial and animal cells, the ABC superfamily is one of the largest and most widespread protein families known. Competent in the transport of a broad range of substances including sugars, peptides, alkaloids, inorganic anions, and lipids, all ABC transporters are constituted of one or two copies each of an integral membrane sector and cytosolically oriented ATP-binding domain. To date, two major subclasses, the multidrug resistance-associated proteins (MRPs) and multidrug resistance proteins (MDRs) (so named because of the phenotypes conferred by their animal prototypes), have been identified molecularly in plants. However, only the MRPs have been defined functionally. This review therefore focuses on the functional capabilities, energetics, organization, and regulation of the plant MRPs. Otherwise known as GS-X pumps, or glutathione-conjugate or multispecific organic anion Mg2+-ATPases, the MRPs are considered to participate in the transport of exogenous and endogenous amphipathic anions and glutathionated compounds from the cytosol into the vacuole. Encoded by a multigene family and possessing a unique domain organization, the types of processes that likely converge and depend on plant MRPs include herbicide detoxification, cell pigmentation, the alleviation of oxidative damage, and the storage of antimicrobial compounds. Additional functional capabilities might include channel regulation or activity, and/or the transport of heavy metal chelates. The identification of the MRPs, in particular, and the demonstration of a central role for ABC transporters, in general, in plant function not only provide fresh insights into the molecular basis of energy-dependent solute transport but also offer the prospect for manipulating and investigating many fundamental processes that have hitherto evaded analysis at the transport level.
ROOTS IN SOIL: Unearthing the Complexities of Roots and Their Rhizospheres
Authors: McCully Margaret E.
Published: July 2002

▪ Abstract  The root system of a plant is as complicated as the shoot in its diversity, in its reactions with the matrix of substances, and with the myriad organisms that surround it. Laboratory studies blind us to the complexity found by careful study of roots in soil. This complexity is illustrated in the much-studied corn root system, covering the changes along the framework roots: the surface tissues and their interactions with the soil, the water-conducting xylem, whose gradual elaboration dictates the water status of the root. A conspicuous manifestation of the changes is the rhizosheath, whose microflora differs from that on the mature bare zones. The multitude of fine roots is the most active part of the system in acquiring water and nutrients, with its own multitude of root tips, sites of intense chemical activity, that strongly modify the soil they contact, mobilize reluctant ions, immobilize toxic ions, coat the soil particles with mucilage, and select the microflora.
CIRCUMSTELLAR PHOTOCHEMISTRY
Authors: Glassgold A. E.
Published: July 2002

▪ Abstract  The cooling flows or winds from evolved stars are ideal for the formation of molecules and dust. The main location of molecular synthesis is the outer circumstellar envelope, where UV radiation from the interstellar medium penetrates the envelope and, by photodissociating parent molecules, produces the high-energy radicals and ions that activate gas-phase neutral and ion-molecule chemistry. After introducing relevant observational results and theoretical ideas, the salient aspects of the photochemical model are described. The primary application is to the nearby C star, IRC + 10216, where 50 or more circumstellar molecules have been detected. Recent interferometer maps, with resolution approaching 1′′, provide the means to verify the main ideas of the model and to indicate directions for its improvement.
Observations of Brown Dwarfs
Authors: Basri Gibor
Published: July 2002

▪ Abstract  The brown dwarfs occupy the gap between the least massive star and the most massive planet. They begin as dimly stellar in appearance and experience fusion (of at least deuterium) in their interiors. But they are never able to stabilize their luminosity or temperature and grow ever fainter and cooler with time. For that reason, they can be viewed as a constituent of baryonic “dark matter.” Indeed, we currently have a hard time directly seeing an old brown dwarf beyond 100 pc. After 20 years of searching and false starts, the first confirmed brown dwarfs were announced in 1995. This was due to a combination of increased sensitivity, better search strategies, and new means of distinguishing substellar from stellar objects. Since then, a great deal of progress has been made on the observational front. We are now in a position to say a substantial amount about actual brown dwarfs. We have a rough idea of how many of them occur as solitary objects and how many are found in binary systems. We have obtained the first glimpse of atmospheres intermediate in temperature between stars and planets, in which dust formation is a crucial process. This has led to the proposal of the first new spectral classes in several decades and the need for new diagnostics for classification and setting the temperature scale. The first hints on the substellar mass function are in hand, although all current masses depend on models. It appears that numerically, brown dwarfs may well be almost as common as stars (though they appear not to contain a dynamically interesting amount of mass).
Herbig-Haro Flows: Probes of Early Stellar Evolution
Authors: Reipurth Bo , Bally John
Published: July 2002

▪ Abstract  Outflow activity is associated with all stages of early stellar evolution, from deeply embedded protostellar objects to visible young stars. Herbig-Haro (HH) objects are the optical manifestations of this powerful mass loss. Analysis of HH flows, and in particular of the subset of highly collimated HH jets, provides indirect but important insights into the nature of the accretion and mass-loss processes that govern the formation of stars. The recent recognition that HH flows may attain parsec-scale dimensions opens up the possibility of partially reconstructing the mass-ejection history of the newly born driving sources and, therefore, their mass-accretion history. Furthermore, HH flows are astrophysical laboratories for the analysis of shock structures, of hydrodynamics in collimated flows, and of their interaction with the surrounding environment. HH flows may be an important source of turbulence in molecular clouds. Recent technological developments have enabled detailed observations of outflows from young stars at near-infrared, mid-infrared, submillimeter, millimeter, and centimeter wavelengths, providing a comprehensive picture of the outflow phenomenon of young stars.
Sterols and Isoprenoids: Signaling Molecules Derived from the Cholesterol Biosynthetic Pathway
Authors: Edwards Peter A. , Ericsson Johan
Published: July 2002

▪ Abstract  Compounds derived from the isoprenoid/cholesterol biosynthetic pathway have recently been shown to have novel biological activities. These compounds include certain sterols, oxysterols, farnesol, and geranylgeraniol, as well as the diphosphate derivatives of isopentenyl, geranyl, farnesyl, geranylgeranyl, and presqualene. They regulate transcriptional and post-transcriptional events that in turn affect lipid synthesis, meiosis, apoptosis, developmental patterning, protein cleavage, and protein degradation.
Instrumentation for the Genome Project
Authors: Jaklevic J. M. , Garner H. R. , Miller G. A.
Published: July 2002

▪ Abstract  Much of the recent rapid progress in large-scale genomic sequencing has been driven by the dramatic improvements both in the area of biological protocols and in the availability of improved laboratory instrumentation and automation platforms. We discuss recent developments in the area of bioinstrumentation that are contributing to the current revolution in genetic analysis. Examples of systems for laboratory automation are described together with specific single-purpose instruments. Emphasis is placed on those tools that are contributing significantly to the scale-up of genomic mapping and sequencing efforts. In addition, we present a selection of more advanced measurement techniques and instrumentation developments that are likely to contribute significantly to future advances in sequencing and genome analysis.
STRUCTURE AND CONFORMATION OF COMPLEX CARBOHYDRATES OF GLYCOPROTEINS, GLYCOLIPIDS, AND BACTERIAL POLYSACCHARIDES
Authors: Bush C. Allen , Martin-Pastor Manuel , Imbery Anne
Published: July 2002

▪ Abstract  For nuclear magnetic resonance determinations of the conformation of oligosaccharides in solution, simple molecular mechanics calculations and nuclear Overhauser enhancement measurements are adequate for small oligosaccharides that adopt single, relatively rigid conformations. Polysaccharides and larger or more flexible oligosaccharides generally require additional types of data, such as scalar and dipolar coupling constants, which are most conveniently measured in 13C-enriched samples. Nuclear magnetic resonance relaxation data provide information on the dynamics of oligosaccharides, which involves several different types of internal motion. Oligosaccharides complexed with lectins and antibodies have been successfully studied both by X-ray crystallography and by nuclear magnetic resonance spectroscopy. The complexes have been shown to be stabilized by a combination of polar hydrogen bonding interactions and van der Waals attractions. Although theoretical calculations of the conformation and stability of free oligosaccharides and of complexes with proteins can be carried out by molecular mechanics methods, the role of solvent water for these highly polar molecules continues to present computational problems.
Structure and Function of Lipid-DNA Complexes for Gene Delivery
Authors: Chesnoy S. , Huang L.
Published: July 2002

▪ Abstract  Owing to the rapid development of in vivo applications for non-viral gene delivery vectors, it is necessary to have a better understanding of how the structure-activity relationships of these lipid-DNA complexes are affected by their environment. Indeed, research in gene therapy first focused on in vitro cell culture studies to determine the mechanisms involved in the delivery of DNA into the cell. New biophysical techniques such as electron microscopy and X-ray diffraction have been developed to discern the structure of the lipid-DNA complex. However, further studies have revealed discrepancies between optimal lipid-DNA formulations for in vitro transfection and for in vivo administration of these vectors. Furthermore, some immune stimulatory effects have been associated with in vivo lipid-DNA administration. This review summarizes the current state of knowledge on in vitro and in vivo lipid-DNA complex transfections. New prospects of vectors for in vivo gene transfer are also discussed.
SIGNALING TO THE ACTIN CYTOSKELETON
Authors: Schmidt Anja , Hall Michael N.
Published: July 2002

▪ Abstract  The actin cytoskeleton is a highly dynamic network composed of actin polymers and a large variety of associated proteins. The main functions of the actin cytoskeleton are to mediate cell motility and cell shape changes during the cell cycle and in response to extracellular stimuli, to organize the cytoplasm, and to generate mechanical forces within the cell. The reshaping and functions of the actin cytoskeleton are regulated by signaling pathways. Here we broadly review the actin cytoskeleton and the signaling pathways that regulate it. We place heavy emphasis on the yeast actin cytoskeleton.
Continuous Free Oscillations: Atmosphere-Solid Earth Coupling
Authors: Tanimoto Toshiro
Published: July 2002

▪ Abstract  In 1997, after almost forty years since the initial attempt by Benioff et al (1959) , continuous free oscillations of the Earth were discovered. Spheroidal fundamental modes between 2 and 7 millihertz are excited continuously with acceleration amplitudes of about 0.3–0.5 nanogals. The signal is now commonly found in virtually all data recorded by STS-1 type broadband seismometers at quiet sites. Seasonal variation in amplitude and the existence of two coupled modes between the atmosphere and the solid Earth support that these oscillations are excited by the atmosphere. Stochastic excitation due to atmospheric turbulence is a favored mechanism, providing a good match between theory and data. The atmosphere has ample energy to support this theory because excitation of these modes require only 500–10000 W whereas the atmosphere contains about 1017 W of kinetic energy. An application of this phenomenon includes planetary seismology, because other planets may be oscillating owing to atmospheric excitation. The interior structure of planets could be learned by determining the eigenfrequencies in the continuous free oscillations. It is especially attractive to pursue this idea for tectonically quiet planets, since quakes may be too infrequent to be recorded by seismic instruments.
PHYLOGENY AND EVOLUTION OF HOST-PARASITOID INTERACTIONS IN HYMENOPTERA
Authors: Whitfield J. B.
Published: July 2002

▪ Abstract  Recent studies of hymenopteran phylogeny using both comparative morphology and DNA sequence data have greatly enhanced our understanding of the evolution of that order. Resulting phylogenetic hypotheses make possible more rigorous investigations of the evolution of various biological life-styles, among them the parasitoid habit. This paper reviews the current findings from higher-taxon phylogenetic analyses of the order. A “consensus” phylogeny derived from these findings is used to trace the most likely evolutionary pathways leading to the current diversity of parasitoid habits. Taxa and biological phenomena for which our current understanding is fragmentary are highlighted. Based on current evidence, it appears that parasitism arose, from mycophagous ancestors, a single time within the order. Many subsequent elaborations of the parasitic mode of life (e.g. endoparasitism, secondary phytophagy, etc) apparently evolved independently more than once.
Polyene hydrocarbons and epoxides: A Second Major Class of Lepidopteran Sex Attractant Pheromones
Authors: Millar Jocelyn G.
Published: July 2002

▪ Abstract  Polyene hydrocarbons and epoxides are used as pheromone components and sex attractants by four macrolepidopteran families: the Geometridae, Noctuidae, Arctiidae, and Lymantriidae. They constitute a second major class of lepidopteran pheromones, different from the C10-C18 acetates, alcohols, and aldehydes commonly found in other species. They are biosynthesized from diet-derived linoleic or linolenic acids and are characterized by C17-C23 straight chains, 1-3 cis double bonds separated by methylene groups, and 0, 1, or 2 epoxide functions. Pheromone blends are created from components with different chain lengths, numbers of double bonds, and functional groups, or from mixtures of epoxide regioisomers or enantiomers, with several examples of synergism between enantiomers. Behavioral antagonists also limit interspecific attraction, with numerous examples of antagonism by enantiomers. This review summarizes the taxonomic distribution, mechanisms used to generate unique pheromone blends, and the identification, synthesis, and biosynthesis of these compounds.
SPECIESTRAITS ANDENVIRONMENTALCONSTRAINTS: Entomological Research and the History of Ecological Theory
Authors: Statzner Bernhard , Hildrew Alan G. , Resh Vincent H.
Published: July 2002

▪ Abstract  The role that entomology has played in the historical (1800s–1970s) development of ecological theories that match species traits with environmental constraints is reviewed along three lineages originating from the ideas of a minister (Malthus TR. 1798. An Essay on the Principle of Population. London: Johnson) and a chemist (Liebig J. 1840. Die Organische Chemie in ihrer Anwendung auf Agricultur und Physiologie. Braunschweig: Vieweg). Major developments in lineage 1 focus on habitat as a filter for species traits, succession, nonequilibrium and equilibrium conditions, and generalizations about the correlation of traits to environmental constraints. In lineage 2, we trace the evolution of the niche concept and focus on ecophysiological traits, biotic interactions, and environmental conditions. Finally, we describe the conceptual route from early demographic studies of human and animal populations to the r-K concept in lineage 3. In the 1970s, the entomologist Southwood merged these three lineages into the “habitat templet concept” (Southwood TRE. 1977. J. Anim. Ecol. 46:337–65), which has stimulated much subsequent research in entomology and general ecology. We conclude that insects have been a far more important resource for the development of ecological theory than previously acknowledged.
Homogeneous Dynamos in Planetary Cores and in the Laboratory
Authors: Busse F. H.
Published: July 2002

▪ Abstract  New developments have occurred in recent years in the field of dynamo theory. The increase in computer capacity has permitted simulations of convection-driven dynamos in rotating spherical fluid shells in parameter ranges much closer to those of the Earth's core than has been possible before. The progress in handling flows of liquid sodium in large containers, on the other hand, has opened opportunities for realizations of homogeneous dynamos in the laboratory. These developments will lead to a deeper understanding of the origin of magnetic fields in planets and in stars.
G.K. BATCHELOR AND THEHOMOGENIZATION OFTURBULENCE
Authors: Moffatt H.K.
Published: July 2002

▪ Abstract  This essay is based on the G.K. Batchelor Memorial Lecture that I delivered in May 2000 at the Institute for Theoretical Physics (ITP), Santa Barbara, where two parallel programs on Turbulence and Astrophysical Turbulence were in progress. It focuses on George Batchelor's major contributions to the theory of turbulence, particularly during the postwar years when the emphasis was on the statistical theory of homogeneous turbulence. In all, his contributions span the period 1946–1992 and are for the most part concerned with the Kolmogorov theory of the small scales of motion, the decay of homogeneous turbulence, turbulent diffusion of a passive scalar field, magnetohydrodynamic turbulence, rapid distortion theory, two-dimensional turbulence, and buoyancy-driven turbulence.
VIVE LA DIFFÉRENCE: Males vs Females in Flies vs Worms
Authors: Cline Thomas W. , Meyer Barbara J.
Published: July 2002

▪ Abstract  For 600 million years, the two best-understood metazoan species, the nematode Caenorhabditis elegans and the fruit fly Drosophila melanogaster, have developed independent strategies for solving a biological problem faced by essentially all metazoans: how to generate two sexes in the proper proportions. The genetic program for sexual dimorphism has been a major focus of research in these two organisms almost from the moment they were chosen for study, and it may now be the best-understood general aspect of their development. In this review, we compare and contrast the strategies used for sex determination (including dosage compensation) between “the fly” and “the worm” and the way this understanding has come about. Although no overlap has been found among the molecules used by flies and worms to achieve sex determination, striking similarities have been found in the genetic strategies used by these two species to differentiate their sexes.
ASSESSMENT OF BACTERIAL PATHOGENESIS BY ANALYSIS OF GENE EXPRESSION IN THE HOST
Authors: Mahan Michael J. , Heithoff Douglas M. , Sinsheimer Robert L. , Low David A.
Published: July 2002

▪ Abstract  A number of techniques have been developed to assess the expression of microbial virulence genes within the host (in vivo). These studies have shown that bacteria employ a wide variety of mechanisms to coordinately regulate the expression of these genes during infection. Two tenets have emerged from these studies: bacterial adaptation responses are critical to growth within the host, and interactions between microorganisms and the microenvironments of their hosts cannot be revealed from in vitro studies alone. Results that support these tenets include (i) the prevalent class of in vivo expressed genes are involved in adaptation to environmental stresses, (ii) pathogens recovered from host tissues (versus laboratory growth) are often more resistant to host killing mechanisms, and (iii) virulence gene expression can differ in the animal compared to laboratory media. Thus, pathogenicity comprises the unique ability to adapt to the varied host milieus encountered as the infection proceeds.