bluuebunny/crossref_metadata_2025 huggingface dataset:
Analysis and applications of Priest's distillation
Authors: Nievergelt Yves
Published: January 2005

Correcting an infinite loop in Douglas M. Priest's renormalization algorithm, the theory proved here supports streamlined algorithms to resolve the tablemaker's dilemma for the floating-point computation of real and complex sums and dot-products, properly rounded to the ultimate digit. Applications include computations of areas, volumes, and intersections.
BACOL
Authors: Wang R. , Keast P. , Muir P.
Published: January 2005

BACOL is a new, high quality, robust software package in Fortran 77 for solving one-dimensional parabolic PDEs, which has been shown to be significantly more efficient than any other widely available software package of the same class (to our knowledge), especially for problems with solutions exhibiting rapid spatial variation. A novel feature of this package is that it employs high order, adaptive methods in both time and space, controlling and balancing both spatial and temporal error estimates. The software implements a spline collocation method at Gaussian points, with a B-spline basis, for the spatial discretization. The time integration is performed using a modification of the popular DAE solver, DASSL. Based on the computation of a second, higher order, global solution, a high quality
a posteriori
spatial error estimate is obtained after each successful time step. The spatial error is controlled by a sophisticated new mesh selection algorithm based on an equidistribution principle. In this article we describe the overall structure of the BACOL package, and in particular the modifications to the DASSL package that improve its performance within BACOL. An example is provided in the online Appendix to illustrate the use of the package.
Algorithms
Authors: Waters Richard C.
Published: January 2005

It is my intention to publish two different kinds of algorithms articles: articles that present utilities built on top of Common Lisp and articles that discuss and explain interesting parts of Common Lisp. The following article is an example of the latter type. It shows how to take advantage of some of the advanced features of the pretty printing facilities that have been adopted as part of the forthcoming draft Common Lisp standard.
A routing scheme for integrated networks
Authors: Sheedy Chris
Published: January 2005

A routing scheme using delay, bandwidth and reliability measures is presented, and flow control is partially included in the method. Decisions are distributed, and the routing tables at each node contain lists of non-dominated best paths to all other nodes. Two algorithms are presented for constructing the tables, and simulation results show that their overheads are comparable to those of existing algorithms. The routing scheme is suitable for integrated packet switched and circuit switched computer networks.
Verification of flow control protocols
Authors: Hansen Klaus
Published: January 2005

An important issue in computer network design is end-to-end control, a term covering error control and flow control. The validity of schemes for these purposes may be demonstrated using simple formal models, in which assertions about central program variables are proven. S. Krogdahl [2] and D. E. Knuth [1] have shown the validity of error control for a class of data link protocols using such methods. In this paper their method is extended to cover flow control. The method is illustrated by proving assertions for a simple case, and it is shown how complex systems may be seen as compositions of the simple case.
Format based data compression
Authors: Lyons Norman R.
Published: January 2005

One way to increase the amount of information that can be stored on data storage devices is to develop techniques for reducing redundancy in the data. The obvious first approach is the development of variable length records that repeat the fields for tables and array only as many times as required. This approach helps considerably, but the problem of redundancy in the fields that make up the record still remains. In most computer systems, the fields in a record are assumed to be fixed length, padded on the right with blanks if they are alphanumeric, and padded on the left with zeros if they are numeric. This approach can be wasteful of storage space since field lengths are usually set so they can accommodate even the longest of the data items that will be placed in the field. For fields holding data like an individual's last name, this usually means setting aside about 20 or 25 character positions even though most last names are considerably shorter.
Review of "Database Processing Fundamentals, Modelling, Applications by David Kroenke"; Science Research Association, Inc., 1977
Authors: Benbasat Izak , Goldstein Robert C.
Published: January 2005

Database Processing
is an introductory level book on data base systems written in a clear, easily understood style. It contains a large number of diagrams and flowcharts which are well-integrated with the text and help to clarify some of the complex ideas that are presented. The book is divided into four major sections, following an introductory chapter on the advantages and disadvantages of the data base approach and its relation to earlier methods of file handling.
Some structured analysis techniques
Authors: Chapin Ned
Published: January 2005

Structured analysis advocates have recommended different graphic aids as the foundation technique. Ross has advocated the actigram and datagram (12). DeMarco and Rose have advocated the data flow diagram (DFD) or bubble chart as it is also known (8, 11). Gane and Sarson have advocated a graphic technique they also call the DFD (9).
Review of "Humanized Input, by T. Gilb and G. M. Weinberg", Winthrop Publishers, Inc., 1977
Authors: Barkin Stephen R.
Published: January 2005

Certainly a problem area of business data processing is the control of input. We have seen, however, few publications directed at this error-prone topic. Glib and Weinberg have given us the first volume I have seen solely concerned with input design and control. On its plus side, the book presents in handbook form chapters on default messages, positional messages, checkwords, checking and variance. I found these chapters to make good sense and provide many useful techniques to exercise over input.
User experience
Authors: Sampson Fred
Published: January 2005

"Pushing the Envelope" previews a special topic to be covered in an upcoming issue of <
interactions
>. We hope it piques your interest and encourages you to contribute! The theme discussed here will be published in the May-June issue. The deadline for contributing is February 7, 2005. For more information, contact eic@interactions.acm.org.
Ease your design anguish
Authors: Gill-Hesselgrave Deborah , Hall Mark
Published: January 2005

Do you yearn for more involvement in design but find yourself limited to evaluating interfaces produced by others? Maybe the problem is how you see your role. Deborah Gill-Hesselgrave and Mark Hall give us suggestions for examining some "false truths" we may hold about our work, and for overcoming obstacles to contributing at a higher level.---
Elizabeth Buie
User-centered design in the enterprise
Authors: Marcus Aaron
Published: January 2005

While some major corporations are now establishing centers of excellence for UCD, other organizations treat it is as a relative unknown---one which still requires careful nurturing.
The need for a programming discipline to support the APSE
Authors: Druffel Larry E.
Published: January 2005

Many of us recognize that Ada® has tremendous potential as a common state-of-the-art high order language which provides features to support the software development process. We also recognize that pursuit of the Ada Programming Support Environment (APSE) will enable us to build tools to support such a software development process. However, we will not realize the full potential of Ada until we are able to define a software development methodology complete with management practices which can in turn be supported by automated tools.
An object-based virtual operating system for the Ada programming support environment
Authors: Taft S. Tucker
Published: January 2005

As part of a major effort to increase programmer productivity, the U.S. Department of Defense has supported the design of an Ada Programming Support Environment (APSE) based on the Pebbleman/Stoneman sequence of documents [4]. We have recently completed the first phase of this design, incorporating a standardized re-hostable virtual operating system and a retargetable Ada compiler with appropriate support tools. To support the coexistence on this system of many large and small software development projects, a sophisticated centralized database has been proposed that incorporates the concepts of object-based architecture [5] as well as more conventional hierarchical file systems [1].
USIM
Authors: Mooney James D.
Published: January 2005

This paper proposes a control mechanism for the user interface. This mechanism provides two principal services of frequent importance in interactive systems: management of alternate file input, and log files. The mechanism is independent of the command language interpreter and thus its services are available to all programs.
On proof rules for monitors
Authors: Adams J. M. , Black A. P.
Published: January 2005

An inadequacy is pointed out in the original proof rules for monitors and in later extended rules. This inadequacy gives rise to an anomaly in proving the invariant for a monitor simulating a counting semaphore. New proof rules are proposed and used to give a sound proof of the invariant.
Problems in supporting data base transactions in an operating system transaction manager
Authors: Stonebraker Michael , DuBourdieux Deborah , Edwards William
Published: January 2005

This paper reports on the experience of the authors in attempting to support data base transactions on top of an existing operating system transaction manager. It will be seen that significant modifications to both the example data base system and the example operating system are required to support the concept. The conclusion to be drawn is that operating system transaction managers will have to be designed more generally than is now suggested and that application programs (such as data base systems) will have to participate in the transaction management process.
On improvements to password security
Authors: Singh Kamaljit
Published: January 2005

Due to the increasing value of information being stored in computers, it is important that unforgeable user authentication policies are implemented. Existing password authentication schemes, threats and counter-measures are described. A solution to eavesdropping problems using public-key cryptography is proposed. A technique to allow long password-phrases that makes an exhaustive search impracticable is presented.
Beyond the ballot box
Authors: Medina Eden Miller
Published: January 2005

On 2 November 2004, millions of Americans went to the polls and cast their vote for the person they felt would best determine the future of America. Young people constituted a crucial part of the deciding vote and many organizations from MTV to the presidential campaigns made considerable efforts to increase the political awareness and involvement of this demographic category, typically characterized as the 18--24 year-old voter. This attentiveness to youth participation in national politics, albeit commendable, should not begin and end on Election Day. All citizens have a responsibility to remain informed of government actions and to express their approval or disapproval though public elections, communication with their elected representatives, or participation in any number of public forums or community organizations. However, readers of this magazine have a particualr responsibility as educators of the future generation of computer and technologically literate citizens.
Outgoing links
Authors: McCauley Renée
Published: January 2005

As all good things come to an end, we have reached the final Links column. About ten years ago (circa early 1994), we as educators were scrambling to install and learn to use the tools available for accessing the vast new information resource - the internet. There was already a lot of information out there accessible via rather esoteric tools like "archie" and "gopher." Those early Internet "scouts" ("Internet surfing" was not yet accepted, as the Internet "wave" had not emerged yet) had to work hard to find useful resources Then, suddenly, there came HTML and Mosaic, which provided access to all types of hypermedia information, and made things so much more exciting. [1] Being able to see graphics juxtaposed with text coming from computers far, far away was revolutionary. It revolutionized the way we shared information with others. (Granted, the ease through which information was shared, lowered the average quality of the material available. But still, more and more useful material became easier and easier to access.)
Penny piles
Authors: Henderson Peter B.
Published: January 2005

Given ten pennies, how many different ways can you create piles on a table, or stacks, with them? Two obvious answers at each end of the spectrum are one pile of ten pennies and ten piles of one penny. When given a problem, students should learn to look for the obvious and simple first, even if this entails simplifying the problem to get started or better understand it. Indeed, getting started is frequently an impediment for many students. Engage yourself, do something, anything!
The practicum in computer science education
Authors: Hazzan Orit , Lapidot Tami
Published: January 2005

This article focuses on the practicum, one of the more important parts of computer science teacher preparation. During this stage, the prospective teachers practice the teaching of computer science in a high school setting before becoming actual computer science teachers. The practicum is highlighted in this article from three angles: the prospective teacher's perspective, the MTCS course perspective and the university mentor's perspective. For each perspective we illustrate the importance of the practicum by explaining how it bridges a specific gap. These gaps are illustrated by two examples that focus on content and pedagogical aspects of computer science education.
Searching the web to develop inquiry and collaborative skills
Authors: Hamelin Denis
Published: January 2005

Learning how to search for information on the Web is a process both of technique and intuition. Although the former can be taught, the latter must be experienced. The exercise called the treasure hunt consisted of questions that were to be answered using the Web search engines. Questions were on geography, popular culture, art, history, science, technology and current events. This exercise aimed to help students to develop their own investigating senses while assimilating computer techniques and acquiring general knowledge. This paper presents the results of an experiment that used an assignment involving collaborative and inquiry processes to acquire efficient heuristics to search the Web.
Interacting factors that predict success and failure in a CS1 course
Authors: Rountree Nathan , Rountree Janet , Robins Anthony , Hannah Robert
Published: January 2005

The factors that contribute to success and failure in introductory programming courses continue to be a topic of lively debate, with recent conference panels and papers devoted to the subject (e.g. Rountree et al. 2004, Ventura et al., 2004, Gal-Ezer et al., 2003). Most work in this area has concentrated on the ability of single factors (e.g. gender, math background, etc.) to predict success, with the exception of Wilson et al. (2001), which used a general linear model to gauge the effect of combined factors. In Rountree et al. (2002) we presented the results of a survey of our introductory programming class that considered factors (such as student expectations of success, among other things) in isolation. In this paper, we reassess the data from that survey by using a decision tree classifier to identify combinations of factors that interact to predict success or failure more strongly than single, isolated factors.
Making embedded software reuse practical and safe
Authors: Leveson Nancy G. , Weiss Kathryn Anne
Published: January 2005

Reuse of application software has been limited and sometimes has led to accidents. This paper suggests some requirements for successful and safe application software reuse and demonstrates them using a case study on a real spacecraft.
Efficient incremental algorithms for dynamic detection of likely invariants
Authors: Perkins Jeff H. , Ernst Michael D.
Published: January 2005

Dynamic detection of likely invariants is a program analysis that generalizes over observed values to hypothesize program properties. The reported program properties are a set of likely invariants over the program, also known as an operational abstraction. Operational abstractions are useful in testing, verification, bug detection, refactoring, comparing behavior, and many other tasks.

Previous techniques for dynamic invariant detection scale poorly or report too few properties. Incremental algorithms are attractive because they process each observed value only once and thus scale well with data sizes. Previous incremental algorithms only checked and reported a small number of properties. This paper takes steps toward correcting this problem. The paper presents two new incremental algorithms for invariant detection and compares them analytically and experimentally to two existing algorithms. Furthermore, the paper presents four optimizations and shows how to implement them in the context of incremental algorithms. The result is more scalable invariant detection that does not sacrifice functionality.
System architecture
Authors: Uchitel Sebastian , Chatley Robert , Kramer Jeff , Magee Jeff
Published: January 2005

Constructing rigorous models for analysing the behaviour of concurrent and distributed systems is a complex task. Our aim is to facilitate model construction. Scenarios provide simple, intuitive, example based descriptions of the behaviour of component instances in the context of a simplified architecture instance. The specific architecture instance is generally chosen to provide sufficient context to indicate the expected behaviour of particular instances of component types to be used in the real system. Existing synthesis techniques provide mechanisms for building behaviour models for these simplified and specific architectural settings. However, the behaviour models required are those for the full generality of the system architecture, and not the simplified architecture used for scenarios. In this paper we exploit architectural information in the context of behaviour model synthesis from scenarios. Software architecture descriptions give the necessary contextual information so that component instance behaviour can be generalised to component type behaviour. Furthermore, architecture description languages can be used to describe the complex architectures in which the generalised behaviours need to be instantiated. Thus, architectural information used in conjunction with scenario-based model synthesis can support both model construction and elaboration, where the behaviour derived from simple architecture fragments can be instantiated in more complex ones.
PSE
Authors: Manevich Roman , Sridharan Manu , Adams Stephen , Das Manuvir , Yang Zhe
Published: January 2005

In this paper, we describe PSE (Postmortem Symbolic Evaluation), a static analysis algorithm that can be used by programmers to diagnose software failures. The algorithm requires minimal information about a failure, namely its kind (e.g. NULL dereference), and its location in the program's source code. It produces a set of execution traces along which the program can be driven to the given failure.

PSE tracks the flow of a single value of interest from the point in the program where the failure occurred back to the points in the program where the value may have originated. The algorithm combines a novel dataflow analysis and memory alias analysis in a manner that allows for precise exploration of the program's behavior in polynomial time.

We have applied PSE to the problem of diagnosing potential NULL-dereference errors in a suite of C programs, including several SPEC benchmarks and a large commercial operating system. In most cases, the analysis is able to either validate a pointer dereference, or find precise error traces demonstrating a NULL value for the pointer, in less than a second.
Engineering human trust in mobile system collaborations
Authors: Capra Licia
Published: January 2005

Rapid advances in wireless networking technologies have enabled mobile devices to be connected anywhere and anytime. While roaming, applications on these devices dynamically discover hosts and services with whom interactions can be started. However, the fear of exposure to risky transactions with potentially unknown entities may seriously hinder collaboration. To minimise this risk, an engineering approach to the development of trust-based collaborations is necessary. This paper introduces hTrust, a human trust management model and framework that facilitates the construction of trust-aware mobile systems and applications. In particular, hTrust supports: reasoning about trust (trust formation), dissemination of trust information in the network (trust dissemination), and derivation of new trust relationships from previously formed ones (trust evolution). The framework views each mobile host as a self-contained unit, carrying along a portfolio of credentials that are used to prove its trustworthiness to other hosts in an ad-hoc mobile environment. Customising functions are defined to capture the natural disposition to trust of the user of the device inside our trust management framework.
Implementing protocols via declarative event patterns
Authors: Walker Robert J. , Viggers Kevin
Published: January 2005

This paper introduces declarative event patterns (DEPs) as a means to implement protocols while improving their traceability, comprehensibility, and maintainability. DEPs are descriptions of sequences of events in the execution of a system that include the ability to recognize properly nested event structures. DEPs allow a developer to describe a protocol at a high-level, without the need to express extraneous details. A developer can indicate that specific actions be taken when a given pattern occurs. DEPs are automatically translated into the appropriate instrumentation and automaton for recognizing a given pattern. Support for DEPs has been implemented in a proof-of-concept extension to the AspectJ language that is based on advanced compiler technology. A case study is described that compares the use of DEPs in the implementation of a protocol (FTP user authentication) to the use of a set of other approaches, both object-oriented and aspect-oriented.
A type system for object models
Authors: Edwards Jonathan , Jackson Daniel , Torlak Emina
Published: January 2005

A type system for object models is described that supports subtyping, unions, and overloading of relation names. No special features need be added to the modelling language; in particular, there are no casts, and the meaning of an object model can be understood without mentioning types. A type error is associated with an expression that can be proved to be _irrelevant_, in the sense that it can be replaced by an empty set or relation without affecting the value of its enclosing constraint. Relevance is computed by a simple abstract interpretation.
Relevancy based semantic interoperation of reuse repositories
Authors: Pan Ying , Wang Lei , Zhang Lu , Xie Bing , Yang Fuqing
Published: January 2005

Software reuse is a promising solution to the software crisis. Reuse repositories are the basic infrastructure for software reuse. During the past decade, various academic, commercial, governmental, and industrial organizations have developed many Internet-enabled reuse repositories to provide access to software components and related resources. It has necessitated semantic interoperation to allow distributed maintenance and management of these repositories while enabling users to efficiently and conveniently access resources from multiple reuse repositories via a single representation view. In this paper, we have proposed an approach to enhancing the semantic interoperability of reuse repositories, called the improved relevancy matching and ranking (IRMR) method, based on analyzing the correlation of terms in representation methods of the repositories. A prototype system, the Virtual Repository supporting Semantic Interoperation (VRSI), is presented to illustrate the application of this approach to support the semantic interoperation of reuse repositories. Experimental results on real world reuse repositories demonstrated significant improvement in terms of searching effectiveness.
How a good software practice thwarts collaboration
Authors: de Souza Cleidson R. B. , Redmiles David , Cheng Li-Te , Millen David , Patterson John
Published: January 2005

The principle of information hiding has been very influential in software engineering since its inception in 1972. This principle prescribes that software modules hide implementation details from other modules in order to decrease their interdependencies. This separation also decreases the dependency among software developers implementing modules, thus simplifying some aspects of collaboration. A common instantiation of this principle is in the form of application programming interfaces (APIs). We performed a qualitative study on how practitioners use APIs in their daily work. Although particularly interested in aspects of collaboration, we report all findings about their observed use. The findings include mundane observations that are predicted by theory, ways that APIs support collaborative software development. But the findings also include some surprises, ways that APIs hinder collaboration. The surprises indicate directions for further improvement of collaborative software development practices and tools.
Using an SQL coverage measurement for testing database applications
Authors: Suárez-Cabal María José , Tuya Javier
Published: January 2005

Many software applications have a component based on database management systems in which information is generally handled through SQL queries embedded in the application code. When automation of software testing is mentioned in the research, this is normally associated with programs written in imperative and structured languages. However, the problem of automated software testing applied to programs that manage databases using SQL is still an open issue. This paper presents a measurement of the coverage of SQL queries and the tool that automates it. We also show how database test data may be revised and changed using this measurement by means of completing or deleting information to achieve the highest possible value of coverage of queries that have access to the database.
Empirical evaluation of defect projection models for widely-deployed production software systems
Authors: Li Paul Luo , Shaw Mary , Herbsleb Jim , Ray Bonnie , Santhanam P.
Published: January 2005

Defect-occurrence projection is necessary for the development of methods to mitigate the risks of software defect occurrences. In this paper, we examine user-reported software defect-occurrence patterns across twenty-two releases of four widely-deployed, business-critical, production, software systems: a commercial operating system, a commercial middleware system, an open source operating system (OpenBSD), and an open source middleware system (Tomcat). We evaluate the suitability of common defect-occurrence models by first assessing the match between characteristics of widely-deployed production software systems and model structures. We then evaluate how well the models fit real world data. We find that the Weibull model is flexible enough to capture defect-occurrence behavior across a wide range of systems. It provides the best model fit in 16 out of the 22 releases. We then evaluate the ability of the moving averages and the exponential smoothing methods to extrapolate Weibull model parameters using fitted model parameters from historical releases. Our results show that in 50% of our forecasting experiments, these two naive parameter-extrapolation methods produce projections that are worse than the projection from using the same model parameters as the most recent release. These findings establish the need for further research on parameter-extrapolation methods that take into account variations in characteristics of widely-deployed, production, software systems across multiple releases.
A classification of symbolic transition systems
Authors: Henzinger Thomas A. , Majumdar Rupak , Raskin Jean-François
Published: January 2005

We define five increasingly comprehensive classes of infinite-state systems, called STS1--STS5, whose state spaces have finitary structure. For four of these classes, we provide examples from hybrid systems.STS1 These are the systems with finite
bisimilarity
quotients. They can be analyzed symbolically by iteratively applying predecessor and Boolean operations on state sets, starting from a finite number of observable state sets. Any such iteration is guaranteed to terminate in that only a finite number of state sets can be generated. This enables model checking of the μ-calculus.STS2 These are the systems with finite
similarity
quotients. They can be analyzed symbolically by iterating the predecessor and positive Boolean operations. This enables model checking of the existential and universal fragments of the μ-calculus.STS3 These are the systems with finite
trace-equivalence
quotients. They can be analyzed symbolically by iterating the predecessor operation and a restricted form of positive Boolean operations (intersection is restricted to intersection with observables). This enables model checking of all ω-regular properties, including linear temporal logic.STS4 These are the systems with finite
distance-equivalence
quotients (two states are equivalent if for every distance
d
, the same observables can be reached in
d
transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new state sets are generated. This enables model checking of the existential conjunction-free and universal disjunction-free fragments of the μ-calculus.STS5 These are the systems with finite
bounded-reachability
quotients (two states are equivalent if for every distance
d
, the same observables can be reached in
d
or fewer transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new states are encountered (this is a weaker termination condition than above). This enables model checking of reachability properties.
Making abstract domains condensing
Authors: Giacobazzi Roberto , Ranzato Francesco , Scozzari Francesca
Published: January 2005

In this article, we show that reversible analyses of logic languages by abstract interpretation can be performed without loss of precision by systematically refining abstract domains. This is obtained by adding to the abstract domain the minimal amount of concrete semantic information so that this refined abstract domain becomes rich enough to allow goal-driven and goal-independent analyses agree. These domains are known as condensing abstract domains. Essentially, an abstract domain
A
is condensing when the goal-driven analysis performed on
A
for a program
P
and a given query can be retrieved with no loss of precision from the goal-independent analysis on
A
of
P
. We show that condensation is an abstract domain property and that the problem of making an abstract domain condensing boils down to the problem of making the corresponding abstract interpretation complete, in a weakened form, with respect to unification. In the case of abstract domains for logic program analysis approximating computed answer substitutions, we provide a clean logical characterization of condensing domains as fragments of propositional linear logic. We apply our methodology to the systematic design of condensing domains for freeness and independence analysis.
Incremental validation of XML documents
Authors: Balmin Andrey , Papakonstantinou Yannis , Vianu Victor
Published: January 2005

We investigate the incremental validation of XML documents with respect to DTDs, specialized DTDs, and XML Schemas, under updates consisting of element tag renamings, insertions, and deletions. DTDs are modeled as extended context-free grammars. "Specialized DTDs" allow the decoupling of element types from element tags. XML Schemas are abstracted as specialized DTDs with limitations on the type assignment. For DTDs and XML Schemas, we exhibit an
O
(
m
log
n
) incremental validation algorithm using an auxiliary structure of size
O
(
n
), where
n
is the size of the document and
m
the number of updates. The algorithm does not handle the incremental validation of XML Schema wrt renaming of internal nodes, which is handled by the specialized DTDs incremental validation algorithm. For specialized DTDs, we provide an
O
(
m
log
2
n
) incremental algorithm, again using an auxiliary structure of size
O
(
n
). This is a significant improvement over brute-force re-validation from scratch.We exhibit a restricted class of DTDs called
local
that arise commonly in practice and for which incremental validation can be done in practically constant time by maintaining only a list of counters. We present implementations of both general incremental validation and local validation on an XML database built on top of a relational database.Our experimentation includes a study of the applicability of local validation in practice, results on the calibration of parameters of the auxiliary data structure, and results on the performance comparison between the general incremental validation technique, the local validation technique, and brute-force validation from scratch.
Google
Authors: Cusumano Michael A.
Published: January 2005

Searching for the most successful combination of usefulness, expansiveness, and sustainability.
E-government usability for older adults
Authors: Becker Shirley Ann
Published: January 2005

It is imperative that online government services appreciate the navigational needs of an ever-growing segment of their constituency.
A scheduling algorithm for optimization and early planning in high-level synthesis
Authors: Memik Seda Ogrenci , Kastner Ryan , Bozorgzadeh Elaheh , Sarrafzadeh Majid
Published: January 2005

Complexities of applications implemented on embedded and programmable systems grow with the advances in capacities and capabilities of these systems. Mapping applications onto them manually is becoming a very tedious task. This draws attention to using high-level synthesis within design flows. Meanwhile, it is essential to provide a flexible formulation of optimization objectives as well as to perform efficient planning for various design objectives early on in the design flow. In this work, we address these issues in the context of data flow graph (DFG) scheduling, which is an essential element within the high-level synthesis flow. We present an algorithm that schedules a chain of operations with data dependencies among consecutive operations at a single step. This local problem is repeated to generate the schedule for the whole DFG. The local problem is formulated as a maximum weight noncrossing bipartite matching. We use a technique from the computational geometry domain to solve the matching problem. This technique provides a theoretical guarantee on the solution quality for scheduling a single chain of operations. Although still being local, this provides a relatively wider perspective on the global scheduling objectives. In our experiments we compared the latencies obtained using our algorithm with the optimal latencies given by the exact solution to the integer linear programming (ILP) formulation of the problem. In 9 out of 14 DFGs tested, our algorithm found the optimal solution, while generating latencies comparable to the optimal solution in the remaining five benchmarks. The formulation of the objective function in our algorithm provides flexibility to incorporate different optimization goals. We present examples of how to exploit the versatility of our algorithm with specific examples of objective functions and experimental results on the ability of our algorithm to capture these objectives efficiently in the final schedules.
A 4-geometry maze router and its application on multiterminal nets
Authors: Jan Gene Eu , Chang Ki-Yin , Gao Su , Parberry Ian
Published: January 2005

The maze routing problem is to find an optimal path between a given pair of cells on a grid plane. Lee's algorithm and its variants, probably the most widely used maze routing method, fails to work in the 4-geometry of the grid plane. Our algorithm solves this problem by using a suitable data structure for uniform wave propagation in the 4-geometry, 8-geometry, etc. The algorithm guarantees finding an optimal path if it exists and has linear time and space complexities. Next, to solve the obstacle-avoiding rectilinear and 4-geometry Steiner tree problems, a heuristic algorithm is presented. The algorithm utilizes a cost accumulation scheme based on the maze router to determine the Torricelli vertices (points) for improving the quality of multiterminal nets. Our experimental results show that the algorithm works well in practice. Furthermore, using the 4-geometry router, path lengths can be significantly reduced up to 12% compared to those in the rectilinear router.
A unified method for phase shifter computation
Authors: Kagaris Dimitri
Published: January 2005

Phase shifters are used to shift the bit sequences produced by the successive stages of a built-in test pattern generator (TPG) based on a linear finite state machine (LFSM) by a specified amount (
phase shift
) relative to the characteristic sequence. An upper bound on the number of taps to be used for each phase shifter and a lower bound on the phase-shift value between successive stages of the TPG mechanism are the general parameters of the problem. Methods to design such phase shifters have been given in the past separately for Type-1 LFSRs, Type-2 LFSRs, and three-neighborhood cellular automata. In this article, we show how phase shifters can be synthesized uniformly and efficiently for any LFSM, including the aforementioned ones. We demonstrate the method by showing how to obtain phase shifters for two-dimensional cellular automata and for ring generators.
An efficient algorithm for finding the minimal-area FPGA technology mapping
Authors: Kao Chi-Chou , Lai Yen-Tai
Published: January 2005

Minimum area is one of the important objectives in technology mapping for lookup table-based field-progrmmable gate arrays (FPGAs). Although there is an algorithm that can find an optimal solution in polynomial time for the minimal-area FPGA technology mapping problem without gate duplication, its time complexity can grow exponentially with the number of inputs of the lookup-tables. This article proposes an algorithm with approximate to the area-optimal solution and lower time complexity. The time complexity of this algorithm is proven theoretically to be bounded by
O
(
n
3
), where
n
is the total number of gates in the given circuit. It is shown that except for some cases the proposed algorithm can find an optimal solution of a given problem. We have combined the proposed algorithm with the existing postprocessing procedures which are used to find the gates that can be duplicated on a set of benchmark examples. The experimental results demonstrate the effectiveness of our algorithm.
Implementation of a “Lisp comprehension” macro
Authors: Lapalme Guy
Published: January 2005

This paper describes a set of Lisp macros that enable the use of "list comprehensions" which are a very powerful notation that provides a very compact expression of common list operations see [2] for a full discussion. List comprehensions have been introduced by David Turner in KRC, where they were called ZF-expressions [7]. They have since been introduced in several other pure functional languages like SASL [8], Miranda
1
[5] and Haskell [3].
Implementation of an iteration macro
Authors: van Melle Bill
Published: January 2005

This article describes the implementation of a set of iteration macros. These macros are found in the Portable Common Loops (PCL) implementation of the Common Lisp Object System, though they are not dependent on PCL in any way. The macros were designed to be more functional than the small set of iteration macros found in Common Lisp (e.g., do), while still having a "Lisp-like" syntax that is easy to understand and extend. Pavel Curtis is responsible for the essential insights about program transformation that make feasible an efficient implementation of this conceptually simple iteration form. The implementation makes extensive use of the PCL code walker, which was described in the previous issue of
Lisp Pointers
.
The WINTERP Widget INTERPreter—a Lisp prototyping and extension environment for OSF/motif based applications user-interfaces
Authors: Mayer Niels P.
Published: January 2005

Winterp
is an interactive, language-based user-interface and application-construction environment enabling rapid prototyping of applications with graphical user interfaces based on the OSF/Motif UI Toolkit.
Winterp
also serves as a customization environment for delivered applications by providing a real programming language as an extension language. Many existing user-interface languages only have the expressive power to describe static layout of user interface forms; by using a high-level language for extensions and prototyping,
Winterp
also handles the dynamic aspects of UI presentation, e.g. the use of direct manipulation, browsers, and dialog.
Winterp
makes rapid prototyping possible because its language is based on an interpreter, thereby enabling interactive construction of application functionality and giving immediate feedback on incremental changes.
Winterp's
language is based on David Betz's public domain
Xlisp
interpreter which features a subset of Common Lisp's functionality. The language is extensible, permitting new Lisp primitives to be added in the C language and allowing hybrid implementations constructed from interpreted Lisp and compiled C. Hybrid implementation gives
Winterp
-based applications the successful extension and rapid-prototyping capabilities of Lisp-based environments, while delivering the multiprocessing perfor- mance of C applications running on personal
Unix
workstations.
UnicStep-a visual stepper for COMMON LISP
Authors: Haulsen Ivo , Sodan Angela
Published: January 2005

This article presents a visual stepper for Common Lisp with simple backup feature. The stepper is based on Lieberman's approach for visual stepping. The stepper operates at the source level of programs and uses the GNU Emacs editor for source code processing. Problems encountered on implementing this stepper are described: read-syntax, macroexpansion, and source-localization. Especially, language features are discussed which affected our goal to make this tool portable across Common Lisp systems.
Projective ML
Authors: Rémy Didier
Published: January 2005

We propose a projective lambda calculus as the basis for operations on records. Projections operate on elevations, that is, records with defaults. This calculus extends lambda calculus while keeping its essential properties. We build projective ML from this calculus by adding the ML Let typing rule to the simply typed projective calculus. We show that projective ML possesses the subject reduction property, which means that well-typed programs can be reduced safely. Elevations are practical data structures that can be compiled efficiently. Moreover, standard records are difinable in terms of projections.
Finiteness conditions for fixed point iteration
Authors: Nielson Flemming , Nielson Hanne Riis
Published: January 2005

This paper provides a link between the formulation of static program analyses using the framework of abstract interpretation (popular for functional languages and using the more classical framework of data flow anlysis (popular for imperative languages). In particular we show how the classical notions of fastness, rapidity and
k
-boundedness carry over to the abstract interpretation framework and how this may be used to bound the number of times a functional should be unfolded in order to yield the fixed point. This is supplemented with a number of results on how to calculate the bounds for iterative forms (as for tail recursion), for linear forms (as for one nested recursive call), and for primitive recursive forms. In some cases this improves the “worst case” results of, but more importantly it gives much better“average case” results.
Proving the correctness of storage representations
Authors: Wand Mitchell , Oliva Dino P.
Published: January 2005

Conventional techniques for semantics-directed compiler derivation yield abstract machines that manipulate trees. However, in order to produce a real compiler, one has to represent these trees in memory. In this paper we show how the technique of
storage-layout relations
can be applied to verify the correctness of storage representations in a very general way. This technique allows us to separate denotational from operational reasoning, so that each can be used when needed. As an example, we show the correctness of a stack implementation of a language including dynamic catch and throw. The representation uses static and dynamic links to thread the environment and continuation through the stack. We discuss other uses of these techniques.
A confluent calculus of Macro expansion and evaluation
Authors: Bove Ana , Arbilla Laura
Published: January 2005

Syntactic abbreviations or
macros
provide a powerful tool to increase the syntactic expressiveness of programming languages. The expansion of these abbreviations can be modeled with substitutions. This paper presents an operational semantics of macro expansions and evaluation where substitutions are handled explicitly. The semantics is defined in terms of a confluent, simple, and intuitive set of rewriting rules. The resulting semantics is also a basis for developing correct implementations.
Back to direct style II
Authors: Danvy Olivier , Lawall Julia L.
Published: January 2005

We continue to investigate the direct-style transformation by extending it to programs requiring
call-with-current-continuation
(a.k.a.
call/cc
). The direct style (DS) and the continuation-passing style (CPS) transformations form a Galois connection. This pair of functions has a place in the programmer's toolbox—yet we are not aware of the existence of any other DS transformer.

Starting from our DS transformer towards pure, call-by-value functional terms (Scheme), we extend it with a counting analysis to detect non-canonical occurrences of a continuation. The declaration of such a continuation is translated into a
call/cc
and its application into the application of the corresponding first-class continuation

We also present staged versions of the DS and of the CPS transformations, where administrative reductions are separated from the actual translation, and where the actual translations are carried out by local, structure-preserving rewriting rules. These staged transformations are used to prove the Galois continuation.

Together, the CPS and the DS transformations enlarge the class of programs that can be manipulated on a semantic basis. We illustrate this point with partial evaluation, by specializing a Scheme program with respect to a static part of its input. The program uses coroutines. This illustration achieves a first: a static coroutine is executed statically and its computational content is inlined in the residual program.