bluuebunny/crossref_metadata_2025 huggingface dataset:
Probabilistic diagnosis of multiprocessor systems
Authors: Lee Sunggu , Shin Kang Geun
Published: July 2002

This paper critically surveys methods for the automated probabilistic diagnosis of large multiprocessor systems. In recent years, much of the work on system-level diagnosis has focused on probabilistic methods, which can diagnose intermittently faulty processing nodes and can be applied ingeneralsituations ongeneralinterconnection networks. The theory behind the probabilistic diagnosis methods is explained, and the various diagnosis algorithms are described in simple terms with the aid of a running example. The diagnosis methods are compared and analyzed, and a chart is produced, showing the comparative advantages of the various diagnosis algorithms on the basis of several factors important to the probabilistic diagnosis.
Modular stratification and magic sets for Datalog programs with negation
Authors: Ross Kenneth A.
Published: July 2002

A class of “modularly stratified” logic programs is defined. Modular stratification generalizes stratification and local stratification, while allowing programs that are not expressible as stratified programs. For modularly stratified programs, the well-founded semantics coincides with the stable model semantics and makes every ground literal true or false. Modularly stratified programs are weakly stratified, but the converse is false. Unlike some weakly stratified programs, modularly stratified programs can be evaluated in a subgoal-at-a time fashion. An extension of top-down methods with memoing that handles this broader class of programs is presented. A technique for rewriting a modularly stratified program for bottom-up evaluation is demonstrated and extended to include magic-set techniques. The rewritten program, when evaluated bottom-up, gives correct answers according to the well-founded semantics, but much more efficiently than computing the complete well-founded model. A one-to-one correspondence between steps of the extended top-down method and steps during the bottom-up evaluation of the magic-rewritten program is exhibited, demonstrating that the complexity of the two methods is the same. Extensions of modular stratification to other operators such as set-grouping and aggregation, which have traditionally been stratified to prevent semantic difficulties, are discussed.
Decomposition of magic rewriting
Authors: Wang Ke , Zhang Weining , Chau Siu-Cheung
Published: July 2002

The magic rewriting focuses on relevant data but suffers from additional rules, predicates, and tuples that are generated in search for the relevant data. Reducing the arity of predicates can cut down the number of such rules, predicates, and tuples by an exponential factor. In this paper, we consider a subclass of linear single-IDB programs and show that the magic rewriting can be decomposed in such a way that it is applied to only programs having smaller arities and fewer recursive rules, without losing the binding capacity. The decomposed rewriting is shown to be much more efficient than the standard one and amenable to distributed and parallel environments. The considered subclass significantly generalizes recursions previously proposed for efficient implementation. The decomposed rewriting and the standard generalized magic rewriting are extended to multi-binding queries in such a way that data relevant to one binding is not necessarily considered as relevant to other bindings. The work in this paper shows the use of tuple ID as an important technique in optimizing logic programs.
Three logics for branching bisimulation
Authors: De Nicola Rocco , Vaandrager Frits
Published: July 2002

Three temporal logics are introduced that induce on labeled transition systems the same identifications as branching bisimulation, a behavioral equivalence that aims at ignoring invisible transitions while preserving the branching structure of systems. The first logic is an extension of Hennessy-Milner Logic with an “until” operator. The second one is another extension of Hennessy-Milner Logic, which exploits the power of backward modalities. The third logic is CTL* without the next-time operator. A relevant side-effect of the last characterization is that it sets a bridge between the state- and action-based approaches to the semantics of concurrent systems.
Fast simulation of rare events in queueing and reliability models
Authors: Heidelberger Philip
Published: July 2002

This paper surveys efficient techniques for estimating, via simulation, the probabilities of certain rare events in queueing and reliability models. The rare events of interest are long waiting times or buffer overflows in queueing systems, and system failure events in reliability models of highly dependable computing systems. The general approach to speeding up such simulations is to accelerate the occurrence of the rare events by using importance sampling. In importance sampling, the system is simulated using a new set of input probability distributions, and unbiased estimates are recovered by multiplying the simulation output by a likelihood ratio. Our focus is on describing asymptotically optimal importance sampling techniques. Using asymptotically optimal importance sampling, the number of samples required to get accurate estimates grows slowly compared to the rate at which the probability of the rare event approaches zero. In practice, this means that run lengths can be reduced by many orders of magnitude, compared to standard simulation. In certain cases, asymptotically optimal importance sampling results in estimates having bounded relative error. With bounded relative error, only a fixed number of samples are required to get accurate estimates, no matter how rare the event of interest is. The queueing systems studied include simple queues (e.g., GI/GI/1), Jackson networks, discrete time queues with multiple autocorrelated arrival processes that arise in the analysis of Asynchronous Transfer Mode communications switches, and tree structured networks of such switches. Both Markovian and non-Markovian reliability models are treated.
An approach to natural gesture in virtual environments
Authors: Wexelblat Alan
Published: July 2002

This article presents research—an experiment and the resulting prototype—on a method for treating gestural input so that it can be used for multimodal applications, such as interacting with virtual environments. This method involves the capture and use of natural , empty-hand gestures that are made during conventional descriptive utterances. Users are allowed to gesture in a normal continuous manner, rather than being restricted to a small set of discrete gestural commands as in most other systems. The gestures are captured and analyzed into a higher-level description. This description can be used by an application-specific interpreter to understand the gestural input in its proper context. Having a gesture analyzer of this sort enables natural gesture input to any appropriate application.
Algorithm 745: computation of the complete and incomplete Fermi-Dirac integral
Authors: Goano Michele
Published: July 2002

Portable Fortran subroutines computing the Fermi-Dirac integral
F
j
(x) and the incomplete Fermi-Dirac integral
F
j
(x,b) are presented. For the first time a set of series expansions is implemented allowing these special functions to be evaluated efficiently within a prescribed accuracy for real
j
and
x
.
Parallelism in sequential multiprocessor simulation models
Authors: Sellami Hatem , Yalamanchili Sudhakar
Published: July 2002

The design and analysis of multiprocessor simulation models represents a complex and computationally demanding application that is a candidate for parallel simulation. This paper examines the application of conservative parallel discrete event simulation on a set of existing “real-world” models created over the years with no thought given to the parallel execution. These models are based on a subset of Petri Nets known asMarked graphs. The results of the study of the transparent and automatic parallel execution of the simulation of these models will be presented. Focus will be on the amount of inherent parallelism in such models, means of exploiting it, obstacles prohibiting parallelization, and sensitivity to different system and model parameters.
Object orientation in multidatabase systems
Authors: Pitoura Evaggelia , Bukhres Omran , Elmagarmid Ahmed
Published: July 2002

A multidatabase system (MDBS) is a confederation of preexisting distributed, heterogeneous, and autonomous database systems. There has been a recent proliferation of research suggesting the application of object-oriented techniques to facilitate the complex task of designing and implementing MDBSs. Although this approach seems promising, the lack of a general framework impedes any further development. The goal of this paper is to provide a concrete analysis and categorization of the various ways in which object orientation has affected the task of designing and implementing MDBSs.

We identify three dimensions in which the object-oriented paradigm has influenced this task: the general system architecture, the schema architecture, and the heterogeneous transaction management. Then we provide a classification and a comprehensive analysis of the issues related to each of the above dimensions. To demonstrate the applicability of this analysis, we conclude with a comparative review of existing multidatabase systems.
Internal representation and rule development in object-oriented design
Authors: Kim Jinwoo , Lerch F. Javier , Simon Herbert A.
Published: July 2002

This article proposes a cognitive framework describing the software development process in object-oriented design (OOD) as building internal representations and developing rules. Rule development (method construction) is performed in two problem spaces: a rule space and an instance space. Rules are generated, refined, and evaluated in the rule space by using three main cognitive operations: Infer, Derive, and Evoke. Cognitive activities in the instance space are called mental simulations and are used in conjunction with the Infer operation in the rule space. In an empirical study with college students, we induced different representations to the same problem by using problem isomorphs. Initially, subjects built a representation based on the problem description. As rule development proceeded, the initial internal representation and designed objects were refined, or changed if necessary, to correspond to knowledge gained during rule development. Differences in rule development processes among groups created final designs that are radically different in terms of their level of abstraction and potential reusability. The article concludes by discussing the implications of these results for object-oriented design.
Principles and applications of chaotic systems
Authors: Ditto William , Munakata Toshinori
Published: July 2002

There lies a behavior between rigid regularity and randomness based on pure chance. It's called a
chaotic system,
or
chaos
for short [5]. Chaos is all around us. Our notions of physical motion or dynamic systems have encompassed the precise clock-like ticking of periodic systems and the vagaries of dice-throwing chance, but have often been overlooked as a way to account for the more commonly observed chaotic behavior between these two extremes. When we see irregularity we cling to randomness and disorder for explanations. Why should this be so? Why is it that when the ubiquitous irregularity of engineering, physical, biological, and other systems are studied, it is assumed to be random and the whole vast machinery of probability and statistics is applied? Rather recently, however, we have begun to realize that the tools of chaos theory can be applied toward the understanding, manipulation, and control of a variety of systems, with many of the practical applications coming after 1990. To understand why this is true, one must start with a working knowledge of how chaotic systems behave—profoundly, but sometimes subtly different, from the behavior of random systems.
LAPACK-style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs
Authors: Kågström Bo , Poromaa Peter
Published: July 2002

Robust and fast software to solve the generalized Sylvester equation (
AR - LB = C, DR - LE = F
) for unknowns
R
and
L
is presented. This special linear system of equations, and its transpose, arises in computing error bounds for computed eigenvalues and eigenspaces of the generalized eigenvalue problem
S-λT
, in computing deflating subspaces of the same problem, and in computing certain decompositions of transfer matrices arising in control theory. Our contributions are twofold. First, we reorganize the standard algorithm for this problem to use Level 3 BLAS operations, like matrix multiplication, in its inner loop. This speeds up the algorithm by a factor of 9 on an IBM RS6000. Second, we develop and compare several condition estimation algorithms, which inexpensively but accurately estimate the sensitivity of the solution of this linear system.
The chaining approach for software test data generation
Authors: Ferguson Roger , Korel Bogdan
Published: July 2002

Software testing is very labor intensive and expensive and accounts for a significant portion of software system development cost. If the testing process could be automated, the cost of developing software could be significantly reduced. Test data generation in program testing is the process of identifying a set of test data that satisfies a selected testing criterion, such as statement coverage and branch coverage. In this article we present achaining approachfor automated software test data generation which builds on the current theory of execution-oriented test data generation. In the chaining approach, test data are derived based on the actual execution of the program under test. For many programs, the execution of the selected statement may require prior execution of some other statements. The existing methods of test data generation may not efficiently generate test data for these types of programs because they only use control flow information of a program during the search process. The chaining approach uses data dependence analysis to guide the search process, i.e., data dependence analysis automatically identifies statements that affect the execution of the selected statement. The chaining approach uses these statements to form a sequence of statements that is to be executed prior to the execution of the selected statement. The experiments have shown that the chaining approach may significantly improve the chances of finding test data as compared to the existing methods of automated test data generation.
Tabled evaluation with delaying for general logic programs
Authors: Chen Weidong , Warren David S.
Published: July 2002

SLD resolution with negation as finite failure (SLDNF) reflects the procedural interpretation of predicate calculus as a programming language and forms the computational basis for Prolog systems. Despite its advantages for stack-based memory management, SLDNF is often not appropriate for query evaluation for three reasons: (a) it may not terminate due to infinite positive recursion; (b) it may be terminate due to infinite recursion through negation; and (c) it may repeatedly evaluate the same literal in a rule body, leading to unacceptable performance.

We address all three problems for goal-oriented query evaluation of general logic programs by presenting tabled evaluation with delaying, called SLG resolution. It has three distinctive features:

(i) SLG resolution is a partial deduction procedure, consisting of seven fundamental transformations. A query is transformed step by step into a set of answers. The use of transformations separates logical issues of query evaluation from procedural ones. SLG allows an arbitrary computation rule for selecting a literal from a rule body and an arbitrary control strategy for selecting transformations to apply.

(ii) SLG resolution is sound and search space complete with respect to the well-founded partial model for all non-floundering queries, and preserves all three-valued stable models. To evaluate a query under differenc three-valued stable models, SLG resolution can be enhanced by further processing of the answers of subgoals relevant to a query.

(iii) SLG resolution avoids both positive and negative loops and always terminates for programs with the bounded-term-size property. It has a polynomial time data complexity for well-founded negation of function-free programs. Through a delaying mechanism for handling ground negative literals involved in loops, SLG resolution avoids the repetition of any of its derivation steps.

Restricted forms of SLG resolution are identified for definite, locally stratified, and modularly stratified programs, shedding light on the role each transformation plays.
The design of MA48
Authors: Duff I. S. , Reid J. K.
Published: July 2002

We describe the design of a new code for the direct solution of sparse unsymmetric linear systems of equations. The new code utilizes a novel restructuring of the symbolic and numerical phases, which increases speed and saves storage without sacrifice of numerical stability. Other features include switching to full-matrix processing in all phases of the computation enabling the use of all three levels of BLAS, treatment of rectangular or rank-deficient matrices, partial factorization, and integrated facilities for iterative refinement and error estimation.
Concurrent dynamic logic
Authors: Peleg David
Published: July 2002

In this paper concurrent dynamic logic (CDL) is introduced as an extension of dynamic logic tailored toward handling concurrent programs. Properties of CDL are discussed, both on the propositional and first-order level, and the extension is shown to possess most of the desirable properties of DL. Its relationships with the μ-calculus, game logic, DL with recursive procedures, and PTIME are further explored, revealing natural connections between concurrency, recursion, and alternation.
A combinatorial treatment of balancing networks
Authors: Busch Costas , Mavronicolas Marios
Published: July 2002

Balancing networks, originally introduced by Aspnes et al.(Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represent a new class of distributed, low-contention data structures suitable for solving many fundamental multi-processor coordination problems that can be expressed asbalancing problems. In this work, we present a mathematical study of the combinatorial structure of balancing networks, and a variety of its applications.

Our study identifies important combinatorialtransfer parametersof balancing networks. In turn, necessary and sufficient combinatorial conditions are established, expressed in terms of transfer parameters, which precisely characterize many important and well studied classes of balancing networks such ascounting networksandsmoothing networks. We propose these combinatorial conditions to be “balancing analogs” of the well knownZero-One principleholding forsorting networks

Within the combinatorial framework we develop, our first application is in deriving combinatorial conditions, involving the transfer parameters, which precisely delimit the boundary between counting networks and sorting networks.
Eraser
Authors: Savage Stefan , Burrows Michael , Nelson Greg , Sobalvarro Patrick , Anderson Thomas
Published: July 2002

Multithreaded programming is difficult and error prone. It is easy to make a mistake in synchronization that produces a data race, yet it can be extremely hard to locate this mistake during debugging. This article describes a new tool, called Eraser, for dynamically detecting data races in lock-based multithreaded programs. Eraser uses binary rewriting techniques to monitor every shared-monory reference and verify that consistent locking behavior is observed. We present several case studies, including undergraduate coursework and a multithreaded Web search engine, that demonstrate the effectiveness of this approach.
Formal verification in hardware design
Authors: Kern Christoph , Greenstreet Mark R.
Published: July 2002

In recent years, formal methods have emerged as an alternative approach to ensuring the quality and correctness of hardware designs, overcoming some of the limitations of traditional validation techniques such as simulation and testing.

There are two main aspects to the application of formal methods in a design process: the formal framework used to specify desired properties of a design and the verification techniques and tools used to reason about the relationship between a specification and a corresponding implementation. We survey a variety of frameworks and techniques proposed in the literature and applied to actual designs. The specification frameworks we describe include temporal logics, predicate logic, abstraction and refinement, as well as containment between ω-regular languages. The verification techniques presented include model checking, automata-theoretic techniques, automated theorem proving, and approaches that integrate the above methods.

In order to provide insight into the scope and limitations of currently available techniques, we present a selection of case studies where formal methods were applied to industrial-scale designs, such as microprocessors, floating-point hardware, protocols, memory subsystems, and communications hardware.
Parallel methods for integrating ordinary differential equations
Authors: Nievergelt J.
Published: July 2002

This paper is dedicated to the proposition that, in order to take full advantage for real-time computations of highly parallel computers as can be expected to be available in the near future, much of numerical analysis will have to be recast in a more “parallel” form. By this is meant that serial algorithms ought to be replaced by algorithms which consist of several subtasks which can be computed without knowledge of the results of the other subtasks. As an example, a method is proposed for “parallelizing” the numerical integration of an ordinary differential equation, which process, by all standard methods, is entirely serial.
Design of the S system for data analysis
Authors: Becker Richard A. , Chambers John M.
Published: July 2002

S is a language and system for interactive data analysis and graphics. It emphasizes interactive analysis and graphics, ease of use, flexibility, and extensibility. While sharing many characteristics with other statistical systems, S differs significantly in its design goals, its implementation, and the way it is used. This paper presents some of the design concepts and implementation techniques in S and relates these general ideas in computing to the specific design goals for S and to other statistical systems.
Reverse path forwarding of broadcast packets
Authors: Dalal Yogen K. , Metcalfe Robert M.
Published: July 2002

A broadcast packet is for delivery to all nodes of a network. Algorithms for accomplishing this delivery through a store-and-forward packet switching computer network include (1) transmission of separately addressed packets, (2) multidestination addressing, (3) hot potato forwarding, (4) spanning tree forwarding, and (5) source based forwarding. To this list of algorithms we add (6) reverse path forwarding, a broadcast routing method which exploits routing procedures and data structures already available for packet switching. Reverse path forwarding is a practical algorithm for broadcast routing in store-and-forward packet switching computer networks. The algorithm is described as being
practical
because it is not
optimal
according to metrics developed for its analysis in this paper, and also because it can be implemented in existing networks with less complexity than that required for the known alternatives.
A linear space algorithm for computing maximal common subsequences
Authors: Hirschberg D. S.
Published: July 2002

The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadratic time and in linear space.
A cell organized raster display for line drawings
Authors: Jordan B. W. , Barrett R. C.
Published: July 2002

Raster scan computer graphics displays with “real time” character generators have previously been limited to alphanumeric characters. A display is described which extends the capabilities of this organization to include general graphics.

The feasibility of such a display is shown by deriving the minimum number of patterns required in the read only memory of the character generator to synthesize an arbitrary line. The synthesis process does not compromise picture quality, since the resulting dot patterns are identical with those of a conventional raster display. Furthermore, the time constraints of a raster display are shown to be satisfied for a typical design for very complex line drawings.
Simulation of outpatient appointment systems
Authors: Katz Jesse H.
Published: July 2002

An experimental computer program is described which simulates appointment systems employed by outpatient departments of hospitals. Both major kinds of appointment systems—individual and block—can be simulated. The purpose of the Simulator is to enable the user to evaluate the effectiveness of alternative appointment systems in a given clinical environment.
A compiler for analyzing cryptographic protocols using noninterference
Authors: Durante Antonio , Focardi Riccardo , Gorrieri Roberto
Published: July 2002

The Security Process Algebra (SPA) is a CCS-like specification languag e where actions belong to two different levels of confidentiality. It has been used to define several noninterference-like security properties whose verification has been automated by the tool CoSeC. In recent years, a method for analyzing security protocols using SPA and CoSeC has been developed. Even if it has been useful in analyzing small security protocols, this method has shown to be error-prone, as it requires the protocol description and its environment to be written by hand. This problem has been solved by defining a protocol specification language more abstract than SPA, called VSP, and a compiler CVS that automatically generates the SPA specification for a given protocol described in VSP. The VSP/CVS technology is very powerful, and its usefulness is shown with some case studies: the Woo-Lam one-way authentication protocol, for which a new attack to authentication is found, and the Wide Mouthed Frog protocol, where different kinds of attack are detected and analyzed.
Methods for analyzing data from computer simulation experiments
Authors: Naylor Thomas H. , Wertz Kenneth , Wonnacott Thomas H.
Published: July 2002

This paper addresses itself to the problem of analyzing data generated by computer simulations of economic systems. We first turn to a hypothetical firm, whose operation is represented by a single-channel, multistation queueing model. The firm seeks to maximize total expected profit for the coming period by selecting one of five operating plans, where each plan incorporates a certain marketing strategy, an allocation of productive inputs, and a total cost.

The results of the simulated activity under each plan are subjected to anF-test, two multiple comparison methods, and a multiple ranking method. We illustrate, compare, and evaluate these techniques. The paper adopts the position that the particular technique of analysis (possibly not any one of the above) chosen by the experimenter should be an expression of his experimental objective: TheF-test tests the homogeneity of the plans; multiple comparison methods quantify their differences; and multiple ranking methods directly identify the one best plan or best plans.
On programming of arithmetic operations
Authors: Ershov A. P.
Published: July 2002

The concepts used without explanation are taken from [1].
Efficient reasoning
Authors: Greiner Russell , Darken Christian , Santoso N. Iwan
Published: July 2002

Many tasks require “reasoning”—i.e., deriving conclusions from a corpus of explicitly stored information—to solve their range of problems. An ideal reasoning system would produce all-and-only thecorrectanswers to every possible query, produce answers that are asspecificas possible, beexpressiveenough to permit any possible fact to be stored and any possible query to be asked, and be (time)efficient. Unfortunately, this is provably impossible: as correct and precise systems become more expressive, they can become increasingly inefficient, or even undecidable. This survey first formalizes these hardness results, in the context of both logic- and probability-based reasoning, then overviews the techniques now used to address, or at least side-step, this dilemma.
A simple universal generator for continuous and discrete univariate T-concave distributions
Authors: Leydold Josef
Published: July 2002

We use inequalities to design short universal algorithms that can be used to generate random variates from large classes of univariate continuous or discrete distributions (including all log-concave distributions). The expected time is uniformly bounded over all these distributions. The algorithms can be implemented in a few lines of high-level language code. In opposition to other black-box algorithms hardly any setup step is required, and thus it is superior in the changing-parameter case.
Spatiotemporal sensitivity and visual attention for efficient rendering of dynamic environments
Authors: Yee Hector , Pattanaik Sumanita , Greenberg Donald P.
Published: July 2002

We present a method to accelerate global illumination computation in prerendered animations by taking advantage of limitations of the human visual system. A spatiotemporal error tolerance map, constructed from psychophysical data based on velocity dependent contrast sensitivity, is used to accelerate rendering. The error map is augmented by a model of visual attention in order to account for the tracking behavior of the eye. Perceptual acceleration combined with good sampling protocols provide a global illumination solution feasible for use in animation. Results indicate an order of magnitude improvement in computational speed.
On knowledge-based programming with sensing in the situation calculus
Authors: Reiter Ray
Published: July 2002

We consider a class of knowledge-based Golog programs with sense actions. These programs refer explicitly to an agent's knowledge, and are designed to execute on-line, and under a dynamic closed-world assumption on knowledge. On-line execution of sense actions dynamically updates the background axioms with sentences asserting knowledge of the sense actions' outcomes. We formalize what all this might mean, and show that under suitable assumptions the knowledge modality in such programs can be implemented by provability. This leads to an on-line Golog interpreter for such programs, which we demonstrate on a knowledge-based program with sensing for the blocks world.
Stability of binary exponential backoff
Authors: Goodman Jonathan , Greenberg Albert G. , Madras Neal , March Peter
Published: July 2002

Binary exponential backoff is a randomized protocol for regulating transmissions on a multiple-access broadcast channel. Ethernet, a local-area network, is built upon this protocol. The fundamental theoretical issue is stability: Does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough? It is assumedn≥ 2 stations share the channel, each having an infinite buffer where packets accumulate while the station attempts to transmit the first from the buffer. Here, it is established that binary exponential backoff is stable if the sum of the arrival rates is sufficiently small. Detailed results are obtained on which rates lead to stability whenn= 2 stations share the channel. In passing, several other results are derived bearing on the efficiency of the conflict resolution process. Simulation results are reported that, in particular, indicate alternative retransmission protocols can significantly improve performance.
A wider view of business process reengineering
Authors: Grant Delvin
Published: July 2002

Technology alone does not enable organizational change.
A collaborative approach to ontology design
Authors: Holsapple Clyde W. , Joshi K. D.
Published: July 2002

Creating a general ontology characterizing the conduct of knowledge management.
Sort sets in the relational model
Authors: Ginsburg Seymour , Hull Richard
Published: July 2002

The notion ofsort setis introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways to enhance the efficiency of an implemented database. A characterization of when order dependency implies the existence of sort sets in a database is presented, along with several corollaries concerning complexity, Armstrong relations, and cliques of certain graphs. Sort-set dependencies are then introduced. A (finite) sound and complete set of inference rules for sort-set dependencies is presented, as well as a proof that there is no such set for functional and sort-set dependencies taken together. Deciding logical implication for sort-set dependencies is proved to be polynomial, but if functional dependencies are included the problem is co-NP-complete. Each set of sort-set and functional dependencies is shown to have an Armstrong relation. A natural generalization of Armstrong relation, here calledseparator, is given and then used to study the relationship between order and sort-set dependencies.
Software development of real-time systems
Authors: Gomaa Hassan
Published: July 2002

Concentrating on those aspects of software development peculiar to real-time systems, this collection of development methods and tools emphasizes incremental development; the testing of tusk interfaces during integration testing, as well as unit and partial integration testing on the development system; and the development of automated tools to assist in the testing process.
A model for concurrency in nested transactions systems
Authors: Beeri Catriel , Bernstein Philip A. , Goodman Nathan
Published: July 2002

Today's standard model for database concurrency control, called serializability theory, represents executions of transactions as partial orders of operations. The theory tells when an execution is serializable, that is, when the set of operations of a transaction execute atomically with respect to those of other transactions. It has been used successfully to prove correctness of most database concurrency control algorithms. Its most serious limitation is its inability to represent nested computations conveniently.

This paper presents a more general model that permits nested transactions. In this model, transactions may execute subtransactions, giving rise to tree-structured computations. A serializability theory is developed for this model, which can be used to prove the correctness of concurrency control algorithms for nested transactions and for multilevel database systems.

The theory is based on an abstract model of computation that allows arbitrary operations, and parallel and even nondeterministic programs. Axioms are presented that express the basic properties that programs that manage or access data need to satisfy. We use these axioms to derive proof techniques. One new technique—substitution—shows the equivalence of two executions by substituting one subcomputation by another, usually shallower (i.e., less nested), one. Our proof techniques are illustrated by applying them to several well-known concurrency control problems.
Computing as a discipline
Authors: Comer D. E. , Gries David , Mulder Michael C. , Tucker Allen , Turner A. Joe , Young Paul R.
Published: July 2002

The final report of the Task Force on the Core of Computer Science presents a new intellectual framework for the discipline of computing and a new basis for computing curricula. This report has been endorsed and approved for release by the ACM Education Board.
Can the field of MIS be disciplined?
Authors: Banville Claude , Landry Maurice
Published: July 2002

Preoccupations about the present and future evolution of MIS as a scientific field seem to be gaining popularity among researchers. The authors contend that most models used by the investigators of the MIS field have been based on an inappropriate monistic view of science.
Table-driven implementation of the exponential function in IEEE floating-point arithmetic
Authors: Tang Ping-Tak Peter
Published: July 2002

Algorithms and implementation details for the exponential function in both single- and double-precision of IEEE 754 arithmetic are presented here. With a table of moderate size, the implementations need only working-precision arithmetic and are provably accurate to within 0.54 ulp as long as the final result does not underflow. When the final result suffers gradual underflow, the error is still no worse than 0.77 ulp.
Skip lists: a probabilistic alternative to balanced trees
Authors: Pugh William
Published: July 2002

Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
MEDICAL ANTHROPOLOGY AND EPIDEMIOLOGY
Authors: Trostle James A. , Sommerfeld Johannes
Published: July 2002

▪ Abstract  Over the past decade anthropologists and epidemiologists have begun to move beyond the “benign neglect” that characterized their prior relationship. Some of the most important collaborations between these disciplines concern themes of culture change and stress, social stratification, and the unpacking of other social and cultural variables. Anthropologists have criticized and expanded epidemiological notions of risk and vulnerability. Multidisciplinary teams of anthropologists and epidemiologists have constructed new measures and used multiple methods to increase the validity of their results. Disputes about classification have also linked the two disciplines. Collaborative projects between anthropologists and epidemiologists are leading to more nuanced and accurate descriptions of human behavior and more appropriate and effective interventions. Epidemiological techniques and ideas are also being used for anthropological ends, because disease often spreads along the framework of social structure. These many forms of collaboration create the foundations of a cultural epidemiology.
Cultural Politics of Identity in Latin America
Authors: Hale Charles R.
Published: July 2002

The phrase “identity politics” has come to encapsulate a wide diversity of oppositional movements in contemporary Latin America, marking a transition away from the previous moment of unified, “national-popular” projects. This review takes a dual approach to the literature emerging from that transition, focusing on changes in both the objects of study and the analysts' lens. Four questions drive this inquiry: When did the moment of identity politics arise? What accounts for the shift? How to characterize its contents? What consequences follow for the people involved? Past answers to such questions often have tended to fall into polarized materialist and discursive theoretical camps. In contrast, this review emphasizes emergent scholarship that takes insights from both while refusing the dichotomy, and assigning renewed importance to empirically grounded and politically engaged research.
Conservation and Subsistence in Small-Scale Societies
Authors: Smith Eric Alden , Wishnie Mark
Published: July 2002

▪ Abstract  Some scholars have championed the view that small-scale societies are conservers or even creators of biodiversity. Others have argued that human populations have always modified their environments, often in ways that enhance short-term gains at the expense of environmental stability and biodiversity conservation. Recent ethnographic studies as well as theory from several disciplines allow a less polarized assessment. We review this body of data and theory and assess various predictions regarding sustainable environmental utilization. The meaning of the term conservation is itself controversial. We propose that to qualify as conservation, any action or practice must not only prevent or mitigate resource overharvesting or environmental damage, it must also be designed to do so. The conditions under which conservation will be adaptive are stringent, involving temporal discounting, economic demand, information feedback, and collective action. Theory thus predicts, and evidence suggests, that voluntary conservation is rare. However, sustainable use and management of resources and habitats by small-scale societies is widespread and may often indirectly result in biodiversity preservation or even enhancement via creation of habitat mosaics.
Early Agriculturalist Population Diasporas? Farming, Languages, and Genes
Authors: Bellwood Peter
Published: July 2002

▪ Abstract  The consequences of early agricultural development in several regions of the Old and New Worlds included population growth, the spread of new material cultures and of food-producing economies, the expansions of language families, and in many cases the geographical expansions of the early farming populations themselves into territories previously occupied by hunters and gatherers. This chapter discusses some of the different outcomes that can be expected according to the differing perspectives of archaeology, linguistics, and biological anthropology. I argue that agriculturalist expansion lies at the root of many of the world's major language families, although this need not imply that farmers always replaced hunter-gatherers in the biological sense. History, enviromental variations, and prior cultural configurations dictated many of the outcomes, some of which played a fundamental role in the large-scale genesis of human cultural and biological patterning from Neolithic/Formative times into the world of today.
Anthropology in France
Authors: Rogers Susan Carol
Published: July 2002

▪ Abstract  In France as elsewhere, anthropology developed as an autonomous discipline concerned with the study of faraway primitive or “exotic” societies, but it has shifted its purview, especially over the past several decades, to also include societies closer to home in both time and space. Consideration of the substantial literature produced over the past 30 years by French anthropologists conducting research in France illustrates the specificities of national disciplinary traditions in perceiving and meeting this challenge. Anthropology's position within the institutional framework of contemporary French academic and scholarly life, as well as the intellectual traditions that have been brought to bear on the ethnological study of France (especially the legacies of Durkheimian social thought and folklore studies) are shown to have helped shape both the production of anthropological knowledge of and in France and debates about its pertinence to the discipline's future.
PROGRAMMED CELL DEATH IN PLANT-PATHOGEN INTERACTIONS
Authors: Greenberg Jean T.
Published: July 2002

▪ Abstract  Plants cope with pathogen attacks by using mechanisms of resistance that rely both on preformed protective defenses and on inducible defenses. The latter are the most well studied, and progress is being made in determining which induced responses are responsible for limiting pathogen growth. Many plant-pathogen interactions are accompanied by plant cell death. Recent evidence suggests that this cell death is often programmed and results from an active process on the part of the host. The review considers the roles and possible mechanisms of plant cell death in response to pathogens.
PHOTOSYNTHETIC CYTOCHROMEScIN CYANOBACTERIA, ALGAE, AND PLANTS
Authors: Kerfeld Cheryl A. , Krogmann David W.
Published: July 2002

▪ Abstract  The cytochromes that function in photosynthesis in cyanobacteria, algae, and higher plants have, like the other photosynthetic catalysts, been largely conserved in their structure and function during evolution. Cyanobacteria and algae contain cytochrome c6, which is not found in higher plants and which may enhance survival in their planktonic mode of life. Cyanobacteria and algae contain another cytochrome, low-potential c549,which is not found in higher plants. This cytochrome has a structural role in PSII and may contribute to anaerobic survival. There is a third unique cytochrome, cytochrome M, in the planktonic photosynthesizers, and its function is unknown. New evidence is appearing to indicate evolution of cytochrome interaction mechanisms during the evolution of photosynthesis. The ease of cytochrome gene manipulation in cyanobacteria and in Chlamydomonas reinhardtii now provides great advantages in understanding of photosynthesis. The solution of tertiary and quaternary structures of cytochromes and cytochrome complexes will provide structural and functional detail at atomic resolution.
THE GALACTIC CENTER ENVIRONMENT
Authors: Morris Mark , Serabyn Eugene
Published: July 2002

▪ Abstract  The central half kiloparsec region of our Galaxy harbors a variety of phenomena unique to the central environment. This review discusses the observed structure and activity of the interstellar medium in this region in terms of its inevitable inflow toward the center of the Galactic gravitational potential well. A number of dissipative processes lead to a strong concentration of gas into a “Central Molecular Zone” of about 200-pc radius, in which the molecular medium is characterized by large densities, large velocity dispersions, high temperatures, and apparently strong magnetic fields. The physical state of the gas and the resultant star formation processes occurring in this environment are therefore quite unlike those occurring in the large-scale disk. Gas not consumed by star formation either enters a hot X ray–emitting halo and is lost as a thermally driven galactic wind or continues moving inward, probably discontinuously, through the domain of the few parsec-sized circumnuclear disks and eventually into the central parsec. There, the central radio source SgrA*currently accepts only a tiny fraction of the inflowing material, likely as a result of a limit cycle wherein the continual inflow of matter provokes star formation, which in turn can temporarily halt the inflow via mass-outflow winds.
DETECTION OF EXTRASOLAR GIANT PLANETS
Authors: Marcy Geoffrey W. , Butler R. Paul
Published: July 2002

▪ Abstract  Eight extrasolar planet candidates have now been identified, all revealed by Keplerian Doppler shifts in their host stars. The masses (m sin i) lie between 0.5 and 7 MJUP, and the semimajor axes are less than 2.1 astronomical units (AU). Doppler detectability favors high masses and small orbits, and improvements will render Saturn masses detectable within a few years. The substellar mass function (dN/dM) for companions is roughly flat from 70 down to 10 MJUP, but it exhibits a sharp increase for masses below 5 MJUP. For three of these companions (47 UMa, ρ Crb, and 55 Cnc), their circular orbits must be primordial (not tidally induced), indicating formation in a disk, as presumed for Solar System planets. Eccentric orbits may be explained by gravitational perturbations, either by companion stars, other planets, or disk resonances. The detections imply that ∼6% of solar-type stars have giant planets within 2 AU. The small orbits (a < 2 AU) imply that the planets formed either in situ, without the benefit of ice grains, or suffered inward migration. Orbital decay within 1 Myr in disks appears inevitable and may shape the planet mass distribution. The observed stability of spectral line shapes suggests that nonradial stellar oscillations do not affect the planet detections.