bluuebunny/crossref_metadata_2025 huggingface dataset:
Seasonal variation in competitive effect on water stress and pine responses
Authors: Perry M.A. , Mitchell R.J. , Zutter B.R. , Glover G.R. , Gjerstad D.H.
Published: August 2009

Plant mixtures were established that differed in both proportion and density of loblolly pine (Pinustaeda L.), sweetgum (Liquidambarstyraciflua L.), and broomsedge (Andropogonvirginicus L.). Soil moisture availability to the pine seedlings was quantified every 2 weeks by measuring predawn xylem pressure potentials. Temporal variation in pine water potential was accounted for by a water stress integral approach. Cumulative water stress integral values were calculated over four overlapping periods, from May to June, May to July, May to August, and May to September and compared with the mean seedling stem volume index at each period to determine competitive responses at the whole plant scale. Diurnal measures of stomatal conductance were taken each month to compare competitive responses at the leaf scale. In addition, environmental and plant responses that may control stomatal behavior were quantified. The pine water stress integral was strongly influenced by competing vegetation after the onset of a period of drought in early summer. The correlation between the water stress integral and pine growth increased after a significant drying period, accounting for more than half of the variation in stem volume index at the end of the first growing season. Stomatal conductance was also influenced by competition, with competitive effects more evident during times of drought. Conductance was most often related to bulk leaf water potential, which in turn was related to competitive effects on soil moisture availability. Vapor pressure deficit also influenced stomatal conductance, but this was largely unrelated to competitive effects.
Starch synthesis and localization in post-germination Pinusedulis seedlings
Authors: Murphy J. Brad , Hammer Mark F.
Published: August 2009

Following pine seed germination, lipids in the megagametophyte are converted to sucrose, which is transported to the emerging seedling to support its growth. In several conifer species, an increase in the seedling starch content following germination has been reported. To further characterize this phenomenon, starch accumulation and localization, starch synthase (EC 2.4.1.21) activity (both soluble and granule-bound), and partitioning of exogenous 14C-sucrose were determined following germination of pinyon (Pinusedulis Engelm.) seeds. Starch was a minor component in dry embryos, accounting for only 3% of the dry weight. Starch levels increased 22-fold and 15-fold in the cotyledons and hypocotyl, respectively, by 8 days after germination. Starch accumulated to 65% of the dry weight in the cotyledons and 46% in the hypocotyl. The root and epicotyl accumulated relatively low levels of starch, only about 7%. Starch was localized primarily in the cortex and pith of the hypocotyl, the cortex of the cotyledons, and the root cap. Only granule-bound starch synthase showed a significant increase in activity during germination, and its changes more closely followed the pattern of starch accumulation. Exogenous 14C-sucrose was partitioned primarily into starch. After a 24-h labeling period, starch in both the cotyledons and hypocotyl accounted for 38% of total label (61% of the incorporated label) in these organs. In the roots, starch accounted for only 2.5 and 14%, respectively, of the total and incorporated label. The spatial and temporal pattern of starch accumulation closely paralleled previously reported patterns for the activity of sucrose synthase, which is apparently associated with the sucrose–starch conversion. Starch accumulation in the seedling accounts for approximately 50% of the sucrose transported from the megagametophyte following pinyon seed germination. Thus, starch appears to serve as an important transitory carbon pool for the growing seedling and may serve additional functions during seedling development.
Comparison of sequential and double sampling designs for estimating point density within seedling populations
Authors: Newton P.F.
Published: August 2009

Sequential and double sampling plans calibrated for estimating point density (mean number of seedlings per quadrat) at a specified level of precision (ratio of the standard error of the mean to the mean) within mixed black spruce (Piceamariana (Mill.) B.S.R)–balsam fir (Abiesbalsamea (L.) Mill.) seedling populations were compared using sampling simulations. Specifically, plans employing a precision level of 0.25 and 10.1-m2 quadrat size were assessed on the following criteria: (i) total number of samples required; (ii) bias in the resultant point density estimates; and (iii) bias in precision levels attained (i.e., difference between the precision level specified in the plans and the actual levels obtained during sampling). The data base consisted of three population clusters derived from forty-three 0.121-ha sample plots situated on recently disturbed sites throughout central insular Newfoundland. Variation in stocking level and spatial pattern heterogeneity characterized differences between clusters: low stocking levels and highly aggregated spatial patterns (cluster A), moderate stocking levels and aggregated spatial patterns (cluster B), and high stocking levels and slightly aggregated spatial patterns (cluster C). Results indicated that the sequential plan required fewer samples than the double sampling plan irrespective of cluster conditions. The percentage of point density estimates within ±25% of their population cluster means obtained from sequential sampling was 63, 71, and 68% for clusters A, B, and C, respectively. Corresponding values for double sampling were 68, 75, and 73% for clusters A, B, and C, respectively. The percentage of sequential simulations in which the specified precision was attained or exceeded was 34, 64, and 61% for clusters A, B, and C, respectively. Corresponding values for double sampling were 51, 77, and 71% for clusters A, B, and C, respectively. Although these results suggest that double sampling may be a practical alternative to sequential sampling, further research into the economic consequences of increased sample sizes coupled with decreased survey distances at various scales is required before the operational utility of the plan is fully ascertained.
Tissue water relations of Pinusponderosa and Arctostaphylospatula exposed to various levels of soil moisture depletion
Authors: Anderson Paul D. , Helms John A.
Published: August 2009

The tissue water relations of Pinusponderosa Dougl. ex Laws, (ponderosa pine) and Arctostaphylospatula Greene (greenleaf manzanita) seedlings subjected to three levels of soil moisture availability were monitored over a 6-month period. Throughout the study, osmotic potentials at full turgor and at the turgor loss point were approximately 0.5 MPa greater for pine than for manzanita. Osmotic adjustment occurred for both species as evidenced by declines in osmotic potentials at full turgor and at the turgor loss point of 0.5–0.6 MPa over the study period. Pine maintained higher bulk tissue elasticity and lower water content at the turgor loss point relative to manzanita. Moisture regime had little effect on the measured parameters except for apoplasmic water content which increased at moderate and high stress levels for both species. Results suggest that osmotic adjustment occurred, at least partially, as a result of factors other than moisture availability. The lower tissue elasticity and higher water content at the turgor loss point for manzanita suggest that the shrub species is more dependent upon high foliar water content for the maintenance of turgor compared with the conifer.
A device for assisting in the recovery of jammed increment borers from trees
Authors: Murphy John O.
Published: August 2009

A simple device for assisting in the recovery of a jammed increment borer from a tree or log is described. The low-cost parts are readily obtained.
TOPOLOGICAL HORSESHOES AND COMPUTER ASSISTED VERIFICATION OF CHAOTIC DYNAMICS
Authors: YANG XIAO-SONG
Published: August 2009

In this tutorial paper, we present a history of Smale horseshoe and an overview of the progress of topological horseshoe theory. Then we offer a pedagogical exposition of elements of topological horseshoe theory with a lot of examples. Finally we demonstrate some typical applications of topological horseshoe theory to practical dynamical systems.
ON THE DYNAMICAL BEHAVIOR OF CELLULAR AUTOMATA
Authors: XU XU , SONG YI , BANKS STEPHEN P.
Published: August 2009

In this paper, we show that the mathematical classification of one-dimensional cellular automata given by Dubois–Violette and Rouet [1987] does not truly represent the different behaviors possible. In fact we show that many rules of their type O have totally different behavior. A better classification is based on Smale's basic sets and nonwandering points.
SYNCHRONY-BREAKING PERIOD-DOUBLING BIFURCATIONS FOR THREE-CELL HOMOGENEOUS COUPLED MAPS
Authors: COMANICI ADELA
Published: August 2009

Network architecture can lead to robust synchrony in coupled maps and to codimension one bifurcations from synchronous fixed-points at which the associated Jacobian is nilpotent.

We discuss the codimension one synchrony-breaking period-doubling bifurcations for three-cell coupled maps. Interesting phenomena occur for all these coupled maps — a branch of period-2 points with amplitude growing as |λ|⅙ for coupled networks of feed-forward type, as well as multiple (two) branches of period-2 points with amplitude growing as |λ|½ for coupled networks of feed-forward type.

We also discuss how some results related to patterns of synchrony that are valid for coupled vector fields are also valid for coupled maps.
IRREGULARLY DECIMATED CHAOTIC MAP(S) FOR BINARY DIGITS GENERATIONS
Authors: KANSO ALI , SMAOUI NEJIB
Published: August 2009

This paper proposes a new technique for generating random-looking binary digits based on an irregularly decimated chaotic map. We present a class of irregularly decimated chaos-based keystream generators, related to the shrinking generator, for the generation of binary sequences. Each generator consists of two subsystems: a control subsystem and a generating subsystem, where each subsystem is based on a single chaotic map. This chaotic map is presented as a 1-D piecewise chaotic map related to the chaotic logistic map. We conduct an analysis of the dynamical behavior of the proposed map to integrate it as a component in the proposed generators subsystems. The output bits of these keystream generators are produced by applying a threshold function to convert the floating-point iterates of the irregularly decimated map into a binary form. The generated keystream bits are demonstrated to exhibit high level of security, long period length, high linear complexity measure and random-like properties at given certain parameter values. Standard statistical tests on the proposed generators, as well as other keystream generators, are performed and compared.
BEHAVIOR OF HARMONICS GENERATED BY A DUFFING TYPE EQUATION WITH A NONLINEAR DAMPING: PART II
Authors: KHAMMARI HÉDI , MIRA CHRISTIAN
Published: August 2009

This paper is Part II of an earlier paper dealing with the numerical study of a two-dimensional nonautonomous ordinary differential equation with a strong cubic nonlinearity, and an external periodical excitation of period τ = 2π/ω (amplitude E). In the absence of this excitation, this equation of Duffing type does not give rise to self-oscillations. Part I was essentially devoted to analyze the harmonics behavior of period τ solutions, more precisely the behavior of rank-p harmonics according to the points of the parameter plane (ω,E). The present Part II deals with period kτ solutions related to a cascade of closed fold bifurcation curves related to fractional harmonics p/k, k = 3, p = 3,4,…. With respect to the organization of bifurcation curves associated with rank-p harmonics of the basic period τ, this study shows that the situation is a lot more complex for the sequence of bifurcation curves related to rank-p/3 harmonics.
MODEL REDUCTION OF TURBULENT FLUID FLOWS USING THE SUPPLY RATE
Authors: SHARMA A. S.
Published: August 2009

A method for finding reduced-order approximations of turbulent flow models is presented. The method preserves bounds on the production of turbulent energy in the sense of the [Formula: see text] norm of perturbations from a notional laminar profile. This is achieved by decomposing the Navier–Stokes system into a feedback arrangement between the linearized system and the remaining, normally neglected, nonlinear part. The linear system is reduced using a method similar to balanced truncation, but preserving bounds on the supply rate. The method involves balancing two algebraic Riccati equations. The bounds are then used to derive bounds on the turbulent energy production. An example of the application of the procedure to flow through a long straight pipe is presented. Comparison shows that the new method approximates the supply rate at least as well as, or better than, canonical balanced truncation.
INFLUENCE OF OPTIMAL CONTROL ON BIFURCATIONS OF 3D AXISYMMETRIC BUOYANT FLOWS
Authors: NAVARRO M. C. , HERRERO H.
Published: August 2009

This paper shows the effects of optimal control techniques on pattern formation in a three-dimensional Rayleigh–Bénard problem with nonhomogeneous heating from below. In particular, we consider a cylindrical domain with a heating profile at the bottom localized around the origin. An axisymmetric basic state appears as soon a nonzero horizontal temperature gradient is imposed. The basic state may bifurcate to different solutions as spiral waves, stationary patterns, etc., depending on the vertical and lateral temperature gradients and on the shape of the heating function. An optimal control problem that determines the thermal boundary condition minimizing the enstrophy is proposed. The control boundary condition obtained changes the leading mode in the bifurcation and allows to eliminate the instabilities for some values of the parameters.
BREAKING WAVE SOLUTIONS TO THE SECOND CLASS OF SINGULAR NONLINEAR TRAVELING WAVE EQUATIONS
Authors: LI JIBIN , ZHAO XIAOHUA , CHEN GUANRONG
Published: August 2009

The existence of breaking wave solutions of the second class of singular nonlinear wave equations is proved by methods from the dynamical systems theory. For the second class of singular nonlinear traveling wave equations, dynamical behaviors of the traveling wave solutions are completely classified and thoroughly discussed. Corresponding to some bounded orbits of the traveling systems, exact parametric representations of traveling wave solutions are derived within different parameter regions of the parameter space.
BREAKING A SC-CNN-BASED CHAOTIC MASKING SECURE COMMUNICATION SYSTEM
Authors: ORUE AB. , FERNANDEZ V. , ALVAREZ G. , PASTOR G. , ROMERA M. , MONTOYA F. , SANCHEZ-AVILA C. , LI SHUJUN
Published: August 2009

This paper studies the security of a chaotic cryptosystem based on Chua's circuit and implemented with State Controlled Cellular Neural Networks (SC-CNN). Here, we prove that the plaintext can be retrieved by bandpass filtering of the ciphertext or by using an imperfect decoder with wrong receiver parameters. In addition, we find that the key space of the system can be reduced notably, and the required resolution of the parameter values to recover a meaningful plaintext is as coarse as 5%, easing a brute-force attack. The system parameters can be determined with high precision through the analysis of the decoding error produced by the mismatch between the parameters of receiver and transmitter.
RECONFIGURABLE IMPLEMENTATIONS OF CHUA'S CIRCUIT
Authors: KILIC RECAI , DALKIRAN FATMA YILDIRIM
Published: August 2009

Chua's circuit is very suitable as a programmable chaos generator because of its robust nonlinearity. In addition to exhibiting a rich variety of bifurcation and chaos phenomenon, this circuit can be modeled and realized with a fixed main system block and many different nonlinear function blocks such as piecewise-linear function, cubic-like function, piecewise-quadratic function and other trigonometric functions. This paper presents a FPAA (Field Programmable Analog Array) based programmable implementation of Chua's circuit. Nonlinear function blocks used in Chua's circuit are modeled with an FPAA and hence a model can be rapidly changed for realization of other nonlinear functions. In this study, four FPAA-based reconfigurable implementations of Chua's circuit have been realized. Experimental results agree with numerical simulation and results obtained from discrete electronic implementations of Chua's circuit.
A PIECEWISE LINEAR DYNAMICAL SYSTEM WITH TWO DROPPING SECTIONS
Authors: GAIKO VALERY A. , VAN HORSSEN WIM T.
Published: August 2009

In this paper, we consider a planar dynamical system with a piecewise linear function containing two dropping sections and approximating some continuous nonlinear function. Studying all possible local and global bifurcations of its limit cycles, we prove that such a piecewise linear dynamical system, with five singular points, can have at most four limit cycles, three of which surround the foci one by one and the fourth limit cycle surrounds all of the singular points of this system.
$\overline{R} = \overline{P}$ FOR MAPS OF DENDRITES X WITH Card(End(X)) < c
Authors: MAI JIEHUA , SHI ENHUI
Published: August 2009

Let X be a dendrite and f : X → X be a continuous map. Denote by R(f) and P(f) the sets of recurrent points and periodic points of f respectively. In this paper we show that, if the cardinal number Card ( End (X)) of the set of endpoints of X is less than the cardinal number c of the continuum, then [Formula: see text]. From this we derive that, if Card ( End (X)) < c, then f is chaotic in the sense of Devaney if and only if f is transitive.
ON MINIMALLY COUPLED BOOLEAN NETWORKS
Authors: ALONSO-SANZ RAMÓN , BULL LARRY
Published: August 2009

Traditional Boolean networks consist of nodes within a single network, each updating synchronously, although asynchronous versions have also been presented. In this paper the dynamics of two, mutually coupled traditional networks are investigated. In particular, the effects of varying the degree and type of intra-network connectivity are explored. The effects from different inter-network evolution rates are then considered, i.e. asynchronousity at the network level is examined. Finally, state memory is included within the nodes of coupled networks and shown to alter the dynamics of the networks under certain circumstances.
CONTROLLING HOPF BIFURCATION IN FLUID FLOW MODEL OF INTERNET CONGESTION CONTROL SYSTEM
Authors: DING DAWEI , ZHU JIE , LUO XIAOSHU , LIU YULIANG
Published: August 2009

In this paper, a time-delayed feedback controller is applied to a fluid flow model of Internet congestion control system in order to control Hopf bifurcation. It has been shown that the system without control loses stability and a Hopf bifurcation occurs when the bifurcation parameter, which is the communication delay of the model, passes through a critical value. Therefore, a control approach based on delayed feedback is proposed to postpone the onset of undesired Hopf bifurcation. Theoretical analysis and numerical simulations confirm that the controller is efficient in bifurcation control of the Internet congestion control system.
AN EXTENDED ŠIL'NIKOV HOMOCLINIC THEOREM AND ITS APPLICATIONS
Authors: CHEN BAOYING , ZHOU TIANSHOU , CHEN GUANRONG
Published: August 2009

The classical Šil'nikov homoclinic theorem provides an analytic criterion for proving the existence of chaos in three-dimensional autonomous systems, but it can only be applied to systems with fixed points of the saddle-focus type. This paper extends this powerful theorem to a degenerate case where one of the eigenvalues of the Jacobian evaluated at an equilibrium point is zero and the other two are a pair of conjugate complex numbers, and consequently establishes a set of criteria for proving the existence of chaos in the sense of having Smale horseshoes. Based on this new extended Šil'nikov homoclinic theorem, a new chaotic system is constructed, whose corresponding bounded chaotic attractor is first verified numerically through phase trajectories, Lyapunov exponents, bifurcation routes and Poincaré mappings, followed by theoretical analysis on the existence of one homoclinic orbit, the key component of the extended Šil'nikov homoclinic theorem.
SIMPLEST NORMAL FORMS FOR PLANAR SYSTEMS ON EQUILIBRIUM MANIFOLDS
Authors: LIN MU , TANG YUN , CHEN GUANRONG , SHI YUMING
Published: August 2009

Equilibrium manifold is a manifold that consists of equilibrium points. Planar systems with one-dimensional equilibrium manifolds are considered in this paper. First, for such planar systems, a unified equation with the horizontal axis as the equilibrium curve is formulated. Then, according to the corresponding linearized systems, different cases are discussed: For the nondegenerate case, the simplest normal form of a system with simplified Bogdanov–Takens singularities is obtained; for the general first-order degenerative case, the simplest normal forms are completely characterized; finally, for the general higher-order degenerative case, deduction of the simplest normal form is illustrated.
ON TWO-DIMENSIONAL DYNAMICAL SYSTEMS ASSOCIATED WITH MEMBRANE KINETICS UNDERLYING CARDIAC ARRHYTHMIAS
Authors: BAKER B. M. , KIDWELL M. E. , KLINE R. P. , POPOVICI I.
Published: August 2009

We study the orbits, stability and coexistence of orbits in the two-dimensional dynamical system introduced by Kline and Baker to model cardiac rhythmic response to periodic stimulation — as a function of (a) kinetic parameters (two amplitudes, two rate constants) and (b) stimulus period. The original paper focused mostly on the one-dimensional version of this model (one amplitude, one rate constant), whose orbits, stability properties, and bifurcations were analyzed via the theory of skew-tent (hence unimodal) maps; the principal family of orbits were so-called "n-escalators", with n a positive integer.

The two-dimensional analog (motivated by experimental results) has led to the current study of continuous, piecewise smooth maps of a polygonal planar region into itself, whose dynamical behavior includes the coexistence of stable orbits. Our principal results show (1) how the amplitude parameters control which escalators can come into existence, (2) escalator bifurcation behavior as the stimulus period is lowered — leading to a "1/n bifurcation law", and (3) the existence of basins of attraction via the coexistence of three orbits (two of them stable, one unstable) at the first (largest stimulus period) bifurcation. We consider the latter result our most important, as it is conjectured to be connected with arrhythmia.
A NONLINEAR DYNAMICS PERSPECTIVE OF WOLFRAM'S NEW KIND OF SCIENCE. PART X: PERIOD-1 RULES
Authors: CHUA LEON O. , PAZIENZA GIOVANNI E. , SHIN JINWOOK
Published: August 2009

This stage of our journey through the universe of one-dimensional binary Cellular Automata is devoted to period-1 rules, constituting the first of the six groups in which we systematized the 88 globally-independent CA rules.

The first part of this article is mainly dedicated to reviewing the terminology and the empirical results found in the previous papers of our quest. We also introduce the concept of the ω-limit orbit with the purpose of linking our work to the classical theory of nonlinear dynamical systems. Moreover, we present the basin tree diagrams of all period-1 rules — except for rule [Formula: see text], which is trivial — along with their Boolean cubes and time-1 characteristic functions.

In the second part, we prove a theorem demonstrating that all rules belonging to group 1 have robust period-1 rules for any finite, and infinite, bit-string length L. This is the first time we give analytical results on the behavior of CA local rules for large values of L and, consequently, for bi-infinite bit strings.

The theoretical treatment is complemented by two remarkable practical results: an explicit formula for generating isomorphic basin trees, and an algorithm for creating new periodic orbits by concatenation. We also provide several examples of both of them, showing how they help to avoid tedious simulations.
Proving that non-blocking algorithms don't block
Authors: Gotsman Alexey , Cook Byron , Parkinson Matthew , Vafeiadis Viktor
Published: August 2009

A concurrent data-structure implementation is considered non-blocking if it meets one of three following liveness criteria: wait-freedom, lock-freedom, or obstruction-freedom. Developers of non-blocking algorithms aim to meet these criteria. However, to date their proofs for non-trivial algorithms have been only manual pencil-and-paper semi-formal proofs. This paper proposes the first fully automatic tool that allows developers to ensure that their algorithms are indeed non-blocking. Our tool uses rely-guarantee reasoning while overcoming the technical challenge of sound reasoning in the presence of interdependent liveness properties.
A model of cooperative threads
Authors: Abadi Martin , Plotkin Gordon
Published: August 2009

We develop a model of concurrent imperative programming with threads. We focus on a small imperative language with cooperative threads which execute without interruption until they terminate or explicitly yield control. We define and study a trace-based denotational semantics for this language; this semantics is fully abstract but mathematically elementary. We also give an equational theory for the computational effects that underlie the language, including thread spawning. We then analyze threads in terms of the free algebra monad for this theory.
Static contract checking for Haskell
Authors: Xu Dana N. , Peyton Jones Simon , Claessen Koen
Published: August 2009

Program errors are hard to detect and are costly both to programmers who spend significant efforts in debugging, and for systems that are guarded by runtime checks. Static verification techniques have been applied to imperative and object-oriented languages, like Java and C#, but few have been applied to a higher-order lazy functional language, like Haskell. In this paper, we describe a sound and automatic static verification framework for Haskell, that is based on contracts and symbolic execution. Our approach is modular and gives precise blame assignments at compile-time in the presence of higher-order functions and laziness.
Masked types for sound object initialization
Authors: Qi Xin , Myers Andrew C.
Published: August 2009

This paper presents a type-based solution to the long-standing problem of object initialization. Constructors, the conventional mechanism for object initialization, have semantics that are surprising to programmers and that lead to bugs. They also contribute to the problem of null-pointer exceptions, which make software less reliable. Masked types are a new type-state mechanism that explicitly tracks the initialization state of objects and prevents reading from uninitialized fields. In the resulting language, constructors are ordinary methods that operate on uninitialized objects, and no special default value (null) is needed in the language. Initialization of cyclic data structures is achieved with the use of conditionally masked types. Masked types are modular and compatible with data abstraction. The type system is presented in a simplified object calculus and is proved to soundly prevent reading from uninitialized fields. Masked types have been implemented as an extension to Java, in which compilation simply erases extra type information. Experience using the extended language suggests that masked types work well on real code.
Flexible types
Authors: Leijen Daan
Published: August 2009

We present HML, a type inference system that supports full first-class polymorphism where few annotations are needed: only function parameters with a polymorphic type need to be annotated. HML is a simplification of MLF where only flexibly quantified types are used. This makes the types easier to work with from a programmers perspective, and simplifies the implementation of the type inference algorithm. Still, HML retains much of the expressiveness of MLF, it is robust with respect to small program transformations, and has a simple specification of the type rules with an effective type inference algorithm that infers principal types. A small reference implementation with many examples is available at: http://research.microsoft.com/users/daan/pubs.html.
Formal certification of code-based cryptographic proofs
Authors: Barthe Gilles , Grégoire Benjamin , Zanella Béguelin Santiago
Published: August 2009

As cryptographic proofs have become essentially unverifiable, cryptographers have argued in favor of developing techniques that help tame the complexity of their proofs. Game-based techniques provide a popular approach in which proofs are structured as sequences of games and in which proof steps establish the validity of transitions between successive games. Code-based techniques form an instance of this approach that takes a code-centric view of games, and that relies on programming language theory to justify proof steps. While code-based techniques contribute to formalize the security statements precisely and to carry out proofs systematically, typical proofs are so long and involved that formal verification is necessary to achieve a high degree of confidence. We present Certicrypt, a framework that enables the machine-checked construction and verification of code-based proofs. Certicrypt is built upon the general-purpose proof assistant Coq, and draws on many areas, including probability, complexity, algebra, and semantics of programming languages. Certicrypt provides certified tools to reason about the equivalence of probabilistic programs, including a relational Hoare logic, a theory of observational equivalence, verified program transformations, and game-based techniques such as reasoning about failure events. The usefulness of Certicrypt is demonstrated through various examples, including a proof of semantic security of OAEP (with a bound that improves upon existing published results), and a proof of existential unforgeability of FDH signatures. Our work provides a first yet significant step towards Halevi's ambitious programme of providing tool support for cryptographic proofs.
Wild control operators
Authors: Barker Chris
Published: August 2009

Linguists seek to understand the semantics of expressions in human languages. Certainly there are many natural language expressions--operators in the wild, so to speak--that control evaluation in ways that are familiar from programming languages: just think of the natural-language counterparts of
if
,
unless
,
while
, etc. But in general, how well-behaved are control operators found in the wild? Can we always understand them in terms of familiar programming constructs, or do they go significantly beyond the expressive power of programming languages?

As an example where operators from a programming langauge can provide an insightful analysis of a natural language construction, consider the difference in meaning between the following two sentences:

(1) a. & John only drinks PERRIER. (emphasis on
Perrier
)

b. John only DRINKS Perrier. (emphasis on
drinks
)

The first sentence entails that John never drinks, say, Evian, but the second sentence entails instead that John never does anything (relevant) with Perrier except drink it. I will suggest that we can understand this difference by expressing the meanings of these sentences in terms of Sitaram's
fcontrol
and
run
operators (variants on
throw
and
catch
).

But not all wild operators are so easily captured. I will discuss in some detail the meaning of the word
same
in English as it occurs in the following sentence:

(2) & John and Bill read the same book.

This sentence has a prominent interpretation on which it means (roughly) 'there is some book
x
such that John read
x
and Bill read
x
. I provide a preliminary analysis based on Danvy and Filinski's
shift
and
reset
. However, the
shift reset
approach does not generalize to the full range of related sentences in English. I give a more general solution expressed in a Type Logical Grammar (a certain kind of substructural logic) with explicit continuations. But even this is inadequate: I go on to discuss additional, only slightly less ordinary uses of
same
that remain untamed by any known compositional semantics.
Lazy evaluation and delimited control
Authors: Garcia Ronald , Lumsdaine Andrew , Sabry Amr
Published: August 2009

The call-by-need lambda calculus provides an equational framework for reasoning syntactically about lazy evaluation. This paper examines its operational characteristics.

By a series of reasoning steps, we systematically unpack the standard-order reduction relation of the calculus and discover a novel abstract machine definition which, like the calculus, goes "under lambdas." We prove that machine evaluation is equivalent to standard-order evaluation.

Unlike traditional abstract machines, delimited control plays a significant role in the machine's behavior. In particular, the machine replaces the manipulation of a heap using store-based effects with disciplined management of the evaluation stack using control-based effects. In short, state is replaced with control.

To further articulate this observation, we present a simulation of call-by-need in a call-by-value language using delimited control operations.
The third homomorphism theorem on trees
Authors: Morihata Akimasa , Matsuzaki Kiminori , Hu Zhenjiang , Takeichi Masato
Published: August 2009

Parallel programs on lists have been intensively studied. It is well known that associativity provides a good characterization for divide-and-conquer parallel programs. In particular, the third homomorphism theorem is not only useful for systematic development of parallel programs on lists, but it is also suitable for automatic parallelization. The theorem states that if two sequential programs iterate the same list leftward and rightward, respectively, and compute the same value, then there exists a divide-and-conquer parallel program that computes the same value as the sequential programs.

While there have been many studies on lists, few have been done for characterizing and developing of parallel programs on trees. Naive divide-and-conquer programs, which divide a tree at the root and compute independent subtrees in parallel, take time that is proportional to the height of the input tree and have poor scalability with respect to the number of processors when the input tree is ill-balanced.

In this paper, we develop a method for systematically constructing scalable divide-and-conquer parallel programs on trees, in which two sequential programs lead to a scalable divide-andconquer parallel program. We focus on paths instead of trees so as to utilize rich results on lists and demonstrate that associativity provides good characterization for scalable divide-and-conquer parallel programs on trees. Moreover, we generalize the third homomorphism theorem from lists to trees.We demonstrate the effectiveness of our method with various examples. Our results, being generalizations of known results for lists, are generic in the sense that they work well for all polynomial data structures.
Feedback-directed barrier optimization in a strongly isolated STM
Authors: Bronson Nathan G. , Kozyrakis Christos , Olukotun Kunle
Published: August 2009

Speed improvements in today's processors have largely been delivered in the form of multiple cores, increasing the importance of abstractions that ease parallel programming. Software transactional memory (STM) addresses many of the complications of concurrency by providing a simple and composable model for safe access to shared data structures. Software transactions extend a language with an atomic primitive that declares that the effects of a block of code should not be interleaved with actions executing concurrently on other threads. Adding barriers to shared memory accesses provides atomicity, consistency and isolation.

Strongly isolated STMs preserve the safety properties of transactions for all memory operations in a program, not just those inside an atomic block. Isolation barriers are added to non-transactional loads and stores in such a system to prevent those accesses from observing or corrupting a partially completed transaction. Strong isolation is especially important when integrating transactions into an existing language and memory model. Isolation barriers have a prohibitive performance overhead, however, so most STM proposals have chosen not to provide strong isolation.

In this paper we reduce the costs of strong isolation by customizing isolation barriers for their observed usage. The customized barriers provide accelerated execution by blocking threads whose accesses do not follow the expected pattern. We use hot swap to tighten or loosen the hypothesized pattern, while preserving strong isolation. We introduce a family of optimization hypotheses that balance verification cost against generality.

We demonstrate the feasibility of dynamic barrier optimization by implementing it in a bytecode-rewriting Java STM. Feedback-directed customization reduces the overhead of strong isolation from 505% to 38% across 11 non-transactional benchmarks; persistent feedback data further reduces the overhead to 16%. Dynamic optimization accelerates a multi-threaded transactional benchmark by 31% for weakly-isolated execution and 34% for strongly-isolated execution.
Semi-sparse flow-sensitive pointer analysis
Authors: Hardekopf Ben , Lin Calvin
Published: August 2009

Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-sensitivity, and while there has been significant recent progress regarding scalable context-sensitive pointer analysis, relatively little progress has been made in improving the scalability of flow-sensitive pointer analysis.

This paper presents a new interprocedural, flow-sensitive pointer analysis algorithm that combines two ideas-semi-sparse analysis and a novel use of BDDs-that arise from a careful understanding of the unique challenges that face flow-sensitive pointer analysis. We evaluate our algorithm on 12 C benchmarks ranging from 11K to 474K lines of code. Our fastest algorithm is on average 197x faster and uses 4.6x less memory than the state of the art, and it can analyze programs that are an order of magnitude larger than the previous state of the art.
A combination framework for tracking partition sizes
Authors: Gulwani Sumit , Lev-Ami Tal , Sagiv Mooly
Published: August 2009

We describe an abstract interpretation based framework for proving relationships between sizes of memory partitions. Instances of this framework can prove traditional properties such as memory safety and program termination but can also establish upper bounds on usage of dynamically allocated memory. Our framework also stands out in its ability to prove properties of programs manipulating both heap and arrays which is considered a difficult task. Technically, we define an abstract domain that is parameterized by an abstract domain for tracking memory partitions (sets of memory locations) and by a numerical abstract domain for tracking relationships between cardinalities of the partitions. We describe algorithms to construct the transfer functions for the abstract domain in terms of the corresponding transfer functions of the parameterized abstract domains. A prototype of the framework was implemented and used to prove interesting properties of realistic programs, including programs that could not have been automatically analyzed before.
The theory of deadlock avoidance via discrete control
Authors: Wang Yin , Lafortune Stéphane , Kelly Terence , Kudlur Manjunath , Mahlke Scott
Published: August 2009

Deadlock in multithreaded programs is an increasingly important problem as ubiquitous multicore architectures force parallelization upon an ever wider range of software. This paper presents a theoretical foundation for dynamic deadlock avoidance in concurrent programs that employ conventional mutual exclusion and synchronization primitives (e.g., multithreaded C/Pthreads programs). Beginning with control flow graphs extracted from program source code, we construct a formal model of the program and then apply Discrete Control Theory to automatically synthesize deadlock-avoidance control logic that is implemented by program instrumentation. At run time, the control logic avoids deadlocks by postponing lock acquisitions. Discrete Control Theory guarantees that the program instrumented with our synthesized control logic cannot deadlock. Our method furthermore guarantees that the control logic is maximally permissive: it postpones lock acquisitions only when necessary to prevent deadlocks, and therefore permits maximal runtime concurrency. Our prototype for C/Pthreads scales to real software including Apache, OpenLDAP, and two kinds of benchmarks, automatically avoiding both injected and naturally occurring deadlocks while imposing modest runtime overheads.
Equality saturation
Authors: Tate Ross , Stepp Michael , Tatlock Zachary , Lerner Sorin
Published: August 2009

Optimizations in a traditional compiler are applied sequentially, with each optimization destructively modifying the program to produce a transformed program that is then passed to the next optimization. We present a new approach for structuring the optimization phase of a compiler. In our approach, optimizations take the form of equality analyses that add equality information to a common intermediate representation. The optimizer works by repeatedly applying these analyses to infer equivalences between program fragments, thus saturating the intermediate representation with equalities. Once saturated, the intermediate representation encodes multiple optimized versions of the input program. At this point, a profitability heuristic picks the final optimized program from the various programs represented in the saturated representation. Our proposed way of structuring optimizers has a variety of benefits over previous approaches: our approach obviates the need to worry about optimization ordering, enables the use of a global optimization heuristic that selects among fully optimized programs, and can be used to perform translation validation, even on compilers other than our own. We present our approach, formalize it, and describe our choice of intermediate representation. We also present experimental results showing that our approach is practical in terms of time and space overhead, is effective at discovering intricate optimization opportunities, and is effective at performing translation validation for a realistic optimizer.
Linear types for computational effects
Authors: Simpson Alex
Published: August 2009

I shall present an extension of Moggi's computational metalanguage with primitives from linear logic, the enriched effect-calculus. Illustrative applications to side effects, continuations, nondeterminism and polymorphism will be considered. The talk is based on joint work with Jeff Egger and Rasmus Mogelberg.
Classical BI
Authors: Brotherston James , Calcagno Cristiano
Published: August 2009

We show how to extend O'Hearn and Pym's logic of bunched implications, BI, to classical BI (CBI), in which both the additive and the multiplicative connectives behave classically. Specifically, CBI is a non-conservative extension of (propositional) Boolean BI that includes multiplicative versions of falsity, negation and disjunction. We give an algebraic semantics for CBI that leads us naturally to consider resource models of CBI in which every resource has a unique dual. We then give a cut-eliminating proof system for CBI, based on Belnap's display logic, and demonstrate soundness and completeness of this proof system with respect to our semantics.
The semantics of x86-CC multiprocessor machine code
Authors: Sarkar Susmit , Sewell Peter , Nardelli Francesco Zappa , Owens Scott , Ridge Tom , Braibant Thomas , Myreen Magnus O. , Alglave Jade
Published: August 2009

Multiprocessors are now dominant, but real multiprocessors do not provide the sequentially consistent memory that is assumed by most work on semantics and verification. Instead, they have subtle relaxed (or weak) memory models, usually described only in ambiguous prose, leading to widespread confusion.

We develop a rigorous and accurate semantics for x86 multiprocessor programs, from instruction decoding to relaxed memory model, mechanised in HOL. We test the semantics against actual processors and the vendor litmus-test examples, and give an equivalent abstract-machine characterisation of our axiomatic memory model. For programs that are (in some precise sense) data-race free, we prove in HOL that their behaviour is sequentially consistent. We also contrast the x86 model with some aspects of Power and ARM behaviour.

This provides a solid intuition for low-level programming, and a sound foundation for future work on verification, static analysis, and compilation of low-level concurrent code.
Parallel thinking
Authors: Blelloch Guy E.
Published: August 2009

Assuming that the multicore revolution plays out the way the microprocessor industry expects, it seems that within a decade most programming will involve parallelism at some level. One needs to ask how this affects the the way we teach computer science, or even how we have people think about computation. With regards to teaching there seem to be three basic choices: (1) we only train a small number of experts in parallel computation who develop a collection of libraries, and everyone else just uses them; (2) we leave our core curriculum pretty much as is, but add some advanced courses on parallelism or perhaps tack on a few lectures at the end of existing courses; or (3) we start teaching parallelism from the start and embed it throughout the curriculum with the idea of getting students to think about parallelism as the most natural form of computation and sequential computation as a special case.

This talk will examine some of the implications of the third option. It will argue that thinking about parallelism, when treated in an appropriate way, might be as easy or easier that thinking sequentially. A key prerequisite, however, is to identify what the core ideas in parallelism are and how they might be layered and integrated with existing concepts. Another more difficult issue is how to cleanly integrate these ideas among courses. After all much of the success of sequential computation follows from the concept of a random access machine and its ability to serve as a simple, albeit imperfect, interface between programming languages, algorithm analysis, and hardware design. The talk will go through an initial list of some core ideas in parallelism, and an approach to integrating these ideas between parallel algorithms, programming languages, and, to some extent, hardware. This requires, however, moving away from the concept of a machine model as a interface for thinking about computation.