bluuebunny/crossref_metadata_2025 huggingface dataset:
Predicting occurrences of geographically restricted rare floral elements with qualitative habitat data
Authors: MacDougall A S , Loo J A
Published: September 2002

Habitat-directed survey methods are often used for locating narrowly distributed rare species and communities across landscapes, though their predictive accuracy varies, depending on the element targeted and the type of data employed. We discuss habitat-directed surveys for rare floral elements in the context of landscape-level management planning, focusing in particular upon a case study from southern New Brunswick. Databases of rare species and community occurrences are important requisites for such planning, but existing information is usually deficient and expensive to develop. A habitat-based approach directs surveys to sites with a higher-than-random probability of hosting rare elements and avoids areas deemed unlikely to be of interest due to environment or disturbance factors. We describe a four-part survey procedure that uses readily available qualitative habitat descriptions and geographic information systems (GIS) based land resource data to identify sites potentially hosting rare biota. The procedure includes remote-sensed and on-site screening to confirm significance and collect ancillary data needed for conservation planning. The use of existing data is cost and time efficient, a necessity given often narrow planning windows and restricted budgets. The method described here is well suited to geographically restricted plant biota associated with distinct habitats, especially in unsurveyed or highly fragmented landscapes. However, the approach does not apply to species of wide-ranging and environmentally heterogeneous habitats. As well, by targeting only highly specific locations assumed to be "optimal" habitat, the occurrence of rare biota in other areas cannot be definitively determined and some sites will almost certainly be missed. The limitations of the procedure highlight the need for multifaceted biodiversity assessment over large areas.Key words: ecosystem management, rare species, gap analysis, habitat-directed biodiversity survey, reserve network, New Brunswick.
Dynamics of North American boreal mixedwoods
Authors: Chen H YH , Popadiouk R V
Published: September 2002

Boreal mixedwoods (BMWs) are the most productive and diverse forest ecosystems in North American boreal forests. A good understanding of BMW stand dynamics is a prerequisite for sustainable management of these vital resources. In this review, we describe the patterns and processes of BMWs created by natural disturbances, examine the biotic and abiotic factors that influence these patterns and processes, and discuss forest management implications related to stand development. Based on distinct structural and developmental features, BMW stand development is characterized by four stages: stand initiation, stem exclusion, canopy transition, and gap dynamics. These four stages of stand development provide a conceptual model of complex developmental processes. However, multiple pathways are possible during BMW stand development depending on disturbances, neighbour effects, and stand condition. Boreal mixedwood management at the stand level needs to emulate the natural development process and target a specific stand structure and species composition. Alternative silvicultural techniques are available to achieve the multiple objectives of BMWs. Further considerations at various temporal and spatial scales and at the operational level are required to ensure sustainable BMW management. Key words: stand dynamics, boreal mixedwoods, natural disturbance, stand structure, developmental process, management implications.
Identical nuclei in coherent pion production at intermediate energies
Authors: Deutchman P A
Published: September 2002

The formalism for the calculation of constructive, coherent production of pions through the collision of intermediate-energy nuclei now includes for the first time the exchange symmetry due to identical nuclei both in the initial two-body state and in the final three-body state. Of the eight terms that contribute to the pion-energy distributions, four of the amplitudes are equal in pairs, effectively leaving four amplitudes with direct terms in the initial state and direct and exchange terms in the final state. Of these remaining amplitudes, the final-state exchange terms are negligible as far as the calculation is concerned. This holds for pion-energy distributions over the incident energies from 100 MeV/nucleon to 2 GeV/nucleon for pions fixed in the forward direction (θπ = 0°) and the projectile and target, respectively, fixed in the fore and aft directions. This work is also generalized to include schematic solutions for the cases of identical nuclei in the initial state only, identical nuclei in the final state only, and the case of no identical nuclei at all.

PACS Nos.: 24.10Cn, 24.30Cz, 25.70-z, 25.80-e
Potential curves and rovibrational energies for electronic states of the molecular ion KCs+
Authors: Korek M , Allouche A R , Abdul Al S N
Published: September 2002

The KCs+ molecular ion potential curves are investigated over a wide range of internuclear distance for electronic states described in a 2Λ(+) representation (neglecting the spin-orbit effect) as well as in an Ω(+) representation (including the spin-orbit effect). This calculation has been done in a one active electron approach by using an ab initio method based on non-empirical pseudopotentials with core-valence effect taken into account through parameterized l-dependent polarization potentials. Gaussian basis sets have been used for both atoms, and spin-orbit effects have been taken into account through a semiempirical spin-orbit pseudopotential. The canonical functions approach is used to do a rovibrational study by calculating the eigenvalues Ev, the rotational constant Bv, the centrifugal distortion constants Dv (up to 106 vibrational levels), and the spectroscopic constants are deduced for six bound states. The permanent and transition dipole moment functions have been derived for transitions between the bound states 2 Σ+ and 2Π as well as the oscillator strengths for the transitions v = 0, 10, 20, and Δ v = 0, 1, 2, ..., 6. To the best of our knowledge neither theoretical nor experimental data are available in the literature for the molecular ion KCs+. Extensive tables of Ev, Bv, Dv, and the energy values versus internuclear distance are displayed at the following address: http://hplasim2.univ-lyon1.fr/allouche/kcsplus.html.

PACS Nos.: 33.15Dj, 33.20wr
The intensity dependence of the free-free transition in a bichromatic laser field
Authors: Zhang Sh T , Chen J , Shu-min L
Published: September 2002

In this paper, we investigate the intensity dependence of a freefree transition in the presence of a bichromatic laser field. Based on the first Born approximation, we calculate the differential cross section and total differential cross section versus the field intensity. This dependence relates to the momentum of the incident electron, the ratio of the two frequencies, and the phase difference between the two components of the bichromatic laser field. While the two intensity components are comparable, this dependence is the most striking. The results also show that the intensity dependence relates to the geometrical configurations between the direction of polarization of the laser fields and the incident electron.

PACS Nos.: 34.80Bm, 32.80Qk
Curling rock dynamics: Towards a realistic model
Authors: Denny M
Published: September 2002

We present a model of curling rock motion, which yields realistic dependence upon the dynamical parameters. The underlying assumptions are motivated by physical arguments. We make clear which of the model predictions depend upon the assumptions made about frictional asymmetry and which are independent of these assumptions.

PACS Nos.: 45.20
Isotopic quantum effects in the structure of liquid ethanol
Authors: Tomberli B , Benmore C J , Neuefeind J , Egelstaff P A
Published: September 2002

High-energy electromagnetic-radiation-scattering techniques have been used to measure the structural differences between five isotopic samples of ethanol (CH3CH2OH, CD3CD2OD, CD3CH2OH, CH3CH2OD, and CH3CD2OH) at room temperature and ambient pressure. The differences in the X-ray structure factors between several pairs of isotopes, ΔSX(Q), are shown to have maximum amplitudes that are on the order of a few percent compared to the total structure factor for CH3CH2OH. Our uncertainties are an order of magnitude smaller than those of early gamma-ray measurements on methanol (C.J. Benmore and P.A. Egelstaff. J. Phys. Condens. Matter, 8, 9429 (1996)). These studies have shown that isotopic structural differences in room-temperature ethanol vary as a function of substitution site and are in qualitative agreement with similar differences found in liquid methanol.

PACS Nos.: 61.20-p, 61.25E, 61.10-E
Computer-assisted microanalysis of parallel programs
Authors: Hickey Timothy J. , Cohen Jacques , Hotta Hirofumi , PetitJean Thierry
Published: October 2002

This paper consists of two parts: the first provides the theoretical foundations for analyzing parallel programs and illustrates how the theory can be applied to estimate the execution time of a class of parallel programs being executed on a MIMD computer. The second part describes a program analysis system, based on the theoretical model, which allows a user to interactively analyze the results of executing (or simulating the execution) of such parallel programs. Several examples illustrating the use of the tool are presented. A novel contribution is the separation (both at the conceptual and the implementation levels) of the machine-independent and the machine-dependent parts of the analysis. This separation enables the users of the system to establish speed-up curves for machines having varying characteristics.
Linking programs incrementally
Authors: Quong Russell W. , Linton Mark A.
Published: October 2002

Linking is traditionally a batch process that resolves cross-references between object modules and run-time libraries to produce a stand-alone executable image. Because most program changes only involve a small part of the program, we have implemented an incremental linker, named Inclink, that processes only the changed modules. Inclink generates a new executable in time proportional to the size of change; in contrast, a batch linker generates an executable in time proporitonal to the size of the program. To minimize updates to the executable, Inclink allocates extra space for every module. By allocating 24 percent more space in the executable for overflows, Inclink can update a module in place over 97 percent of the time. Measurements show that Inclink is more than an order of magnitude faster than the UNIX [2] batch linker and that 88 percent of all links will take less than 2 s of CPU time on a MicroVAX-2, independent of program size.
Incremental generation of lexical scanners
Authors: Heering J. , Klint P. , Rekers J.
Published: October 2002

It is common practice to specify textual patterns by means of a set of regular expressions and to transform this set into a finite automaton to be used for the scanning of input strings. In many applications, the cost of this preprocessing phase can be amortized over many uses of the constructed automaton. In this paper new techniques for lazy and incremental scanner generation are presented. The lazy technique postpones the construction of parts of the automaton until they are really needed during the scanning of input. The incremental technique allows modifications to the original set of regular expressions to be made and reuses major parts of the previous automaton. This is interesting in applications such as environments for the interactive development of language definitions in which modifications to the definition of lexical syntax and the uses of the generated scanners alternate frequently.
Efficient register allocation via coloring using clique separators
Authors: Gupta Rajiv , Soffa Mary Lou , Ombres Denise
Published: October 2002

Although graph coloring is widely recognized as an effective technique for register allocation, memory demands can become quite high for large interference graphs that are needed in coloring. In this paper we present an algorithm that uses the notion of clique separators to improve the space overhead of coloring. The algorithm, based on a result by R. Tarjan regarding the colorability of graphs, partitions program code into code segments using clique separators. The interference graphs for the code partitions are constructed one at a time and colored independently. The colorings for the partitions are combined to obtain a register allocation for the entire program. This approach can be used to perform register allocation in a space-efficient manner. For straight-line code (e.g., local register allocation), an optimal allocation can be obtained from optimal allocations for individual code partitions. Experimental results are presented demonstrating memory demand reductions for interference graphs when allocating registers using clique separators.
Reasoning about probabilistic parallel programs
Authors: Rao Josyula R.
Published: October 2002

The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficiency, and solvability results in a trade-off of the traditional notion of absolute correctness of algorithms for a more quantitative notion: correctness with a probability between 0 and 1. The addition of the notion of parallelism to the already unintuitive idea of randomization makes reasoning about probabilistic parallel programs all the more tortuous and difficult.

In this paper we address the problem of specifying and deriving properties of probabilistic parallel programs that either hold deterministically or with probability 1. We present a proof methodology based on existing proof systems for probabilistic algorithms, the theory of the predicate transformer, and the theory of UNITY. Although the proofs of probabilistic programs are slippery at best, we show that such programs can be derived with the same rigor and elegance that we have seen in the derivation of sequential and parallel programs. By applying this methodology to derive probabilistic programs, we hope to develop tools and techniques that would make randomization a useful paradigm in algorithm design.
An evaluation of an automatically generated compiler
Authors: Sloane Anthony M.
Published: October 2002

Compilers or language translators can be generated using a variety of formal specification techniques. Whether generation is worthwhile depends on the effort required to specify the translation task and the quality of the generated compiler. A systematic comparison was conducted between a hand-coded translator for the Icon programming language and one generated by the Eli compiler construction system. A direct comparison could be made since the generated program performs the same translation as the hand-coded program. The results of the comparison show that efficient compilers can be generated from specifications that are much smaller and more problem oriented than the equivalent source code. We also found that further work must be done to reduce the dynamic memory usage of the generated compilers.
Using dataflow analysis techniques to reduce ownership overhead in cache coherence protocols
Authors: Skeppstedt Jonas , Stenström Per
Published: October 2002

In this article, we explore the potential of classical dataflow analysis techniques in removing overhead in write-invalidate cache coherence protocols for shared-memory multiprocessors. We construct the compiler algorithms with varying degree of sophistication that detect loads followed by stores to the same address. Such loads are marked and constitute a hint to the cache to obtain an exclusive copy of the block so that the subsequent store does not introduce access penalties. The simplest of the three compiler algorithms analyzes the existence of load-store sequences within each basic blocks of code whereas the other two analyze load-store sequences across basic blocks at the intraprocedural level. The algorithms have been incorporated into an optimizing C compiler, and we have evaluated their efficiencies by compiling and executing seven parallel programs on a simulated multiprocessor. Our results show that the detection efficiency of the most aggressive algorithm is 96% or higher for four of the seven programs studied. We also compare the efficiency of these static algorithms with that of dynamic hardware-based algorithms that reduce ownership overhead. We find that the static analysis using classical dataflow analysis results in similar performance improvements as dynamic hardware-based approaches.
A natural semantics for Eiffel dynamic binding
Authors: Attali Isabelle , Caromel Denis , Ehmety Sidi Ould
Published: October 2002

This article formally defines Eiffel dynamic binding in presence of renaming and redefinition. Message passing, inheritance, and polymorphism are expressed in an operational style using natural semantics. From the formal specification, we derive an algorithm to determine the appropriate version of a feature to apply to a given object. This algorithm, based only on the class hierarchy and not using any intermediate structure, gives a practical approach to the understanding of inheritance, renaming, and redefinition in Eiffel.
Sublinear-space evaluation algorithms for attribute grammars
Authors: Reps Thomas , Demers Alan
Published: October 2002

A major drawback of attribute-grammar-based systems is that they are profligate consumers of storage. This paper concerns new storage-management techniques that reduce the number of attribute values retained at any stage of attribute evaluation; it presents an algorithm for evaluating an
n
-attribute tree that never retains more than
O
(log
n
) attribute values. This method is optimal, although it may require nonlinear time. A second algorithm, which never retains more than
O
(√
n
) attribute values, is also presented, both as an introduction to the
O
(log
n
) method and because it works in linear time.
Combinatory formulations of concurrent languages
Authors: Raja N. , Shyamasundar R. K.
Published: October 2002

We design a system with six
Basic Combinators
and prove that it is powerful enough to embed the full asynchronous π-calculus, including replication. Our theory for constructing
Combinatory Versions
of concurrent languages is based on a method, used by Quine and Bernays, for the general elimination of variables in linguistic formalisms. Our combinators are designed to eliminate the requirement of
names
that are
bound
by an
input prefix
. They also eliminate the need for input prefix, output prefix, and the accompanying mechanism of
substitution
. We define a notion of
bisimulation
for the combinatory version and show that the combinatory version preserves the semantics of the original calculus. One of the distinctive features of the approach is that it can be used to rework several process algebras in order to derive equivalent combinatory versions.
Polymorphic splitting
Authors: Wright Andrew K. , Jagannathan Suresh
Published: October 2002

This article describes a general-purpose program analysis that
computes global control-flow and data-flow information for
higher-order, call-by-value languages. The analysis employs a
novel form of polyvariance called polymorhic splitting that uses
let-expressions as syntactic clues to gain precision. The information
derived from the analysis is used both to eliminate run-time checks
and to inline procedure. The analysis and optimizations have been
applied to a suite of Scheme programs. Experimental results obtained
from the prototype implementation indicate that the analysis is
extremely precise and has reasonable cost. Compared to monovariant
flow analyses such as 0CFA, or analyses based on type inference such as
soft typing, the analysis eliminates significantly more run-time checks. Run-time check elimination and inlining together typically yield a 20 to 40% performance improvement for the benchmark suite, with some programs running four times as fast.
Controlling generalization and polyvariance in partial deduction of normal logic programs
Authors: Leuschel Michael , Martens Bern , De Schreye Danny
Published: October 2002

Given a program and some input data, partial deduction computes a
specialized program handling any remaining input more efficiently.
However, controlling the process well is a rather difficult problem.
In this article, we elaborate global control for partial deduction:
for which atoms, among possibly infinitely many, should specialized
relations be produced, meanwhile guaranteeing correctness as well as
termination? Our work is based on two ingredients. First, we use the
concept of a characteristic tree, encapsulating specialization
behavior rather than syntactic structure, to guide generalization and
polyvariance, and we show how this can be done in a correct and
elegant way. Second, we structure combinations of atoms and
associated characteristic trees in global trees registering “causal” relationships among such pairs. This allows us to spot looming nontermination and perform proper generalization in order to avert the danger, without having to impose a depth bound on characteristic trees. The practical relevance and benefits of the work are
illustrated through extensive experiments. Finally, a similar
approach may improve upon current (on-line) control strategies for
program transformation in general such as (positive) supercompilation
of functional programs. It also seems valuable in the context of
abstract interpretation to handle infinite domains of infinite
height with more precision.
Finitary fairness
Authors: Alur Rajeev , Henzinger Thomas A.
Published: October 2002

Fairness is a mathematical abstraction: in a multiprogramming environment, fairness abstracts the details of admissible (“fair”) schedulers; in a distributed environment, fairness abstracts the relative speeds of processors. We argue that the standard definition of fairness often is unnecessarily weak and can be replaced by the stronger, yet still abstract, notion of finitary fairness. While standard weak fairness requires that no enabled transition is postponed forever, finitary weak fairness requires that for every computation of a system there is an unknown bound
k
such that no enabled transition is postponed more than
k
consecutive times. In general, the
finitary restriction fin
(
F
) of any given fairness requirement
F
is the union of all ω-regular safety properties contained in
F
. The adequacy of the proposed abstraction is shown in two ways. Suppose we prove a program property under the assumption of finitary fairness. In a multiprogramming environment, the program then satisfies the property for all fair finite-state schedulers. In a distributed environment, the program then satisfies the property for all choices of lower and upper bounds on the speeds (or timings) of processors. The benefits of finitary fairness are twofold. First, the proof rules for verifying liveness properties of concurrent programs are simplified: well-founded induction over the natural numbers is adequate to prove termination under finitary fairness. Second, the fundamental problem of consensus in a faulty asynchronous distributed environment can be solved assuming finitary fairness.
Dynamic typing for distributed programming in polymorphic languages
Authors: Duggan Dominic
Published: October 2002

While static typing is widely accepted as being necessary for secure
program execution, dynamic typing is also viewed as being essential in some applications, particularly for distributed programming environments.
Dynamics
have been proposed as a language construct for dynamic typing, based on experience with languages such as CLU, Cedar/Mesa, and Modula-3. However proposals for incorporating dynamic typing into languages with parametric polymorphism have serious shortcomings. A new approach is presented to extending polymorphic lnanguages with dynamic typing. At the heart of the approach is the use of dynamic type dispatch, where polymorphic functions may analyze the structure of their type arguments. This approach solves several open problems with the traditional approach to adding dynamic typing to polymorphic languages. An explicity typed language XML
dyn
is presented; this language uses
refinement kinds
to ensure that dynamic type dispatch does not fail at run-time.
Safe dynamics
are a new form of dynamics that use refinement kinds to statically check the use of run-time dynamic typing. Run-time errors are isolated to a separate construct for performing run-time type checks
Space-efficient scheduling of nested parallelism
Authors: Narlikar Girija J. , Blelloch Guy E.
Published: October 2002

Many of today's high-level parallel languages support dynamic,
fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program. This article presents an on-line scheduling algorithm that is provably space efficient and time efficient for nested-parallel languages. For a computation with depth
D
and serial space requirement
S
1
, the algorithm generates a schedule that requires at most
S
1
+
O
(K•D•p
) space (including scheduler space) on
p
processors. Here,
K
is a user-adjustable runtime parameter specifying the net amount of memory that a thread may allocate before it is preempted by the scheduler. Adjusting the value of
K
provides a trade-off between the running time and the memory requirement of a parallel computation. To allow the scheduler to scale with the number of processors we also parallelize the scheduler and analyze the space and time bounds of the computation to include scheduling costs. In addition to showing that the scheduling algorithm is space and time efficient in theory, we demonstrate that it is effective in practice. We have implemented a runtime system that uses our algorithm to schedule lightweight parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.
Linearity and the pi-calculus
Authors: Kobayashi Naoki , Pierce Benjamin C. , Turner David N.
Published: October 2002

The economy and flexibility of the pi-calculus make it an attractive object of theoretical study and a clean basis for concurrent language design and implementation. However, such generality has a cost: encoding higher-level features like functional computation in pi-calculus throws away potentially useful information. We show how a linear type system can be used to recover important static information about a process's behavior. In particular, we can guarantee that two processes communicating over a linear channel cannot interfere with other communicating processes. After developing standard results such as soundness of typing, we focus on equivalences, adapting the standard notion of barbed bisimulation to the linear setting and showing how reductions on linear channels induce a useful “partial confluence” of process behaviors. For an extended example of the theory, we prove the validity of a tail-call optimization for higher-order functions represented as processes.
An automata-theoretic approach to modular model checking
Authors: Kupferman Orna , Vardi Moshe Y.
Published: October 2002

In
modular verification
the specification of a module consists of two part. One part describes the guaranteed behavior of the module. The other part describes the assumed behavior of the system in which the module is interacting. This is called the
assume-guarantee
paradigm. In this paper we consider assume-guarantee specifications in which the guarantee is specified by branching temporal formulas. We distinguish between two approaches. In the first approach, the assumption is specified by branching temporal formulas too. In the second approach, the assumption is specified by linear temporal logic. We consider guarantees in ∀CTL, and ∀CTL*. We develop two fundamental techniques: building maximal models for ∀CTL and ∀CTL* formulas and using alternating automata to obtain space-efficient algorithms for fair model checking. Using these techniques we classify the complexity of satisfiability, validity, implication, and modular verification for ∀CTL and ∀CTL*. We show that modular verification is PSPACE-complete for ∀CTL and is EXSPACE-complete for ∀CTL*. We prove that when the assumption is linear, these bounds hold also for guarantees in CTL and CTL*. On the other hand, the problem remains EXSPACE-hard even when we restrict the assumptions to LTL and take the guarantees as a fixed ∀CTL formula.
Efficient and safe-for-space closure conversion
Authors: Shao Zhong , Appel Andrew W.
Published: October 2002

Modern compilers often implement function calls (or returns) in two steps: first, a “closure” environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a “jump with arguments (for results).” Closure conversion—which decides where and how to represent closures at runtime—is a crucial step in the compilation of functional languages. This paper presents a new algorithm that exploits the use of compile-time control and data-flow information to optimize funtion calls. By extensive closure sharing and allocation by 36% and memory fetches for local and global variables by 43%; and improves the already efficient code generated by an earlier version of the Standard ML of New Jersey compiler by about 17% on a DECstation 5000. Moreover, unlike most other approaches, our new closure-allocation scheme the strong
safe-for-space-complexity
rule, thus achieving good asymptotic space usage.
Morris's Garbage Compaction Algorithm Restores Reference Counts
Authors: Wise David S.
Published: October 2002

The two-pass compaction algorithm of F.L. Morris, which follows upon the mark phase in a garbage collector, may be modified to recover reference counts for a hybrid storage management system. By counting the executions of two loops in that algorithm where upward and downward references, respectively, are forwarded to the relocation address of one node, we can initialize a count of active references and then update it but once. The reference count may share space with the mark bit in each node, but it may not share the additional space required in each pointer by Morris's algorithm, space which remains unused outside the garbage collector.
A Space Efficient Dynamic Allocation Algorithm for Queuing Messages
Authors: Beyer Eric , Buneman Peter
Published: October 2002

A simple dynamic allocation algorithm is described for queuing variable length messages in memory. The algorithm makes use of the ability of many operating system to increase and decrease available memory as required. Some results describing its efficiency are presented.
Prettyprinting
Authors: Oppen Dereck C.
Published: October 2002

An algorithm for prettyprinting is given. For an input stream of length
n
and an output device with linewidth
m
, the algorithm requires time
O
(
n
) and space
O
(
m
). The algorithm is described in terms of two parallel processes: the first scans the input stream to determine the space required to print logical blocks of tokens; the second uses this information to decide where to break lines of text; the two processes communicate by means of a buffer of size
O
(
m
). The algorithm does not wait for the entire stream to be input, but begins printing as soon as it has received a full line of input. The algorithm is easily implemented.
Specification of Abstract Data Types in Modula
Authors: Ernst George W. , Ogden William F.
Published: October 2002

The programming language MODULA is extended to permit the formal specification of the structure and functional capabilities of modules. This makes true hierarchical programming possible in MODULA by allowing programmers of higher level parts of a system to ignore completely the internal structure of lower level modules and to rely entirely on the specifications of the capabilities of these modules. An example is included to illustrate this technique. We show that our specification mechanisms are sufficiently powerful to support formal verification rules for modules that have disjoint representations for abstract objects.
A balanced code placement framework
Authors: von Hanxleden Reinhard , Kennedy Ken
Published: October 2002

Give-N-Take is a code placement framework which uses a generic producer-consumer mechanism. An instance of this could be a communication step between a processor that computes (produces) some data, and other processors that subsequently reference (consume) these data in an expression. An advantage of Give-N-Take over traditional partial redundancy elimination techniques is its concept of production
regions
, instead of single locations, which can be beneficial for general latency hiding. Give-N-Take also guarantees
balanced
production, i.e., each production will be started and stopped exactly once. The framework can also take advantage of production coming “for free,” as induced by side effects, without disturbing balance. Give-N-Take can place production either before or after consumption, and it also provides the option to speculatively hoist code out of potentially zero-trip loop (nest) constructs. Give-N-Take uses a fast elimination method based on Tarjan intervals, with a complexity linear in the program size in most cases. We have implemented Give-N-Take as partof a Fortran D compiler prototype, where it solves various communication generation problems associated with compiling data-parallel languages onto distributed-memory architectures.
An assume-guarantee rule for checking simulation
Authors: Henzinger Thomas A. , Qadeer Shaz , Rajamani Sriram K. , Tasiran Serdar
Published: October 2002

The simulation preorder on state transition systems is widely accepted as a useful notion of refinement, both in its own right and as an efficiently checkable sufficient condition for trace containment. For composite systems, due to the exponential explosion of the state space, there is a need for decomposing a simulation check of the form
P
≤

s

Q
, denoting "
P
is simulated by
Q
," into simpler simulation checks on the components of
P
and
Q
. We present an assume-guarantee rule that enables such a decomposition. To the best of our knowledge, this is the first assume-guarantee rule that applies to a refinement relation different from trace containment. Our rule is circular, and its soundness proof requires induction on trace trees. The proof is constructive: given simulation relations that witness the simulation preorder between corresponding components of
P
and
Q
, we provide a procedure for constructing a witness relation for
P
≤

s

Q
. We also extend our assume-guarantee rule to account for fairness constraints on transition systems.
The ML approach to the readable all-purpose language
Authors: Spooner C. R.
Published: October 2002

The ideal computer language is seen as one that would be as readable as natural language, and so adaptable that it could serve as the only language a user need ever know. An approach to language design has emerged that shows promise of allowing one to come much closer to that ideal than might reasonably have been expected. Using this approach, a language referred to as ML has been developed, and has been implemented as a language-creation system in which user-defined procedures invoked at translation time translate the source to some object code. In this way the user can define both the syntax and the semantics of the source language. Both language and implementation are capable of further development. This paper describes the approach, the language, and the implementation and recommends areas for further work.
Swarm intelligence
Authors: Tarasewich Peter , McMullen Patrick R.
Published: October 2002

Following a trail of insects as they work together to accomplish a task offers unique possibilities for problem solving.
Changes in computer science accreditation
Authors: Jones Lawrence G. , Price Arthur L.
Published: October 2002

Computer science evolves, program evaluation techniques shift, and the accreditation process must keep pace to reflect those changes.
Emerging scientific applications in data mining
Authors: Han Jiawei , Altman Russ B. , Kumar Vipin , Mannila Heikki , Pregibon Daryl
Published: October 2002

Automated, scalable systems would reveal and help exploit the deeper meanings in scientific data, especially in biomedical engineering, telecommunications, geospatial exploration, and climate and Earth ecosystem modeling.
Moshe
Authors: Keidar Idit , Sussman Jeremy , Marzullo Keith , Dolev Danny
Published: October 2002

We present Moshe, a novel scalable group membership algorithm built specifically for use in wide area networks (WANs), which can suffer partitions. Moshe is designed with three new significant features that are important in this setting: it avoids delivering views that reflect out-of-date memberships; it requires a single round of messages in the common case; and it employs a client-server design for scalability. Furthermore, Moshe's interface supplies the hooks needed to provide clients with full virtual synchrony semantics. We have implemented Moshe on top of a network event mechanism also designed specifically for use in a WAN. In addition to specifying the properties of the algorithm and proving that this specification is met, we provide empirical results of an implementation of Moshe running over the Internet. The empirical results justify the assumptions made by our design and exhibit good performance. In particular, Moshe terminates within a single communication round over 98% of the time. The experimental results also lead to interesting observations regarding the performance of membership algorithms over the Internet.
Typed interpretations of extensible objects
Authors: Bono Viviana , Bugliesi Michele , Crafa Silvia
Published: October 2002

Finding typed encodings of object-oriented into procedural or functional programming sheds light on the theoretical foundations of object-oriented languages and their specific typing constructs and techniques. This article describes a type preserving and computationally adequate interpretation of a full-fledged object calculus that supports message passing and constructs for object update and extension. The target theory is a higher-order λ-calculus with records and recursive folds/unfolds, polymorphic and recursive types, and subtyping. The interpretation specializes to calculi of nonextensible objects, and validates the expected subtypin
Trainable videorealistic speech animation
Authors: Ezzat Tony , Geiger Gadi , Poggio Tomaso
Published: October 2002

We describe how to create with machine learning techniques a generative, speech animation module. A human subject is first recorded using a videocamera as he/she utters a predetermined speech corpus. After processing the corpus automatically, a visual speech module is learned from the data that is capable of synthesizing the human subject's mouth uttering entirely novel utterances that were not recorded in the original video. The synthesized utterance is re-composited onto a background sequence which contains natural head and eye movement. The final output is videorealistic in the sense that it looks like a video camera recording of the subject. At run time, the input to the system can be either real audio sequences or synthetic audio produced by a text-to-speech system, as long as they have been phonetically aligned.The two key contributions of this paper are 1) a variant of the
multidimensional morphable model
(MMM) to synthesize new, previously unseen mouth configurations from a small set of mouth image prototypes; and 2) a
trajectory synthesis technique
based on regularization, which is automatically trained from the recorded video corpus, and which is capable of synthesizing trajectories in MMM space corresponding to any desired utterance.
Perspective shadow maps
Authors: Stamminger Marc , Drettakis George
Published: October 2002

Shadow maps are probably the most widely used means for the generation of shadows, despite their well known aliasing problems. In this paper we introduce
perspective shadow maps,
which are generated in normalized device coordinate space, i.e., after perspective transformation. This results in important reduction of shadow map aliasing with almost no overhead. We correctly treat light source transformations and show how to include all objects which cast shadows in the transformed space. Perspective shadow maps can directly replace standard shadow maps for interactive hardware accelerated rendering as well as in high-quality, offline renderers.
Algorithm 821
Authors: Hanson Richard J. , Breshears Clay P. , Gabb Henry A.
Published: October 2002

Pthreads is the library of POSIX standard functions for concurrent, multithreaded programming. The POSIX standard only defines an application programming interface (API) to the C programming language, not to Fortran. Many scientific and engineering applications are written in Fortran. Also, many of these applications exhibit functional, or task-level, concurrency. They would benefit from multithreading, especially on symmetric multiprocessors (SMP). We present here an interface to that part of the Pthreads library that is compatible with standard Fortran. The contribution consists of two primary source files: a Fortran module and a collection of C wrappers to Pthreads functions. The Fortran module defines the data structures, interface and initialization routines used to manage threads. The stability and portability of the Fortran API to Pthreads has been demonstrated using common mathematical computations on several SMP systems.
Why software still stinks
Authors: Tepper Michele
Published: October 2002

Back in 1997, technology journalist Clive Thompson wrote that "Software is badly made. More than that, it is often horribly made. It is developed with the sort of irresponsible abandon that would be unconscionable if it were applied to bridge-building, car-making and possibly even plumbing." Five years later, does he think the situation has gotten better? "If anything," he says, "it's gotten worse."
The undecidability of associativity and commutativity analysis
Authors: Charlesworth Arthur
Published: October 2002

Associativity is required for the use of general scans and reductions in parallel languages. Some systems also require functions used with scans and reductions to be commutative. We prove the undecidability of both associativity and commutativity. Thus, it is impossible in general for a compiler to check for those conditions. We also prove the stronger result that the resulting relations fail to be recursively enumerable. We prove that these results hold for the kind of function subprograms of practical interest in such a situation: function subprograms that, due to syntactical restrictions, are guaranteed to halt. Thus, our results are stronger than one can obtain from Rice's Theorem. We also obtain limitations concerning the construction of functions and limitations concerning compiler-generated run-time checks. In addition, we prove an undecidability result about programmer-constructed run-time checks.
Reverse engineering under siege
Authors: Samuelson Pamela
Published: October 2002

Is reverse engineering a lawful way to acquire trade secrets?
Distributed FIFO allocation of identical resources using small shared space
Authors: Fischer Michael J. , Lynch Nancy A. , Burns James E. , Borodin Allan
Published: October 2002

We present a simple and efficient algorithm for the FIFO allocation of
k
identical resources among asynchronous processes that communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against process failure through unannounced stopping, making it attractive also for use in an environment of processes of widely differing speeds. In addition to its practical advantages, we show that for fixed
k
, the shared space complexity of the algorithm as a function of the number
N
of processes is optimal to within a constant factor.
Designing families of data types using exemplars
Authors: LaLonde Wilf R.
Published: October 2002

Designing data types in isolation is fundamentally different from designing them for integration into communities of data types, especially when inheritance is a fundamental issue. Moreover, we can distinguish between the design of families—integrated types that are variations of each other—and more general communities where totally different but cohesive collections of types support specific applications (e.g., a compiler). We are concerned with the design of integrated families of data types as opposed to individual data types; that is, on the issues that arise when the focus is intermediate between the design of individual data types and more general communities of data types. We argue that design at this level is not adequately served by systems providing only class-based inheritance hierarchies and that systems which additionally provide a coupled subtype specification hierarchy are still not adequate. We propose a system that provides an unlimited number of uncoupled specification hi
erarchies and illustrate it with three: a subtype hierarchy, a specialization/generalization hierarchy, and a like hierarchy. We also resurrect a relatively unknown Smalltalk design methodology that we call programming-by-exemplars and argue that it is an important addition to a designer's grab bag of techniques. The methodology is used to show that the subtype hierarchy must be decoupled from the inheritance hierarchy, something that other researchers have also suggested. However, we do so in the context of exemplar-based systems to additionally show that they can already support the extensions required without modification and that they lead to a better separation between users and implementers, since classes and exemplars can be related in more flexible ways. We also suggest that class-based systems need the notion of private types if they are to surmount their current limitations. Our points are made in the guise of designing a family of List data types. Among these is a new variety of lists that have
never been previously published: prefix-sharing lists. We also argue that there is a need for familial classes to serve as an intermediary between users and the members of a family.
Code generation using tree matching and dynamic programming
Authors: Aho Alfred V. , Ganapathi Mahadevan , Tjiang Steven W. K.
Published: October 2002

Compiler-component generators, such as lexical analyzer generators and parser generators, have long been used to facilitate the construction of compilers. A tree-manipulation language called
twig
has been developed to help construct efficient code generators.
Twig
transforms a tree-translation scheme into a code generator that combines a fast top-down tree-pattern matching algorithm with dynamic programming.
Twig
has been used to specify and construct code generators for several experimental compilers targeted for different machines.
win
and
sin
: predicate transformers for concurrency
Authors: Lamport Leslie
Published: October 2002

The
weakest liberal precondition
and
strongest postcondition
predicate transformers are generalized to the
weakest invariant
and
strongest invariant
. These new predicate transformers are useful for reasoning about concurrent programs containing operations in which the grain of atomicity is unspecified. They can also be used to replace behavioral arguments with more rigorous assertional ones.