bluuebunny/crossref_metadata_2025 huggingface dataset:
Reading patterns and usability in visualizations of electronic documents
Authors: Hornbæk Kasper , Frøkjær Erik
Published: August 2003

We present an exploration of reading patterns and usability in visualizations of electronic documents. Twenty subjects wrote essays and answered questions about scientific documents using an overview+detail, a fisheye, and a linear interface. We study reading patterns by progression maps that visualize the progression of subjects' reading activity, and by visibility maps that show for how long different parts of the document are visible. The reading patterns help explain differences in usability between the interfaces and show how interfaces affect the way subjects read. With the overview+detail interface, subjects get higher grades for their essays. All but one of the subjects prefer this interface. With the fisheye interface, subjects use more time on gaining an overview of the document and less time on reading the details. Thus, they read the documents faster, but display lower incidental learning. We also show how subjects only briefly have visible the parts of the document that are not initially readable in the fisheye interface, even though they express a lack of trust in the algorithm underlying the fisheye interface. When answering questions, the overview is used for jumping directly to answers in the document and to already-visited parts of the document. However, subjects are slower at answering questions with the overview+detail interface. From the visualizations of the reading activity, we find that subjects using the overview+detail interface often explore the document further even when a satisfactory answer to the given question has already been read. Thus, overviews may grab subjects' attention and possibly distract them.
Typechecking XML views of relational databases
Authors: Alon Noga , Milo Tova , Neven Frank , Suciu Dan , Vianu Victor
Published: August 2003

Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the
typechecking
problem for transformations of relational data into tree data (XML). The problem consists of statically verifying that the output of every transformation belongs to a given output tree language (specified for XML by a DTD), for input databases satisfying given integrity constraints. The typechecking problem is parameterized by the class of formulas defining the transformation, the class of output tree languages, and the class of integrity constraints. While undecidable in its most general formulation, the typechecking problem has many special cases of practical interest that turn out to be decidable. The main contribution of this article is to trace a fairly tight boundary of decidability for typechecking in this framework. In the decidable cases we examine the complexity, and show lower and upper bounds. We also exhibit a practically appealing restriction for which typechecking is in PTIME.
Substructural logic and partial correctness
Authors: Kozen Dexter , Tiuryn Jerzy
Published: August 2003

We formulate a noncommutative sequent calculus for partial correctness that subsumes propositional Hoare Logic. Partial correctness assertions are represented by intuitionistic linear implication. We prove soundness and completeness over relational and trace models. As a corollary, we obtain a complete sequent calculus for inclusion and equivalence of regular expressions.
Topological incompleteness and order incompleteness of the lambda calculus
Authors: Salibra Antonino
Published: August 2003

A model of the untyped lambda calculus univocally induces a lambda theory (i.e., a congruence relation on λ-terms closed under α- and β-conversion) through the kernel congruence relation of the interpretation function. A semantics of lambda calculus is
(equationally) incomplete
if there exists a lambda theory that is not induced by any model in the semantics. In this article, we introduce a new technique to prove in a uniform way the incompleteness of all denotational semantics of lambda calculus that have been proposed so far, including the strongly stable one, whose incompleteness had been conjectured by Bastonero, Gouy and Berline. We apply this technique to prove the incompleteness of any semantics of lambda calculus given in terms of partially ordered models with a bottom element. This incompleteness removes the belief that partial orderings with a bottom element are intrinsic to models of the lambda calculus, and that the incompleteness of a semantics is only due to the richness of the structure of representable functions. Instead, the incompleteness is also due to the richness of the structure of lambda theories. Further results of the article are: (i) an incompleteness theorem for partially ordered models with finitely many connected components (= minimal upward and downward closed sets); (ii) an incompleteness theorem for topological models whose topology satisfies a suitable property of connectedness; (iii) a completeness theorem for topological models whose topology is non-trivial and metrizable.
Eliminating definitions and Skolem functions in first-order logic
Authors: Avigad Jeremy
Published: August 2003

From proofs in any classical first-order theory that proves the existence of at least two elements, one can eliminate definitions in polynomial time. From proofs in any classical first-order theory strong enough to code finite functions, including sequential theories, one can also eliminate Skolem functions in polynomial time.
A word-based approach for modeling and discovering temporal relations embedded in Chinese sentences
Authors: Li Wenjie , Wong Kam-Fai
Published: August 2003

Conventional information extraction systems cannot effectively mine temporal information. For example, users' queries on how one event is related to another in time could not be handled effectively. For this reason, it is important to capture and deduce temporal knowledge associated with the relevant events. It is generally acknowledged that information extraction cannot be isolated from natural language processing. As Chinese has no tenses, conventional means for finding temporal references based on verb forms no longer apply. In this article we present an approach for formulating and discovering temporal relations in Chinese. A set of rules is devised to map the combinational effects of the temporal indicators (also known as temporal markers, gathered from various grammatical categories) in a sentence to its corresponding temporal relation. To evaluate the proposed algorithm, experiments were conducted using a set of news reports and the results look promising. Problem discussions are also provided. Through this work, we hope to open up new doors for future research in Chinese temporal information extraction and processing.
Automatic corpus-based tone and break-index prediction using K-ToBI representation
Authors: Lee Jin-Seok , Kim Byeongchang , Lee Gary Geunbae
Published: August 2003

In this article we present a prosody generation architecture based on K-ToBI (Korean Tone and Break Index) representation. ToBI is a multitier representation system based on linguistic knowledge that transcribes events in an utterance. The TTS (Text-To-Speech) system, which adopts ToBI as an intermediate representation, is known to exhibit higher flexibility, modularity, and domain/task portability compared to the direct prosody generation TTS systems. However, for practical-level performance, the cost of corpus preparation is very expensive because the ToBI labeled corpus is constructed manually by many prosody experts, and normally requires large amounts of data for statistical prosody modeling. Unlike previous ToBI-based systems, this article proposes a new method, which transcribes the K-ToBI labels in Korean speech completely automatically. We develop automatic corpus-based K-ToBI labeling tools and prediction methods based on several lexico-syntactic linguistic features for decision-tree induction. We demonstrate the performance of F0 generation from automatically predicted K-ToBI labels, and confirm that the performance is reasonably comparable to state-of-the-art direct prosody generation methods and previous ToBI-based methods.
A comparison of Chinese document indexing strategies and retrieval models
Authors: Luk Robert W. P. , Kwok K. L.
Published: August 2003

With the advent of the Internet and intranets, substantial interest is being shown in Asian language information retrieval; especially in Chinese, which is a good example of an Asian ideographic language (other examples include Japanese and Korean). Since, in this type of language, spaces do not delimit words, an important issue is which index terms should be extracted from documents. This issue also has wider implications for indexing other languages such as agglutinating languages (e.g., Finnish and Turkish), archaic ideographic languages like Egyptian hieroglyphs, and other types of information such as data stored in genomic databases. Although comparisons of indexing strategies for Chinese documents have been made, almost all of them are based on a single retrieval model. This article compares the performance of various combinations of indexing strategies (i.e., character, word, short-word, bigram, and Pircs indexing) and retrieval models (i.e., vector space, 2-Poisson, logistic regression, and Pircs models). We determine which model (and its parameters) achieves the (near) best retrieval effectiveness without relevance feedback, and compare it with the open evaluations (i.e., TREC and NTCIR) for both long and title queries. In addition, we describe a more extensive investigation of retrieval efficiency. In particular, the storage cost of word indexing is only slightly more than character indexing, and bigram indexing is about double the storage cost of other indexing strategies. The retrieval time typically varies linearly with the number of unique terms in the query, which is supported by correlation values above 90%. The Pircs retrieval system achieves robust and good retrieval performance, but it appears to be the slowest method, whereas vector space models were not very effective in retrieval, but were able to respond quickly. For robust, near-best retrieval effectiveness, without considering storage overhead, the 2-Poisson model using bigram indexing appears to be a good compromise between retrieval effectiveness and efficiency for both long and title queries.
A language and character set determination method based on N-gram statistics
Authors: Suzuki Izumi , Mikami Yoshiki , Ohsato Ario , Chubachi Yoshihide
Published: August 2003

An N-gram-based language, script, and encoding scheme-detection method is introduced in this article. The method detects language, script, and encoding schemes using a target text document encoded by computer by checking how many byte sequences of the target match the byte sequences that can appear in the texts belonging to a language, script, and encoding scheme. This detection mechanism is different from conventional N-gram-based methods in that its threshold for any category is uniquely predetermined. The method was originally created for a survey of web pages conducted to find how many web pages are written in a particular language, script, and encoding scheme. The requirement is that the method must be able to respond to either "correct answer" or "unable to detect" where "unable to detect" includes "other than registered." There are some minor problems with this method, but its effectiveness as a language, script, and encoding scheme-detection method has been confirmed by experiments.
ROBOT interpreter
Authors: Carlisle Martin C. , Shomper Keith
Published: August 2003

The ROBOT Interpreter is an environment for running programs for the ROBOT computer. It is intended to be a companion teaching device. The ROBOT computer is a simple demonstration of the fetch/execute cycle useful for an introductory or computer literacy course. The ROBOT has simple movement and sensing commands (and a
go to
command to implement looping), which are stored in its thirty-two 8-bit memory locations.The ROBOT's environment (called a scene) is a square room from 1x1 to 11x11, possibly containing doors. The ROBOT initially begins somewhere inside the room facing in any direction. The interpreter allows for ROBOT programs and scenes to be loaded and saved.ROBOT Interpreter is freely distributed by the Department of Computer Science at the United States Air Force Academy as a service to the CS education community.
Ada/Mindstorms 2.0 user's guide and reference manual
Authors: Fagin Barry
Published: August 2003

Ada/Mindstorms 2.0 is an Ada interface to the Lego RCX "brick," included as part of the Lego Mindstorms™ Robotics Invention System. Programs are written with an Ada compiler, translated into Dave Baum's Not Quite C language (NQC), then recompiled and downloaded through the Mindstorms IR transmitter to the RCX.Ada/Mindstorms 2.0 is distributed with the USAFA AdaGIDE Windows Ada compiler. This document assumes that you have obtained and installed AdaGIDE. If you are using another Ada compiler, see Appendix B. We also assume a working knowledge of Ada. If you haven't used Ada before, we recommend learning the basics first before reading further. http://www.adahome.com/Discover/Introduction.html is a good place to start. We also assume a general familiarity with the Lego Mindstorms Robotics Invention System and the RCX.
Effective binary perspectives in algorithmic problem solving
Authors: Ginat David
Published: August 2003

The effectiveness of viewing, representing, and manipulating data via binary values is illustrated in the domain of algorithmic problem solving. A variety of illuminating binary aspects, regarded as
binary perspectives
, are displayed through four lively algorithmic challenges, some of which are two-player games. The illustrations demonstrate the benefits of invoking binary representation of numbers, binary complement, bit-by-bit processing, parity considerations, and the reduction of an integer task into a 0/1 task. The solutions to the challenges are presented gradually, encapsulating general algorithmic considerations and problem-solving methods, including invariant properties, stepwise refinement, processing by atomic components, auxiliary coloring, backward reasoning, and inductive generalization. Each of the illustrations is tied to a variety of referenced algorithmic schemes and applications, which employ the aspects demonstrated in this article. The variety of binary aspects, algorithmic considerations, and problem-solving methods make these illustrations appealing teaching resources for computer science educators, in particular in the domain of algorithms.
Networks new economical virtual private
Authors: Ben-Ameur Walid , Kerivin Hervé
Published: August 2003

The idea is to reduce costs without undermining quality of service.
Asynchronous health care communication
Authors: Wilson E. Vance
Published: August 2003

Patients' desire for online communication with their health care providers is likely to change the course of both telemedicine and e-health technologies.
Facilitating tacit knowledge exchange
Authors: Desouza Kevin C.
Published: August 2003

Sharings insights from a humanistic and entertainment approach to improving organizational efficiency.
Trust in the preservation of digital information
Authors: Hart Peter E. , Liu Ziming
Published: August 2003

An institutional guarantee can help address the major hurdle of digital preservation---winning people's trust.
Analyzing security costs
Authors: Mercuri Rebecca T.
Published: August 2003

Quantification tools, if applied prudently, can assist in the anticipation, budgeting, and control of direct and indirect computer security costs.
Trade secrets vs. free speech
Authors: Samuelson Pamela
Published: August 2003

How to balance the benefits of free speech and the need for secrecy.
The McCarthy protocols
Authors: DeMarco Tom
Published: August 2003

Maximizing developers' contributions while minimizing social discomfort, they guide personal interaction and focus the development agenda.
Introduction
Authors: Stafford Thomas F.
Published: August 2003

As I sit here considering how to introduce this special section on e-services, I'm reminded of a superb experience I recently had filing my U.S. federal income tax return. In lieu of a $400 fee for paying someone to prepare my modestly complex 2002 financial circumstances, and having moved to a new state far from my long-time accountant, I decided to take a chance on one of the new tax filing services available online. This would be, in fact, my first substantial e-services experience as a consumer. Given I was dealing with the Internal Revenue Service (IRS), and the fact that thousands of dollars were at stake, it was no mere exercise to me.
Fulfilling the Web services promise
Authors: Kreger Heather
Published: August 2003

The creation and support of standards for Web services is a critical component to their effective functionality and ultimate success.
What are Web services?
Authors: Ferris Christopher , Farrell Joel
Published: August 2003

A Web service, as defined by the W3C Web Services Architecture Working Group, is "a software application identified by a URI, whose interfaces and bindings are capable of being defined, described, and discovered as XML artifacts. A Web service supports direct interactions with other software agents using XML-based messages exchanged via Internet-based protocols."
1
Others refine this definition further by requiring the description be a Web Services Description Language (WSDL) document and the protocol be SOAP.
E-service
Authors: Rust Roland T. , Kannan P.K.
Published: August 2003

Firms must take full advantage of Net-based e-service opportunities, particularly in the transition of products to services, to garner long-term customer relationships and loyalty.
Marketing challenges of e-services
Authors: Bolton Ruth N.
Published: August 2003

Technological innovations---such as the telephone, television, and the Internet---enable new capabilities that may create long-lasting changes in organizational structure, conduct, and performance. E-commerce currently accounts for a small portion of the U.S. economy, and an even smaller portion of the economies of other developed countries. Hence, marketers imperfectly understand the long-run ramifications of e-commerce for the behavior of buyers and sellers, organizational conduct and performance, the function and evolution of markets, and public policy. For example, there are differences between traditional and computer-mediated buying environments, with the latter characterized by increased information flows, interactivity, reduced information asymmetry between buyers and sellers, and a shift away from geographically based competition. However, the consequences of these features for organizational behavior are (as yet) unclear.
E-services at FedEx
Authors: Song Hongjun
Published: August 2003

Providing customer services online brought a new dimension to corporate functionalities at Federal Express.
Data completeness
Authors: Brohman M. Kathryn , Watson Richard T. , Piccoli Gabriele , Parasurama A.
Published: August 2003

To gain and maintain customer loyalty, a firm must learn how to best translate and mine the data they have on those customers.
Marketing + MIS = e-service
Authors: Hoffman K. Douglas
Published: August 2003

Traditional service marketers moving to e-services find fewer obstacles and more revenue opportunities in the process.
Technology enablers to recover from failures in e-services
Authors: Shaw Neal G. , Craighead Christopher W.
Published: August 2003

Although the goal of e-providers should be to provide quality service to all customers at all times, occasional failure is inevitable. Whether the failure is inherent in the content of the e-service (for example, a service that does not meet the expectations of the customer) or in the process (for example, the customer encountered problems with a Web site), the e-provider must be prepared to recover from this failure---a process known as
service recovery.
Successful service recovery is critical to customer retention and maintaining or possibly increasing customer loyalty [1]. Although service recovery has received a significant amount of attention in the fields of marketing (for example, [2]) and operations management (for example, [3]), the existing concepts must be adapted to the e-service environment. Accordingly, we provide the following seven action items for an e-service provider to remember when it attempts to
recover
from a service failure:
The Web services debate
Authors: Williams Joseph
Published: August 2003

As the articles in this section attest, the future of Web services is as certain as it is unclear. That is, the Web services arena is most certainly the next technological wave; what is not so clear is what direction (of many) that wave will flow. The challenge of selecting the tools to successfully pull all the components together is particularly daunting.
Toward public-key infrastructure interoperability
Authors: Backhouse James , Hsu Carol , McDonnell Aidan
Published: August 2003

Lessons from an information security standard accreditation scheme.
Discovering all most specific sentences
Authors: Gunopulos Dimitrios , Khardon Roni , Mannila Heikki , Saluja Sanjeev , Toivonen Hannu , Sharma Ram Sewak
Published: August 2003

Data mining can be viewed, in many instances, as the task of computing a representation of a theory of a model or a database, in particular by finding a set of maximally specific sentences satisfying some property. We prove some hardness results that rule out simple approaches to solving the problem.The
a priori
algorithm is an algorithm that has been successfully applied to many instances of the problem. We analyze this algorithm, and prove that is optimal when the maximally specific sentences are "small". We also point out its limitations.We then present a new algorithm, the Dualize and Advance algorithm, and prove worst-case complexity bounds that are favorable in the general case. Our results use the concept of hypergraph transversals. Our analysis shows that the
a priori
algorithm can solve the problem of enumerating the transversals of a hypergraph, improving on previously known results in a special case. On the other hand, using results for the general case of the hypergraph transversal enumeration problem, we can show that the Dualize and Advance algorithm has worst-case running time that is sub-exponential to the output size (i.e., the number of maximally specific sentences).We further show that the problem of finding maximally specific sentences is closely related to the problem of exact learning with membership queries studied in computational learning theory.
Ending spam's free ride
Authors: Weiss Aaron
Published: August 2003

Spam is now a felony in the state of Virginia, as long as the unsolicited messages contain falsified information about the sender. With the harshest anti-spam law in the United States recently passed, Virginia---home to major ISPs such as America Online---is hoping to prove that legislation is finally providing the tools needed to cap the flow of bulk e-mail advertising. But to skeptics even the strongest anti-spam laws will be hobbled by long processing times and fuzzy jurisdiction. Rather, argues Barry Shein, owner of "The World" (which was America's first public dial-up ISP), effectively ending spam requires an inversion of the economics of e-mail---shift the burden of cost onto the spammers. Until then, argues Shein and other like-minded voices, even the strongest legislation and most advanced technological defenses will only continue to drop the costs of spam on our collective shoulders.
The art circuit
Authors: Campbell Marisa E.
Published: August 2003

Give an adult some discarded bits and pieces of a computer, and chances are they'll help you cart it off to the dump site. Give the same technology fragments to children and they'll most likely use it to create cities, animal-filled scenes, or even the outer reaches of space.
Programming literacy
Authors: Treese Win
Published: August 2003

In the early 1980s, my mother started teaching computer science at her high school along with her usual math classes. The main focus was on programming, mainly for simple programs in BASIC and Pascal. As personal computers started to become more common, the classes grew in size. I started to think that programming wasn't the best topic, since most of the students would never spend much time writing code. The more important thing for them---I thought---would be to learn how to use the computer and the applications that were becoming available.
Flexible reference trace reduction for VM simulations
Authors: Kaplan Scott F. , Smaragdakis Yannis , Wilson Paul R.
Published: August 2003

The unmanageably large size of reference traces has spurred the development of sophisticated trace reduction techniques. In this article we present two new algorithms for trace reduction:
Safely Allowed Drop
(SAD) and
Optimal LRU Reduction
(OLR). Both achieve high reduction factors and guarantee
exact simulations
for common replacement policies and for memories larger than a user-defined threshold. In particular, simulation on OLR-reduced traces is accurate for the LRU replacement algorithm, while simulation on SAD-reduced traces is accurate for the LRU and OPT algorithms. Both policies can easily be modified and extended to maintain timing information, thus allowing for exact simulation of the Working Set and VMIN policies. OLR also satisfies an optimality property: for a given original trace and chosen memory size, it produces the shortest possible reduced trace that has the same LRU behavior as the original for a memory of at least the chosen size. We present a proof of this optimality of OLR, and show that SAD, while not optimal, yields nearly optimal performance in practice.Our approach has multiple applications, especially in simulating virtual memory systems; many page replacement algorithms are similar to LRU in that more recently referenced pages are likely to be resident. For several replacement algorithms in the literature, SAD- and OLR-reduced traces yield exact simulations. For many other algorithms, our trace reduction eliminates information that matters little: we present extensive measurements to show that the error for simulations of the clock and segq (segmented queue) replacement policies (the most common LRU approximations) is under 3% for the vast majority of memory sizes. In nearly all cases, the error is much smaller than that incurred by the well-known
stack deletion
technique.SAD and OLR have many desirable properties. In practice, they achieve reduction factors up to several orders of magnitude. The reduction translates to both storage savings
and
simulation speedups. Both techniques require little memory and perform a single forward traversal of the original trace, making them suitable for online trace reduction. Neither requires that the simulator be modified to accept the reduced trace.
Declaration of unknowns in DAE-based hybrid system specification
Authors: van Beek D. A. , Bos V. , Rooda J. E.
Published: August 2003

The majority of hybrid languages are based on the assumption that discontinuities in differential variables at discrete events are modeled by explicit mappings. When there are algebraic equations restricting the allowed new values of the differential variables, explicit remapping of differential variables forces the modeler to solve the algebraic equations. To overcome this difficulty, hybrid languages use many different language elements. This article shows that only one language element is needed for this purpose: an unknown declaration, which allows the explicit declaration of a variable as unknown. The syntax and semantics of unknown declarations are discussed. Examples are given, using the Chi language, in which unknown declarations are used for modeling multi-body collision, steady-state initialization, and consistent initialization of higher index systems. It is also illustrated how the declaration of unknowns can help to clarify the structure of the system of equations, and how it can help the modeler detect structurally singular systems of equations.
Efficient simulation of queues in heavy traffic
Authors: Wang Chia-Li , Wolff Ronald W.
Published: August 2003

When simulating queues in heavy traffic, estimators of quantities such as average delay in queue
d
converge slowly to their true values. This problem is exacerbated when interarrival and service distributions are irregular. For the
GI/G/
1 queue, delay moments can be expressed in terms of moments of idle period
I
. Instead of estimating
d
directly by a standard regenerative estimator that we call DD, a method we call DI estimates
d
from estimated moments of
I
. DI was investigated some time ago and shown to be much more efficient than DD in heavy traffic. We measure
efficiency
as the factor by which variance is reduced. For the
GI/G/
1 queue, we show how to generate a sequence of realized values of the
equilibrium
idle period,

I
e

, that are not independent and identically distributed, but have the correct statistical properties in the long run. We show how to use this sequence to construct a new estimator of
d
, called DE, and of higher moments of delay as well. When arrivals are irregular, we show that DE is more efficient than DI, in some cases by a large factor,
independent of the traffic intensity
. Comparing DE with DD, these factors
multiply
. For
GI/G/c
, we construct a control-variates estimator of average delay in queue

d
c

that is efficient in heavy traffic. It uses DE to estimate the average delay for the corresponding fast single server. We compare the efficiency of this method with another method in the literature. For
M/G/c
, we use insensitivity to construct another control-variates estimator of

d
c

. We compare the efficiency of this estimator with the two c-server estimators above.
Modeling methodology for integrated simulation of embedded systems
Authors: Ledeczi Akos , Davis James , Neema Sandeep , Agrawal Aditya
Published: August 2003

Developing a single embedded application involves a multitude of different development tools including several different simulators. Most tools use different abstractions, have their own formalisms to represent the system under development, utilize different input and output data formats, and have their own semantics. A unified environment that allows capturing the system in one place and one that drives all necessary simulators and analysis tools from this shared representation needs a common representation technology that must support several different abstractions and formalisms seamlessly. Describing the individual formalisms by metamodels and carefully composing them is the underlying technology behind MILAN, a Model-based Integrated Simulation Framework. MILAN is an extensible framework that supports multigranular simulation of embedded systems by seamlessly integrating existing simulators into a unified environment. Formal metamodels and explicit constraints define the domain-specific modeling language developed for MILAN that combines hierarchical, heterogeneous, parametric dataflow representation with strong data typing. Multiple modeling aspects separate orthogonal concepts. The language also allows the representation of the design space of the application, not just a point solution. Nonfunctional requirements are captured as formal, application-specific constraints. MILAN has integrated tool support for design-space exploration and pruning. The models are used to automatically configure the integrated functional simulators, high-level performance and power estimators, cycle-accurate performance simulators, and power-aware simulators. Simulation results are used to automatically update the system models. The article focuses on the modeling methodology and briefly describes how the integrated models are utilized in the framework.
Rank 2 intersection types for local definitions and conditional expressions
Authors: Damiani Ferruccio
Published: August 2003

We propose a rank 2 intersection type system with new typing rules for local definitions (let-expressions and letrec-expressions) and conditional expressions (if-expressions and match-expressions). This is a further step towards the use of intersection types in "real" programming languages.The technique for typing local definitions relies entirely on the principal typing property (i.e. it does not depend on particulars of rank 2 intersection), so it can be applied to any system with principal typings. The technique for typing conditional expressions, which is based on the idea of introducing metrics on types to "limit the use" of the intersection type constructor in the types assigned to the branches of the conditionals, is instead tailored to rank 2 intersection. However, the underlying idea might also be useful for other type systems.
Automatic program specialization for Java
Authors: Schultz Ulrik P. , Lawall Julia L. , Consel Charles
Published: August 2003

The object-oriented style of programming facilitates program adaptation and enhances program genericness, but at the expense of efficiency. We demonstrate experimentally that state-of-the-art Java compilers fail to compensate for the use of object-oriented abstractions in the implementation of generic programs, and that program specialization can eliminate a significant portion of these overheads. We present an automatic program specializer for Java, illustrate its use through detailed case studies, and demonstrate experimentally that it can significantly reduce program execution time. Although automatic program specialization could be seen as being subsumed by existing optimizing compiler technology, we show that specialization and compiler optimization are in fact complementary.
Continuous program optimization
Authors: Kistler Thomas , Franz Michael
Published: August 2003

Much of the software in everyday operation is not making optimal use of the hardware on which it actually runs. Among the reasons for this discrepancy are hardware/software mismatches, modularization overheads introduced by software engineering considerations, and the inability of systems to adapt to users' behaviors.A solution to these problems is to delay code generation until load time. This is the earliest point at which a piece of software can be fine-tuned to the actual capabilities of the hardware on which it is about to be executed, and also the earliest point at wich modularization overheads can be overcome by global optimization.A still better match between software and hardware can be achieved by replacing the already executing software at regular intervals by new versions constructed on-the-fly using a background code re-optimizer. This not only enables the use of live profiling data to guide optimization decisions, but also facilitates adaptation to changing usage patterns and the late addition of dynamic link libraries.This paper presents a system that provides code generation at load-time and continuous program optimization at run-time. First, the architecture of the system is presented. Then, two optimization techniques are discussed that were developed specifically in the context of continuous optimization. The first of these optimizations continually adjusts the storage layouts of dynamic data structures to maximize data cache locality, while the second performs profile-driven instruction re-scheduling to increase instruction-level parallelism. These two optimizations have very different cost/benefit ratios, presented in a series of benchmarks. The paper concludes with an outlook to future research directions and an enumeration of some remaining research problems.The empirical results presented in this paper make a case in favor of continuous optimization, but indicate that it needs to be applied judiciously. In many situations, the costs of dynamic optimizations outweigh their benefit, so that no break-even point is ever reached. In favorable circumstances, on the other hand, speed-ups of over 120% have been observed. It appears as if the main beneficiaries of continuous optimization are shared libraries, which at different times can be optimized in the context of the currently dominant client application.
Algorithm 823
Authors: Hong Hee Sun , Hickernell Fred J.
Published: August 2003

Random scrambling of deterministic (t,m,s)-nets and (t,s)-sequences eliminates their inherent bias while retaining their low-discrepancy properties. This article describes an implementation of two types of random scrambling, one proposed by Owen and another proposed by Faure and Tezuka. The four different constructions of digital sequences implemented are those proposed by Sobol', Faure, Niederreiter, and Niederreiter and Xing. Because the random scrambling involves manipulating all digits of each point, the code must be written carefully to minimize the execution time. Computed root mean square discrepancies of the scrambled sequences are compared to known theoretical results. Furthermore, the performances of these sequences on various test problems are discussed.
MATCONT
Authors: Dhooge A. , Govaerts W. , Kuznetsov Yu. A.
Published: August 2003

MATCONT is a graphical MATLAB software package for the interactive numerical study of dynamical systems. It allows one to compute curves of equilibria, limit points, Hopf points, limit cycles, period doubling bifurcation points of limit cycles, and fold bifurcation points of limit cycles. All curves are computed by the same function that implements a prediction-correction continuation algorithm based on the Moore-Penrose matrix pseudo-inverse. The continuation of bifurcation points of equilibria and limit cycles is based on bordering methods and minimally extended systems. Hence no additional unknowns such as singular vectors and eigenvectors are used and no artificial sparsity in the systems is created. The sparsity of the discretized systems for the computation of limit cycles and their bifurcation points is exploited by using the standard Matlab sparse matrix methods. The MATLAB environment makes the standard MATLAB Ordinary Differential Equations (ODE) Suite interactively available and provides computational and visualization tools; it also eliminates the compilation stage and so makes installation straightforward. Compared to other packages such as AUTO and CONTENT, adding a new type of curves is easy in the MATLAB environment. We illustrate this by a detailed description of the limit point curve type.
GloptiPoly
Authors: Henrion Didier , Lasserre Jean-Bernard
Published: August 2003

GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally nonconvex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality, or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum without any problem splitting. Global optimality is detected and isolated optimal solutions are extracted automatically. Numerical experiments show that for most of the small-scale problems described in the literature, the global optimum is reached at low computational cost.
The spectral signal processing suite
Authors: Sarra Scott A.
Published: August 2003

A software suite written in the Java programming language for the postprocessing of Chebyshev approximations to discontinuous functions is presented. It is demonstrated how to use the package to remove the effects of the Gibbs-Wilbraham phenomenon from Chebyshev approximations of discontinuous functions. Additionally, the package is used to postprocess Chebyshev collocation and Chebyshev super spectral viscosity approximations of hyperbolic partial differential equations. The postprocessing method is the Gegenbauer reconstruction procedure. The Spectral Signal Processing Suite is the first publicly available package that implements the procedure. State-of-the-art techniques are used to implement the algorithms with efficiency while reducing round-off error.
Formal derivation of algorithms
Authors: Quintana-Ortí Enrique S. , van de Geijn Robert A.
Published: August 2003

In this paper we apply a formal approach for the derivation of dense linear algebra algorithms to the triangular Sylvester equation. The result is a large family of provably correct algorithms. By using a coding style that reflects the algorithms as they are naturally presented, the correctness of the algorithms carries through to the correctness of the implementations. Analytically motivated heuristics are used to subsequently choose members from the family that can be expected to yield high performance. Finally, we report performance on the Intel (R) Pentium (R) III processor that is competitive with that of recursive algorithms reported previously in the literature for this operation.
On the hardware-software partitioning problem
Authors: López-Vallejo Marisa , López Juan Carlos
Published: August 2003

This paper presents an in-depth study of several system partitioning procedures. It is based on the appropriate formulation of a general system model, being therefore independent of either the particular co-design problem or the specific partitioning procedure. The techniques under study are a knowledge-based system and three classical circuit partitioning algorithms (Simulated Annealing, Kernighan&Lin and Hierarchical Clustering). The former has been entirely proposed by the authors in previous works while the later have been properly extended to deal with system level issues. We will show how the way the problem is solved biases the results obtained, regarding both quality and convergence rate. Consequently it is extremely important to choose the most suitable technique for the particular co-design problem that is being confronted.
Gravity
Authors: Obenaus Stefan Thomas , Szymanski Ted H.
Published: August 2003

Three dimensional integration is an increasingly feasible method of implementing complex circuitry. For large circuits, which most benefit from 3-D designs, efficient placement algorithms with low time complexity are required.We present an iterative 3-D placement algorithm that places circuit elements in three dimensions in linear time. Using an order of magnitude less time, our proposed algorithm produces placements with better than 11% less wire lengths than partitioning placement using the best and fastest partitioner. Due to the algorithms iterative nature, wire-length results can be further improved by increasing the number of iterations.Further, we provide empirical evidence that large circuits benefit most from 3-D technology and that even a small number of layers can provide significant wire-length improvements.
Synthesis of saturation arithmetic architectures
Authors: Constantinides G. A. , Cheung P. Y. K. , Luk W.
Published: August 2003

This paper describes a synthesis technique for automating the design of linear Digital Signal Processing (DSP) systems such as digital filters. The proposed methodology makes optimized use of saturation arithmetic to produce a small design implemented directly in hardware. An analytical technique is proposed to estimate the saturation error resulting from a particular implementation, and an optimization procedure is introduced to aim for the smallest implementation satisfying user-specified bounds on saturation and roundoff error. Results are presented illustrating significant speedup and area reduction compared with standard DSP design techniques: up to 22% improvement in area and 28% improvement in speed have been obtained on Field Programmable Gate Array (FPGA) implementations.
Constraints-driven scheduling and resource assignment
Authors: Kuchcinski Krzysztof
Published: August 2003

This paper describes a new method for modeling and solving different scheduling and resource assignment problems that are common in high-level synthesis (HLS) and system-level synthesis. It addresses assignment of resources for operations and tasks as well as their static, off-line scheduling. Different heterogeneous constraints are considered for these problems. These constraints can be grouped into two classes: problem-specific constraints and design-oriented constraints. They are uniformly modeled, in our approach, by finite domain (FD) constraints and solved using related constrained programming (CP) techniques. This provides a way to improve quality of final solutions. We have developed in Java a constraint solver engine, JaCoP (
Ja
va
Co
nstraint
P
rogramming), to evaluate this approach. This solver and a related framework make it possible to model different resource assignment and scheduling problems, and handle them uniformly. The JaCoP prototype system has been extensively evaluated on a number of HLS and system-level synthesis benchmarks. We have been able to obtain optimal results together with related proofs of optimality for all HLS scheduling benchmarks and for all explored design styles (except one functional pipeline design). Many system-level benchmarks can also be solved optimally. For large randomly generated task graphs, we have used heuristic search methods and obtained results that are 1--3% worse than lower bounds or optimal results. These experiments have proved the feasibility of the presented approach.
Primality and identity testing via Chinese remaindering
Authors: Agrawal Manindra , Biswas Somenath
Published: August 2003

We give a simple and new randomized primality testing algorithm by reducing primality testing for number
n
to testing if a specific univariate identity over

Z
n

holds.We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over

Z
n

for any
n
. The running time of the algorithms is polynomial in the size of arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, for example, the Schwartz--Zippel test [Schwartz 1980; Zippel 1979], Chen--Kao and Lewin--Vadhan tests [Chen and Kao 1997; Lewin and Vadhan 1998].
Algorithms adapting to point contention
Authors: Attiya Hagit , Fouren Arie
Published: August 2003

This article introduces the
sieve
, a novel building block that allows to adapt to the number of simultaneously active processes (the
point contention
) during the execution of an operation. We present an implementation of the sieve in which each sieve operation requires
O
(
k
log
k
) steps, where
k
is the point contention during the operation.The sieve is the cornerstone of the first wait-free algorithms that adapt to point contention using only read and write operations. Specifically, we present efficient algorithms for long-lived renaming, timestamping and collecting information.
Computability theory of generalized functions
Authors: Zhong Ning , Weihrauch Klaus
Published: August 2003

The theory of generalized functions is the foundation of the modern theory of partial differential equations (PDE). As computers are playing an ever-larger role in solving PDEs, it is important to know those operations involving generalized functions in analysis and PDE that can be computed on digital computers. In this article, we introduce natural concepts of computability on test functions and generalized functions, as well as computability on Schwartz test functions and tempered distributions. Type-2 Turing machines are used as the machine model [Weihrauch 2000]. It is shown here that differentiation and integration on distributions are computable operators, and various types of Fourier transforms and convolutions are also computable operators. As an application, it is shown that the solution operator of the distributional inhomogeneous three dimensional wave equation is computable.