bluuebunny/crossref_metadata_2025_split huggingface dataset:
Implementation issues in the development of the parsec parser
Authors: Harper Mary P. , Helzerman Randall A. , Zoltowski Carla B. , Yeo Boon‐Dock , Chan Yin , Stewart Todd , Pellom Bryan L. 
Published: November 2006

AbstractThis paper describes the implementation of a constraint‐based parser, PARSEC (Parallel ARchitecture SEntence Constrainer), which has the required flexibility that a user may easily construct a custom grammar and test it. Once the user designs grammar parameters, constraints, and a lexicon, our system checks them for consistency and creates a parser for the grammar. The parser has an X‐windows interface that allows a user to view the state of a parse of a sentence, test new constraints, and dump the constraint network to a file. The parser has an option to perform the computationally expensive constraint propagation steps on the MasPar MP‐1. Stream and socket communication was used to interface the MasPar constraint parser with a standard X‐windows interface on our Sun Sparcstation.The design of our heterogeneous parser has benefitted from the use of object‐oriented techniques. Without these techniques, it would have been more difficult to combine the processing power of the MasPar with a Sun Sparcstation. Also, these techniques allowed the parser to gracefully evolve from a system that operated on single sentences, to one capable of processing word graphs containing multiple sentences, consistent with speech processing. This system should provide an important component of a real‐time speech understanding system.
Signatures: A language extension for improving type abstraction and subtype polymorphism in C++
Authors: Baumgartner Gerald , Russo Vincent F. 
Published: November 2006

AbstractC++ uses inheritance as a substitute for subtype polymorphism. We give examples where this makes the type system too inflexible. We then describe a conservative language extension that allows a programmer to define an abstract type hierarchy independent of any implementation hierarchies, to retroactively abstract over an implementation, and to decouple subtyping from inheritance. This extension gives the user more of the flexibility of dynamic typing while retaining the efficiency and security of static typing. Withdefault implementationsandviewsflexible mechanisms are provided for implementing an abstract type by different concrete class types. We first show how the language extension can be implemented in a preprocessor to a C++ compiler, and then detail and analyse the efficiency of an implementation we directly incorporated in the GNU C++ compiler.
Adding compression to a full‐text retrieval system
Authors: Zobel Justin , Moffat Alistair 
Published: November 2006

AbstractWe describe the implementation of a data compression scheme as an integral and transparent layer within a full‐text retrieval system. Using a semi‐static word‐based compression model, the space needed to store the text is under 30 per cent of the original requirement. The model is used in conjunction with canonical Huffman coding and together these two paradigms provide fast decompression. Experiments with 500 Mb of newspaper articles show that in full‐text retrieval environments compression not only saves space, it can also yield faster query processing ‐ a win‐win situation.
The heart of IGES
Authors: Kahrs Mark 
Published: November 2006

AbstractThis paper describes the problems and complexity of implementing an interpreter for IGES. IGES (the Initial Graphics Exchange Standard) is an attempt to define a language that can specify geometrical, electrical and mechanical specifications with a uniform syntax.The syntax of IGES is sketched first. This is followed by a short review of the primitives available within IGES. The interior of the interpreter is presented next with particular attention paid to the implementation of the macro language residing inside of IGES.
A prettier compiler‐compiler: Generating higher‐order parsers in C
Authors: Breuer Peter T. , Bowen Jonathan P. 
Published: November 2006

AbstractTop‐down (LL) context‐sensitive parsers with integrated synthesis and use of attributes are easy to express in functional programming languages, but the elegant functional programming model can also serve as an exact prototype for a more efficient implementation of the technology in ANSI C. The result is a compiler‐compiler that takes unlimited lookahead and backtracking, the extended BNF notation, and parameterized grammars with (higher‐order) meta‐parameters to the world of C programming. This article reports on the utility in question three years after public release.Preccgenerates standard ANSI C and is ‘plug compatible’ withlex‐ generated lexical analyzers prepared for the UNIXyacccompiler‐compiler. In contrast toyacc, however, the generated code is modular, which allows parts of scripts to be compiled separately and linked together incrementally. The constructed code is relatively efficient, as is demonstrated by the example Occam parser treated in depth here, but the main advantages we claim are ease of use, separation of specification and implementation concerns, and maintainability.
A scalability test for parallel code
Authors: Lyon Gordon , Kacker Raghu , Linz Arnaud 
Published: November 2006

AbstractCode scalability, crucial on any parallel system, determines how well parallel code avoids becoming a bottleneck as its host computer is made larger. The scalability of computer code can be estimated by statistically designed experiments that empirically approximate a multivariate Taylor expansion of the code's execution response function. Each suspected code bottleneck corresponds to a first‐order term in the expansion, the coefficient for that term indicating how sensitive execution is to changes in the suspect location. However, it is the expansion coefficients for second‐order interactions between code segments and the number of processors that are fundamental to discovering which program elements impede parallel speedup. A new, unified view of these second‐order coefficients yields an informal relative scalability test of high utility in code development. Discussion proceeds through actual examples, including a straightforward illustration of the test applied to SLALOM, a complex, multiphase benchmark. A quick graphical shortcut makes the scalability test readily accessible.
A specification case study using the B‐methodology
Authors: Storey Andrew 
Published: November 2006

AbstractThe B‐Method is a complete formal development process for mathematically transforming software systems from specification through to code. This article provides the reader with an overview of the process including a description of the language used for specifying systems (Abstract Machine Notation) and demonstrates its application by a simple, real‐life case study. The method has tool support in the form of a tool‐kit which is described here and applied to the case study. The results of the case study show how a system can be validated and verified in the early stages of its development through proof of the mathematical specification and an animating tool.
Employing static information in the generation of test cases
Authors: Gupta Rajiv , Soffa Mary Lou 
Published: November 2006

AbstractA commonly used approach for detecting defects in a program is to generate a suite of test inputs which exercises the entire program under a given testing criterion. Current techniques to generate test cases automatically that satisfy a testing criterion choose test input data by considering the testing requirements in an arbitrary order. In this paper, a technique is presented that groups the requirements and orders the generation of the test cases to reduce the number of test cases generated. The grouping is based on the statically determined property of post‐dominance. Test cases for each group are generated taking into account requirements for other groups. The use of this technique to generate test cases can be expected to produce fewer test cases that have to be retained with the software. A smaller number of test cases will require less effort and resources to test the software. The technique is especially useful in the maintenance environment, whether retesting of a changed program is done exhaustively or incrementally. The technique not only attempts to minimize the number of test cases generated but also reduces the effort to generate the test cases using the concept of a program slice.
Defining testability metrics axiomatically
Authors: Bainbridge John 
Published: November 2006

AbstractTestability measures have been defined on flowgraphs modelling the control flow through a program. These measures attempt to quantify aspects of the structural complexity of code that might give useful information about the testing stage of software production. This paper shows how two such metrics, the Number of Trails metric and the Mask [k = 2] metric, can be calculated axiomatically.
Transformational program analysis
Authors: Lano K. 
Published: November 2006

AbstractThis paper describes an approach to the semantic analysis of procedural code. The techniques differ from those adopted in current static analysis tools such as MALPAS (Bramson, 1984) and SPADE (Clutterbuck and Carré, 1988) in two key respects: (1) A database is used, together with language‐specific and language‐independent data models, as a repository for all information about a program or set of programs which is required for analysis, and for storing and interrelating the results of analyses; (2) The techniques aim to treat the full language under consideration by a process of successive transformation and abstraction from the source code until a representation is obtained which is amenable to analysis. This abstraction process can include the production of formal specifications from code. The techniques have been partially implemented for the OS/VS IBM diallect of COBOL '74 and for FORTRAN '77. Several components of the resulting toolset have been formally specified in Z, thus meeting some of the integrity requirements for verification tools given in ‘The procurement of safety critical software in defence equipment’ (MoD, 1991). The techniques have been applied in practice to a wide range of source programs and analysis problems (Lano and Haughton, 1993b; Lano, et al., 1991), including assessment problems (Lloyd's Register, 1992, 1993; Hornsby and Eldridge, 1990). Section 1 gives an overview of the analysis process. Section 2 describes the representations used to support the process. Section 3 describes some of the techniques involved, and Section 4 gives examples of applications of the process. The Appendix contains extracts from a large case study carried out using tools developed to support the process.
Re‐designing tasking structures of Ada programs for analysis: A case study
Authors: Yeh Wei Jen , Young Michal 
Published: November 2006

AbstractIn previous publications the authors described a compositional (hierarchical) approach to reachability analysis of Ada tasking programs based on process algebra. The abstraction capabilities of process algebra provide an effective means to control state explosion in automated state‐space analysis, but only if a design is carefully modularized to encapsulate details of behaviour. This paper reports experience modifying an existing design (a remote temperature sensor system described by Sanden) to make it more amenable to hierarchical analysis. Redesign for analysis was effective in improving the design in other ways as well: flaws uncovered in the analysis (and present in the original design) were easy to understand and correct because of the increased understandability of the revised design. This also suggests that these flaws might have been avoided, and the design generally improved, had ‘design for analysis’ been applied from the start.
An experimental evaluation of capture‐recapture in software inspections
Authors: Wohlin Claes , Runeson Per , Brantestam Johan 
Published: November 2006

AbstractThe use of capture‐recapture to estimate the residual faults in a software artifact has evolved as a promising method. However, the assumptions needed to make the estimates are not completely fulfilled in software development, leading to an underestimation of the residual fault content. Therefore, a method employing a filtering technique with an experience factor to improve the estimate of the residual faults is proposed in this paper. An experimental study of the capture‐recapture method with this correction method has been conducted. It is concluded that the correction method improves the capture‐recapture estimate of the number of residual defects in the inspected document.
Exploring the pyridoxal 5′‐phosphate‐dependent enzymes
Authors: Mozzarelli Andrea , Bettati Stefano 
Published: November 2006

AbstractPyridoxal 5′‐phosphate (PLP)‐dependent enzymes represent about 4% of the enzymes classified by the Enzyme Commission. The versatility of PLP in carrying out a large variety of reactions exploiting the electron sink effect of the pyridine ring, the conformational changes accompanying the chemical steps and stabilizing distinct catalytic intermediates, and the spectral properties of the different coenzyme‐substrate derivatives signaling the reaction progress, are some of the features that have attracted our interest to investigate the structure–dynamics–function relationships of PLP‐dependent enzymes. To this goal, an integrated approach combining biochemical, biophysical, computational, and molecular biology methods was used. The extensive work carried out on two enzymes, tryptophan synthase and O‐acetylserine sulfhydrylase, is presented and discussed as representative of other PLP‐dependent enzymes we have investigated. Finally, perspectives of PLP‐dependent enzymes functional genomics and drug targeting highlight the continuous novelty of an “old” class of enzymes. © 2006 The Japan Chemical Journal Forum and Wiley Periodicals, Inc. Chem Rec 6: 275–287; 2006: Published online in Wiley InterScience (www.interscience.wiley.com) DOI 10.1002/tcr.20094
Heating and melting deformable models
Authors: Terzopoulos Demetri , Platt John , Fleischer Kurt 
Published: November 2006

AbstractWe develop physically‐based graphics models of non‐rigid objects capable of heat conduction, thermoelasticity, melting and fluid‐like behaviour in the molten state. These deformable models feature non‐rigid dynamics governed by Lagrangian equations of motion and conductive heat transfer governed by the heat equation for non‐homogeneous, non‐isotropic media. In its solid state, the discretized model is an assembly of hexahedral finite elements in which thermoelastic units interconnect particles situated in a lattice. The stiffness of a thermoelastic unit decreases as its temperature increases, and the unit fuses when its temperature exceeds the melting point. The molten state of the model involves a molecular dynamics simulation in which ‘fluid’ particles that have broken free from the lattice interact through long‐range attraction forces and short‐range repulsion forces. We present a physically‐based animation of a thermoelastic model in a simulated physical world populated by hot constraint surfaces.
Rendering hair using pixel blending and shadow buffers
Authors: Leblanc André M. , Turner Russell , Thalmann Daniel 
Published: November 2006

AbstractA technique is described for adding natural‐looking hair to standard rendering algorithms. Using an explicit hair model, in which each individual hair is represented by a three‐dimensional curve, the technique uses pixel blending combined with Z‐buffer and shadow buffer information from the scene to yield a final anti‐aliased image with soft shadows. Although developed for rendering human hair, this technique can also be used to render any model consisting of long filaments of sub‐pixel width. The technique can be adapted to any rendering method that outputs Z‐buffer and shadow buffer information and is amenable to hardware implementation.
Interference detection through rasterization
Authors: Shinya Mikio , Forgue Marie‐Claire 
Published: November 2006

AbstractInterference detection is a useful technique, but it is also generally time‐consuming. In this paper, a new type of interference detection algorithm is proposed for real‐time interference detection. The algorithm first rasterizes the projection of the target objects and calculates the z‐values, just as done by the z‐buffer visible surface algorithm. For interference detection, all z‐values and pointers to the corresponding faces of objects are saved in a z‐list for each pixel. Sorting the z‐list against the z‐values allows the detection of overlapping objects in the z‐direction at each pixel position and, thus, finds interfering faces by referring to the face pointers in the z‐list.The algorithm is simple and easy to implement. Its computational complexity is directly proportional to the number of polygons, and, in addition, standard graphics hardware can be used to greatly accelerate execution. Another advantage is that the algorithm can be applied to all ‘ray‐traceable’ objects, including algebraic surfaces, and procedurally defined objects; traditionally these were not suitable subjects for interference detection.The algorithm is implemented on a graphics workstation using a standard graphics library. Interference detection at a practical interaction speed is achieved for complicated objects such as polyhedra with thousands of polygons. The algorithm can be used in two ways: for inexpensive interference detection, and as an efficient culling method for more precise collision/interference detection algorithms.
Volume seeds: A volume exploration technique
Authors: Ma Kwan‐Liu , Cohen Michael F. , Painter James S. 
Published: November 2006

AbstractRay‐traced volume rendering has been shown to be an effective method for visualizing 3D scalar data. However, with currently available workstation technology, interactive volume exploration using conventional volume rendering is still too slow to be attractive. This paper describes an enhanced volume rendering method which allows interactive changes of rendering parameters such as colour and opacity maps. An innovative technique is provided which allows the user to plant a ‘seed’ in the volume to rapidly modify local shading parameters. For a fixed viewing position, the user can interactively explore specific regions of interest. Furthermore, a virtual cutting technique with the exploratory seed allows the user to remove surfaces and see the internal structure of the volume. Examples demonstrate these techniques as an attractive option in many applications.
Choreographed image flow
Authors: Sims Karl 
Published: November 2006

AbstractChoreographed fluid‐like motions have been created and used to animate two dimensional images. Techniques are presented for generating these animations by repeatedly warping images using vector field representations of arbitrary flowing motions. Tools that allow interactively creating and aligning vector flow‐fields with images are also described. These methods lend themselves well to highly parallel computation, and have been implemented using the Connection Machine System.
Hanging cloths and dangling rods: A unified approach to constraints in computer animation
Authors: van Overveld C. W. A. M. , van Loon Erik 
Published: November 2006

AbstractA simple unified approach for dealing with constraints on real‐valued parameters in computer simulations and computer animation is described. The main characteristics of the approach are its flexibility (it works for a variety of constraint‐types and it can be implemented to handle both under‐ and over‐constrained systems in a stable way) and its ease for distributed computation. The method is based on the idea of genetic algorithms. The mathematical merits of the method for one constraint‐type are discussed in some detail and some examples of applications are given.
Shape transformation by boundary representation interpolation: A recursive approach to establishing face correspondences
Authors: Parent Richard E. 
Published: November 2006

AbstractThe issues relating to the shape transformation problem are discussed and a new algorithm is presented for computing the transformation of one shape into another. In this algorithm, the boundary definitions of the two initial shapes are used and a mapping is established between the vertices and edges of the respective objects. New vertices and edges are introduced into the object definitions when necessary to establish a one‐to‐one vertex correspondence and to match connectivity relationships between vertices. These can then be used to do a vertex‐to‐vertex interpolation that maintains valid polyhedral topologies for all of the intermediate shapes. The algorithm establishes a mapping between areas of the object such that adjacency relationships are preserved. These areas are recursively subdivided so that adjacency relationships of subareas are also preserved. During subdivision, vertices and edges are added to the boundaries of subareas so that a one‐to‐one mapping is established between them. Subdivision continues until each subarea consists of a single face. The algorithm presented works for objects that are topologically equivalent to spheres and can easily be extended to other pairs of objects as long as they are topologically equivalent to each other.
NPSNET: Real‐time collision detection and response
Authors: Zyda Michael J. , Pratt David R. , Osborne William D. , Monahan James G. 
Published: November 2006

AbstractThe Graphics and Video Laboratory of the Naval Postgraduate School (NPS) is in the process of constructing a three dimensional (3D) virtual world called NPSNET.1 NPSNET is a low‐cost, commercial workstation‐based 3D visual simulator that uses SIMNET terrain databases and networking.2 NPSNET is programmed using off‐the‐shelf SGI IRIS graphics workstations, rather than the platform‐specific nodes of SIMNET. Part of the work in constructing the NPSNET world is detecting and resolving collisions in real‐time. Such collision detection and resolution has been accomplished and integrated into the latest version of NPSNET, NPSNET‐2. The detection of vehicle‐weapon, vehicle‐vehicle and vehicle‐stationary non‐vehicle collisions is performed throughout the virtual world.
The same origin ray set query for realistic illumination: Algorithm and analysis
Authors: Rappoport Ari 
Published: November 2006

AbstractThe same origin ray set (SORS) is a computational primitive which can be used by ray tracing, radiosity and multiple pass illumination simulation algorithms for realistic image synthesis. A SORS consists of a set of rays emanating from the same point in space. The SORS query computes the first object intersected by each ray and the intersection point. In this paper we present an efficient projection algorithm for computing a SORS query for polygonal scenes. The algorithm achieves its efficiency by separating ray‐polygon intersection detection from the computation of the intersection point between the ray and the polygon's plane. The algorithm can be integrated with all current illumination acceleration schemes. We analyse the projection algorithm and compare it to the alternative of computing the SORS query one ray at a time. The analysis' results are expressed in terms of a few intuitive parameters, measuring the success of the acceleration scheme in culling irrelevant objects and the concentration of the ray set. The projection algorithm can be up to five times more efficient, depending on these parameters and the quality of the image. The relative advantage of the projection increases with image quality.