bluuebunny/crossref_metadata_2025 huggingface dataset:
The impact on retrieval effectiveness of skewed frequency distributions
Authors: Sanderson Mark , Van Rijsbergen C. J.
Published: July 2002

We present an analysis of word senses that provides a fresh insight
into the impact of word ambiguity on retrieval effectiveness with potential broader implications for other processes of information retrieval. Using a methodology of forming artifically ambiguous words, known as pseudowords, and through reference to other researchers' work, the analysis illustrates that the distribution of the frequency of occurrance of the senses of a word plays a strong role in ambiguity's impact of effectiveness. Further investigation shows that this analysis may also be applicable to other processes of retrieval, such as Cross Language Information Retrieval, query expansion, retrieval of OCR'ed texts, and stemming. The analysis appears to provide a means of explaining, at least in part, reasons for the processes' impact (or lack of it) on effectiveness.
OOPM/RT
Authors: Lee Kangsun , Fishwick Paul A.
Published: July 2002

When we build a model of real-time systems, we need ways of representing the knowledge about the system and also time requirements for simulating the model. Considering these different needs, our question is “How can we determine the optimal model that simulates the system by a given deadline while still producing valid outputs at an acceptable level of detail?” We have designed OOPM/RT (Object-Oriented Physical Modeler for Real-Time Simulation) methodology. The OOPM/RT framework has three phases: (1) Generation of multimodels in OOPM using both structural and behavioral abstraction techniques, (2) Generation of AT (Abstraction Tree) which organizes the multimodels based on the abstraction relationship to facilitate the optimal model selection process, and (3) Selection of the optimal model that guarantees the deliver simulation results by the given amount of time. A more-detailed model (low abstraction model) is selected when we have enough time to simulate, while a less-detailed model (high abstraction model) is selected when the deadline is immediate. The basic idea of selection is to trade structural information for a faster runtime while minimizing the loss of behavioral information. We propose two possible approaches for the selection: an integer-programming-based approach and a search-based approach. By systematically handling simulation deadlines while minimizing the modeler's interventions, OOPM/RT provides an efficient modeling environment for real-time systems.
Special-purpose processors in theoretical physics
Authors: Pearson Robert B. , Richardson John L. , Toussaint Doug
Published: July 2002

Specially designed processors can provide a method for attacking some of the difficult computational problems facing theoretical physicists.
Transcending the individual human mind—creating shared understanding through collaborative design
Authors: Arias Ernesto , Eden Hal , Fischer Gerhard , Gorman Andrew , Scharff Eric
Published: July 2002

Complex design problems require more knowledge than any single person possesses because the knowledge relevant to a problem is usually distributed among stakeholders. Bringing different and often controversial points of view together to create a shared understanding among these stakeholders can lead to new insights, new ideas, and new artifacts. New media that allow owners of problems to contribute to framing and resolving complex design problems can extend the power of the individual human mind. Based on our past work and study of other approaches, systems, and collaborative and participatory processes, this article identifies challenges we see as the limiting factors for future collaborative human-computer systems. The Envisionment and Discovery Collaboratory (EDC) is introduced as an integrated physical, and computational environment addressing some of these challenges. The vision behind the EDC shifts future development away from the computer as the focal point, toward an emphasis that tries to improve our understanding of the human, social, and cultural system that creates the context for use. This work is based on new conceptual principles that include creating shared understanding among various stakeholders, contextualizing information to the task at hand, and creating objects to think with in collaborative design activities. Although the EDC framework is applicable to different domains; our initial effort has focused on the domain of urban planning (specifically transportation planning) and community development.
Algorithm 802
Authors: Hörmann Wolfgang
Published: July 2002

Different automatic (also called universal or black-box) methods have been suggested to sample from univariate log-concave distributions. Our new automatic algorithm for bivariate log-concave distributions is based on the method of transformed density rejection. In order to construct a hat function for a rejection algorithm the bivariate density is transformed by the logarithm into a concave function. Then it is possible to construct a dominating function by taking the minimum of several tangent planes, which are by exponentiation transformed back into the original scale. The choice of the points of contact is automated using adaptive rejection sampling. This means that points that are rejected by the rejection algorithm can be used as additional points of contact. The article describes the details how this main idea can be used to construct Algorithm ALC2D that can generate random pairs from all bivariate log-concave distributions with known domain, computable density, and computable partial derivatives.
Environment modeling and language universality
Authors: Raimi Richard , Hojati Ramin , Namjoshi Kedar S.
Published: July 2002

In this paper we outline a theory for the
environment-modeling problem
, the problem of abstracting component finite state machines (FSMs)bordering a particular FSM of interest within a network of interacting FSMs. The goal is to lay a theoretical foundation for the automatic state reduction of large FSM networks. We feel this is a prerequisite for the efficient use of many verification techniques. We focus on computing conditions for the
safe removal
of a component FSM in a FSM network, where removal is safe if it preserves a certain well-defined trace equivalence. We present an optimized algorithm for determining
language universality
of a FSM, as well as determining
independence
of a FSM from those of its inputs connected to outputs of neighboring FSMs. These two properties, input independence and language universality, provide the necessary and sufficient conditions for safe removal. In addition, we show how simulation relations can be utilized, both to reduce the cost of computing safe removal and to create an appropriate abstract FSM when safe removal is not possible.
Efficient routability check algorithms for segmented channel routing
Authors: Yang Cheng-Hsing , Chen Sao-Jie , Ho Jan-Ming , Tsai Chia-Chun
Published: July 2002

The segmented channel-routing problem arises in the context of row-based field programmable gate arrays (FPGAs). Since the
K
-segment channel-routing problem is NP-complete for
K
≥ 2, an efficient algorithm using the weighted bipartite-matching approach is developed for this problem. Connections that;form a maximum clique are chosen first to be routed to the segmented channel. Then, another maximum clique of the remained connections is routed until all connections have been processed. In addition, a powerful “unroutability check” algorithm is uniquely proposed to tell whether the horizontal switches in an interval of the segmented channel are sufficient for routing or not. Hence, we can precisely discriminate the routable and the unroutable ones from all the test cases. As shown in the experiments, average discrimination ratios of 98.8% and 99.4% are obtained for the 2-segmentation and 3-segmentation models, respectively. Moreover, when applying our routing algorithm to the analyzed nonunroutable cases, a routing failure ratio of 1.5% is reported for the 2-segmentation model, compared to Zhu and Wong's 5.9%; also, a routing failure ratio of 0.8% (less than their 4.7%) is obtained for the 3-segmentation model. In total, the routing failure ratio of our routing algorithm is less than 21% of Zhu and Wong's.
A practical parallel algorithm for solving band symmetric positive definite systems of linear equations
Authors: Bar-on Ilan
Published: July 2002

We give a practical parallel algorithm for solving band symmetric positive definite systems of linear equations in
O
(
m
* log
n
) time using
nm
/log
n
processors. Here
n
denotes the system size and
m
its bandwidth. Hence, the algorithm is efficient. For tridiagonal systems, the algorithm runs in
O
(log
n
) time using
n
/log
n
processors. Furthermore, an improved version runs in
O
(log
m
log
n
) time using
nm
2
/(log
m
log
n
) processors.
Self-Assessment Procedure XIV
Authors: Devlin Jane P. , Lowell William A. , Alger Anne E.
Published: July 2002

A self-assessment procedure dealing with the legal issues of computing
HYDRA
Authors: Wulf W. , Cohen E. , Corwin W. , Jones A. , Levin R. , Pierson C. , Pollack F.
Published: July 2002

This paper describes the design philosophy of HYDRA—the kernel of an operating system for C.mmp, the Carnegie-Mellon Multi-Mini-Processor. This philosophy is realized through the introduction of a generalized notion of “resource,” both physical and virtual, called an “object.” Mechanisms are presented for dealing with objects, including the creation of new types, specification of new operations applicable to a given type, sharing, and protection of any reference to a given object against improper application of any of the operations defined with respect to that type of object. The mechanisms provide a coherent basis for extension of the system in two directions: the introduction of new facilities, and the creation of highly secure systems.
Signature schemes based on the strong RSA assumption
Authors: Cramer Ronald , Shoup Victor
Published: July 2002

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called strong RSA assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA assumption.
A method for obtaining digital signatures and public-key cryptosystems
Authors: Rivest R. L. , Shamir A. , Adleman L.
Published: July 2002

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences:

Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key.

A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product,
n
, of two large secret prime numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d = 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor,
n
.
A first order approximation to the optimum checkpoint interval
Authors: Young John W.
Published: July 2002

To avoid having to restart a job from the beginning in case of random failure, it is standard practice to save periodically sufficient information to enable the job to be restarted at the previous point at which information was saved. Such points are referred to as checkpoints, and the saving of such information at these points is called checkpointing [1].
A note on the confinement problem
Authors: Lampson Butler W.
Published: July 2002

onfining a program during its execution so that it cannot transmit information to any other program except its caller. A set of examples attempts to stake out the boundaries of the problem. Necessary conditions for a solution are stated and informally justified.
Applications of symbol manipulation in theoretical physics
Authors: Hearn Anthony C.
Published: July 2002

This paper surveys the applications of symbolic computation techniques to problems in theoretical physics. Particular emphasis is placed on applications in quantum electrodynamics where the most activity has occurred.
A multiple-precision division algorithm
Authors: Mifsud Charles J.
Published: July 2002

A generalized division algorithm for use with positive integral operands is presented. Depending upon the algebraic relationship of the first two ciphers of the divisor, one or at most two adjustments to the original divisor and dividend must be performed before the division operation can be initiated. The uniqueness of this method will cause each trial cipher in the quotient to be either equal to or one greater than its final replacement.
Unrecorded magnetic tape for information interchange (9 track—200 and 800 CPI, NRZI and 1600 CPI, P.E.)
Authors: Lynn M. Stuart
Published: July 2002

This proposed American National Standard has been accepted for publication by American National Standards Committee X3, Computers and Information Processing. In order that the final version of the proposed standard reflect the largest public consensus, X3 authorized publication of this document to elicit comment and general public reaction, with the understanding that such a working document is an intermediate result in the standardization process and is subject to change, modification, or withdrawal in part or in whole. Comments should be directed to the X3 Secretary, Business Equipment Manufacturers Association, 1828 L Street, NW, Washington, DC 20036.—C.K.
An algorithm for Filon quadrature
Authors: Chase Stephen M. , Fosdick Lloyd D.
Published: July 2002

An algorithm for Filon quadrature is described. Considerable attention has been devoted to an analysis of the round-off and truncation errors. The algorithm includes an automatic error control feature.
An improved equivalence algorithm
Authors: Galler Bernard A. , Fisher Michael J.
Published: July 2002

An algorithm for assigning storage on the basis of EQUIVALENCE, DIMENSION and COMMON declarations is presented. The algorithm is based on a tree structure, and has reduced computation time by 40 percent over a previously published algorithm by identifying all equivalence classes with one scan of the EQUIVALENCE declarations. The method is applicable in any problem in which it is necessary to identify equivalence classes, given the element pairs defining the equivalence relation.
One-line random number generators and their use in combinations
Authors: Marsaglia George , Bray T. A.
Published: July 2002

Some one-line random number generators, i.e. generators requiring a single FORTRAN instruction are discussed, and some short FORTRAN programs which mix several such generators are described. The aim is to provide methods for incorporating random number generators directly in FORTRAN programs, by means of a few in-line instructions. The advantages are speed (avoiding linkage to and from a subroutine), convenience, and versatility. Anyone wishing to experiment with generators, either using congruential generators by themselves or mixing several generators to provide a composite with potentially better statistical properties than the library generators currently available, may wish to consider some of the simple FORTRAN programs discussed here.
Some basic terminology connected with mechanical languages and their processors
Authors: Gorn Saul
Published: July 2002

The suggestions in this paper are part of the terminology used in work for the University of Pennsylvania's Office of Computer Research and Education. The work is jointly supported by the National Science Foundation
*
and the Air Force Office of Scientific Research.†
Notes on geometric weighted check digit verfication
Authors: Wilson J. G.
Published: July 2002

This note describes a method for utilizing geometric weight modulus 11 checking digits on a computer which does not have either multiplication or division. In addition some attempt has been made to show some limitations of this system.
Machine calculation of moments of a probability distribution
Authors: Lechner J. A.
Published: July 2002

A method is presented for the calculation on a machine of the moments of a probability distribution, necessitating little more than
n
additions and
n
references to memory for each moment, instead of the minimum of
n
multiplication, 2
n
additions, and 2
n
references to memory required by the most straightforward method (where
n
is the number of entries in the probability distribution). The method is directly applicable when a tabulated distribution exists, as when it has been computed by repeated convolution; but in this case it conserves both time and accuracy.
Electronic document addressing
Authors: Ashman Helen
Published: July 2002

The management of electronic document collections is fundamentally different from the management of paper documents. The ephemeral nature of some electronic documents means that the document address (i.e., reference details of the document) can become incorrect some time after coming into use, resulting in references, such as index entries and hypertext links, failing to correctly address the document they describe. A classic case of invalidated references is on the World Wide Web—links that point to a named resource fail when the domain name, file name, or any other aspect of the addressed resource is changed, resulting in the well-known Error 404. Additionally, there are other errors which arise from changes to document collections.

This paper surveys the strategies used both in World Wide Web software and other hypertext systems for managing the integrity of references and hence the integrity of links. Some strategies are
preventative
, not permitting errors to occur; others are
corrective
, discovering references errors and sometimes attempting to correct them; while the last strategy is
adaptive
, because references are calculated on a just-in-time basis, according the current state of the document collection.
Trajectory computation in a problem-oriented language
Authors: MacDonald Clarice
Published: July 2002

A new problem-oriented language,
XYZ
, is being used on an experimental basis for trajectory computation. In the experiment,
XYZ
is compared with FORTRAN to determine the relative advantages of the two systems for use in flight simulation work. The comparison is concerned with the steps of: problem definition, program design, coding, checkout, and production.
A modified inversion procedure for product form of the inverse linear programming codes
Authors: Larsen L. J.
Published: July 2002

This paper describes a new algorithm for the selection of the pivot row in matrix inversion when using the product form of the inverse. This algorithm has been developed for linear programming codes; however, it would be valuable for the inversion of any non-dense matrix.

The procedures described in this paper have been thoroughly tested and have been in operation on the Esso Research and Engineering IBM 7090 computer for nine months. Substantial computer cost savings have been realized because of this procedure.
A guided tour to approximate string matching
Authors: Navarro Gonzalo
Published: July 2002

We survey the current techniques to cope with the problem of string matching that allows errors. This is becoming a more and more relevant issue for many fast growing areas such as information retrieval and computational biology. We focus on online searching and mostly on edit distance, explaining the problem and its relevance, its statistical behavior, its history and current developments, and the central ideas of the algorithms and their complexities. We present a number of experiments to compare the performance of the different algorithms and show which are the best choices. We conclude with some directions for future work and open problems.
Generalized best-first search strategies and the optimality of A*
Authors: Dechter Rina , Pearl Judea
Published: July 2002

This paper reports several properties of heuristic best-first search strategies whose scoring functions ƒ depend on all the information available from each candidate path, not merely on the current cost
g
and the estimated completion cost
h
. It is shown that several known properties of A* retain their form (with the minmax of
f
playing the role of the optimal cost), which helps establish general tests of admissibility and general conditions for node expansion for these strategies. On the basis of this framework the computational optimality of A*, in the sense of never expanding a node that can be skipped by some other algorithm having access to the same heuristic information that A* uses, is examined. A hierarchy of four optimality types is defined and three classes of algorithms and four domains of problem instances are considered. Computational performances relative to these algorithms and domains are appraised. For each class-domain combination, we then identify the strongest type of optimality that exists and the algorithm for achieving it. The main results of this paper relate to the class of algorithms that, like A*, return optimal solutions (i.e., admissible) when all cost estimates are optimistic (i.e.,
h
≤
h
*). On this class, A* is shown to be not optimal and it is also shown that no optimal algorithm exists, but if the performance tests are confirmed to cases in which the estimates are also consistent, then A* is indeed optimal. Additionally, A* is also shown to be optimal over a subset of the latter class containing all
best-first
algorithms that are guided by path-dependent evaluation functions.
Incremental execution of guarded theories
Authors: De Giacomo Giuseppe , Levesque Hector J. , Sardiña Sebastian
Published: July 2002

When it comes to building controllers for robots or agents, high level programming languages like
Golog
and
ConGolog
offer a useful compromise between planning-based approaches and low-level robot programming. However, two serious problems typically emerge in practical implementations of these languages: how to evaluate test in a program efficiently enough in an open-world setting, and how to make appropiate nondeterministic choices while avoiding full lookahead. Recent proposals in the literature suggest that one could tackle the first problem by exploiting sensing information, and tackle the second by specifying the amount of lookahead allowed explicitly in the program. In this paper, we combine these two ideas and demonstrate their power by presenting an interpreter, written in Prolog, for a variant of
Golog
that is suitable for efficiently operating in open-world setting by exploiting sensing and bounded lookahead.
Strongly equivalent logic programs
Authors: Lifschitz Vladimir , Pearce David , Valverde Agustín
Published: July 2002

A logic program Π
1
is said to be equivalent to a logic program Π
2
in the sense of the answer set semantics if Π
1
and Π
2
have the same answer sets. We are interested in the following stronger condition: for every logic program, Π, Π
1
, ∪ Π has the same answer sets as Π
2
∪ Π. The study of strong equivalence is important, because we learn from it how one can simplify a part of a logic program without looking at the rest of it. The main theorem shows that the verification of strong equivalence can be accomplished by cheching the equivalence of formulas in a monotonic logic, called the logic of here-and-there, which is intermediate between classical logic and intuitionistic logic.
Achieving per-flow fair rate allocation in Diffserv
Authors: Li Na , Borrego Marissa , Li San-Qi
Published: July 2002

This article addresses the fundamental issue of providing per-flow fairness. In particular, it focuses on fairness within the Diffserv framework. We propose the Fair Allocation Derivative Estimation (FADE) algorithm for estimating flow fair share in the absence of per-flow information. FADE calculates fair share feedback using a modified quasi-Newton method. This efficient method for estimating fair share provides a more precise model than other existing fairness estimation approaches. As such, it is able to more accurately estimate fair share and quickly converge to the proper rate. The simulation compares FADE to other proposals. The results demonstrate the overall effectiveness of the algorithm.
Application of aboutness to functional benchmarking in information retrieval
Authors: Wong Kam-Fai , Song Dawei , Bruza Peter , Cheng Chun-Hung
Published: July 2002

Experimental approaches are widely employed to benchmark the performance of an information retrieval (IR) system. Measurements in terms of recall and precision are computed as performance indicators. Although they are good at assessing the retrieval effectiveness of an IR system, they fail to explore deeper aspects such as its underlying functionality and explain why the system shows such performance. Recently, inductive (i.e., theoretical) evaluation of IR systems has been proposed to circumvent the controversies of the experimental methods. Several studies have adopted the inductive approach, but they mostly focus on theoretical modeling of IR properties by using some metalogic. In this article, we propose to use inductive evaluation for functional benchmarking of IR models as a complement of the traditional experiment-based performance benchmarking. We define a functional benchmark suite in two stages: the evaluation criteria based on the notion of "aboutness," and the formal evaluation methodology using the criteria. The proposed benchmark has been successfully applied to evaluate various well-known classical and logic-based IR models. The functional benchmarking results allow us to compare and analyze the functionality of the different IR models.
Complexity and expressive power of logic programming
Authors: Dantsin Evgeny , Eiter Thomas , Gottlob Georg , Voronkov Andrei
Published: July 2002

This article surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional logic programming and datalog, but we also mention general logic programming with function symbols. Next to classical results on plain logic programming (pure Horn clause programs), more recent results on various important extensions of logic programming are surveyed. These include logic programming with different forms of negation, disjunctive logic programming, logic programming with equality, and constraint logic programming.
Parallel thinning with two-subiteration algorithms
Authors: Guo Zicheng , Hall Richard W.
Published: July 2002

Two parallel thinning algorithms are presented and evaluated in this article. The two algorithms use two-subiteration approaches: (1) alternatively deleting north and east and then south and west boundary pixels and (2) alternately applying a thinning operator to one of two subfields. Image connectivities are proven to be preserved and the algorithms' speed and medial curve thinness are compared to other two-subiteration approaches and a fully parallel approach. Both approaches produce very thin medial curves and the second achieves the fastest overall parallel thinning.
A critical investigation of recall and precision as measures of retrieval system performance
Authors: Raghavan Vijay , Bollmann Peter , Jung Gwang S.
Published: July 2002

Recall and precision are often used to evaluate the effectiveness of information retrieval systems. They are easy to define if there is a single query and if the retrieval result generated for the query is a linear ordering. However, when the retrieval results are weakly ordered, in the sense that several documents have an identical retrieval status value with respect to a query, some probabilistic notion of precision has to be introduced. Relevance probability, expected precision, and so forth, are some alternatives mentioned in the literature for this purpose. Furthermore, when many queries are to be evaluated and the retrieval results averaged over these queries, some method of interpolation of precision values at certain preselected recall levels is needed. The currently popular approaches for handling both a weak ordering and interpolation are found to be inconsistent, and the results obtained are not easy to interpret. Moreover, in cases where some alternatives are available, no comparative analysis that would facilitate the selection of a particular strategy has been provided. In this paper, we systematically investigate the various problems and issues associated with the use of recall and precision as measures of retrieval system performance. Our motivation is to provide a comparative analysis of methods available for defining precision in a probabilistic sense and to promote a better understanding of the various issues involved in retrieval performance evaluation.
Reliable communication in the presence of failures
Authors: Birman Kenneth P. , Joseph Thomas A.
Published: July 2002

The design and correctness of a communication facility for a distributed computer system are reported on. The facility provides support forfault-tolerant process groupsin the form of a family of reliable multicast protocols that can be used in both local- and wide-area networks. These protocols attain high levels of concurrency, while respecting application-specific delivery ordering constraints, and have varying cost and performance that depend on the degree of ordering desired. In particular, a protocol that enforces causal delivery orderings is introduced and shown to be a valuable alternative to conventional asynchronous communication protocols. The facility also ensures that the processes belonging to a fault-tolerant process group will observe consistent orderings of events affecting the group as a whole, including process failures, recoveries, migration, and dynamic changes to group properties like member rankings. A review of several uses for the protocols in the ISIS system, which supports fault-tolerant resilient objects and bulletin boards, illustrates the significant simplification of higher level algorithms made possible by our approach.
Learnability and the Vapnik-Chervonenkis dimension
Authors: Blumer Anselm , Ehrenfeucht A. , Haussler David , Warmuth Manfred K.
Published: July 2002

Valiant's learnability model is extended to learning classes of concepts defined by regions in Euclidean space

E
n

. The methods in this paper lead to a unified treatment of some of Valiant's results, along with previous results on distribution-free convergence of certain pattern recognition algorithms. It is shown that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned. Using this parameter, the complexity and closure properties of learnable classes are analyzed, and the necessary and sufficient conditions are provided for feasible learnability.
Grand challenges to computation science
Authors: Levin Eugene
Published: July 2002

The Grand Challenges to Computational Science conference held last January attracted over 100 scientists from major universities, national laboratories, and industrial research centers. The author reports some of the highlights of the conference.
Lightweight remote procedure call
Authors: Bershad Brian N. , Anderson Thomas E. , Lazowska Edward D. , Levy Henry M.
Published: July 2002

Lightweight Remote Procedure Call (LRPC) is a communication facility designed and optimized for communication between protection domains on the same machine. In contemporary small-kernel operating systems, existing RPC systems incur an unnecessarily high cost when used for the type of communication that predominates—between protection domains on the same machine. This cost leads system designers to coalesce weakly related subsystems into the same protection domain, trading safety for performance. By reducing the overhead of same-machine communication, LRPC encourages both safety and performance. LRPC combines the control transfer and communication model of capability systems with the programming semantics and large-grained protection model of RPC. LRPC achieves a factor-of-three performance improvement over more traditional approaches based on independent threads exchanging messages, reducing the cost of same-machine communication to nearly the lower bound imposed by conventional hardware. LRPC has been integrated into the Taos operating system of the DEC SRC Firefly multiprocessor workstation.
Efficient ray tracing of volume data
Authors: Levoy Marc
Published: July 2002

Volume rendering
is a technique for visualizing sampled scalar or vector fields of three spatial dimensions without fitting geometric primitives to the data. A subset of these techniques generates images by computing 2-D projections of a colored semitransparent volume, where the color and opacity at each point are derived from the data using local operators. Since all voxels participate in the generation of each image, rendering time grows linearly with the size of the dataset. This paper presents a front-to-back image-order volume-rendering algorithm and discusses two techniques for improving its performance. The first technique employs a pyramid of binary volumes to encode spatial coherence present in the data, and the second technique uses an opacity threshold to adaptively terminate ray tracing. Although the actual time saved depends on the data, speedups of an order of magnitude have been observed for datasets of useful size and complexity. Examples from two applications are given: medical imaging and molecular graphics.
Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
Authors: Orda Ariel , Rom Raphael
Published: July 2002

In this paper the shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered. Algorithms for finding the shortest path and minimum delay under various waiting constraints are presented and the properties of the derived path are investigated. It is shown that if departure time from the source node is unrestricted, then a shortest path can be found that is simple and achieves a delay as short as the most unrestricted path. In the case of restricted transit, it is shown that there exist cases in which the minimum delay is finite, but the path that achieves it is infinite.
British Social Anthropology: A Retrospective
Authors: Spencer Jonathan
Published: July 2002

▪ Abstract  This article reviews the history of British social anthropology, concentrating on the expansion of the discipline in the British university sector since the 1960s. Particular emphasis is placed on the relationship between social anthropology and the main source of its funding, the British government, in particular the Economic and Social Research Council. After a particularly difficult time in the 1980s, social anthropology in the 1990s has grown swiftly. In this period of growth, formerly crucial boundaries—between academic anthropology and practical policy-related research, between “social” and “cultural” anthropology—appear to have withered away. Yet British social anthropology retains much of its distinctive identity, not least because of the peculiar institutional structures, such as the research seminar, in which the social anthropological habitus is reproduced in new generations of researchers.
Critical Discourse Analysis
Authors: Blommaert Jan , Bulcaen Chris
Published: July 2002

▪ Abstract  This paper provides a survey of critical discourse analysis (CDA), a recent school of discourse analysis that concerns itself with relations of power and inequality in language. CDA explicitly intends to incorporate social-theoretical insights into discourse analysis and advocates social commitment and interventionism in research. The main programmatic features and domains of enquiry of CDA are discussed, with emphasis on attempts toward theory formation by one of CDA's most prominent scholars, Norman Fairclough. Another section reviews the genesis and disciplinary growth of CDA, mentions some of the recent critical reactions to it, and situates it within the wider picture of a new critical paradigm developing in a number of language-oriented (sub) disciplines. In this critical paradigm, topics such as ideology, inequality, and power figure prominently, and many scholars productively attempt to incorporate social-theoretical insights into the study of language.
THE FUNCTIONS AND REGULATION OF GLUTATHIONE S-TRANSFERASES IN PLANTS
Authors: Marrs Kathleen A.
Published: July 2002

▪ Abstract  Glutathione S-transferases (GSTs) play roles in both normal cellular metabolism as well as in the detoxification of a wide variety of xenobiotic compounds, and they have been intensively studied with regard to herbicide detoxification in plants. A newly discovered plant GST subclass has been implicated in numerous stress responses, including those arising from pathogen attack, oxidative stress, and heavy-metal toxicity. In addition, plant GSTs play a role in the cellular response to auxins and during the normal metabolism of plant secondary products like anthocyanins and cinnamic acid. This review presents the current knowledge about the functions of GSTs in regard to both herbicides and endogenous substrates. The catalytic mechanism of GST activity as well as the fate of glutathione S-conjugates are reviewed. Finally, a summary of what is known about the gene structure and regulation of plant GSTs is presented.
STRUCTURE AND BIOGENESIS OF THE CELL WALLS OF GRASSES
Authors: Carpita Nicholas C.
Published: July 2002

▪ Abstract  The chemical structures of the primary cell walls of the grasses and their progenitors differ from those of all other flowering plant species. They vary in the complex glycans that interlace and cross-link the cellulose microfibrils to form a strong framework, in the nature of the gel matrix surrounding this framework, and in the types of aromatic substances and structural proteins that covalently cross-link the primary and secondary walls and lock cells into shape. This review focuses on the chemistry of the unique polysaccharides, aromatic substances, and proteins of the grasses and how these structural elements are synthesized and assembled into dynamic and functional cell walls. Despite wide differences in wall composition, the developmental physiology of grasses is similar to that of all flowering plants. Grass cells respond similarly to environmental cues and growth regulators, exhibit the same alterations in physical properties of the wall to allow cell growth, and possess similar patterns of wall biogenesis during the development of specific cell and tissue types. Possible unifying mechanisms of growth are suggested to explain how grasses perform the same wall functions as other plants but with different constituents and architecture.
THE WATER-WATER CYCLE IN CHLOROPLASTS: Scavenging of Active Oxygens and Dissipation of Excess Photons
Authors: Asada Kozi
Published: July 2002

▪ Abstract  Photoreduction of dioxygen in photosystem I (PSI) of chloroplasts generates superoxide radicals as the primary product. In intact chloroplasts, the superoxide and the hydrogen peroxide produced via the disproportionation of superoxide are so rapidly scavenged at the site of their generation that the active oxygens do not inactivate the PSI complex, the stromal enzymes, or the scavenging system itself. The overall reaction for scavenging of active oxygens is the photoreduction of dioxygen to water via superoxide and hydrogen peroxide in PSI by the electrons derived from water in PSII, and the water-water cycle is proposed for these sequences. An overview is given of the molecular mechanism of the water-water cycle and microcompartmentalization of the enzymes participating in it. Whenever the water-water cycle operates properly for scavenging of active oxygens in chloroplasts, it also effectively dissipates excess excitation energy under environmental stress. The dual functions of the water-water cycle for protection from photoinihibition are discussed.
PHOSPHATE ACQUISITION
Authors: Raghothama K. G.
Published: July 2002

▪ Abstract  Phosphorus is one of the major plant nutrients that is least available in the soil. Consequently, plants have developed numerous morphological, physiological, biochemical, and molecular adaptations to acquire phosphate (Pi). Enhanced ability to acquire Pi and altered gene expression are the hallmarks of plant adaptation to Pi deficiency. The intricate mechanisms involved in maintaining Pi homeostasis reflect the complexity of Pi acquisition and translocation in plants. Recent discoveries of multiple Pi transporters have opened up opportunities to study the molecular basis of Pi acquisition by plants. An increasing number of genes are now known to be activated under Pi starvation. Some of these genes may be involved in Pi acquisition, transfer, and signal transduction during Pi stress. This review provides an overview of plant adaptations leading to enhanced Pi acquisition, with special emphasis on recent developments in the molecular biology of Pi acquisition.
PLANT PROTEIN SERINE/THREONINE KINASES: Classification and Functions
Authors: Hardie D. G.
Published: July 2002

▪ Abstract  The first plant protein kinase sequences were reported as recently as 1989, but by mid-1998 there were more than 500, including 175 in Arabidopsis thaliana alone. Despite this impressive pace of discovery, progress in understanding the detailed functions of protein kinases in plants has been slower. Protein serine/threonine kinases from A. thaliana can be divided into around a dozen major groups based on their sequence relationships. For each of these groups, studies on animal and fungal homologs are briefly reviewed, and direct studies of their physiological functions in plants are then discussed in more detail. The network of protein-serine/threonine kinases in plant cells appears to act as a “central processor unit” (cpu), accepting input information from receptors that sense environmental conditions, phytohormones, and other external factors, and converting it into appropriate outputs such as changes in metabolism, gene expression, and cell growth and division.
SUGAR-INDUCED SIGNAL TRANSDUCTION IN PLANTS
Authors: Smeekens Sjef
Published: July 2002

▪ Abstract  Sugars have important signaling functions throughout all stages of the plant's life cycle. This review presents our current understanding of the different mechanisms of sugar sensing and sugar-induced signal transduction, including the experimental approaches used. In plants separate sensing systems are present for hexose and sucrose. Hexokinase-dependent and -independent hexose sensing systems can further be distinguished. There has been progress in understanding the signal transduction cascade by analyzing the function of the SNF1 kinase complex and the regulatory PRL1 protein. The role of sugar signaling in seed development and in seed germination is discussed, especially with respect to the various mechanisms by which sugar signaling controls gene expression. Finally, recent literature on interacting signal transduction cascades is discussed, with particular emphasis on the ethylene and ABA signal transduction pathways.
GROWTH RETARDANTS: Effects on Gibberellin Biosynthesis and Other Metabolic Pathways
Authors: Rademacher Wilhelm
Published: July 2002

▪ Abstract  Plant growth retardants are applied in agronomic and horticultural crops to reduce unwanted longitudinal shoot growth without lowering plant productivity. Most growth retardants act by inhibiting gibberellin (GA) biosynthesis. To date, four different types of such inhibitors are known: (a) Onium compounds, such as chlormequat chloride, mepiquat chloride, chlorphonium, and AMO-1618, which block the cyclases copalyl-diphosphate synthase and ent-kaurene synthase involved in the early steps of GA metabolism. (b) Compounds with an N-containing heterocycle, e.g. ancymidol, flurprimidol, tetcyclacis, paclobutrazol, uniconazole-P, and inabenfide. These retardants block cytochrome P450-dependent monooxygenases, thereby inhibiting oxidation of ent-kaurene into ent-kaurenoic acid. (c) Structural mimics of 2-oxoglutaric acid, which is the co-substrate of dioxygenases that catalyze late steps of GA formation. Acylcyclohexanediones, e.g. prohexadione-Ca and trinexapac-ethyl and daminozide, block particularly 3ß-hydroxylation, thereby inhibiting the formation of highly active GAs from inactive precursors, and (d) 16,17-Dihydro-GA5 and related structures act most likely by mimicking the GA precursor substrate of the same dioxygenases. Enzymes, similar to the ones involved in GA biosynthesis, are also of importance in the formation of abscisic acid, ethylene, sterols, flavonoids, and other plant constituents. Changes in the levels of these compounds found after treatment with growth retardants can mostly be explained by side activities on such enzymes.
ONE-CARBONMETABOLISM INHIGHERPLANTS
Authors: Hanson Andrew D , Roje Sanja
Published: July 2002

▪ Abstract  The metabolism of one-carbon (C1) units is essential to plants, and plant C1metabolism has novel features not found in other organisms—plus some enigmas. Despite its centrality, uniqueness, and mystery, plant C1biochemistry has historically been quite poorly explored, in part because its enzymes and intermediates tend to be labile and low in abundance. Fortunately, the integration of molecular and genetic approaches with biochemical ones is now driving rapid advances in knowledge of plant C1enzymes and genes. An overview of these advances is presented. There has also been progress in measuring C1metabolite fluxes and pool sizes, although this remains challenging and there are relatively few data. In the future, combining reverse genetics with flux and pool size determinations should lead to quantitative understanding of how plant C1pathways function. This is a prerequisite for their rational engineering.
PLANT MITOCHONDRIA AND OXIDATIVE STRESS: Electron Transport, NADPH Turnover, and Metabolism of Reactive Oxygen Species
Authors: Møller Ian M
Published: July 2002

▪ Abstract  The production of reactive oxygen species (ROS), such as O2− and H2O2, is an unavoidable consequence of aerobic metabolism. In plant cells the mitochondrial electron transport chain (ETC) is a major site of ROS production. In addition to complexes I–IV, the plant mitochondrial ETC contains a non-proton-pumping alternative oxidase as well as two rotenone-insensitive, non-proton-pumping NAD(P)H dehydrogenases on each side of the inner membrane: NDex on the outer surface and NDin on the inner surface. Because of their dependence on Ca2+, the two NDex may be active only when the plant cell is stressed. Complex I is the main enzyme oxidizing NADH under normal conditions and is also a major site of ROS production, together with complex III. The alternative oxidase and possibly NDin(NADH) function to limit mitochondrial ROS production by keeping the ETC relatively oxidized. Several enzymes are found in the matrix that, together with small antioxidants such as glutathione, help remove ROS. The antioxidants are kept in a reduced state by matrix NADPH produced by NADP-isocitrate dehydrogenase and non-proton-pumping transhydrogenase activities. When these defenses are overwhelmed, as occurs during both biotic and abiotic stress, the mitochondria are damaged by oxidative stress.