bluuebunny/crossref_metadata_2025 huggingface dataset:
Tailoring the activity of restriction endonuclease PleI by PNA‐induced DNA looping
Authors: Protozanova Ekaterina , Demidov Vadim V , Soldatenkov Viatcheslav , Chasovskikh Sergey , Frank‐Kamenetskii Maxim D
Published: October 2002

DNA looping is one of the key factors allowing proteins bound to different DNA sites to signal one another via direct contacts. We demonstrate that DNA looping can be generated in an arbitrary chosen site by sequence‐directed targeting of double‐stranded DNA with pseudocomplementary peptide‐nucleic acids (pcPNAs). We designed pcPNAs to mask the DNA from cleavage by type IIs restriction enzyme PleI while not preventing the enzyme from binding to its primary DNA recognition site. Direct interaction between two protein molecules (one bound to the original recognition site and the other to a sequence‐degenerated site) results in a totally new activity of PleI: it produces a nick near the degenerate site. The PNA‐induced nicking efficiency varies with the distance between the two protein‐binding sites in a phase with the DNA helical periodicity. Our findings imply a general approach for the fine‐tuning of proteins bound to DNA sites well separated along the DNA chain.
The nuclear protein HMGB1 is secreted by monocytes via a non‐classical, vesicle‐mediated secretory pathway
Authors: Gardella Stefania , Andrei Cristina , Ferrera Denise , Lotti Lavinia V , Torrisi Maria R , Bianchi Marco E , Rubartelli Anna
Published: October 2002

HMGB1, a non‐histone nuclear factor, acts extracellularly as a mediator of delayed endotoxin lethality, which raises the question of how a nuclear protein can reach the extracellular space. We show that activation of monocytes results in the redistribution of HMGB1 from the nucleus to cytoplasmic organelles, which display ultrastructural features of endolysosomes. HMGB1 secretion is induced by stimuli triggering lysosome exocytosis. The early mediator of inflammation interleukin (IL)‐1β is also secreted by monocytes through a non‐classical pathway involving exocytosis of secretory lysosomes. However, in keeping with their respective role of early and late inflammatory factors, IL‐1β and HMGB1 respond at different times to different stimuli: IL‐1β secretion is induced earlier by ATP, autocrinally released by monocytes soon after activation; HMGB1 secretion is triggered by lysophosphatidylcholine, generated later in the inflammation site. Thus, in monocytes, non‐classical secretion can occur through vescicle compartments that are at least partially distinct.
Using Text Analysis to Identify Functionally Coherent Gene Groups
Authors: Raychaudhuri Soumya , Schütze Hinrich , Altman Russ B.
Published: October 2002

The analysis of large-scale genomic information (such as sequence data or expression patterns) frequently involves grouping genes on the basis of common experimental features. Often, as with gene expression clustering, there are too many groups to easily identify the functionally relevant ones. One valuable source of information about gene function is the published literature. We present a method,neighbor divergence, for assessing whether the genes within a group share a common biological function based on their associated scientific literature. The method uses statistical natural language processing techniques to interpret biological text. It requires only a corpus of documents relevant to the genes being studied (e.g., all genes in an organism) and an index connecting the documents to appropriate genes. Given a group of genes, neighbor divergence assigns a numerical score indicating how “functionally coherent” the gene group is from the perspective of the published literature. We evaluate our method by testing its ability to distinguish 19 known functional gene groups from 1900 randomly assembled groups. Neighbor divergence achieves 79% sensitivity at 100% specificity, comparing favorably to other tested methods. We also apply neighbor divergence to previously published gene expression clusters to assess its ability to recognize gene groups that had been manually identified as representative of a common function.
Identification and Analysis of Over 2000 Ribosomal Protein Pseudogenes in the Human Genome
Authors: Zhang Zhaolei , Harrison Paul , Gerstein Mark
Published: October 2002

Mammals have 79 ribosomal proteins (RP). Using a systematic procedure based on sequence-homology, we have comprehensively identified pseudogenes of these proteins in the human genome. Our assignments are available at http://www.pseudogene.org orhttp://bioinfo.mbb.yale.edu/genome/pseudogene. In total, we found 2090 processed pseudogenes and 16 duplications of RP genes. In relation to the matching parent protein, each of the processed pseudogenes has an average relative sequence length of 97% and an average sequence identity of 76%. A small number (258) of them do not contain obvious disablements (stop codons or frameshifts) and, therefore, could be mistaken as functional genes, and 178 are disrupted by one or more repetitive elements. On average, processed pseudogenes have a longer truncation at the 5′ end than the 3′ end, consistent with the target-primed-reverse-transcription (TPRT) mechanism. Interestingly, on chromosome 16, an RPL26 processed pseudogene was found in the intron region of a functional RPS2 gene. The large-scale distribution of RP pseudogenes throughout the genome appears to result, chiefly, from random insertions with the numbers on each chromosome, consequently, proportional to its size. In contrast to RP genes, the RP pseudogenes have the highest density in GC-intermediate regions (41%–46%) of the genome, with the density pattern being between that of LINEs and Alus. This can be explained by a negative selection theory as we observed that GC-rich RP pseudogenes decay faster in GC-poor regions. Also, we observed a correlation between the number of processed pseudogenes and the GC content of the associated functional gene, i.e., relatively GC-poor RPs have more processed pseudogenes. This ranges from 145 pseudogenes for RPL21 down to 3 pseudogenes for RPL14. We were able to date the RP pseudogenes based on their sequence divergence from present-day RP genes, finding an age distribution similar to that for Alus. The distribution is consistent with a decline in retrotransposition activity in the hominid lineage during the last 40 Myr. We discuss the implications for retrotransposon stability and genome dynamics based on these new findings.
The Bioperl Toolkit: Perl Modules for the Life Sciences
Authors: Stajich Jason E. , Block David , Boulez Kris , Brenner Steven E. , Chervitz Stephen A. , Dagdigian Chris , Fuellen Georg , Gilbert James G.R. , Korf Ian , Lapp Hilmar , Lehväslaiho Heikki , Matsalla Chad , Mungall Chris J. , Osborne Brian I. , Pocock Matthew R. , Schattner Peter , Senger Martin , Stein Lincoln D. , Stupka Elia , Wilkinson Mark D. , Birney Ewan
Published: October 2002

The Bioperl project is an international open-source collaboration of biologists, bioinformaticians, and computer scientists that has evolved over the past 7 yr into the most comprehensive library of Perl modules available for managing and manipulating life-science information. Bioperl provides an easy-to-use, stable, and consistent programming interface for bioinformatics application programmers. The Bioperl modules have been successfully and repeatedly used to reduce otherwise complex tasks to only a few lines of code. The Bioperl object model has been proven to be flexible enough to support enterprise-level applications such as EnsEMBL, while maintaining an easy learning curve for novice Perl programmers. Bioperl is capable of executing analyses and processing results from programs such as BLAST, ClustalW, or the EMBOSS suite. Interoperation with modules written in Python and Java is supported through the evolving BioCORBA bridge. Bioperl provides access to data stores such as GenBank and SwissProt via a flexible series of sequence input/output modules, and to the emerging common sequence data storage format of the Open Bioinformatics Database Access project. This study describes the overall architecture of the toolkit, the problem domains that it addresses, and gives specific examples of how the toolkit can be used to solve common life-sciences problems. We conclude with a discussion of how the open-source nature of the project has contributed to the development effort.

[Supplemental material is available online at www.genome.org. Bioperl is available as open-source software free of charge and is licensed under the Perl Artistic License (http://www.perl.com/pub/a/language/misc/Artistic.html). It is available for download at http://www.bioperl.org. Support inquiries should be addressed to bioperl-l@bioperl.org.]
The Generic Genome Browser: A Building Block for a Model Organism System Database
Authors: Stein Lincoln D. , Mungall Christopher , Shu ShengQiang , Caudy Michael , Mangone Marco , Day Allen , Nickerson Elizabeth , Stajich Jason E. , Harris Todd W. , Arva Adrian , Lewis Suzanna
Published: October 2002

The Generic Model Organism System Database Project (GMOD) seeks to develop reusable software components for model organism system databases. In this paper we describe the Generic Genome Browser (GBrowse), a Web-based application for displaying genomic annotations and other features. For the end user, features of the browser include the ability to scroll and zoom through arbitrary regions of a genome, to enter a region of the genome by searching for a landmark or performing a full text search of all features, and the ability to enable and disable tracks and change their relative order and appearance. The user can upload private annotations to view them in the context of the public ones, and publish those annotations to the community. For the data provider, features of the browser software include reliance on readily available open source components, simple installation, flexible configuration, and easy integration with other components of a model organism system Web site. GBrowse is freely available under an open source license. The software, its documentation, and support are available at http://www.gmod.org.
Identification of Cross-Sectional Parameters of Lateral Meniscal Allografts That Predict Tibial Contact Pressure in Human Cadaveric Knees
Authors: Huang Arthur , Hull M. L. , Howell Stephen M. , Donahue Tammy Haut
Published: October 2002

To guide the development of improved procedures for selecting meniscal allografts, the objective of this study was to identify which cross-sectional parameters of a lateral meniscal allograft predict the contact pressure of the articular surface of the tibia. To meet the objective, the contact pressure of the articular surface of the tibia was measured with a lateral meniscal autograft and a lateral meniscal allograft using pressure sensitive film in 15 fresh-frozen human cadaveric knees. Allografts were matched only in transverse dimensions to the autograft but not in cross-sectional dimensions. Knees were loaded to 1200 N in compression at flexion angles of 0, 15, 30 and 45 degrees using a load application system that allowed unconstrained motion in the remaining degrees of freedom. Five cross-sectional parameters for both of the grafts in each of the anterior, middle, and posterior regions were derived from measurements obtained using a laser-based non-contacting three-dimensional coordinate digitizing system (3-DCDS) (Haut et al., J. Orthop Res, 2000). Five contact variables (i.e. the maximum pressure, mean pressure, contact area, and anterior-posterior and medial-lateral locations of the centroid of contact area) were determined from the pressure sensitive film. When each allograft was paired with the corresponding autograft, the root mean squared percent differences for the cross-sectional parameters ranged from a minimum of 28% for the width of the posterior region to 572% for the height of the posterior region. The root mean squared percent differences between the contact variables for paired grafts were 29% for the maximum pressure, 19% for the mean pressure, and 24% for the contact area. Differences in the cross-sectional parameters between the grafts were related to differences in the contact variables using regression analysis. Difference in the width was most often a predictor variable in the regression models with R2 values ⩾0.45. Differences in all of the four remaining cross-sectional parameters were also important predictor variables. Because failure to match cross-sectional parameters causes substantial difference in contact variables between an allograft and autograft and because cross-sectional parameters predict the contact pressure on the tibial plateau, protocols used to prospectively select allografts should concentrate on matching cross-sectional parameters and particularly the width to those of the original meniscus.
Linear Poroelastic Cancellous Bone Anisotropy: Trabecular Solid Elastic and Fluid Transport Properties
Authors: Kohles Sean S. , Roberts Julie B.
Published: October 2002

The mechanical performance of cancellous bone is characterized using experiments which apply linear poroelasticity theory. It is hypothesized that the anisotropic organization of the solid and pore volumes of cancellous bone can be physically characterized separately (no deformable boundary interactive effects) within the same bone sample. Due to its spongy construction, the in vivo mechanical function of cancellous or trabecular bone is dependent upon fluid and solid materials which may interact in a hydraulic, convective fashion during functional loading. This project provides insight into the organization of the tissue, i.e., the trabecular connectivity, by defining the separate nature of this biphasic performance. Previous fluid flow experiments [Kohles et al., 2001, Journal of Biomechanics, 34(11), pp. 1197–1202] describe the pore space via orthotropic permeability. Ultrasonic wave propagation through the trabecular network is used to describe the solid component via orthotropic elastic moduli and material stiffness coefficients. The linear poroelastic nature of the tissue is further described by relating transport (fluid flow) and elasticity (trabecular load transmission) during regression analysis. In addition, an empirical relationship between permeability and porosity is applied to the collected data. Mean parameters in the superior-inferior (SI) orientation of cubic samples n=20 harvested from a single bovine distal femur were the largest p<0.05 in comparison to medial-lateral (ML) and anterior-posterior (AP) orientations: Apparent elastic modulus (2,139 MPa), permeability (4.65×10−10 m2), and material stiffness coefficient (13.6 GPa). A negative correlation between permeability as a predictor of structural elastic modulus supported a parametric relationship in the ML R2=0.4793, AP R2=0.3018, and SI R2=0.6445 directions p<0.05.
Band gaps and defect modes in periodically structured waveguides
Authors: Munday J. N. , Bennett C. Brad , Robertson W. M.
Published: October 2002

This work examines a simple one-dimensional acoustic band gap system made from a diameter-modulated waveguide. Experimental and theoretical results are presented on perfectly periodic waveguide arrays showing the presence of band gaps—frequency intervals in which the transmission of sound is forbidden. The introduction of defects in the perfect periodicity leads to narrow frequency transmission bands—defect states—within the forbidden band gaps. The circular cross-section waveguide system is straightforward to simulate theoretically and experimental results demonstrate good agreement with theory. The experimental transmission of the periodic waveguide arrays is measured using an impulse response technique.
The effect of reverberation on the damping of bubbles
Authors: Leighton T. G. , White P. R. , Morfey C. L. , Clarke J. W. L. , Heald G. J. , Dumbrell H. A. , Holland K. R.
Published: October 2002

The measurement of an acoustic emission, or scatter, from a bubble is not difficult. However, an accurate interpretation of that signal in terms of the bubble dynamics may require careful consideration. The study presented here is at first sight relatively simple: comparison of the predicted and measured quality factors of injected bubbles. While the measurement is normally done by monitoring the decay of passive emissions from a bubble, this technique becomes difficult with smaller bubbles. Therefore an active technique is introduced, which removes all the frequency-dependent effects on the measurement (such as transducer response) bar one. That, critically, is the effect of the change in the bubble resonance (frequency and damping) which results from the loading on the bubble due to the reverberant field. The vast majority of theoretical treatments of bubble acoustics assume free field conditions, yet the environmental conditions rarely if ever match these. Therefore measurements of bubble damping are compared both with the established free field theory, and with a new theory relevant to the prevailing reverberant conditions (whether caused by tank surfaces, monochromatic neighboring bubbles, or both).
Free field measurements of the absorption coefficient for nonlocally reacting sound absorbing porous layers
Authors: Jansens G. , Lauriks W. , Vermeir G. , Allard J. F.
Published: October 2002

A simple asymptotic approximation with two parameters (the plane wave reflection coefficient and a correction factor) has been derived by Brekhovskikh and Godin [Acoustics of Layered Media II. Point Sources and Bounded Beams (Springer, New York, 1992)], for the spherical field reflected by nonlocally reacting surfaces. In the present work, an expression for the correction factor is obtained for the case of a homogeneous and isotropic porous layer. A free field method for evaluating reflection and absorption coefficients with this approximation is presented. The evaluation of the absorption coefficient at normal incidence is performed on a porous layer on a rigid backing, and compared to measurements performed using a two microphone technique and an impedance tube.
Benefits of amplification for speech recognition in background noise
Authors: Turner Christopher W. , Henry Belinda A.
Published: October 2002

The purpose of the present study was to examine the benefits of providing audible speech to listeners with sensorineural hearing loss when the speech is presented in a background noise. Previous studies have shown that when listeners have a severe hearing loss in the higher frequencies, providing audible speech (in a quiet background) to these higher frequencies usually results in no improvement in speech recognition. In the present experiments, speech was presented in a background of multitalker babble to listeners with various severities of hearing loss. The signal was low-pass filtered at numerous cutoff frequencies and speech recognition was measured as additional high-frequency speech information was provided to the hearing-impaired listeners. It was found in all cases, regardless of hearing loss or frequency range, that providing audible speech resulted in an increase in recognition score. The change in recognition as the cutoff frequency was increased, along with the amount of audible speech information in each condition (articulation index), was used to calculate the “efficiency” of providing audible speech. Efficiencies were positive for all degrees of hearing loss. However, the gains in recognition were small, and the maximum score obtained by an listener was low, due to the noise background. An analysis of error patterns showed that due to the limited speech audibility in a noise background, even severely impaired listeners used additional speech audibility in the high frequencies to improve their perception of the “easier” features of speech including voicing.
Place specificity of multiple auditory steady-state responses
Authors: Herdman Anthony T. , Picton Terence W. , Stapells David R.
Published: October 2002

Auditory steady-state responses (ASSRs) were elicited by simultaneously presenting multiple AM (amplitude-modulated) tones with carrier frequencies of 500, 1000, 2000, and 4000 Hz and modulation frequencies of 77, 85, 93, and 102 Hz, respectively. Responses were also evoked by separately presenting single 500- or 2000-Hz AM tones. The objectives of this study were (i) to determine the cochlear place specificity of single and multiple ASSRs using high-pass noise masking and derived-band responses, and (ii) to determine if there were any differences between single- and multiple-stimulus conditions. For all carrier frequencies, derived-band ASSRs for 1-octave-wide derived bands ranging in center frequency from 0.25 to 8 kHz had maximum amplitudes within a 12 octave of the carrier frequency. For simultaneously presented AM tones of 500, 1000, 2000, and 4000 Hz, bandwidths for the function of derived-band ASSR amplitude by derived-band center frequency were 476, 737, 1177, and 3039 Hz, respectively. There were no significant differences when compared to bandwidths of 486 and 1371 for ASSRs to AM tones of 500 or 2000 Hz presented separately. Results indicate that ASSRs to moderately intense stimuli (60 dB SPL) reflect activation of reasonably narrow cochlear regions, regardless of presenting AM tones simultaneously or separately.
Constant propagation with conditional branches
Authors: Wegman Mark N. , Zadeck F. Kenneth
Published: October 2002

Constant propagation is a well-known global flow analysis problem. The goal of constant propagation is to discover values that are constant on all possible executions of a program and to propagate these constant values as far foward through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the results propagated further. Using the algorithms presented in this paper can produce smaller and faster compiled programs. The same algorithms can be used for other kinds of analyses (e.g., type of determination). We present four algorithms in this paper, all
conservitive
in the sense that all constants may not be found, but each constant found is constant over all possible executions of the program. These algorithms are among the simplest, fastest, and most powerful global constant propagation algorithms known. We also present a new algorithm that performs a form of interprocedural data flow analysis in which aliasing information is gathered in conjunction with constant progagation. Several variants of this algorithm are considered.
Epochs
Authors: Solworth Jon A.
Published: October 2002

To date, the implementation of message passing languages has required hte communications variables (sometimes called ports) either to be limited to the number of physical communications registers in the machine or to be mapped to memory. Neither solution is satisfactory. Limiting the number of variables decreases modularity and efficiency of parallel programs. Mapping variables to memory increases the cost of communications and the granularity of parallelism. We present here a new programming language construct called
epochs
.

Epochs are a scoping mechanism within which the programmer can declare communications variables, which are live only during the scope of that epoch. To limit the range of time a register has to be allocated for a communications variable, the compiler ensures that all processors enter an epoch simultaneously. The programming style engendered fits somewhere between the SIMD data parallel and the MIMD process spawning models.

We describe an implementation for epochs including an efficient synchronization mechanism, a means of statically binding registers to communications variables, and a method of fusing epochs to reduce synchronization overhead.
Composing specifications
Authors: Abadi Martín , Lamport Leslie
Published: October 2002

A rigorous modular specification method requires a proof rule asserting that if each component behaves correctly in isolation, then it behaves correctly in concert with other components. Such a rule is subtle because a component need behave correctly only when its environment does, and each component is part of the others' environments. We examine the precise distinction between a system and its environment, and provide the requisite proof rule when modules are specified with safety and liveness properties.
A calculus for access control in distributed systems
Authors: Abadi Martín , Burrows Michael , Lampson Butler , Plotkin Gordon
Published: October 2002

We study some of the concepts, protocols, and algorithms for access control in distributed systems, from a logical perspective. We account for how a principal may come to believe that another principal is making a request, either on his own or on someone else's behalf. We also provide a logical language for accesss control lists and theories for deciding whether requests should be granted.
The POLYLITH software bus
Authors: Purtilo James M.
Published: October 2002

We describe a system called POLYLITH that helps programmers prepare and interconnect mixed-language software components for execution in heterogeneous environments. POLYLITH's principal benefit is that programmers are free to implement functional requirements separately from their treatment of interfacing requirements; this means that once an application has been developed for use in one execution environment (such as a distributed network) it can be adapted for reuse in other environments (such as a shared-memory multiprocessor) by automatic techniques. This flexibility is provided without loss of performance. We accomplish this by creating a new run-time organization for software. An abstract decoupling agent, called thesoftware bus, is introduced between the system components. Heterogeneity in language and architecture is accommodated since program units are prepared to interface directly to the bus and not to other program units. Programmers specify application structure in terms of a module interconnection language (MIL); POLYLITH uses this specification to guidepackaging(static interfacing activities such as stub generation, source program adaptation, compilation, and linking). At run time, an implementation of the bus abstraction may assist in message delivery, name service, or system reconfiguration.
Parallel programming with control abstraction
Authors: Crowl Lawrence A. , LeBlanc Thomas J.
Published: October 2002

Parallel programming involves finding the potential parallelism in an application and mapping it to the architecture at hand. Since a typical application has more potential parallelism than any single architecture can exploit effectively, programmers usually limit their focus to the parallelism that the available control constructs express easily and that the given architecture exploits efficiently. This approach produces programs that exhibit much less parallelism that exists in the application, and whose performance depends critically on the underlying hardware and software.

We argue for an alternative approach based oncontrol abstraction. Control abstraction is the process by which programmers define new control constructs, specifying constraints on statement ordering separately from an implementation of that ordering. With control abstraction programmers can define and use a rich variety of control constructs to represent an algorithm's potential parallelism.

Since control abstraction separates the definition of a construct from its implementation, a construct may have several different implementations, each exploiting a different subset of the parallelism admitted by the construct. By selecting an implementation for each control construct using annotations, a programmer can vary the parallelism in a program to best exploit the underlying hardware without otherwise changing the source code. This approach produces programs that exhibit most of the potential parallelism in an algorithm, and whose performance can be tuned simply by choosing among the various implementations for the control constructs in use.
Denotational abstract interpretation of logic programs
Authors: Marriott Kim , Søndergaard Harald , Jones Neil D.
Published: October 2002

Logic-programming languages are based on a principle of separation “logic” and “control.”. This means that they can be given simple model-theoretic semantics without regard to any particular execution mechanism (or proof procedure, viewing execution as theorem proving). Although the separation is desirable from a semantical point of view, it makes sound, efficient implementation of logic-programming languages difficult. The lack of “control information” in programs calls for complex data-flow analysis techniques to guide execution. Since data-flow analysis furthermore finds extensive use in error-finding and transformation tools, there is a need for a simple and powerful theory of data-flow analysis of logic programs.

This paper offers such a theory, based on F. Nielson's extension of P. Cousot and R. Cousot's
abstract interpretation
. We present a denotational definition of the semantics of definite logic programs. This definition is of interest in its own right because of its compactness. Stepwise we develop the definition into a generic data-flow analysis that encompasses a large class of data-flow analyses based on the SLD execution model. We exemplify one instance of the definition by developing a provably correct groundness analysis to predict how variables may be bound to ground terms during execution. We also discuss implementation issues and related work.
How to securely replicate services
Authors: Reiter Michael K. , Birman Kenneth P.
Published: October 2002

We present a method for constructing replicated services that retain their availability and integrity despite several servers and clients being corrupted by an intruder, in addition to others failing benignly. We also address the issue of maintaining a causal order among client requests. We illustrate a security breach resulting from an intruder's ability to effect a violation of causality in the sequence of requests processed by the service and propose an approach to counter this attack. An important and novel feature of our techniques is that the client need not be able to identify or authenticate even a single server. Instead, the client is required to possess only a single public key for the service. We demonstrate the performance of our techniques with a service we have implemented using one of our protocols.
Controlled grammatic ambiguity
Authors: Thorup Mikkel
Published: October 2002

A new approach to ambiguity of context-free grammars is presented, and within this approach the LL and LR techniques are generalized to solve the following problems for large classes of ambiguous grammars:

The user may control the parser generation so as to get a parser which finds some specific parse trees for the sentences. The generalized LL and LR techniques will still guarantee that the resulting parser accepts all sentences and terminates in linear time on all input.
Recognizing substrings of LR(k) languages in linear time
Authors: Bates Joseph , Lavie Alon
Published: October 2002

LR parsing techniques have long been studied as being efficient and powerful methods for processing context-free languages. A linear-time algorithm for recognizing languages representable by LR(k) grammars has long been known. Recognizing substrings of a context-free language is at least as hard as recognizing full strings of the language, since the latter problem easily reduces to the former. In this article we present a linear-time algorithm for recognizing substrings of LR(k) languages, thus showing that the substring recognition problem for these languages is no harder than the full string recognition problem. An interesting data structure, the Forest-Structured Stack, allows the algorithm to track all possible parses of a substring without loosing the efficiency of the original LR parser. We present the algorithm, prove its correctness, analyze its complexity, and mention several applications that have been constructed.
Model checking and abstraction
Authors: Clarke Edmund M. , Grumberg Orna , Long David E.
Published: October 2002

We describe a method for using abstraction to reduce the complexity of temporal-logic model checking. Using techniques similar to those involved in abstract interpretation, we construct an abstract model of a program without ever examining the corresponding unabstracted model. We show how this abstract model can be used to verify properties of the original program. We have implemented a system based on these techniques, and we demonstrate their practicality using a number of examples, including a program representing a pipelined ALU circuit with over 10
1300
states.
Deducing fairness properties in UNITY logic—a new completeness result
Authors: Tsay Yih-Kuen , Bagrodia Rajive L.
Published: October 2002

We explore the use of UNITY logic in specifying and verifying fairness properties of UNITY and UNITY-like programs whose semantics can be modeled by weakly fair transition systems. For such programs, strong fairness properties in the form of “if
p
holds infinitely often then
q
also holds infinitely often □◊p⇒□◊q, can be expressed as conditional UNITY properties of the form of “Hypothesis: true→p Conclusion:true→q”. We show that UNITY logic is relatively complete for proving such properties; in the process, a simple inference rule is derived. Specification and verification of weak fairness properties are also discussed.
Combining analyses, combining optimizations
Authors: Click Cliff , Cooper Keith D.
Published: October 2002

Modern optimizing compilers use several passes over a program's intermediate representation to generate good code. Many of these optimizations exhibit a phase-ordering problem. Getting the best code may require iterating optimizations until a fixed point is reached. Combining these phases can lead to the discovery of more facts about the program, exposing more opportunities for optimization. This article presents a framework for describing optimizations. It shows how to combine two such frameworks and how to reason about the properties of the resulting framework. The structure of the frame work provides insight into when a combination yields better results. To make the ideas more concrete, this article presents a framework for combining constant propagation, value numbering, and unreachable-code elimination. It is an open question as to what other frameworks can be combined in this way.
Experimental results from dynamic slicing of C programs
Authors: Venkatesh G. A.
Published: October 2002

Program slicing
is a program analysis technique that has been studied in the context of several different applications in the construction, optimization, maintenance, testing, and debugging of programs. Algorithms are available for constructing slices for a particular execution of a program (dynamic slices), as well as to approximate a subset of the behavior over all possible executions of a program (static slices). However, these algorithms have been studied only in the context of small abstract languages. Program slicing is bound to remain an academic exercise unless one can not only demonstrate the feasibility of building a slicer for nontrivial programs written in a real programming language, but also verify that a type of slice is sufficiently thin, on the average, for the application for which it is chosen. In this article, we present results from using
SLICE
, a dynamic program slicer for C programs, designed and implemented to experiment with several different kinds of program slices and to study them both qualitatively and quantitatively. Several application programs, ranging in size (i.e., number of lines of code) over two orders of magnitude, were sliced exhaustively to obtain average worst-case metrics for the size of program slices.
On the complexity of dataflow analysis of logic programs
Authors: Debray Saumya K.
Published: October 2002

It is widely held that there is a correlation between complexity and precision in dataflow analysis, in the sense that the more precise an analysis algorithm, the more computationally expensive it must be. The details of this relationship, however, appear to not have been explored extensively. This article reports some results on this correlation in the context of logic programs. A formal notion of the “precision” of an analysis algorithm is proposed, and this is used to characterize the worst-case computational complexity of a number of dataflow analyses with different degrees of precision. While this article considers the analysis of logic programs, the technique proposed, namely the use of “exactness sets” to study relationships between complexity and precision of analyses, is not specific to logic programming in any way, and is equally applicable to flow analyses of other language families.
An editor for revision control
Authors: Fraser Christipher W. , Myers Eugene W.
Published: October 2002

Programming environments support revision control in several guises. Explicitly, revision control software manages the trees of revisions that grow as software is modified. Implicitly, editors retain past versions by automatically saving backup copies and by allowing users to undo commands. This paper describes an editor that offers a uniform solution to these problems by never destroying the old version of the file being edited. It represents files using a generalization of AVL trees called “AVL dags,” which makes it affordable to automatically retain past versions of files. Automatic retention makes revision maintenance transparent to users. The editor also uses the same command language to edit both text and revision trees.
Symbolic analysis for parallelizing compilers
Authors: Haghighat Mohammad R. , Polychronopoulos Constantine D.
Published: October 2002

The notion of dependence captures that most important properties of a program for efficient execution on parallel computers. The dependence structure of a program defines that necessary constraints of the order of execution of the program components and provides sufficient information for the exploitation of the available parallelism. Static discovery and management of the dependence structure of programs save a tremendous amount of execution time, and dynamic utilization of dependence information results in a significant performance gain on parallel computers. However, experiments with parallel computers indicate that existing multiprocessing environments are unable to deliver the desired performance over a wide range of real applications, mainly due to lack of precision of their dependence information. This calls for an effective compilation scheme capable of understanding the dependence structure of complicated application programs. This article describes a methodology for capturing analyzing program properties that are essential in the effective detection and efficient exploitation of parallelism on parallel computers. Based on this methodology, a symbolic analysis framework is developed for the Parafrase-2 parallelizing compiler. This framework extends the scope of a variety of important program analysis problems and solves them in a unified way. The attained solution space of these problems is much larger than that handled by existing compiler technology. Such a powerful approach is required for the effective compilation of a large class of application programs.
Eta-expansion does The Trick
Authors: Danvy Olivier , Malmkjær Karoline , Palsberg Jens
Published: October 2002

Partial-evaluation folklore has it that massaging one's source programs can make them specialize better. In Jones, Gomard, and Sestoft's recent textbook, a whole chapter is dedicated to listing such “binding-time improvements”: nonstandard use of continuation-passing style, eta-expansion, and a popular transformation called “The Trick.” We provide a unified view of these binding-time improvements, from a typing perspective. Just as a proper treatment of product values in partial evaluation requires partially static values, a proper treatment of disjoint sums requires moving static contexts across dynamic case expressions. This requirement precisely accounts for the nonstandard use of continuation-passing style encountered in partial evaluation. Eta-expansion thus acts as a uniform binding-time coercion between values and contexts, be they of function type, product type, or disjoint-sum type. For the latter case, it enables “The Trick.” In this article, we extend Gomard and Jones' partial evaluator for the λ-calculus, λ-Mix, with products and disjoint sums; we point out how eta-expansion for (finite) disjoint sums enable The Trick; we generalize our earlier work by identifying the eta-expansion can be obtained in the binding-time analysis simple by adding two coercion rules; and we specify and prove the correctness of our extension to λ-Mix.
On convergence toward a database of program transformations
Authors: Barstow David
Published: October 2002

Several fairly large sets of programming rules have been developed recently. It is natural to ask whether the process of developing such rule bases may converge. Having developed sets of rules for specific programming tasks and domains, will they be helpful when other tasks and domains are considered? While it is too early to give definitive answers, experience with the rules of the PECOS system has been positive. Both during the process of developing the rule set and while developing rules for another domain, the existence of already codified rules proved very helpful.
Generalizing specifications for uniformly implemented loops
Authors: Dunlop Douglas D. , Basili Victor R.
Published: October 2002

The problem of generalizing functional specifications for while loops is considered. This problem occurs frequently when trying to verify that an initialized loop satisfies some functional specification, i.e., produces outputs which are some function of the program inputs.

The notion of a valid generalization of a loop specification is defined. A particularly simple valid generalization, a base generalization, is discussed. A property of many commonly occurring while loops, that of being uniformly implemented, is defined. A technique is presented which exploits this property in order to systematically achieve a valid generalization of the loop specification. Two classes of uniformly implemented loops that are particularly susceptible to this form of analysis are defined and discussed. The use of the proposed technique is illustrated with a number of applications. Finally, an implication of the concept of uniform loop implementation for the validation of the obtained generalization is explained.
Commutativity analysis
Authors: Rinard Martin C. , Diniz Pedro C.
Published: October 2002

This article presents a new analysis technique, commutativity analysis, for automatically parallelizing computations that manipulate dynamic, pointer-based data structures. Commutativity analysis views the computation as composed of operations on objects. It then analyzes the program at this granularity to discover when operations commute (i.e., generate the same final result regardless of the order in which they execute). If all of the operations required to perform a given computation commute, the compiler can automatically generate parallel code. We have implemented a prototype compilation system that uses commutativity analysis as its primary analysis technique. We have used this system to automatically parallelize three complete scientific computations: the Barnes-Hut N-body solver, the Water liquid simulation code, and the String seismic simulation code. This article presents performance results for the generated parallel code running on the Stanford DASH machine. These results provide encouraging evidence that commutativity analysis can serve as the basis for a successful parallelizing compiler.
A note on “On the conversion of indirect to direct recursion”
Authors: Yu Ting , Kaser Owen
Published: October 2002

In the article “On the Conversion of Indirect to Direct Recursion”(
ACM Lett. Program. Lang. 2,
1-4. pp. 151-164), a method was introduced to convert indirect to direct recursion. It was claimed that for any call graph, there is a mutual-recursion elimination sequence if and only if no strongly connected component contains two node-disjoint circuits. We first give a counterexample and then provide a correction.
Solving shape-analysis problems in languages with destructive updating
Authors: Sagiv Mooly , Reps Thomas , Wilhelm Reinhard
Published: October 2002

This article concerns the static analysis of programs that perform
destructive updating on heap-allocated storage. We give an algorithm
that uses finite shape graphs to approximate conservatively the
possible “shapes” that heap-allocated structures in a program can take on. For certain programs, our technique is able to determine
such properties as (1) when the input to the program is a list, the
output is also a list and (2) when the input to the program is a tree,
the output is also a tree. For example, the method can determine that
“listness” is preserved by (1) a program that performs list reversal
via destructive updating of the input list and (2) a program that
searches a list and splices a new element into the list. None of the previously known methods that use graphs to model the
program's store are capable of determining that “listness” is
preserved on these examples (or examples of similar complexity).
In contrast with most previous work, our shape analysis algorithm is
even accurate for certain programs that update cyclic data structures;
that is, it is sometimes able to show that when the input to the
program is a circular list, the output is also a circular list. For
example, the shape-analysis algorithm can determine that an insertion
into a circular list preserves “circular listness.”
A practical and flexible flow analysis for higher-order languages
Authors: Ashley J. Michael , Dybvig R. Kent
Published: October 2002

A flow analysis collects data-flow and control-flow information about programs. A compiler can use this information to enable optimizations. The analysis described in this article unifies and extends previous work on flow analysis for higher-order languages supporting assignment and control operators. The analysis is abstract interpretation based and is parameterized over two polyvariance operators and a projection operator. These operators are used to regulate the speed and accuracy of the analysis. An implementation of the analysis is incorporated into and used in a production Scheme compiler. The analysis can process any legal Scheme program without modification. Others have demonstrated that a 0CFA analysis can enables the optimizations, but a 0CFA analysis is
O
(
n
)
3
). An
O
(
n
) instantiation of our analysis successfully enables the optimization of closure representations and procedure calls. Experiments with the cheaper instantiation show that it is as effective as 0CFA for these optimizations.