bluuebunny/crossref_metadata_2025 huggingface dataset:
Local and temporal predicates in distributed systems
Authors: Charron-Bost Bernadette , Delporte-Gallet Carole , Fauconnier Hugues
Published: October 2002

The definitions of the predicates Possibly φ and Definitely φ, where φ is a global predicate of a distributed computation, lead to the definitions of two predicate transformers
P
and
D
. We show that
P
plays the same role with respect to
time
as the predicate transformers

K
i

in knowledge theory play with respect to
space
. Pursuing this analogy, we prove that local predicates are exactly the fixed points of the

K
i

's while the stable predicates are the fixed points of
P
. In terms of the predicate transformers
P
and
D
, we define a new class of predicates that we call
observer-independent
predicates and for which the detection of Possibly φ and Definitely φ is quite easy. Finally, we establish a temporal counterpart to the knowledge change theorem of Chandy and Misra which formally proves that the global view of a distributed system provided by its various observations does not differ too much from its truth behavior.
Type classes in Haskell
Authors: Hall Cordelia V. , Hammond Kevin , Peyton Jones Simon L. , Wadler Philip L.
Published: October 2002

This article defines a set of type inference rules for resolving overloading introduced by type classes, as used in the functional programming language Haskell. Programs including type classes are transformed into ones which may be typed by standard Hindley-Milner inference rules. In contrast to other work on type classes, the rules presented here relate directly to Haskell programs. An innovative aspect of this work is the use of second-order lambda calculus to record type information in the transformed program.
Optimal prepaging and font caching
Authors: Fuchs David R. , Knuth Donald E.
Published: October 2002

An efficient algorithm for communicating letter-shape information from a high-speed computer with a large memory to a typesetting device that has a limited memory is presented. The encoding is optimum, in the sense that the total time for typesetting is minimized, using a model that generalizes well-known “demand paging” strategies to the case where changes to the cache are allowed before the associated information is actually needed. Extensive empirical data show that good results are obtained even when difficult technical material is being typeset on a machine that can store information concerning only 100 characters. The methods of this paper are also applicable to other hardware and software caching applications with restricted lookahead.
Complementation in abstract interpretation
Authors: Cortesi Agostino , Filé Gilberto , Ranzato Francesco , Giacobazzi Roberto , Palamidessi Catuscia
Published: October 2002

Reduced product of abstract domains is a rather well-known operation for domain composition in abstract interpretation. In this article, we study its inverse operation, introducing a notion of domain complementation in abstract interpretation. Complementation provides as systematic way to design new abstract domains, and it allows to systematically decompose domains. Also, such an operation allows to simplify domain verification problems, and it yields space-saving representations for complex domains. We show that the complement exists in most coses, and we apply complementation to three well-know abstract domains, notably to Cousot and Cousot's interval domain for integer variable analysis, to Cousot and Cousot's domain for comportment analysis of functional languages, and to the domain
Sharing
for aliasing analysis of logic languages.
Data descriptors: a compile-time model of data and addressing
Authors: Holt R. C.
Published: October 2002

Data descriptors, which have evolved from Wilcox's value descriptors [16], are a notation for representing run-time data objects at compile time. One of the principal reasons for developing this notation was to aid in the rapid construction of code generators, especially for new microprocessors. Each data descriptor contains a base, a displacement, and a level of indirection. For example, a variable
x
lying at displacement 28 from base register B3 is represented by this data descriptor: @B3.28. The general form of a data descriptor is @

k
b.d.i

where
k
gives the number of levels of indirection,
b
is a base,
d
is a displacement, and
I
is an index.

Data descriptors are convenient for representing addressing in Fortran (with static allocation and common blocks), in Pascal and Turing (with automatic allocation and stack frames), and in more general languages such as Euclid and PL/I. This generality of data descriptors allows code generation to be largely independent of the source language.

Data descriptors are able to encode the addressing modes of typical computer architectures such as the IBM 360 and the PDP-11. This generality of data descriptors allows code generation to be largely machine independent.

This paper gives a machine independent method of storage allocation that uses data descriptors. Techniques are given for local optimization of basic arithmetic and addressing code using data descriptors. Target machine dependencies are isolated so that the part of the code generator that handles high-level addressing (such as subscripting) is machine independent. The techniques described in this paper have proven effective in the rapid development of a number of production code generators.
Mobile objects in distributed Oz
Authors: Van Roy Peter , Haridi Seif , Brand Per , Smolka Gert , Mehl Michael , Scheidhauer Ralf
Published: October 2002

Some of the most difficult questions to answer when designing a distributed application are related to mobility: what information to transfer between sites and when and how to transfer it. Network-transparent distribution, the property that a program's behavior is independent of how it is partitioned among sites, does not directly address these questions. Therefore we propose to extend all language entities with a network behavior that enables
efficient
distributed programming by giving the programmer a simple and predictable control over network communication patterns. In particular, we show how to give objects an arbitrary mobility behavior that is independent of the objects definition. In this way, the syntax and semantics of objects are the same regardless of whether they are used as stationary servers, mobile agents, or simply as caches. These ideas have been implemented in Distributed Oz, a concurrent object-oriented language that is state aware and has dataflow synchronization. We prove that the implementation of objects in Distributed Oz is network transparent. To satisfy the predictability condition, the implementation avoids forwarding chains through intermediate sites. The implementation is an extension to the publicly available DFKI Oz 2.0 system.
Constraint-based array dependence analysis
Authors: Pugh William , Wonnacott David
Published: October 2002

Traditional array dependence analysis, which detects potential memory aliasing of array references is a key analysis technique for automatic parallelization. Recent studies of benchmark codes indicate that limitations of analysis cause many compilers to overlook large amounts of potential parallelism, and that exploiting this parallelism requires algorithms to answer new question about array references, not just get better answers to the old questions of aliasing. We need to ask about the flow of values in arrays, to check the legality of array privatization, and about the conditions under which a dependence exists, to obtain information about conditional parallelism. In some cases, we must answer these questions about code containing nonlinear terms in loop bounds or subscripts. This article describes techniques for phrasing these questions in terms of systems of contstraints. Conditional dependence analysis can be performed with a constraint operation we call the "gist" operation. When subscripts and loop bounds are affine, questions about the flow of values in array variables can be phrased in terms of Presburger Arithmetic. When the constraints describing a dependence are not affine, we introduce uninterpreted function symbols to represent the nonaffine terms. Our constraint language also provides a rich language for communication with the dependence analyzer, by either the programmer or other phases of the compiler. This article also documents our investigations of the praticality of our approach. The worst-case complexity of Presburger Arithmetic indicates that it might be unsuitable for any practical application. However, we have found that analysis of benchmark programs does not cause the exponential growth in the number of constraints that could occur in the worst case. We have studied the constraints produced during our aanalysis, and identified characteristics that keep our algorithms free of exponential behavior in practice.
Efficient logic variables for distributed computing
Authors: Haridi Seif , Van Roy Peter , Brand Per , Mehl Michael , Scheidhauer Ralf , Smolka Gert
Published: October 2002

We define a practical algorithm for distrubuted rational tree unification and prove its correctness in both the off-line and on-line cases. We derive the distributed algorithm from a centralized one, showing clearly the trade-offs between local and distributed execution. The algorithm is used to realize logic variables in the Mozart Programming System, which implements the Oz language (see http://www/mozart-oz.org). Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Logic variables implement the dataflow behavior. We show that lohgic variables can easily be added to the more restricted models of Java and ML, thus providing an alternative way to do concurent programming in these languages. We present common distributed programming idioms in a network-transparent way using logic variables. We show that in common cases the algorithm maintains the same message latency as explicit message passing. In addition, it is able to handle uncommon cases that arise from the properties of latency tolerance and third-party independence. This is evidence that using logic variables in distributed computing is beneficial at both the system and language levels. At the system level, they improve latency tolerance and third-party independence. At the language level, they help make network-transparent distribution practical.
Partial redundancy elimination in SSA form
Authors: Kennedy Robert , Chan Sun , Liu Shin-Ming , Lo Raymond , Tu Peng , Chow Fred
Published: October 2002

The SSAPRE algorithm for performing partial redundancy elimination based entirely on SSA form is presented. The algorithm is formulated based on a new conceptual framework, the factored redundancy graph, for analyzing redundancy, and representes the first sparse approach to the classical problem and on methods for its solution. With the algorithm description, theorems and their proofs are given showing that the algorithm produces the best possible code by the criteria of computational optimality and lifetime optimality of the introduced temporaries. In addition to the base algorithm, a practical implementation of SSAPRE that exhibits additional compile-time efficiencies is described. In closing, measurement statistics are provided that characterize the instances of the partial redundancy problem from a set of benchmark programs and compare optimization time spent by an implementation of SSAPRE aganist a classical partial redundancy elimination implementation. The data lend insight into the nature of partial redundancy elimination and demonstrate the expediency of this new approach.
Distributed Termination
Authors: Francez Nissim
Published: October 2002

Discussed is a distributed system based on communication among disjoint processes, where each process is capable of achieving a post-condition of its local space in such a way that the conjunction of local post-conditions implies a global post-condition of the whole system. The system is then augmented with extra control communication in order to achieve distributed termination, without adding new channels of communication. The algorithm is applied to a problem of constructing a sorted partition.
The Activity of a Variable and Its Relation to Decision Trees
Authors: Moret B. E. , Thomason M. , Gonzalez R. C.
Published: October 2002

The construction of sequential testing procedures from functions of discrete arguments is a common problem in switching theory, software engineering, pattern recognition, and management. The concept of the activity of an argument is introduced, and a theorem is proved which relates it to the expected testing cost of the most general type of decision trees. This result is then extended to trees constructed from relations on finite sets and to decision procedures with cycles. These results are used, in turn, as the basis for a fast heuristic selection rule for constructing testing procedures. Finally, some bounds on the performance of the selection rule are developed.
A schema for interprocedural modification side-effect analysis with pointer aliasing
Authors: Ryder Barbara G. , Landi William A. , Stocks Philip A. , Zhang Sean , Altucher Rita
Published: October 2002

The first interprocedural modification side-effects analysis for C (MOD

C

) that obtains better than worst-case precision on programs with general-purpose pointer usage is presented with empirical results. The analysis consists of an algorithm schema corresponding to a family of MOD

C

algorithms with two independent phases: one for determining pointer-induced aliases and a subsequent one for propagating interprocedural side effects. These MOD

C

algorithms are parameterized by the aliasing method used. The empirical results compare the performance of two dissimilar MOD

C

algorithms: MOD

C

(
FSAlias
) uses a flow-sensitive, calling-context-sensitive interprocedural alias analysis; MOD

C

(
FIAlias
uses a flow-insensitive, calling-context-insensitive alias analysis which is much faster, but less accurate. These two algorithms were profiled on 45 programs ranging in size from 250 to 30,000 lines of C code, and the results demonstrate dramatically the possible cost-precision trade-offs. This
first comparative
implementation of MOD

C

analyses offers insight into the differences between
flow-/context-sensitive
and
flow-/context-insensitive
analyses. The analysis cost versus precision trade-offs in side-effect information obtained are reported. The results show surprisingly that the precision of flow-sensitive side-effect analysis is not always prohibitive in cost, and that the precision of flow-insensitive analysis is substantially better than worst-case estimates and seems sufficient for certain applications. On average MOD

C

(
FSAlias
) for procedures and calls is in the range of 20% more precise than MOD

C

(
FIAlias
); however, the performance was found to be at least an order of magnitude slower than MOD

C

(
FIAlias
).
The specification statement
Authors: Morgan Carroll
Published: October 2002

Dijkstra's programming language is extended by
specification statements
, which specify parts of a program “yet to be developed.” A weakest precondition semantics is given for these statements so that the extended language has a meaning as precise as the original.

The goal is to improve the
development
of programs, making it closer to manipulations within a single calculus. The extension does this by providing one semantic framework for specifications and programs alike: Developments begin with a program (a single specification statement) and end with a program (in the executable language). And the notion of
refinement
or
satisfaction
, which normally relates a specification to its possible implementations, is automatically generalized to act between specifications and between programs as well.

A surprising consequence of the extension is the appearance of
miracles
: program fragments that do not satisfy Dijkstra's
Law of the Excluded Miracle
. Uses for them are suggested.
Axioms for memory access in asynchronous hardware systems
Authors: Misra J.
Published: October 2002

The problem of concurrent accesses to registers by asynchronous components is considered. A set of axioms about the values in a register during concurrent accesses is proposed. It is shown that if these axioms are met by a register, then concurrent accesses to it may be viewed as nonconcurrent, thus making it possible to analyze asynchronous algorithms without elaborate timing analysis of operations. These axioms are shown, in a certain sense, to be the weakest. Motivation for this work came from analyzing low-level hardware components in a VLSI chip which concurrently accesses a flip-flop.
PARLOG: parallel programming in logic
Authors: Clark Keith , Gregory Steve
Published: October 2002

PARLOG is a logic programming language in the sense that nearly every definition and query can be read as a sentence of predicate logic. It differs from PROLOG in incorporating parallel modes of evaluation. For reasons of efficient implementation, it distinguishes and separates and-parallel and or-parallel evaluation.

PARLOG relations are divided into two types: single-solution relations and all-solutions relations. A conjunction of single-solution relation calls can be evaluated in parallel with shared variables acting as communication channels for the passing of partial bindings. Only one solution to each call is computed, using committed choice nondeterminism.

A conjunction of all-solutions relation calls is evaluated without communication of partial bindings, but all the solutions may be found by an or-parallel exploration of the different evaluation paths. A set constructor provides the main interface between single-solution relations and all-solutions relations.

This paper is a tutorial introduction to PARLOG. It assumes familiarity with logic programming. Categories and Subject Descriptors: D.l.l [Programming Techniques]: Applicative (Functional)
High-performance computer architecture and algorithm simulator
Authors: Hoganson Kenneth E.
Published: October 2002

This simulation tool allows the user to explore different computer architectures with hardware support at any or all of five levels of parallelism, from intrainstruction (pipeline) through distributed
n
-tier client/server systems. The tool supports the simulation of various user-configurable architectures and interconnection networks, running a user-configurable and variable workload. This allows the student and the instructor to observe how performance changes through the five levels of parallelism with changes in either the architecture or workload. The successful use of the simulation tool in a variety of undergraduate courses at the author's institution is presented, along with examples, and a set of experiments. The simulator is a Java applet, which can be used from a Web browser, allowing anyone with an Internet connection access to the tool, without concern about student licensing requirements. The simulator is hosted at the author's institution with funding provided by a recent grant. Its design as an applet also allows improvements and enhancements to the software to be implemented and instantly made available to all users of the product.
Boolean satisfiability with transitivity constraints
Authors: Bryant Randal E. , Velev Miroslav N.
Published: October 2002

We consider a variant of the Boolean satisfiability problem where a subset ε of the propositional variables appearing in formula
F
sat
encode a symmetric, transitive, binary relation over
N
elements. Each of these
relational
variables,
e

i,j

, for 1 ≤
i
<
j
≤
N
, expresses whether or not the relation holds between elements
i
and
j
. The task is to either find a satisfying assignment to
F
sat
that also satisfies all transitivity constraints over the relational variables (e.g.,
e
1,2
∧
e
2,3
⇒
e
1,3
), or to prove that no such assignment exists. Solving this satisfiability problem is the final and most difficult step in our decision procedure for a logic of equality with uninterpreted functions. This procedure forms the core of our tool for verifying pipelined microprocessors.To use a conventional Boolean satisfiability checker, we augment the set of clauses expressing
F
sat
with clauses expressing the transitivity constraints. We consider methods to reduce the number of such clauses based on the sparse structure of the relational variables.To use Ordered Binary Decision Diagrams (OBDDs), we show that for some sets ε, the OBDD representation of the transitivity constraints has exponential size for all possible variable orderings. By considering only those relational variables that occur in the OBDD representation of
F
sat
, our experiments show that we can readily construct an OBDD representation of the relevant transitivity constraints and thus solve the constrained satisfiability problem.
Creating models of truss structures with optimization
Authors: Smith Jeffrey , Hodgins Jessica , Oppenheim Irving , Witkin Andrew
Published: October 2002

We present a method for designing truss structures, a common and complex category of buildings, using non-linear optimization. Truss structures are ubiquitous in the industrialized world, appearing as bridges, towers, roof supports and building exoskeletons, yet are complex enough that modeling them by hand is time consuming and tedious. We represent trusses as a set of rigid bars connected by pin joints, which may change location during optimization. By including the location of the joints as well as the strength of individual beams in our design variables, we can simultaneously optimize the geometry and the mass of structures. We present the details of our technique together with examples illustrating its use, including comparisons with real structures.
Dual contouring of hermite data
Authors: Ju Tao , Losasso Frank , Schaefer Scott , Warren Joe
Published: October 2002

This paper describes a new method for contouring a signed grid whose edges are tagged by Hermite data (i.e; exact intersection points and normals). This method avoids the need to explicitly identify and process "features" as required in previous Hermite contouring methods. Using a new, numerically stable representation for quadratic error functions, we develop an octree-based method for simplifying contours produced by this method. We next extend our contouring method to these simpli£ed octrees. This new method imposes no constraints on the octree (such as being a restricted octree) and requires no "crack patching". We conclude with a simple test for preserving the topology of the contour during simplification.
Image-based 3D photography using opacity hulls
Authors: Matusik Wojciech , Pfister Hanspeter , Ngan Addy , Beardsley Paul , Ziegler Remo , McMillan Leonard
Published: October 2002

We have built a system for acquiring and displaying high quality graphical models of objects that are impossible to scan with traditional scanners. Our system can acquire highly specular and fuzzy materials, such as fur and feathers. The hardware set-up consists of a turntable, two plasma displays, an array of cameras, and a rotating array of directional lights. We use multi-background matting techniques to acquire alpha mattes of the object from multiple viewpoints. The alpha mattes are used to construct an
opacity hull.
The opacity hull is a new shape representation, defined as the visual hull of the object with view-dependent opacity. It enables visualization of complex object silhouettes and seamless blending of objects into new environments. Our system also supports relighting of objects with arbitrary appearance using surface reflectance fields, a purely image-based appearance representation. Our system is the first to acquire and render surface reflectance fields under varying illumination from arbitrary viewpoints. We have built three generations of digitizers with increasing sophistication. In this paper, we present our results from digitizing hundreds of models.
Jigsaw image mosaics
Authors: Kim Junhwan , Pellacini Fabio
Published: October 2002

This paper introduces a new kind of mosaic, called Jigsaw Image Mosaic (JIM), where image tiles of arbitrary shape are used to compose the final picture. The generation of a Jigsaw Image Mosaic is a solution to the following problem: given an arbitrarily-shaped container image and a set of arbitrarily-shaped image tiles, fill the container as compactly as possible with tiles of similar color to the container taken from the input set while optionally deforming them slightly to achieve a more visually-pleasing effect. We approach the problem by defining a mosaic as the tile configuration that minimizes a mosaicing energy function. We introduce a general energy-based framework for mosaicing problems that extends some of the existing algorithms such as Photomosaics and Simulated Decorative Mosaics. We also present a fast algorithm to solve the mosaicing problem at an acceptable computational cost. We demonstrate the use of our method by applying it to a wide range of container images and tiles.
Image based flow visualization
Authors: van Wijk Jarke J.
Published: October 2002

A new method for the visualization of two-dimensional fluid flow is presented. The method is based on the advection and decay of dye. These processes are simulated by defining each frame of a flow animation as a blend between a warped version of the previous image and a number of background images. For the latter a sequence of filtered white noise images is used: filtered in time and space to remove high frequency components. Because all steps are done using images, the method is named Image Based Flow Visualization (
IBFV
). With
IBFV
a wide variety of visualization techniques can be emulated. Flow can be visualized as moving textures with line integral convolution and spot noise. Arrow plots, streamlines, particles, and topological images can be generated by adding extra dye to the image. Unsteady flows, defined on arbitrary meshes, can be handled.
IBFV
achieves a high performance by using standard features of graphics hardware. Typically fifty frames per second are generated using standard graphics cards on PCs. Finally,
IBFV
is easy to understand, analyse, and implement.
WYSIWYG NPR
Authors: Kalnins Robert D. , Markosian Lee , Meier Barbara J. , Kowalski Michael A. , Lee Joseph C. , Davidson Philip L. , Webb Matthew , Hughes John F. , Finkelstein Adam
Published: October 2002

We present a system that lets a designer directly annotate a 3D model with strokes, imparting a personal aesthetic to the non-photorealistic rendering of the object. The artist chooses a "brush" style, then draws strokes over the model from one or more viewpoints. When the system renders the scene from any new viewpoint, it adapts the number and placement of the strokes appropriately to maintain the original look.
Determining the cost of IT services
Authors: Gerlach James , Neumann Bruce , Moldauer Edwin , Argo Martha , Frisby Daniel
Published: October 2002

Providing managerial information to explain costs in the context of personnel and equipment activities and processes.
Algorithm 820
Authors: Ferrando Sebastian E. , Kolasa Lawrence A. , Kovačević Natasha
Published: October 2002

In digital signal processing it is often advantageous to analyze a given signal using an adaptive method. The signal is approximated or represented as a superposition of "basic" waveforms chosen from a
dictionary
of such waveforms so as to best match the signal. The matching pursuit algorithm of Mallat and Zhang is such a method and is discussed in the context of discretized Gabor functions on an interval. We describe two software implementations based on these dictionaries. Both implementations rely on functions defined on an interval to avoid edge effects. One implementation allows for users to have great flexibility in the Gabor dictionary to be used. This is a useful improvement over other implementations, which only allow for a fixed dictionary. The other implementation takes advantage of the FFT algorithm and is faster. These implementations are written in C++, and can be used in practical applications.
Information flow vs. resource access in the asynchronous pi-calculus
Authors: Hennessy Matthew , Riely James
Published: October 2002

We propose an extension of the asynchronous π-calculus in which a variety of security properties may be captured using types. These are an extension of the input/output types for the π-calculus in which I/O capabilities are assigned specific security levels. The main innovation is a uniform typing system that, by varying slightly the allowed set of types, captures different notions of security.We first define a typing system that ensures that processes running at security level σ cannot access resources with a security level higher than σ. The notion of
access control
guaranteed by this system is formalized in terms of a Type Safety Theorem.We then show that, by restricting the allowed types, our system prohibits implicit information flow from high-level to low-level processes. We prove that low-level behavior can not be influenced by changes to high-level behavior. This is formalized as a
noninterference
theorem with respect to may testing.
Verifying temporal properties without temporal logic
Authors: Alpern Bowen , Schneider Fred B.
Published: October 2002

An approach to proving temporal properties of concurrent programs that does not use temporal logic as an inference system is presented. The approach is based on using Buchi automata to specify properties. To show that a program satisfies a given property, proof obligations are derived from the Buchi automata specifying that property. These obligations are discharged by devising suitable invariant assertions and variant functions for the program. The approach is shown to be sound and relatively complete. A mutual exclusion protocol illustrates its application.
The impact of interprocedural analysis and optimization in the R
n
programming environment
Authors: Cooper Keith D. , Kennedy Ken , Torczon Linda
Published: October 2002

In spite of substantial progress in the theory of interprocedural data flow analysis, few practical compiling systems can afford to apply it to produce more efficient object programs. To perform interprocedural analysis, a compiler needs not only the source code of the module being compiled, but also information about the side effects of every procedure in the program containing that module, even separately compiled procedures. In a conventional batch compiler system, the increase in compilation time required to gather this information would make the whole process impractical. In an integrated programming environment, however, other tools can cooperate with the compiler to compute the necessary interprocedural information
incrementally
. as the program is being developed, decreasing both the overall cost of the analysis and the cost of individual compilations.

A central goal of the R
n
project at Rice University is to construct a prototype software development environment that is designed to build whole programs, rather than just individual modules. It employs interprocedural analysis and optimization to produce high-quality machine code for whole programs. This paper presents an overview of the methods used by the environment to accomplish this task and discusses the impact of these methods on the various environment components. The responsibilities of each component of the environment for the preparation and use of interprocedural information are presented in detail.
Static inference of modes and data dependencies in logic programs
Authors: Debray Saumya K.
Published: October 2002

Mode and data dependency analyses find many applications in the generation of efficient executable code for logic programs. For example, mode information can be used to generate specialized unification instructions where permissible, to detect determinacy and functionality of programs, generate index structures more intelligently, reduce the amount of runtime tests in systems that support goal suspension, and in the integration of logic and functional languages. Data dependency information can be used for various source-level optimizing transformations, to improve backtracking behavior and to parallelize logic programs. This paper describes and proves correct an algorithm for the static inference of modes and data dependencies in a program. The algorithm is shown to be quite efficient for programs commonly encountered in practice.
Linguistic support for atomic data types
Authors: Weihl William E.
Published: October 2002

The problems of concurrency and failures in distributed systems can be addressed by implementing applications in terms of atomic data types: data types whose objects provide serializability and recoverability for transactions using them. The specifications of the types can be used to permit high levels of concurrency among transactions while still ensuring atomicity. However, highly concurrent implementations can be quite complicated. In this paper we analyze the expressive power of existing proposals for language features intended to support the implementation of atomic types. We illustrate several limitations of existing proposals and propose a new approach that avoids these problems.
An interval-based approach to exhaustive and incremental interprocedural data-flow analysis
Authors: Burke Michael
Published: October 2002

We reformulate interval analysis so that it can he applied to any monotone data-flow problem, including the nonfast problems of flow-insensitive interprocedural analysis. We then develop an incremental interval analysis technique that can be applied to the same class of problems. When applied to flow-insensitive interprocedural data-flow problems, the resulting algorithms are simple, practical, and efficient. With a single update, the incremental algorithm can accommodate any sequence of program changes that does not alter the structure of the program call graph. It can also accommodate a large class of structural changes. For alias analysis, we develop an incremental algorithm that obtains the exact solution as computed by an exhaustive algorithm. Finally, we develop a transitive closure algorithm that is particularly well suited to the very sparse matrices associated with the problems we address.
The priority-based coloring approach to register allocation
Authors: Chow Fred C. , Hennessy John L.
Published: October 2002

Global register allocation plays a major role in determining the efficacy of an optimizing compiler. Graph coloring has been used as the central paradigm for register allocation in modern compilers. A straightforward coloring approach can suffer from several shortcomings. These shortcomings are addressed in this paper by coloring the graph using a priority ordering. A natural method for dealing with the spilling emerges from this approach. The detailed algorithms for a priority-based coloring approach are presented and are contrasted with the basic graph-coloring algorithm. Various extensions to the basic algorithms are also presented. Measurements of large programs are used to determine the effectiveness of the algorithm and its extensions, as well as the causes of an imperfect allocation. Running time of the allocator and the impact of heuristics aimed at reducing that time are also measured.
A Cell Biological Perspective on Alzheimer's Disease
Authors: Annaert Wim , De Strooper Bart
Published: October 2002

▪ Abstract  The amyloid precursor protein and the proteases cleaving this protein are important players in the pathogenesis of Alzheimer's disease via the generation of the amyloid peptide. Physiologically, the amyloid precursor protein is implied in axonal vesicular trafficking and the proteases are implicated in developmentally important signaling pathways, most significantly those involving regulated intramembrane proteolysis or RIP. We discuss the cell biology behind the amyloid and tangle hypothesis for Alzheimer's disease, drawing on the many links to the fields of cell biology and developmental biology that have been established in the recent years.
Inhibition of Intestinal Cholesterol Absorption by Ezetimibe in Humans
Authors: Sudhop Thomas , Lütjohann Dieter , Kodal Annette , Igel Michael , Tribble Diane L. , Shah Sukrut , Perevozskaya Inna , von Bergmann Klaus
Published: October 2002

Background—

Ezetimibe has been shown to inhibit cholesterol absorption in animal models, but studies on cholesterol absorption in humans have not been performed thus far.

Methods and Results—

The effect of ezetimibe (10 mg/d) on cholesterol absorption and synthesis, sterol excretion, and plasma concentrations of cholesterol and noncholesterol sterols was investigated in a randomized, double-blind, placebo-controlled, crossover study in 18 patients with mild to moderate hypercholesterolemia. Treatment periods lasted 2 weeks with an intervening 2-week washout period. Fractional cholesterol absorption rates averaged 49.8±13.8% on placebo and 22.7±25.8% on ezetimibe, indicating a reduction of 54% (geometric mean ratio;
P
< 0.001). Cholesterol synthesis increased by 89% from 931±1027 mg/d on placebo to 1763±1098 mg/d on ezetimibe (
P
<0.001), while the ratio of lathosterol-to-cholesterol, an indirect marker of cholesterol synthesis, was increased by 72% (
P
<0.001). Bile acid synthesis was insignificantly increased (placebo: 264±209 mg/d, ezetimibe: 308±184 mg/d;
P
=0.068). Mean percent changes from baseline for LDL and total cholesterol after ezetimibe treatment were −20.4% and −15.1%, respectively (
P
<0.001 for both), whereas campesterol and sitosterol were decreased by −48% and − 41%, respectively.

Conclusion—

In humans, ezetimibe inhibits cholesterol absorption and promotes a compensatory increase of cholesterol synthesis, followed by clinically relevant reductions in LDL and total cholesterol concentrations. Ezetimibe also reduces plasma concentrations of the noncholesterol sterols sitosterol and campesterol, suggesting an effect on the absorption of these compounds as well.
Missed Opportunities to Treat Atherosclerosis in Patients Undergoing Peripheral Vascular Interventions
Authors: Mukherjee Debabrata , Lingam Prasanth , Chetcuti Stanley , Grossman P. Michael , Moscucci Mauro , Luciano Ann E. , Eagle Kim A.
Published: October 2002

Background—

Peripheral vascular disease is a manifestation of systemic atherosclerosis and is associated with an increased risk of cardiovascular morbidity and mortality.

Methods and Results—

We examined clinical outcomes in 66 consecutive patients undergoing peripheral vascular interventions at our institution between January 2001 and October 2001. At hospital discharge and at 6 months, lifestyle modifications and use of evidence-based therapy was suboptimal. At 6 months, a significant proportion continued to smoke (22.7%) and only half of the patients exercised, controlled their weight, or modified their diet for lipid control. The use of antiplatelet therapy was 77.2%; of angiotensin-converting enzyme, 35.9%; of β-blockers, 42.5%; and of statins, 50%. Twelve of the 66 patients (18.2%) had a clinical event of death, myocardial infarction, or stroke. An appropriateness algorithm for use of secondary prevention measures was created with the use of evidence-based therapy guidelines, and a composite appropriateness variable was also created. The use of evidence-based therapy was associated with a significant reduction of the composite of death, myocardial infarction, and stroke at 6 months (OR 0.02, 95% CI 0.01 to 0.44,
P
=0.01).

Conclusions—

Atherosclerosis risk factors are very prevalent in patients with peripheral vascular disease, but these patients receive less than optimal treatment after a predominantly technical vascular intervention. Effective secondary prevention with appropriate lifestyle interventions and evidence-based medical therapy needs to be strongly encouraged and implemented in these patients.
The Geography of Creation: Décalage as Impulse, Process, and Outcome in the Theatre of Robert Lepage
Authors: Bunzli James
Published: October 2002

Quebec director Robert Lepage combines hi-tech, artistic process, environmental theatre, autobiography, and a very special sense of theatre travel.
Seven Blind Men and an Elephant: the God of Time
Authors: Turner Frederick
Published: October 2002

In this paper I take as an experimental hypothesis the idea that all religions are true. The problem would be how to pack all those religious truths into the same universe: What would the universe have to be shaped like to contain them all? Given two implications that flow from the uniqueness and unity of the universe - 1. if God exists, he is in the universe; and 2. we can see things indirectly - it makes good sense to attempt to see God. Though there may not be enough room in space for the divine, there may well be room enough in time. Fraser's evolutionary universe with its hierarchy of temporal umwelts provides plenty of ways for the divine to appear in different guises. Contemporary cosmology and computational physics suggest that the universe can best be considered as made of information, engaged in computation of its own future states. If this is true, it is constituted of three warring computational systems: a timeless but unreal Bohm quantum computer, a massively parallel but badly damaged Turing machine with considerable degrees of freedom, and a genetic-algorithm ensemble of fast self-progamming computers (sentient life). These make up the emergent tricameral mind of God.
Characterization and Differentiation of Chemical Heterogeneity in Humic Substances by Continuous Intrinsic Proton Affinity Distribution
Authors: Hongxia Zhang , Wenming Dong , Meide Huang , Zuyi Tao
Published: October 2002

The chemical heterogeneity of proton binding on humic substances was studied via continuous intrinsic proton affinity distributions calculated using the condensation approximation from the master curves for two soil fulvic acids (FAs), one soil humic acid (HA) and one fulvic acid obtained from weathered coal. The master curves, i.e. plots of θT,H (the overall protonation degree) versus Hs (the proton concentration in the diffuse double layer), were obtained from potentiometric titration curves at three ionic strengths. The value of Hs was calculated using an electrical double-layer model in which the humic substances were considered as rigid impermeable spheres. For all four samples, the proton affinity distributions were characterized by a few peaks with peak positions in the range 4–5.5. The similarities and differences between the samples studied were discussed.
Adsorption of Dissociating Aromatic Compounds by Activated Carbon: Effects of Ionization on the Adsorption Capacity
Authors: Nouri S. , Haghseresht Fouad
Published: October 2002

The adsorption of three dissociating aromatic compounds on an untreated commercially available activated carbon was investigated systematically. All adsorption experiments were carried out in pH-controlled aqueous solutions. The experimental isotherms were analyzed using the homogeneous Langmuir model. The effects of surface heterogeneity were investigated via the theory of localized physical adsorption, using the Langmuir equation as the local isotherm equation and assuming a Gaussian adsorption energy distribution. A new method of utilizing the extracted parameters from the homogeneous and heterogeneous models is presented. This new approach provided a better understanding of the change in monolayer capacity and other adsorption characteristics of a carbon/solute system with pH.
APOPTOSIS DURING IRON CHELATOR‐INDUCED DIFFERENTIATION IN F9 EMBRYONAL CARCINOMA CELLS
Authors: Tanaka Tetsuya , Satoh Takatomo , Onozawa Yoshiko , Kohroki Junya , Itoh Norio , Ishidate Motoi , Muto Norio , Tanaka Keiichi
Published: October 2002

We have previously demonstrated that three potent iron chelators, hinokitiol, dithizone and deferoxamine, induce differentiation of F9 embryonal carcinoma cells, as do other well‐known morphogens such as retinoic acid (RA) and sodium butyrate (NaB). In this study, we compared the patterns of cell proliferation, cell death and cell cycle arrest during the process of differentiation induced by these five agents. When F9 cells were cultured with the agents at their individual differentiation‐inducing concentrations, cell proliferation was rapidly inhibited by treatment with the iron chelators and NaB. In contrast, RA did not influence the rate of increase of cell number at the concentration of 1 μm. The three chelators also caused a marked reduction in cell viability, and the treated cells exhibited internucleosomal DNA fragmentation, whereas cells treated with NaB showed no apoptotic characteristics. RA induced apoptosis weakly at 1μm and strongly at higher concentrations. In addition, all the iron chelators hindered cell cycle progression, resulting in an arrest at the G1‐S interface or S phase. The phenomena observed in chelator‐treated cells were considerably different from those in RA‐ or NaB‐treated cells. It is concluded that the three iron chelators cause both severe apoptotic cell death and cell cycle arrest of proliferating F9 cells via cellular iron deprivation, and that this apoptotic change may be independent of the process of differentiation.
Foliose and placodioid species of the lichen family Physciaceae in southernmost Chile
Authors: Elvebakk Arve , Moberg Roland
Published: October 2002

Ten foliose and placodioid species of Physciaceae are reported from the National Park Torres del Paine and from other areas in southernmost Chile. Phaeophyscia constipate and Physconia perisidiosa are reported as new to the Southern Hemisphere, Phaeophyscia endococcina var. endococcina and Phaeorrhiza nimbosa as new to South America, and Dimelaena oreina and Physcia kalbii as new to Chile. The latter was recorded only from the island of Chiloé. Dimelaena appears to be rare in Magallanes and has been recorded only from one steppe locality. Phaeophyscia constipate and Phaeorrhiza nimbosa appear to be confined to the driest steppes, in areas with occurrences of rock outcrops associated with calcareous soil. Physconia muscigena has a similar habitat ecology, but a wider distribution, and is quite common. Physconia perisidiosa and Physcia adscendens were found to be very common in all bioclimatic zones surveyed in the lowland of Torres del Paine. The Physciaceae species treated here are all bipolar or subcosmopolitan, and belong to genera lacking an austral or South American element in the area studied, in contrast to the pattern in all other reasonably large macrolichen groups, except among cetrarioid genera. Their habitat ecology is also very similar to conditions known in the Northern Hemisphere. On the other hand, other widely distributed Northern Hemisphere species such as Physcia stellaris and P. aipolia have known distribution patterns in South America which are disjunct and northern and very different from those of the species treated here.
Late Quaternary Geological History of the Dead Sea Area, Israel
Authors: Yechieli Y. , Magaritz M. , Levy Y. , Weber U. , Kafri U. , Woelfli W. , Bonani G.
Published: October 2002

A 34.5 m borehole, which was drilled near the Dead Sea coast (altitude -394 m) in the southern part of the fan delta of Wadi Zeelim, reveals the geological history of that area from the latest Pleistocene to present. The depositional time frame is based on six 14C dates and two U-Th dates. An erosional (or nondepositional) period is implied by the hiatus between 21,100 yr B.P. (U-Th age, depth 33 m) and 11,315 yr B.P. (14C age, depth 32 m). A subsequent arid phase is recorded by a 6.5-m-thick layer of halite; based on 14C dates this phase relates to the abrupt Younger Dryas cold period reported in temperate to polar regions. The fragility of the environment in this region is indicated by the fact that the region experienced such a severe, short aridification phase (less than 1000 yr), evidence of which is found widely in the desert fringes of the Middle East and North Africa. The aragonite found in most of the Holocene section indicates that the well site was covered by the lake for most of the Holocene. Exceptions are the intervals at 0-3 and 10-14 m depths which represent low stands of the lake.