bluuebunny/crossref_metadata_2025 huggingface dataset:
Effect of interface roughness on gate bias instability of polycrystalline silicon thin-film transistors
Authors: Hastas N. A. , Dimitriadis C. A. , Kamarinos G.
Published: October 2002

The effect of the SiO2/polycrystalline silicon (polysilicon) interface roughness on the stability of n-channel large grain polysilicon thin-film transistors (TFTs) is investigated. The positive gate voltage of 20 V is used in the bias stress experiments, with the source and drain grounded. It is shown that the current through the gate oxide and the stability of the TFT are directly related to the importance of the interface roughness. The evolution of the TFT parameters with stress duration indicates that the turn-on voltage Von and the subthreshold swing voltage S are degraded due to the generation of dangling bond midgap states, while the leakage current IL and the maximum transconductance Gm are degraded due to the generation of strain-bond tail states. Moreover, the parameters Von and IL are found to degrade faster than the parameters S and Gm, respectively, due to electron trapping in the gate oxide.
Predicting temperature dependence of the refractive index and nonlinear optical coefficients in lithium niobate
Authors: Xue D. , Iyi N. , Kitamura K.
Published: October 2002

The optical properties of lithium niobate single crystals are quantitatively calculated at different temperatures. The chemical bond method is used to predict the temperature dependence of the refractive index and nonlinear optical coefficient variations. Employing the chemical bond method, both the refractive index and nonlinear optical coefficients of lithium niobate are theoretically derived from the corresponding crystallographic structure. Calculated results show that the optical properties of lithium niobate at 1.064 μm increase remarkably with increasing temperature, this is due to a high local effect provided by temperature on the valence electrons of constituent ions of lithium niobate. The comparison of our predictions with experimental measurements in literature is discussed. The present work shows us a clear relation among the crystal structure, optical properties, and temperature in lithium niobate single crystals.
Minimizing threading dislocations by redirection during cantilever epitaxial growth of GaN
Authors: Follstaedt D. M. , Provencio P. P. , Missert N. A. , Mitchell C. C. , Koleske D. D. , Allerman A. A. , Ashby C. I. H.
Published: October 2002

A 40-fold reduction in density of vertical threading dislocations (VTDs) at the surface of GaN is obtained with cantilever epitaxy by using narrow (<1 μm) mesas etched into a sapphire substrate and conditions producing angled {11-22} facets to initiate growth by metalorganic chemical vapor deposition. These two techniques redirect VTDs over the mesas to the horizontal and away from device areas above. Further reductions appear possible if the facets uniformly cover all mesas prior to cantilever growth.
Midinfrared luminescence from InAs quantum dots in unipolar devices
Authors: Wasserman D. , Lyon S. A.
Published: October 2002

Midinfrared light has been obtained from InAs quantum dots (QDs) in unipolar semiconductor devices with moderate current densities at low temperatures (77 K). The luminescence signals are broad, extending from the 70 meV cutoff of the HgCdTe detector to 200 meV, however they exhibit a peak at about 150 meV and are clearly distinct from thermal radiation. The QDs are contained within a resonant tunneling structure which includes a superlattice (AlGaAs/GaAs) electron energy filter and are grown with all n-type material by molecular-beam epitaxy. Electroluminescence and photoluminescence experiments have been used to examine the transitions responsible for the midinfrared emission.
Density clamping and longitudinal spatial hole burning in a gain-clamped semiconductor optical amplifier
Authors: Nomura M.-S. , Salleras F. , Dupertuis M. A. , Kappei L. , Marti D. , Deveaud B. , Emery J.-Y. , Crottini A. , Dagens B. , Shimura T. , Kuroda K.
Published: October 2002

We have directly measured, under operating conditions, the distributions of carrier densities and temperatures in a gain-clamped semiconductor optical amplifier designed for operation at 1.55 μm. As expected, longitudinal spatial hole burning is much smaller than in conventional semiconductor optical amplifiers and the effects of gain clamping are clearly evidenced. The amplifier nevertheless shows a sizeable temperature increase for both the lattice and the carriers at high currents, which are attributed to contributions of Auger recombination, intervalence band absorption, and Joule and recombination heating.
The origin of stress reduction by low-temperature AlN interlayers
Authors: Bläsing J. , Reiher A. , Dadgar A. , Diez A. , Krost A.
Published: October 2002

Thin low-temperature AlN interlayers can be applied to reduce stress to grow thick crack-free AlGaN layers on GaN buffer layers on sapphire and thick crack-free GaN layers on Si. The mechanism leading to stress reduction is investigated by high resolution x-ray diffractometry measurements on metalorganic chemical vapor phase epitaxy grown samples on Si(111) with different interlayer deposition temperatures. A decrease of tensile stress with decreasing interlayer growth temperature is observed. From reciprocal space maps we conclude that interlayers grown at high temperatures are pseudomorphic, while grown at lower temperatures they are relaxed. Therefore, AlGaN or GaN layers grown on a low temperature AlN interlayer grow under compressive interlayer-induced strain. The stress in the GaN layer depends on the growth temperature that likely controls the amount of AlN interlayer relaxation.
Scanning Lorentz force microscopy
Authors: Okuda Atsushi , Ichihara Jun , Majima Yutaka
Published: October 2002

We describe a technique for imaging magnetic flux density by measuring lateral Lorentz force generated by current through a nonmagnetic tip in a stray magnetic flux density emanating from a sample. We demonstrate its usefulness by showing Lorentz force images of recorded tracks in a magnetic hard disk together with the topographic image. The lateral resolution of the technique is also discussed.
Nonvolatile two-color holography in Mn-doped near-stoichiometric lithium niobate
Authors: Liu Youwen , Kitamura Kenji , Takekawa Shunji , Ravi Ganesan , Nakamura Masaru , Hatano Hideki , Yamaji Takashi
Published: October 2002

Nonvolatile holograms are recorded in near-stoichiometric LiNbO3 doped with 8 ppm of Mn by use of a two-color holographic recording method. An IR laser with wavelength of 778 nm is used for writing and a UV laser with wavelength of 350 nm is used for gating. Dependences of two-color sensitivity and M/♯ on gating and writing intensities are presented. Significant improvements of sensitivity, M/♯, and dark decay are obtained compared with reduced near-stoichiometric LiNbO3. The obtained high two-color sensitivity of 0.21 cm/J with a gating intensity of 1.5 W/cm2 is attributed to large light-induced absorption of small polarons.
Microstructure of squarylium dye J aggregate films examined on the basis of optical behavior at low temperature
Authors: Tatsuura Satoshi , Tian Minquan , Furuki Makoto , Sato Yasuhiro , Iwasa Izumi , Pu Lyong Sun , Kawashima Hitoshi , Ishikawa Hiroshi
Published: October 2002

The microstructure of a spin-coated film of squarylium dye J aggregates is examined on the basis of the measurement of the optical properties and the third-order nonlinear optical susceptibility χ(3) at low temperature. The absorption maximum of J aggregates shifted to lower energies as the film temperature decreased, while χ(3) was independent of the temperature. The latter finding indicates that the coherent length of J aggregates is confined by a structural boundary rather than by phonons; consequently, the observed peak energy shift can be due to temperature-dependent conformational change of the aggregates. The small aggregation size may contribute to the ultrahigh-speed optical response of squarylium dye J aggregates.
Si(100) surface morphology evolution during normal-incidence sputtering with 100–500 eV Ar+ ions
Authors: Ludwig F. , Eddy C. R. , Malis O. , Headrick R. L.
Published: October 2002

Grazing incidence small-angle x-ray scattering and atomic force microscopy have been used to systematically investigate the evolution of Si(100) surface morphology during normal-incidence Ar+ sputtering as a function of ion energy in the range of 100–500 eV. For ion energy ranges of 100–300 eV, two structures with distinct individual length scales and behaviors form on the surface. There is a smaller scale (lateral size of 20–50 nm) morphology that grows in scattering intensity and coarsens with time. There is also a larger scale (lateral size of approximately 100 nm) morphology that grows in scattering intensity but does not coarsen significantly in the time scales studied. At higher energies (400–500 eV), sputtering causes the Si(100) surface to become smoother on length scales smaller than 200 nm.
The apomorphine test: a biological marker for heroin dependence disorder?
Authors: Guardia José , Casas Miguel , Prat Gemma , Trujols Joan , Segura Lidia , Sánchez‐Turet Miguel
Published: October 2002

This experimental study was conducted in the inpatient detoxification addictive behavior unit of the Sant Pau Hospital in Barcelona and included 22 healthy subjects (HS) and 42 intravenous heroin‐dependent subjects (HDS). Apomorphine‐induced yawning rates were investigated in three different groups; heroin‐dependent patients stabilized on d‐propoxiphene, heroin‐dependent patients recently withdrawn from d‐propoxiphene and normal controls. Yawning responses were recorded continuously by independent observers for periods of 45 minutes following administration of low doses of subcutaneous apomorphine and NaCl. The lowest subcutaneous apomorphine dose able to induce a significantly higher number of yawning responses in HS was 0.005 mg/kg. The yawning responses induced by this dose in HDS were also significantly higher than those induced by placebo. When comparing the number of yawning responses between the study groups, differences were observed only between HDS and HS and no effect of gender was obtained. The apomorphine test may be useful in assessing central dopamine system alterations associated with chronic heroin consumption and could be a stable and reliable biological marker of heroin‐dependence disorders.
Absence of Telomerase Activity in Malignant Bone Tumors and Soft‐TissueSarcomas
Authors: Lauer Nina K. , Maier Sandra M. , Oberringer Martin , Schulte Michael , Mutschler Wolf , Hanselmann Rainer G. , Schartl Manfred , Scherer Stefan J. , Wirbel Reiner J.
Published: October 2002

Purpose: Telomerase activity appears to play a crucial role in the development of many tumors. More than 80% of all malignant
human tumors show an increased telomerase activity. However, conflicting results have been reported about telomerase
activity in sarcomas. The aim of the study was to obtain more information about telomerase activity in sarcomas based on a
large number of cases.

Methods: Telomerase activity was measured in 69 different tumor samples (33 malignant bone tumors and 36 soft tissue
sarcomas). Tumor samples were obtained intraoperatively and frozen immediately in liquid nitrogen. Telomerase activity
was detected by the telomeric repeat amplification assay (TRAP‐assay).

Results: Only 7% of the samples showed telomerase activity. No correlation between staging and telomerase activity could be
observed.

Discussion: The fact that only five out of 69 examined tumor samples showed a telomerase activity provides experimental
evidence that in sarcomas the reactivation of telomerase may play a subordinate role. Our results suggest that alternative
mechanisms for cell immortalization, yet to be determined, seem to be involved in the development and/or maintenance of
soft‐tissue sarcomas and malignant bone tumors.
CDART: Protein Homology by Domain Architecture
Authors: Geer Lewis Y. , Domrachev Michael , Lipman David J. , Bryant Stephen H.
Published: October 2002

The Conserved Domain Architecture Retrieval Tool (CDART) performs similarity searches of the NCBI Entrez Protein Database based on domain architecture, defined as the sequential order of conserved domains in proteins. The algorithm finds protein similarities across significant evolutionary distances using sensitive protein domain profiles rather than by direct sequence similarity. Proteins similar to a query protein are grouped and scored by architecture. Relying on domain profiles allows CDART to be fast, and, because it relies on annotated functional domains, informative. Domain profiles are derived from several collections of domain definitions that include functional annotation. Searches can be further refined by taxonomy and by selecting domains of interest. CDART is available athttp://www.ncbi.nlm.nih.gov/Structure/lexington/lexington.cgi.
An Interface Model for the Periodontal Ligament
Authors: Gei Massimiliano , Genna Francesco , Bigoni Davide
Published: October 2002

A nonlinear interface constitutive law is formulated for modeling the mechanical behavior of the periodontal ligament. This gives an accurate interpolation of the few available experimental results and provides a reasonably simple model for mechanical applications. The model is analyzed from the viewpoints of both mathematical consistency and effectiveness in numerical calculations. In order to demonstrate the latter, suitable two- and three-dimensional nonlinear interface finite elements have been implemented.
Economy of effort in different speaking conditions. II. Kinematic performance spaces for cyclical and speech movements
Authors: Perkell Joseph S. , Zandipour Majid
Published: October 2002

This study was designed to test the hypothesis that the kinematic manipulations used by speakers in different speaking conditions are influenced by kinematic performance limits. A range of kinematic parameter values was elicited by having seven subjects produce cyclical CV movements of lips, tongue blade and tongue dorsum (/bɑ/, /dɑ/, /gɑ/), at rates ranging from 1 to 6 Hz. The resulting measures were used to establish speaker- and articulator-specific kinematic performance spaces, defined by movement duration, displacement and peak speed. These data were compared with speech movement data produced by the subjects in several different speaking conditions in the companion study (Perkell et al., 2002). The amount of overlap of the speech data and cyclical data varied across speakers, from almost no overlap to complete overlap. Generally, for a given movement duration, speech movements were larger than cyclical movements, indicating that the speech movements were faster and were produced with greater effort, according to the performance space analysis. It was hypothesized that the cyclical movements of the tongue and lips were slower than the speech movements because they were more constrained by (coupled to) the relatively massive mandible. To test this hypothesis, a comparison was made of cyclical movements in maxillary versus mandibular frames of reference. The results indicate that the cyclical movements were not strongly constrained by mandible movements. The overall results generally indicate that the cyclical task did not succeed in defining the upper limits of kinematic performance spaces within which the speech data were confined. Thus, the hypothesis that performance limits influence speech kinematics could not be tested effectively. The differences between the speech and cyclical movements may be due to other factors, such as differences in speakers’ “skill” with the two types of movement, or the size of the movements—the speech movements were larger, probably because of a well-defined target for the primary, stressed vowel.
An adaptive tenuring policy for generation scavengers
Authors: Ungar David , Jackson Frank
Published: October 2002

One of the more promising automatic storage reclamation techniques, generation scavenging, suffers poor performance if many objects live for a fairly long time and then die. We have investigated the severity of this problem by simulating a two-generation scavenger using traces taken from actual 4-h sessions. There was a wide variation in the sample runs, with garbage-collection overhead ranging from insignificant, during three of the runs, to severe, during a single run. All runs demonstrated that performance could be improved with two techniques: segregating large bitmaps and strings, and adapting the scavenger's tenuring policy according to demographic feedback. We therefore incorporated these ideas into a commercial Smalltalk implementation. These two improvements deserve consideration for any storage reclamation strategy that utilizes a generation scavenger.
Scheduling time-critical instructions on RISC machines
Authors: Palem Krishna V. , Simons Barbara B.
Published: October 2002

We present a polynomial time algorithm for constructing a minimum completion time schedule of instructions from a basic block on RISC machines such as the Sun SPARC, the IBM 801, the Berkeley RISC machine, and the HP Precision Architecture. Our algorithm can be used as a heuristic for RISC processors with longer pipelines, for which there is no known optimal algorithm. Our algorithm can also handle time-critical instructions, which are instructions that have to be completed by a specific time. Time-critical instructions occur in some real-time computations, and can also be used to make shared resources such as registers quickly available for reuse. We also prove that in the absence of time-critical constraints, a greedy scheduling algorithm always produces a schedule for a target machine with multiple identical pipelines that has a length less than twice that of an optimal schedule. The behavior of the heuristic is of interest because, as we show, the instruction scheduling problem becomes NP-hard for arbitrary length pipelines, even when the basic block of code being input consists of only several independent streams of straightline code, and there are no time-critical constraints. Finally, we prove that the problem becomes NP-hard even for small pipelines, no time-critical constraints, and input of several independent streams of straightline code if either there is only a single register or if no two instructions are allowed to complete simultaneously because of some shared resource such as a bus.
Procedural implementation of algebraic specification
Authors: Lin Huimin
Published: October 2002

An implementation of an algebraic specification in an imperative programming language consists of a representation type, together with an invariant and an equivalence relation over it, and a procedure for each operator in the specification. A formal technique is developed to check the correctness of an implementation with respect to its specification. Here “correctness” means that the implementation satisfies the axioms and preserves the behavior of the specification. Within legal representing value space, a correct implementation behaves like a desirable model of the specification. A notion of implementation refinement is also proposed, and it is shown that the correctness relation between implementations and specifications is preserved by implementation refinement. In the extreme case the procedures in an implementation may be pre-post-condition pairs. Such abstract implementations can be refined into executable code by refining the abstract procedures in it. In this way a formal link between the algebraic and the pre- post-condition specification techniques is established.
Determinacy testing for nondeterminate logic programming languages
Authors: Tick E. , Korsloot M.
Published: October 2002

This paper describes an algorithm for the code generation of determinacy testing for nondeterminate flat concurrent logic programming languages. Languages such as Andorra and Pandora require that procedure invocations suspend if there is more than one candidate clause potentially satisfying the goal. The algorithm described has been developed specifically for a variant of flat Pandora based on FGHC, although the concepts are general. We have extended Kliger and Shapiro's decision-graph construction algorithm to compile “don't-know” procedures that must suspend for nondeterminate goal invocation. The determinacy test is compiled into a decision graph quite different from those of committed-choice procedures: They are more similar to decision trees optimized by code sharing. We present both empirical data of compilation results (code size and graph characteristics), and a correctness proof for our code-generation algorithm.
Live-structure dataflow analysis for Prolog
Authors: Mulkers Anne , Winsborough William , Bruynooghe Maurice
Published: October 2002

For the class of applicative programming languages, efficient methods for reclaiming the memory occupied by released data structures constitute an important aspect of current implementations. The present article addresses the problem of memory reuse for logic programs through program analysis rather than by run-time garbage collection. The aim is to derive run-time properties that can be used at compile time to specialize the target code for a program according to a given set of queries and to automatically introduce destructive assignments in a safe and transparent way so that fewer garbage cells are created.

The dataflow analysis is constructed as an application of abstract interpretation for logic programs. An abstract domain for describing structure-sharing and liveness properties is developed as are primitive operations that guarantee a sound and terminating global analysis. We explain our motivation for the design of the abstract domain, make explicit the underlying implementation assumptions, and discuss the precision of the results obtained by a prototype analyzer.
Operational semantics-directed compilers and machine architectures
Authors: Hannan John
Published: October 2002

We consider the task of automatically constructing intermediate-level machine architectures and compilers generating code for these architectures, given operational semantics for source languages. We use operational semantics in the form of abstract machines given by rewrite systems in which the rewrite rules operate on terms representing states of computations. To construct compilers and new architectures we employ a particular strategy called pass separation, a form of staging transformation, that takes a program
p
and constructs a pair of programs
p
1
,
p
2
such that
p(x, y)
=

p
2
(p
1
(x), y)

) for all
x,y
. If
p
represents an operational semantics for a language, with arguments
x
and
y
denoting a source program and its input data, then pass separation constructs programs

p
1

and

p
2

corresponding to a compiler and an executor.

The compiler translates the source language into an intermediate-level target language, and the executor provides the definition for this language. Our use of pass separation supports the automatic definition of target languages or architectures, and the structure of these architectures is directed by the structure of the given source semantics. These architectures resemble abstract machine languages found in hand-crafted compilers. Our method is restricted to a limited class of abstract machines given as term-rewriting systems, but we argue that this class encompasses a large set of language definitions derived from more natural operational semantics. We provide two examples of our method by constructing compilers and target architectures for a simple functional language and a simple imperative language. Though we construct these architectures automatically, they bear a striking resemblance to existing architectures constructed by hand.
Functions as passive constraints in LIFE
Authors: Aït-Kaci Hassan , Podelski Andreas
Published: October 2002

LIFE is a programming language proposing to integrate logic programming, functional programming, and object-oriented programming. It replaces first-order terms with ψ-terms, data structures that allow computing with partial information. These are approximation structures denoting sets of values. LIFE further enriches the expressiveness of ψ-terms with functional dependency constraints. We must explain the meaning and use of functions in LIFE declaratively, as solving partial information constraints. These constraints do not attempt to generate their solutions but behave as demons filtering out anything else. In this manner, LIFE functions act as declarative coroutines. We need to show that the ψ-term's approximation semantics is congruent with an operational semantics viewing functional reduction as an effective enforcing of passive constraints. In this article, we develop a general formal framework for entailment and disentailment of constraints based on a technique called relative simplification. We study its operational and semantical properties, and we use it to account for functional application over ψ-terms in LIFE.
Optimally profiling and tracing programs
Authors: Ball Thomas , Larus James R.
Published: October 2002

This paper describes algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs with respect to the commonly used technique of placing code in each basic block. Program profiling counts the number of times each basic block in a program executes. Instruction tracing records the sequence of basic blocks traversed in a program execution. The algorithms optimize the placement of counting/tracing code with respect to the expected or measured frequency of each block or edge in a program's control-flow graph. We have implemented the algorithms in a profiling/tracing tool, and they substantially reduce the overhead of profiling and tracing.

We also define and study the hierarchy of profiling problems. These problems have two dimensions: what is profiled (i.e., vertices (basic blocks) or edges in a control-flow graph) and where the instrumentation code is placed (in blocks or along edges). We compare the optimal solutions to the profiling problems and describe a new profiling problem: basic-block profiling with edge counters. This problem is important because an optimal solution to any other profiling problem (for a given control-flow graph) is never better than an optimal solution to this problem. Unfortunately, finding an optimal placement of edge counters for vertex profiling appears to be a hard problem in general. However, our work shows that edge profiling with edge counters works well in practice because it is simple and efficient and finds optimal counter placements in most cases. Furthermore, it yields more information than a vertex profile. Tracing also benefits from placing instrumentation code along edges rather than on vertices.
Automatic isolation of compiler errors
Authors: Whalley David B.
Published: October 2002

This paper describes a tool called
vpoiso
that was developed to isolate errors automatically in the
vpo
compiler system. The two general types of compiler errors isolated by this tool are optimization and nonoptimization errors. When isolating optimization errors,
vpoiso
relies on the
vpo
optimizer to identify sequences of changes, referred to as transformations, that result in semantically equivalent code and to provide the ability to stop performing
improving
(or unnecessary) transformations after a specified number have been performed. A compilation of a typical program by
vpo
often results in thousands of
improving
transformations being performed. The
vpoiso
tool can automatically isolate the first
improving
transformation that causes incorrect output of the execution of the compiled programs by using a binary search that varies the number of
improving
transformation performed. Not only is the illegal transformation automatically isolated, but
vpoiso
also identifies the location and instant the transformation is performed in
vpo
. Nonoptimization errors occur from problems in the front end, code generator, and
necessary
transformations in the optimizer. If another compiler is available that can produce correct (but perhaps more inefficient) code, then
vpoiso
can isolate nonoptimization errors to a single function. Automatic isolation of compiler errors facilitates retargeting a compiler to a new machine, maintenance of the compiler, and supporting experimentation with new optimizations.
A worst case of circularity test algorithms for attribute grammars
Authors: Wu Pei-Chi , Wang Feng-Jian
Published: October 2002

Although the circularity test problem for
attribute grammars
(AGs) has been proven to be intrinsically exponential, to date, a worst case for the existing circularity test algorithms has yet to be presented. This note presents a worst-case AG in which the number of incomparable dependency graphs induced at the root is exponential. The worst case can help to clarify the complexity of the problem.
A complete calculus for the multialgebraic and functional semantics of nondeterminism
Authors: Walicki Michal , Meldal Sigurd
Published: October 2002

The current algebraic models for nondeterminism focus on the notion of
possibility
rather than
necessity
and consequently equate (nondeterministic) terms that one would intuitively not consider equal. Furthermore, existing models for nondeterminism depart radically from the standard models for (equational) specifications of deterministic operators. One would prefer that a specification language for nondeterministic operators be based on an extension of the standard model concepts, preferably in such a way that the reasoning system for (possibly nondeterministic) operators becomes the standard equational one whenever restricted to the deterministic operators—the objective should be to
minimize
the departure from the standard frameworks. In this article we define a specification language for nondeterministic operators and multialgebraic semantics. The first
complete
reasoning system for such specifications is introduced. We also define a transformation of specifications of nondeterministic operators into derived specifications of deterministic ones, obtaining a “computational” semantics of nondeterministic specification by adopting the standard semantics of the derived specification as the semantics of the original one. This semantics turns out to be a refinement of multialgebra semantics. The calculus is shown to be sound and complete also with respect to the new semantics.
Storage assignment to decrease code size
Authors: Liao Stan , Devadas Srinivas , Keutzer Kurt , Tjiang Steven , Wang Albert
Published: October 2002

DSP architectures typically provide indirect addressing modes with autoincrement and decrement. In addition, indexing mode is generally not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address arithmetic to access automatic variables. Subsuming the address arithmetic into autoincrement and decrement modes improves the size of the generated code. In this article we present a formulation of the problem of optimal storage assignment such that explicit instructions for address arithmetic are minimized. We prove that for the case of a single address register the decision problem is NP-complete, even for a single basic block. We then generalize the problem to multiple address registers. For both cases heuristic algorithms are given, and experimental results are presented.
Identifying loops using DJ graphs
Authors: Sreedhar Vugranam C. , Gao Guang R. , Lee Yong-Fong
Published: October 2002

Loop identification is a necessary step in loop transformations for high-performance architectures. One classical technique for detecting loops is Tarjan's interval-finding algorithm. The intervals identified by Tarjan's method are single-entry, strongly connected subgraphs that closely reflect a program's loop structure. We present a simple algorithm for identifying both reducible and irreducible loops using DJ graphs. Our method is a generalization of Tarjan's method, as it identifies nested intervals (or loops) even in the presence of irreducibility.
Information-flow and data-flow analysis of while-programs
Authors: Bergeretti Jean-Francois , Carré Bernard A.
Published: October 2002

Until recently, information-flow analysis has been used primarily to verify that information transmission between program variables cannot violate security requirements. Here, the notion of information flow is explored as an aid to program development and validation.

Information-flow relations are presented for while-programs, which identify those program statements whose execution may cause information to be transmitted from or to particular input, internal, or output values. It is shown with examples how these flow relations can be helpful in writing, testing, and updating programs; they also usefully extend the class of errors which can be detected automatically in the “static analysis” of a program.
The program dependence graph and its use in optimization
Authors: Ferrante Jeanne , Ottenstein Karl J. , Warren Joe D.
Published: October 2002

In this paper we present an intermediate program representation, called theprogram dependence graph(PDG), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the relevant data flow relationships of a program. Control dependences are introduced to analogously represent only the essential control flow relationships of a program. Control dependences are derived from the usual control flow graph. Many traditional optimizations operate more efficiently on the PDG. Since dependences in the PDG connect computationally related parts of the program, a single walk of these dependences is sufficient to perform many optimizations. The PDG allows transformations such as vectorization, that previously required special treatment of control dependence, to be performed in a manner that is uniform for both control and data dependences. Program transformations that require interaction of the two dependence types can also be easily handled with our representation. As an example, an incremental approach to modifying data dependences resulting from branch deletion or loop unrolling is introduced. The PDG supports incremental optimization, permitting transformations to be triggered by one another and applied only to affected dependences.
Compile-time memory reuse in logic programming languages through update in place
Authors: Gudjónsson Gudjón , Winsborough William H.
Published: October 2002

Standard implementation techniques for single-assignment languages modify a data structure without destroying the original, which may subsequently be accessed. Instead a variant structure is created by using newly allocated cells to represent the changed portion and to replace any cell that references a newly allocated cell. The rest of the original structure is shared by the variant. The effort required to leave the original uncorrupted is unnecessary when the program will never reference the original again. This effort includes allocating and initializing new cells, as well as garbage collecting replaced cells. This article specifies a transformation system that introduces update-in-place operations, making Prolog programs update recursive data structures much as an imperative program would. The article introduces the notion of a reuse map, which formalizes reallocation decisions. Because optimal memory reuse is intractable, a heuristical method is presented that performs well in practice. Small Prolog programs that manipulate recursive data structures have their speed increased up to about five times (naive recurse), not counting any speedup obtained by avoiding garbage collection. Quicksort is about three times as fast, merge-sort about one and a half, matrix transposition about twice, and Gaussian elimination is about 1.2 times as fast.
Model-checking concurrent systems with unbounded integer variables
Authors: Bultan Tevfik , Gerber Richard , Pugh William
Published: October 2002

Model checking is a powerful technique for analyzing large, finite-state systems. In an infinite state system, however, many basic properties are undecidable. In this article, we present a new symbolic model checker which conservatively evaluates safety and liveness properties on programs with unbounded integer variables. We use Presburger formulas to symbolically encode a program's transition system, as well as its model-checking computations. All fixpoint calculations are executed symbolically, and their convergence is guaranteed by using approximation techniques. We demonstrate the promise of this technology on some well-known infinite-state concurrency problems.
Specification and dialogue control of visual interaction through visual rewriting systems
Authors: Bottoni P. , Costabile M. F. , Mussio P.
Published: October 2002

Computers are increasingly being seen not only as computing tools but more so as communication tools, thus placing special emphasis on human-computer interaction (HCI). In this article, the focus is on visual HCI, where the messages exchanged between human and computer are images appearing on the computer screen, as usual in current popular user interfaces. We formalize interactive sessions of a human-computer dialogue as a structured set of legal visual sentences, i.e., as a visual language, and show how rewriting systems can be generalized to specify both the pictorial and the computational aspects of visual languages. To this end, Visual Conditional Attributed Rewriting (VCARW) systems are introduced, and use for specification of visual languages. These specifications are given as inputs to a procedure illustrated in the article as a system of algorithms, which automatically generates control mechanisms of the interaction, thus favoring the design of more reliable and usable systems.
Applicability of Software Validation Techniques to Scientific Programs
Authors: Howden W. E.
Published: October 2002

Error analysis involves the examination of a collection of programs whose errors are known. Each error is analyzed and validation techniques which would discover the error are identified. The errors that were present in version five of a package of Fortran scientific subroutines and then later corrected in version six were analyzed. An integrated collection of static and dynamic analysis methods would have discovered the errors in version five before its release. An integrated approach to validation and the effectiveness of individual methods are discussed.
Data types are values
Authors: Donahue James , Demers Alan
Published: October 2002

An important goal of programming language research is to isolate the fundamenal concepts of languages, those basic ideas that allow us to understand the relationships among various language features. This paper examines one of these underlying notions, that of
data type
, with particular attention to the treatment of
generic
or
polymorphic
procedures and static type-checking.
Noncorrecting syntax error recovery
Authors: Richter Helmut
Published: October 2002

A parser must be able to continue parsing after encountering a syntactic error to check the remainder of the input. To achieve this, it is not necessary to perform corrections on either the input text or the stack contents. A formal framework is provided in which noncorrecting syntax error recovery concepts are defined and investigated. The simplicity of these concepts allows the statement of provable properties, such as the absence of spurious error messages or the avoidance of skipping input text. These properties are due to the fact that no assumptions about the nature of the errors need be made to continue parsing.
A mathematical approach to nondeterminism in data types
Authors: Hesselink Wim H.
Published: October 2002

The theory of abstract data types is generalized to the case of nondeterministic operations (set-valuedfunctions). Since the nondeterminism of operations may be coupled, signatures are extended so that operations can have results in Cartesian products. Input/output behavior is used to characterize implementation of one model by another. It is described by means of accumulated arrows, which form a generalization of the term algebra. Morphisms of nondeterministic models are introduced. Both innovations prove to be powerful tools in the analysis of input/output behavior. Extraction equivalence and observable equivalence of values are investigated. Quotient models for such equivalence relations are constructed. The equivalence relations are compared with each other, with separation of values by means of experiments, and with the separation property that characterizes a terminal model. Examples are given to show that the four concepts are different. In deterministic models the concepts coincide.
A formal approach to undo operations in programming languages
Authors: Leeman George B.
Published: October 2002

A framework is presented for adding a general Undo facility to programming languages. A discussion of relevant literature is provided to show that the idea of Undoing pervades several areas in computer science, and even other disciplines. A simple model of computation is introduced, and it is augmented with a minimal amount of additional structure needed for recovery and reversal. Two different interpretations of Undo are motivated with examples. Then, four primitives are defined in a language-independent manner; they are sufficient to support a wide range of Undo capability. Two of these primitives carry out state saving, and the others mirror the two versions of the Undo operation. Properties of and relationships between these primitives are explored, and there are some preliminary remarks on how one could implement a system based on this formalism. The main conclusion is that the notions of recovery and reversal of actions can become part of the programming process.
A PDP-8 emulator program
Authors: Shelburne Brian J.
Published: October 2002

The clean, simple, and elegant architecture of the classic PDP-8 makes it an ideal candidate for studying concepts in computer organization. The PDP-8 emulator program allows a user to write, edit, assemble, debug, trace, and execute PDP-8 machine code and PDP-8 assembler language programs. With it, the user can obtain a feel for the PDP-8. The PDP-8 emulator program includes a simple built-in text editor which is used to write and edit PDP-8 assembler language programs, an assembler to translate these programs into PDP-8 machine code, and a virtual PDP-8 engine upon which to execute the code. PDP-8 code can be executed from a
debug
screen display that allows the user to observe the contents of registers and memory as the code executes or code can be executed using an I/O interface that requires user-written PDP-8 I/O routines. This article provides an introduction to both the PDP-8 architecture and PDP-8 assembler language and discusses how to use the PDP-8 emulator program. The PDP-8 emulator program runs under MS-DOS in a command window.
A procedural approach to authoring solid models
Authors: Cutler Barbara , Dorsey Julie , McMillan Leonard , Müller Matthias , Jagnow Robert
Published: October 2002

We present a procedural approach to authoring layered, solid models. Using a simple scripting language, we define the internal structure of a volume from one or more input meshes. Sculpting and simulation operators are applied within the context of the language to shape and modify the model. Our framework treats simulation as a modeling operator rather than simply as a tool for animation, thereby suggesting a new paradigm for modeling as well as a new level of abstraction for interacting with simulation environments.Capturing real-world effects with standard modeling techniques is extremely challenging. Our key contribution is a concise procedural approach for seamlessly building and modifying complex solid geometry. We present an implementation of our language using a flexible tetrahedral representation. We show a variety of complex objects modeled in our system using tools that interface with finite element method and particle system simulations.
Synthesis of complex dynamic character motion from simple animations
Authors: Liu C. Karen , Popović Zoran
Published: October 2002

In this paper we present a general method for rapid prototyping of realistic character motion. We solve for the natural motion from a simple animation provided by the animator. Our framework can be used to produce relatively complex realistic motion with little user effort.We describe a novel constraint detection method that automatically determines different constraints on the character by analyzing the input motion. We show that realistic motion can be achieved by enforcing a small set of linear and angular momentum constraints. This simplified approach helps us avoid the complexities of computing muscle forces. Simpler dynamic constraints also allow us to generate animations of models with greater complexity, performing more intricate motions. Finally, we show that by learning a small set of key parameters that describe a character pose we can help a non-skilled animator rapidly create realistic character motion.
Hierarchical pattern mapping
Authors: Soler Cyril , Cani Marie-Paule , Angelidis Alexis
Published: October 2002

We present a multi-scale algorithm for mapping a texture defined by an input image onto an arbitrary surface. It avoids the generation and storage of a new, specific texture. The idea is to progressively cover the surface by texture patches of various sizes and shapes, selected from a single input image. The process starts with large patches. A mapping that minimizes the texture fitting error with already textured neighbouring patches is selected. When this error is above a threshold, the patch is split into smaller ones, and the algorithm recursively looks for good fits at a smaller scale. The process ends when the surface is entirely covered. Our results show that the method correctly handles a wide set of texture patterns, which can be used at different mapping scales. Hierarchical texture mapping only outputs texture coordinates in the original texture for each triangle of the initial mesh. Rendering is therefore easy and memory cost minimal. Moreover the initial geometry is preserved.
Compactly encoding unstructured inputs with differential compression
Authors: Ajtai Miklos , Burns Randal , Fagin Ronald , Long Darrell D. E. , Stockmeyer Larry
Published: October 2002

The subject of this article is
differential compression
, the algorithmic task of finding common strings between versions of data and using them to encode one version compactly by describing it as a set of changes from its companion. A main goal of this work is to present new differencing algorithms that (i) operate at a fine granularity (the atomic unit of change), (ii) make no assumptions about the format or alignment of input data, and (iii) in practice use linear time, use constant space, and give good compression. We present new algorithms, which do not always compress optimally but use considerably less time or space than existing algorithms. One new algorithm runs in
O
(
n
) time and
O
(1) space in the worst case (where each unit of space contains [log
n
] bits), as compared to algorithms that run in
O
(
n
) time and
O
(
n
) space or in
O
(
n
2
) time and
O
(1) space. We introduce two new techniques for differential compression and apply these to give additional algorithms that improve compression and time performance. We experimentally explore the properties of our algorithms by running them on actual versioned data. Finally, we present theoretical results that limit the compression power of differencing algorithms that are restricted to making only a single pass over the data.
Improving software inspections with group process support
Authors: Tyran Craig K. , George Joey F.
Published: October 2002

The 'group process' governing any group interaction also influences a group's inspection performance.