bluuebunny/crossref_metadata_2025 huggingface dataset:
On semantic issues connected with incomplete information databases
Authors: Lipski Witold
Published: July 2002

Various approaches to interpreting queries in a database with incomplete information are discussed. A simple model of a database is described, based on attributes which can take values in specified attribute domains. Information incompleteness means that instead of having a single value of an attribute, we have a subset of the attribute domain, which represents our knowledge that the actual value, though unknown, is one of the values in this subset. This extends the idea of Codd's null value, corresponding to the case when this subset is the whole attribute domain. A simple query language to communicate with such a system is described and its various semantics are precisely defined. We emphasize the distinction between two different interpretations of the query language—the external one, which refers the queries directly to the real world modeled in an incomplete way by the system, and the internal one, under which the queries refer to the system's information about this world, rather than to the world itself. Both external and internal interpretations are provided with the corresponding sets of axioms which serve as a basis for equivalent transformations of queries. The technique of equivalent transformations of queries is then extensively exploited for evaluating the interpretation of (i.e. the response to) a query.
Optimization of queries with user-defined predicates
Authors: Chaudhuri Surajit , Shim Kyuseok
Published: July 2002

Relational databases provide the ability to store user-defined functions and predicates which can be invoked in SQL queries. When evaluation of a user-defined predicate is relatively expensive, the traditional method of evaluating predicates as early as possible is no longer a sound heuristic. There are two previous approaches for optimizing such queries. However, neither is able to guarantee the optimal plan over the desired execution space. We present efficient techniques that are able to guarantee the choice of an optimal plan over the desired execution space. The
optimization algorithm with complete rank-ordering
improves upon the naive optimization algorithm by exploiting the nature of the cost formulas for join methods and is polynomial in the number of user-defined predicates (for a given number of relations.) We also propose
pruning rules
that significantly reduce the cost of searching the execution space for both the naive algorithm as well as for the optimization algorithm with complete rank-ordering, without compromising optimality. We also propose a
conservative local heuristic
that is simpler and has low optimization overhead. Although it is not always guaranteed to find the optimal plans, it produces close to optimal plans in most cases. We discuss how, depending on application requirements, to determine the algorithm of choice. It should be emphasized that our optimization algorithms handle user-defined selections as well as user-defined join predicates uniformly. We present complexity analysis and experimental comparison of the algorithms.
Effects of locking granularity in a database management system
Authors: Ries Daniel R. , Stonebraker Michael
Published: July 2002

Many database systems guarantee some form of integrity control upon multiple concurrent updates by some form of locking. Some “granule” of the database is chosen as the unit which is individually locked, and a lock management algorithm is used to ensure integrity. Using a simulation model, this paper explores the desired size of a granule. Under a wide variety of seemingly realistic conditions, surprisingly coarse granularity is called for. The paper concludes with some implications of these results concerning the viability of so-called “predicate locking”.
Computer Evaluation of Indexing and Text Processing
Authors: Salton G. , Lesk M. E.
Published: July 2002

Automatic indexing methods are evaluated and design criteria for modern information systems are derived.
Placement of Records on a Secondary Storage Device to Minimize Access Time
Authors: Grossman David D. , Silverman Harvey F.
Published: July 2002

The problem considered is how to place records on a secondary storage device to minimize average retrieval time, based on a knowledge of the probability for accessing the records. Theorems are presented for two limiting cases. A numerical example for an intermediate case is also given.
An Efficient Algorithm for Finding an Irredundant Set Cover
Authors: Kime Charles R. , Batni Ramachendra P. , Russell Jeffrey D.
Published: July 2002

The set covering problem is considered and an efficient procedure for finding an irredundant cover is presented. For an
m
×
n
cover table, the execution time of the procedure is, in the worst case, proportional to
mn
. Methods are suggested for obtaining alternate irredundant covers based on an initially obtained irredundant cover. The basic cost-independent algorithm is heuristically extended to consider costs so that a reduced-cost irredundant cover can be obtained. A summary of some computational experience is presented, which indicates that the procedure is fast and applicable to large problems.
Characterizations of Reducible Flow Graphs
Authors: Hecht M. S. , Ullman J. D.
Published: July 2002

It is established that if
G
is a reducible flow graph, then edge (
n, m
) is backward (a back latch) if and only if either
n = m
or
m
dominates
n
in
G
. Thus, the backward edges of a reducible flow graph are unique.

Further characterizations of reducibility are presented. In particular, the following are equivalent: (a)
G
= (

N, E, n
0

) is reducible. (b) The “dag” of
G
is unique. (A dag of a flow graph
G
is a maximal acyclic flow graph which is a subgraph of
G
.) (c)
E
can be partitioned into two sets
E
1
and
E
2
such that
E
1
forms a dag
D
of
G
and each (
n, m
) in
E
2
has
n = m
or
m
dominates
n
in
G
. (d) Same as (c), except each (
n, m
) in
E
2
has
n = m
or
m
dominates
n
in
D
. (e) Same as (c), except
E
2
is the back edge set of a depth-first spanning tree for
G
. (f) Every cycle of
G
has a node which dominates the other nodes of the cycle.

Finally, it is shown that there is a “natural” single-entry loop associated with each backward edge of a reducible flow graph.
Simulating Stable Stochastic Systems, VI: Quantile Estimation
Authors: Iglehart Donald L.
Published: July 2002

In this paper the author continues his study of the regenerative method for analyzing simulations of stable stochastic systems. The principal concern is to estimate the quantiles of the stationary distribution of a regenerative process. Markov chains in discrete or continuous time and multiple server queues in light traffic provide concrete examples of regenerative processes to which this technique applies. Approximate confidence intervals for these quantiles are derived from appropriate central limit theorems. The method has been applied to three stochastic simulations, and the numerical results are presented.
Estimating tessellation parameter intervals for rational curves and surfaces
Authors: Zheng Jianmin , Sederberg Thomas W.
Published: July 2002

This paper presents a method for determining
a priori
a constant parameter interval for tessellating a rational curve or surface such that the deviation of the curve or surface from its piecewise linear approximation is within a specified tolerance. The parameter interval is estimated based on information about second-order derivatives in the homogeneous coordinates, instead of using affine coordinates directly. This new step size can be found with roughly the same amount of computation as the step size in Cheng [1992], though it can be proven to always be larger than Cheng's step size. In fact, numerical experiments show the new step is typically orders of magnitude larger than the step size in Cheng [1992]. Furthermore, for rational cubic and quartic curves, the new step size is generally twice as large as the step size found by computing bounds on the Bernstein polynomial coefficients of the second derivatives function.
Orthologic and quantum logic
Authors: Rawling J. P. , Selesnick S. A.
Published: July 2002

Motivated by a growing need to understand the computational potential of quantum devices we suggest an approach to the relevant issues via quantum logic and its model theory. By isolating such notions as quantum parallelism and interference within a model-theoretic setting, quite divorced from their customary physical trappings, we seek to lay bare their logical underpinnings and possible computational ramifications.

In the first part of the paper, a brief account of the relevant model theory is given, and some new results are derived. In the second part, we model the simplest classical gate, namely the N-gate, propose a quantization scheme (which translates between classical and quantum models, and from which emerges a logical interpretation of the notion of quantum parallelism), and apply it to the classical N-gate model. A class of physical instantiations of the resulting quantum N-gate model is also briefly discussed.
Transition network grammars for natural language analysis
Authors: Woods W. A.
Published: July 2002

The use of augmented transition network grammars for the analysis of natural language sentences is described. Structure-building actions associated with the arcs of the grammar network allow for the reordering, restructuring, and copying of constituents necessary to produce deep-structure representations of the type normally obtained from a transformational analysis, and conditions on the arcs allow for a powerful selectivity which can rule out meaningless analyses and take advantage of semantic information to guide the parsing. The advantages of this model for natural language analysis are discussed in detail and illustrated by examples. An implementation of an experimental parsing system for transition network grammars is briefly described.
Algorithm 424: Clenshaw-Curtis quadrature [D1]
Authors: Gentleman W. Morven
Published: July 2002

Clenshaw-Curtis quadrature is one of the most effective automatic quadrature schemes available, particularly for integrands with some continuous derivatives. It can also be used for any piecewise continuous integrand, although it is not recommended for integrands with discontinuities.
Performance Evaluation and Monitoring
Authors: Lucas Henry
Published: July 2002

Three major purposes for evaluating the hardware and software
performance of computer systems--selection evaluation, performance
projection, and performance monitoring--are described. Eight
techniques that have been used or suggested for evaluating
performance are discussed. Each of these techniques is rated on its
suitability for the three purposes of evaluation. Recommendations
are made on the most appropriate technique for each evaluation
purpose. These suggestions include the development of a
comprehensive set of synthetic programs on an industry-wide basis
for selection evaluation purposes. Simulation is recommended as the
most suitable technique for performance projection. Finally, a
number of hardware and software monitors are available for
performance monitoring.
The Japanese approach
Authors: Licker Paul S.
Published: July 2002

With a turnover rate among computer programmers of 25%-50% per year, it's time somebody came up with a better way to manage computer professionals. One approach that holds promise is to create a Japanese-style Theory Z atmosphere in the firm, stressing lifetime employment, non-specialized career paths, collective decision-making, and other holistic matters.
An empirical study of insertion and deletion in binary search trees
Authors: Eppinger Jeffrey L.
Published: July 2002

This paper describes an experiment on the effect of insertions and deletions on the path length of unbalanced binary search trees. Repeatedly inserting and deleting nodes in a random binary tree yields a tree that is no longer random. The expected internal path length differs when different deletion algorithms are used. Previous empirical studies indicated that expected internal path length tends to decrease after repeated insertions and asymmetric deletions. This study shows that performing a larger number of insertions and asymmetric deletions actually increases the expected internal path length, and that for sufficiently large trees, the expected internal path length becomes worse than that of a random tree. With a symmetric deletion algorithm, however, the experiments indicate that performing a large number of insertions and deletions decreases the expected internal path length, and that the expected internal path length remains better than that of a random tree.
Computer-Aided complexity classification of combinational problems
Authors: Lageweg B. J. , Lenstra J. K. , Lawler E. L. , Kan A. H. G. Rinnooy
Published: July 2002

We describe a computer program that has been used to maintain a record of the known complexity results for a class of 4536 machine scheduling problems. The input of the program consists of a listing of known “easy” problems and a listing of known “hard” problems. The program employs the structure of the problem class to determine the implications of these results. The output provides a listing of essential results in the form of maximal easy and minimal hard problems as well as listings of minimal and maximal open problems, which are helpful in indicating the direction of future research. The application of the program to a restricted class of 120 single-machine problems is demonstrated. Possible refinements and extensions to other research areas are suggested. It is also shown that the problem of determining the minimum number of results needed to resolve the status of all remaining open problems in a complexity classification such as ours is itself a hard problem.
Thoth, a portable real-time operating system
Authors: Cheriton David R. , Malcolm Michael A. , Melen Lawrence S. , Sager Gary R.
Published: July 2002

Thoth is a real-time operating system which is designed to be portable over a large set of machines. It is currently running on two minicomputers with quite different architectures. Both the system and application programs which use it are written in a high-level language. Because the system is implemented by the same software on different hardware, it has the same interface to user programs. Hence, application programs which use Thoth are highly portable. Thoth encourages structuring programs as networks of communicating processes by providing efficient interprocess communication primitives.
Synchronization with eventcounts and sequencers
Authors: Reed David P. , Kanodia Rajendra K.
Published: July 2002

Synchronization of concurrent processes requires controlling the relative ordering of events in the processes. A new synchronization mechanism is proposed, using abstract objects called eventcounts and sequencers, that allows processes to control the ordering of events directly, rather than using mutual exclusion to protect manipulations of shared variables that control ordering of events. Direct control of ordering seems to simplify correctness arguments and also simplifies implementation in distributed systems. The mechanism is defined formally, and then several examples of its use are given. The relationship of the mechanism to protection mechanisms in the system is explained; in particular, eventcounts are shown to be applicable to situations where confinement of information matters. An implementation of eventcounts and sequencers in a system with shared memory is described.
An algorithm for reduction of operator strength
Authors: Cocke John , Kennedy Ken
Published: July 2002

A simple algorithm which uses an indexed temporary table to perform reduction of operator strength in strongly connected regions is presented. Several extensions, including linear function test replacement, are discussed. These algorithms should fit well into an integrated package of local optimization algorithms.
A comparison of list schedules for parallel processing systems
Authors: Adam Thomas L. , Chandy K. M. , Dickson J. R.
Published: July 2002

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks is studied. Cases where task execution times are deterministic and others in which execution times are random variables are analyzed. It is shown that different algorithms suggested in the literature vary significantly in execution time and that the B-schedule of Coffman and Graham is near-optimal. A dynamic programming solution for the case in which execution times are random variables is presented.
Universal-stability results and performance bounds for greedy contention-resolution protocols
Authors: Andrews Matthew , Awerbuch Baruch , Fernández Antonio , Leighton Tom , Liu Zhiyong , Kleinberg Jon
Published: July 2002

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet).

We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of
stability
—will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet.

Among other things, we show:

(i) There exist simple greedy protocols that are stable for all networks.

(ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable.

(iii) The
n
-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in
n
).

(iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay.

Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.
Some thoughts on parallel processing
Authors: Yarbrough Lynn D.
Published: July 2002

In the past two years or so I have seen a number of papers and heard a number of talks describing the characteristics of (and the wonders inherent in) certain computers like Gamma 60, LARC, H-800, STRETCH, and others. Of course, all these machines share a capacity for parallel asynchronous multiple processing. Now this is a truly marvelous property, especially from the point of view of the common variety of “my-job's-on-the-machine-keep-your-cotton-pickin'-hands-off” programmer.
Computer-drawn flowcharts
Authors: Knuth Donald E.
Published: July 2002

To meet the need for improved documentation of written computer programs, a simple system for effective communication is presented, which has shown great promise. The programmer describes his program in a simple format, and the computer prepares flow charts and other cross-referenced listings from this input. The description can be kept up-to-date easily, and the final output clearly explains the original program. The system has also proved to be a valuable debugging and coding aid.
Logic of English grammar
Authors: Bohnert Herbert G.
Published: July 2002

The logic of English grammar is being investigated by a process of approximative logical synthesis. Beginning with a kernel language which is an alphabetically spelled form of symbolic logic with English-like vocabulary, English-like extensions are constructed simulating selected features of English grammar. For each extended language, an algorithm is given which would permit a computer to make a left-to-right, word-by-word scan of an input sequence, to transform it by stages (as long as the sequence is found to be a well-formed formula of the extended language) into a sentence in the logical grammar of the kernel (or into a logical symbolization if desired). The algorithm thus constitutes simultaneously (1) a recognition grammar of the extended language, i.e., not just formation rules or productions, but a decision method for sentencehood, and (2) a portion of its transformation rules (defining a consequence relation). To date, languages have been constructed simulating the English determiners, (e.g., “every”, “any”, “no”, “a”) and the system of groupers (“either”, “both”, “if”) with precedence-ordered connectives (e.g., “and”, “and furthermore”, “or”, “or else”) by which English achieves the effect of parentheses. Work soon to be reported extends the analysis to relative, general and indefinite pronouns. It is expected that the algorithms will be embodied in computer programs within the year for purposes of comparison with results of human parsers.
Record linkage
Authors: Newcombe Howard B. , Kennedy James M.
Published: July 2002

Special difficulties are encountered in devising reliable systems for searching and updating any large files of documents that must be identified primarily on the basis of names and other personal particulars. The underlying problem is that of making nearly maximum use of items of identifying information that are individually unreliable but that may collectively be of considerable discriminating power. Rules that can be applied generally to name retrieval systems have been developed In a methodological study of the linkage of vital and health records into family groupings for demographic research purposes. These rules are described, and the ways in which information utilization for matching may be optimized are discussed.
Tables of 64-bit Mersenne twisters
Authors: Nishimura Takuji
Published: July 2002

We give new parameters for a Mersenne Twister pseudorandom number gene rator for 64-bit word machines.
Cost profile of a highly assured, secure operating system
Authors: Smith Richard E.
Published: July 2002

The Logical Coprocessing Kernel (LOCK) began as a research project to stretch the state of the art in secure computing by trying to meet or even exceed the “A1” requirements of the Trusted Computer System Evaluation Criteria (TCSEC). Over the span os seven years, the project was transformed into an effort to develop and deploy a product: the Standard Mail Guard (SMG). Since the project took place under a US government contract, the development team needed to maintain detailed records of the time spent on the project. The records from 1987 to 1992 have been combined with information about software code size and error detection. This information has been used to examine the practical impacts of high assurance techniques on a large-scale software development program. Tasks are associated with the A1 formal assurance requirements added approximately 58% to the development cost of security-critical software. In exchange for these costs, the formal assurance tasks (formal specifications, proofs, and specification code correspondence) uncovered 68% of the security flaws detected in LOCK's critical security mechanisms. However, a study of flaw detection during the SMG program found that only 14% of all flaws detected were of the type that could be detected using formal assurance, and that the work of the formal assusrance team only accounted for 19% of all flaws detected. While formal assurance is clearly effective at detecting flaws, its practicality hinges on the degree to which the formally modeled system properties represent all of a system's esential properties.
On ordered languages and the optimization of linear functions by greedy algorithms
Authors: Faigle Ulrich
Published: July 2002

The optimization problem for linear functions on finite languages is studied, and an (almost) complete characterization of those functions for which a primal and a dual greedy algorithm work well with respect to a canonically associated linear programming problem is given. The discussion in this paper is within the framework of ordered languages, and the characterization uses the notion of rank feasibility of a weighting with respect to an ordered language. This yields a common generalization of a sufficient condition, obtained recently by Korte and Lovász for greedoids, and the greedy algorithm for ordered sets in Faigel's paper [6]. Ordered greedoids are considered the appropriate generalization of greedoids, and the connection is established between ordered languages, polygreedoids, and Coxeteroids. Answering a question of Björner, the author shows in particular that a polygreedoid is a Coxeteroid if and only if it is derived from an integral polymatroid.
On the shortest paths between two convex polyhedra
Authors: Balstan Avikam , Sharir Micha
Published: July 2002

The problem of computing the Euclidean shortest path between two points in three-dimensional space bounded by a collection of convex and disjoint polyhedral obstacles having
n
faces altogether is considered. This problem is known to be NP-hard and in exponential time for arbitrarily many obstacles; it can be solved in
O
(
n
2
log
n
) time for a single convex polyhedral obstacle and in polynomial time for any fixed number of convex obstacles. In this paper Mount's technique is extended to the case of
two
convex polyhedral obstacles and an algorithm that solves this problem in time
O
(
n
3
· 2

O
{
α
(
n
)
4
}

log
n
) (where
α
(
n
) is the functional inverse of Ackermann's function, and is thus extremely slowly growing) is presented, thus improving significantly Sharir's previous results for this special case. This result is achieved by constructing a new kind of Voronoi diagram, called
peeper's Voronoi diagram
, which is introduced and analyzed in this paper, and which may be of interest in its own right.
Distributed systems
Authors: Kleinrock Leonard
Published: July 2002

Growth of distributed systems has attained unstoppable momentum. If we better understood how to think about, analyze, and design distributed systems, we could direct their implementation with more confidence.
Cache performance of operating system and multiprogramming workloads
Authors: Agarwal Anant , Hennessy John , Horowitz Mark
Published: July 2002

Large caches are necessary in current high-performance computer systems to provide the required high memory bandwidth. Because a small decrease in cache performance can result in significant system performance degradation, accurately characterizing the performance of large caches is important. Although measurements on actual systems have shown that operating systems and multiprogramming can affect cache performance, previous studies have not focused on these effects. We have developed a program tracing technique called ATUM (Address Tracing Using Microcode) that captures realistic traces of multitasking workloads including the operating system. Examining cache behavior using these traces from a VAX processor shows that both the operating system and multiprogramming activity significantly degrade cache performance, with an even greater proportional impact on large caches. From a careful analysis of the causes of this degradation, we explore various techniques to reduce this loss. While seemingly little can be done to mitigate the effect of system references, multitasking cache miss activity can be substantially reduced with small hardware additions.
Collisions and perception
Authors: O'Sullivan Carol , Dingliana John
Published: July 2002

Level of Detail (LOD) techniques for real-time rendering and related perceptual issues have received a lot of attention in recent years. Researchers have also begun to look at the issue of perceptually adaptive techniques for plausible physical simulations. In this article, we are particularly interested in the problem of realistic collision simulation in scenes where large numbers of objects are colliding and processing must occur in real-time. An interruptible and therefore degradable collision-handling mechanism is used and the perceptual impact of this degradation is explored. We look for ways in which we can optimize the realism of such simulations and describe a series of psychophysical experiments that investigate different factors affecting collision perception, including eccentricity, separation, distractors, causality, and accuracy of physical response. Finally, strategies for incorporating these factors into a perceptually adaptive real-time simulation of large numbers of visually similar objects are presented.
An authorization model for temporal and derived data
Authors: Atluri Vijayalakshmi , Gal Avigdor
Published: July 2002

The term
information portals
refers to Web sites that serve as main providers of focused information, gathered from distributed data sources. Gathering and disseminating information through information portals introduce new security challenges. In particular, the authorization specifications, as well as the granting process, are temporal by nature. Also, more often than not, the information provided by the portal is in fact derived from more than one backend data source. Therefore, any authorization model for information portals should support access control based on temporal characteristics of the data, and also should provide tools to prevent indirect unauthorized access through the use of derived data. In this article we focus our attention on devising such an authorization model. The distinguishing features of this model include: (1) the specification of authorizations based on temporal characteristics of data, and (2) a formal framework to derive authorizations in a consistent and safe manner, based on relationships among data.
Spoken dialogue technology
Authors: McTear Michael F.
Published: July 2002

Spoken dialogue systems allow users to interact with computer-based applications such as databases and expert systems by using natural spoken language. The origins of spoken dialogue systems can be traced back to Artificial Intelligence research in the 1950s concerned with developing conversational interfaces. However, it is only within the last decade or so, with major advances in speech technology, that large-scale working systems have been developed and, in some cases, introduced into commercial environments. As a result many major telecommunications and software companies have become aware of the potential for spoken dialogue technology to provide solutions in newly developing areas such as computer-telephony integration. Voice portals, which provide a speech-based interface between a telephone user and Web-based services, are the most recent application of spoken dialogue technology. This article describes the main components of the technology---speech recognition, language understanding, dialogue management, communication with an external source such as a database, language generation, speech synthesis---and shows how these component technologies can be integrated into a spoken dialogue system. The article describes in detail the methods that have been adopted in some well-known dialogue systems, explores different system architectures, considers issues of specification, design, and evaluation, reviews some currently available dialogue development toolkits, and outlines prospects for future development.
The spatial metaphor for user interfaces: experimental tests of reference by location versus name
Authors: Jones William P. , Dumais Susan T.
Published: July 2002

The enduring dichotomy between spatial and symbolic modes of representation and retrieval acquires an added pragmatic dimension through recent developments in computer-based information retrieval. The standard name-based approach to object reference is now supplemented on some systems by a spatial alternative-often driven by an office or desktop metaphor. Little rigorous evidence is available, however, to support the supposition that spatial memory in itself is more effective than symbolic memory.

The accuracy of spatial versus symbolic reference was assessed in three experiments. In Experiment 1 accuracy of location reference in a location-only filing condition was initially comparable to that in a name-only condition, but deteriorated much more rapidly with increases in the number of objects filed. In Experiment 2 subjects placed objects in a two-dimensional space containing landmarks (drawings of a desk, table, filing cabinets, etc.) designed to evoke an office metaphor, and in Experiment 3 subjects placed objects in an actual, three-dimensional mock office. Neither of these enhancements served to improve significantly the accuracy of location reference, and performance remained below that of a name-only condition in Experiment 1. The results raise questions about the utility of spatial metaphor over symbolic filing and highlight the need for continuing research in which considerations of technological and economic feasibility are balanced by considerations of psychological utility.
An empirical study of the impact of user involvement on system usage and information satisfaction
Authors: Baroudi Jack J. , Olson Margrethe H. , Ives Blake
Published: July 2002

"User involvement" in information system development is generally considered an important mechanism for improving system quality and ensuring successful system implementation. The common assumption that user involvement leads to system usage and/or information satisfaction is examined in a survey of 200 production managers. Alternative models exploring the causal ordering of the three variables are developed and tested via path analysis. The results demonstrate that user involvement in the development of information systems will enhance both system usage and the user's satisfaction with the system. Further, the study provides evidence that the user's satisfaction with the system will lead to greater system usage.
An introduction to Prolog III
Authors: Colmerauer Alain
Published: July 2002

The Prolog III programming language extends Prolog by redefining the fundamental process at its heart: unification. This article presents the specifications of this new language and illustrates its capabilities.
Exploiting fast matrix multiplication within the level 3 BLAS
Authors: Higham Nicholas J.
Published: July 2002

The Level 3 BLAS (BLAS3) are a set of specifications of FORTRAN 77 subprograms for carrying out matrix multiplications and the solution of triangular systems with multiple right-hand sides. They are intended to provide efficient and portable building blocks for linear algebra algorithms on high-performance computers. We describe algorithms for the BLAS3 operations that are asymptotically faster than the conventional ones. These algorithms are based on Strassen's method for fast matrix multiplication, which is now recognized to be a practically useful technique once matrix dimensions exceed about 100. We pay particular attention to the numerical stability of these “fast BLAS3.” Error bounds are given and their significance is explained and illustrated with the aid of numerical experiments. Our conclusion is that the fast BLAS3, although not as strongly stable as conventional implementations, are stable enough to merit careful consideration in many applications.
Drawing antialiased cubic spline curves
Authors: Klassen R. Victor
Published: July 2002

Cubic spline curves have many nice properties that make them desirable for use in comptuer graphics, and the advantages of antialiasing have been known for some years. Yet, only recently has there been any attempt at directly antialiasing spline curves. Parametric spline curves have resisted antialiasing in several ways: single segments may cross or become tangent to themselves. Cusps and small loops are easily missed entirely. Thus, short pieces of the curve cannot necessarily be rendered in isolation. Finding the distance from a pixel center to the curve accurately and efficiently—usually an essential part of antialiasing—is an unsolved problem. The method presented by Lien, Shantz, and Pratt [21] is a good start, although it considers pixel-length pieces of the curve in isolation and lacks robustness in the handling of certain curves. This paper provides an improved method that is more robust, and is able to handle intersections and tangency.
Modeling Ancient Population Structures and Movement in Linguistics
Authors: Nichols Johanna
Published: July 2002

Linguistic population structure is described in terms of language families. Geographical distributions of language families respond to climate, latitude, and economic factors. Characteristic shapes of phylogenetic descent trees for language families reflect particular types, rates, directionalities, and chronologies of spread. Languages move in predictable ways in particular geographical, economic, and social contexts. In this chapter, the linguistic prehistories of four continents are surveyed with regard to linguistic spreads, linguistic diversity, and language family origins.
Doing Good? The Politics and Antipolitics of NGO Practices
Authors: Fisher William F.
Published: July 2002

This review surveys current literature concerned with the growing numbers, changing functions, and intensifying networks of nongovernmental organizations which have had significant impacts upon globalization, international and national politics, and local lives. Studies of these changes illuminate understandings of translocal flows of ideas, knowledge, funding, and people; shed light on changing relationships among citizenry, associations, and the state; and encourage a reconsideration of connections between the personal and the political. Attention is given to the political implications of discourses about NGOs, the complex micropolitics of these associations, and the importance of situating them as evolving processes within complexes of competing and overlapping practices and discourses.
METABOLITE TRANSPORT ACROSS SYMBIOTIC MEMBRANES OF LEGUME NODULES
Authors: Udvardi Michael K. , Day David A.
Published: July 2002

▪ Abstract  Infection of legume roots or stems with soil bacteria of the Rhizobiaceae results in the formation of nodules that become symbiotic nitrogen-fixing organs. Within the infected cells of these nodules, bacteria are enveloped in a membrane of plant origin, called the peribacteroid membrane (PBM), and divide and differentiate to form nitrogen-fixing bacteroids. The organelle-like structure comprised of PBM and bacteroids is termed the symbiosome, and is the basic nitrogen-fixing unit of the nodule. The major exchange of nutrients between the symbiotic partners is reduced carbon from the plant, to fuel nitrogenase activity in the bacteroid, and fixed nitrogen from the bacteroid, which is assimilated in the plant cytoplasm. However, many other metabolites are also exchanged. The metabolic interaction between the plant and the bacteroids is regulated by a series of transporters and channels on the PBM and the bacteroid membrane, and these form the focus of this review.
MIXING IN STARS
Authors: Pinsonneault M.
Published: July 2002

▪ Abstract  Three cases for mixing not present in standard stellar models are presented: Light element depletion in low mass main-sequence stars, deep mixing in massive stars, and deep mixing in low mass giants. The review begins with the mixing indicators and the predictions of standard models. The observational evidence for anomalous mixing is then presented, followed by the physics of mixing outside the standard model. The status of theoretical models that include extra mixing is then examined.
Extracorporeal Tissue Engineered Liver-Assist Devices
Authors: Tzanakakis Emmanouhl S. , Hess Donavon J. , Sielaff Timothy D. , Hu Wei-Shou
Published: July 2002

▪ Abstract  The treatment of acute liver failure has evolved to the current concept of hybrid bioartificial liver (BAL) support, because wholly artificial systems have not proved efficacious. BAL devices are still in their infancy. The properties that these devices must possess are unclear because of our lack of understanding of the pathophysiology of liver failure. The considerations that attend the development of BAL devices are herein reviewed. These considerations include choice of cellular component, choice of membrane component, and choice of BAL system configuration. Mass transfer efficiency plays a role in the design of BAL devices, but the complexity of the systems renders detailed mass transfer analysis difficult. BAL devices based on hollow-fiber bioreactors currently show the most promise, and available results are reviewed herein. BAL treatment is designed to support patients with acute liver failure until an organ becomes available for transplantation. The results obtained to date, in this relatively young field, point to a bright future. The risks of using xenogeneic treatments have yet to be defined. Finally, the experience gained from the past and current BAL systems can be used as a basis for improvement of future BAL technology.
MINOR GROOVE-BINDING ARCHITECTURAL PROTEINS: Structure, Function, and DNA Recognition
Authors: Bewley Carole A. , Gronenborn Angela M. , Clore G. Marius
Published: July 2002

▪ Abstract  To date, high-resolution structures have been solved for five different architectural proteins complexed to their DNA target sites. These include TATA-box–binding protein, integration host factor (IHF), high mobility group I(Y)[HMG I(Y)], and the HMG-box–containing proteins SRY and LEF-1. Each of these proteins interacts with DNA exclusively through minor groove contacts and alters DNA conformation. This paper reviews the structural features of these complexes and the roles they play in facilitating assembly of higher-order protein–DNA complexes and discusses elements that contribute to sequence-specific recognition and conformational changes.
Mechanisms of Synaptic Vesicle Exocytosis
Authors: Lin Richard C. , Scheller Richard H.
Published: July 2002

▪ Abstract  Chemical synaptic transmission serves as the main form of cell to cell communication in the nervous system. Neurotransmitter release occurs through the process of regulated exocytosis, in which a synaptic vesicle releases its contents in response to an increase in calcium. The use of genetic, biochemical, structural, and functional studies has led to the identification of factors important in the synaptic vesicle life cycle. Here we focus on the prominent role of SNARE (soluble NSF attachment protein receptor) proteins during membrane fusion and the regulation of SNARE function by Rab3a, nSec1, and NSF. Many of the proteins important for transmitter release have homologs involved in intracellular vesicle transport, and all forms of vesicle trafficking share common basic principles. Finally, modifications to the synaptic exocytosis pathway are very likely to underlie certain forms of synaptic plasticity and therefore contribute to learning and memory.
TERRESTRIAL ECOSYSTEM FEEDBACKS TO GLOBAL CLIMATE CHANGE
Authors: Lashof Daniel A. , DeAngelo Benjamin J. , Saleska Scott R. , Harte John
Published: July 2002

▪ Abstract  Anthropogenic greenhouse gases are expected to induce changes in global climate that can alter ecosystems in ways that, in turn, may further affect climate. Such climate-ecosystem interactions can generate either positive or negative feedbacks to the climate system, thereby either enhancing or diminishing the magnitude of global climate change. Important terrestrial feedback mechanisms include CO2fertilization (negative feedbacks), carbon storage in vegetation and soils (positive and negative feedbacks), vegetation albedo (positive feedbacks), and peatland methane emissions (positive and negative feedbacks). While the processes involved are complex, not readily quantifiable, and demonstrate both positive and negative feedback potential, we conclude that the combined effect of the feedback mechanisms reviewed here will likely amplify climate change relative to current projections that have not yet adequately incorporated these mechanisms.
BLOOD FLOW IN ARTERIES
Authors: Ku David N.
Published: July 2002

▪ Abstract  Blood flow in arteries is dominated by unsteady flow phenomena. The cardiovascular system is an internal flow loop with multiple branches in which a complex liquid circulates. A nondimensional frequency parameter, the Womersley number, governs the relationship between the unsteady and viscous forces. Normal arterial flow is laminar with secondary flows generated at curves and branches. The arteries are living organs that can adapt to and change with the varying hemodynamic conditions. In certain circumstances, unusual hemodynamic conditions create an abnormal biological response. Velocity profile skewing can create pockets in which the direction of the wall shear stress oscillates. Atherosclerotic disease tends to be localized in these sites and results in a narrowing of the artery lumen—a stenosis. The stenosis can cause turbulence and reduce flow by means of viscous head losses and flow choking. Very high shear stresses near the throat of the stenosis can activate platelets and thereby induce thrombosis, which can totally block blood flow to the heart or brain. Detection and quantification of stenosis serve as the basis for surgical intervention. In the future, the study of arterial blood flow will lead to the prediction of individual hemodynamic flows in any patient, the development of diagnostic tools to quantify disease, and the design of devices that mimic or alter blood flow. This field is rich with challenging problems in fluid mechanics involving three-dimensional, pulsatile flows at the edge of turbulence.
Laboratory Studies of Orographic Effects in Rotating and Stratified Flows
Authors: Boyer Don L. , Davies Peter A.
Published: July 2002

▪ Abstract  This article reviews some aspects of the roles that laboratory experiments have played in the study of orographic effects in the Earth's atmosphere and oceans. The review focuses on, but is not restricted to, physical systems for which the effects of both background stratification and rotation are important. In the past, such laboratory studies have been largely decoupled from attempts to make quantitative comparisons with the results of numerical-model studies or observations from field programs. Rather, they have been used mostly in the important task of better understanding the physics of rotating and stratified flows. Furthermore, most laboratory experiments concerned with the effects of orography on either homogeneous or stratified rotating fluids have considered laminar flows, whereas their counterpart flows in the atmosphere and ocean are turbulent. We argue that laboratory investigations are likely to be more useful in addressing critical environmental problems if the studies are more closely allied with numerical-modeling efforts. The latter, in turn, should be tied to field projects, with the overall objective of improving our ability to predict the behavior of natural systems. In this same spirit, we conclude that far more attention should be given to the laboratory simulation of the turbulent characteristics of natural flows. The availability of rapidly developing technology to acquire and analyze laboratory data provides the capability necessary to support the increasingly important roles that laboratory experiments can play in understanding and predicting the behavior of our natural environment.
MATING-TYPE GENE SWITCHING IN SACCHAROMYCES CEREVISIAE
Authors: Haber James E.
Published: July 2002

▪ Abstract  Saccharomyces cerevisiae can change its mating type as often as every generation by a highly choreographed, site-specific recombination event that replaces one MAT allele with different DNA sequences encoding the opposite allele. The study of this process has yielded important insights into the control of cell lineage, the silencing of gene expression, and the formation of heterochromatin, as well as the molecular events of double-strand break-induced recombination. In addition, MAT switching provides a remarkable example of a small locus control region—the Recombination Enhancer—that controls recombination along an entire chromosome arm.