bluuebunny/crossref_metadata_2025 huggingface dataset:
Conditional attribute grammars
Authors: Boyland John Tang
Published: October 2002

Attribute grammars are a useful formalism for the specification of computations on structured terms. The classical definition of attribute grammars, however, has no way of treating conditionals nonstrictly. Consequently, the natural way of expressing many otherwise well-behaved computations involves a circularity. This article presents
conditional attribute grammars
, and extension of attribute grammars that enables more precise analysis of conditionals. In conditional attribute grammars, attribute equations may have guards. Equations are active only when their guards are satisfied. The standard attribute grammar evaluation classes are definable for conditional attribute grammars, and the corresponding evaluation techniques can be easily adapted. However, determining membership in standard evaluation classes such as 1-SWEEP, OAG, and SNC is NP-hard.
Iterated register coalescing
Authors: George Lal , Appel Andrew W.
Published: October 2002

An important function of any register allocator is to target registers so as to eliminate copy instructions. Graph-coloring register allocation is an elegant approach to this problem. If the source and destination of a move instruction do not interfere, then their nodes can be coalesced in the interference graph. Chaitin's coalescing heuristic could make a graph uncolorable (i.e., introduce spills); Briggs et al. demonstrated a conservative coalescing heuristic that preserves colorability. But Briggs's algorithm is
too
conservative and leaves too many move instructions in our programs. We show how to interleave coloring reductions with Briggs's coalescing heuristic, leading to an algorithm that is safe but much more aggressive.
Evidence-based static branch prediction using machine learning
Authors: Calder Brad , Grunwald Dirk , Jones Michael , Lindsay Donald , Martin James , Mozer Michael , Zorn Benjamin
Published: October 2002

Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The nameprogram-basedbranch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this article, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. We call this approach to program-based branch predictionevidence-based static prediction, or ESP. The main idea of ESP is that the behavior of a corpus of programs can be used to infer the behavior of new programs. In this article, we use neural networks and decision trees to map static features associated with each branch to a prediction that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique; it is effective across a range of programming languages and programming styles; and it does not rely on the use of expert-defined heuristics. In this article, we describe the application of ESP to the problem of static branch prediction and compare our results to existing program-based branch predictors. We also investigate the applicability of ESP across computer architectures, programming languages, compilers, and run-time systems. We provide results showing how sensitive ESP is to the number and type of static features and programs included in the ESP training sets, and we compare the efficacy of static branch prediction for subroutine libraries. Averaging over a body of 43 C and Fortran programs, ESP branch prediction results in a miss rate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.
Formally based profiling for higher-order functional languages
Authors: Sansom Patrick M. , Peyton Jones Simon L.
Published: October 2002

We present the first source-level profiler for a compiled, nonstrict, higher-order, purely functional language capable of measuring
time
as well as
space
usage. Our profiler is implemented in a production-quality optimizing compiler for Haskell and can successfully profile large applications. A unique feature of our approach is that we give a formal specification of the attribution of execution costs to cost centers. This specification enables us to discuss our design decisions in a precise framework, prove properties about the attribution of costs, and examine to effects of different program transformations on the attribution of costs. Since it is not obvious how to map this specification onto a particular implementation, we also present an implementation-oriented operational semantics, and prove it equivalent to the specification.
Proving concurrent constraint programs correct
Authors: De Boer Frank S. , Gabbrielli Maurizio , Marchiori Elena , Palamidessi Catuscia
Published: October 2002

We introduce a simple compositional proof system for proving (partial) correctness of concurrent constraint programs (CCP). The proof system is based on a denotational approximation of the strongest postcondition semantics of CCP programs. The proof system is proved to be correct for full CCP and complete for the class of programs in which the denotational semantics characterizes exactly the strongest postcondition. This class includes the so-called confluent CCP, a special case of which is constraint logic programming with dynamic scheduling.
A reflection on call-by-value
Authors: Sabry Amr , Wadler Philip
Published: October 2002

One way to model a sound and complete translation from a source calculus into a target calculus is with anadjointor aGalois connection. In the special case of areflection, one also has that the target calculus is isomorphic to a subset of the source. We show that three widely studied translations form reflections. We use as our source language Moggi's computational lambda calculus, which is an extension of Plotkin's call-by-value calculus. We show that Plotkin's CPS translation, Moggi's monad translation, and Girard's translation to linear logic can all be regarded as reflections form this source language, and we put forward the computational lambda calculus as a model of call-by-value computation that improves on the traditional call-by-value calculus. Our work strengthens Plotkin's and Moggi's original results and improves on recent work based onequational correspondence, which uses equations rather than reductions.
A systematic study of functional language implementations
Authors: Douence Rémi , Fradet Pascal
Published: October 2002

We introduce a unified framework to describe, relate, compare, and classify functional language implementations. The compilation process is expressed as a succession of program transformations in the common framework. At each step, different transformations model fundamental choices. A benefit of this approach is to structure and decompose the implementation process. The correctness proofs can be tackled independently for each step and amount to proving program transformations in the functional world. This approach also paves the way to formal comparisons by making it possible to estimate the complexity of individual transformations or compositions of them. Our study aims at covering the whole known design space of sequential functional language implementations. In particular, we consider call-by-value, call-by-name, call-by-need reduction strategies as well as environment- and graph-based implementations. We describe for each compilation step the diverse alternatives as program transformations. In some cases, we illustrate how to compare or relate compilation techniques, express global optimizations, or hybrid implementations. We also provide a classification of well-known abstract machines.
Algorithmic specifications: a constructive specification method for abstract data types
Authors: Loeckx Jacques
Published: October 2002

This paper presents a new specification method for abstract data types and a pertaining logic. The specification method proposed differs from the classical algebraic one by its constructive, yet abstract nature. Although it leads to a different style in specification, the method avoids some fundamental problems inherent in the algebraic specification method. The logic proposed is essentially a first-order logic for strict (partial) functions. It allows in particular the expression of the semantic conditions guaranteeing the consistency of a specification.
A provably time-efficient parallel implementation of full speculation
Authors: Greiner John , Blelloch Guy E.
Published: October 2002

Speculative evaluation, including leniency and futures, is often used to produce high degrees of parallelism. Understanding the performance characteristics of such evaluation, however, requires having a detailed understanding of the implementation. For example, the particular implementaion technique used to suspend and reactivate threads can have an asymptotic effect on performance. With the goal of giving the users some understanding of performance without requiring them to understand the implementation, we present a provable implementation bound for a language based on speculative evaluation. The idea is (1) to supply the users with a semantics for a language that defines abstract costs for measuring or analyzing the performance of computations, (2) to supply the users with a mapping of these costs onto runtimes on various machine models, and (3) to describe an implementation strategy of the language and prove that it meets these mappings. For this purpose we consider a simple language based on speculative evaluation. For every computation, the semantics of the language returns a directed acyclic graph (DAG) in which each node represents a unit of computation, and each edge represents a dependence. We then describe an implementation strategy of the language and show that any computation with
w
work (the number of nodes in the DAG) and
d
depth (the length of the longest path in the DAG) will run on a
p
-processor PRAM in
O
(
w
/
p
+
d
log
p
) time. The bounds are work efficient (within a constant factor of linear speedup) when there is sufficient parallelism,
w
/
d
≥
p
log
p
. These are the first time bounds we know of for languages with speculative evaluation. The main challenge is in parallelizing the necessary queuing operations on suspended threads.
Hierarchical modularity
Authors: Blume Matthias , Appel Andrew W.
Published: October 2002

To cope with the complexity of very large systems, it is not sufficient to divide them into simple pieces because the pieces themselves will either be too numerous or too large. A hierarchical modular structure is the natural solution. In this article we explain how that approach can be applied to software. Our compilation manager provides a language for specifying where individual modules fit into a hierarchy and how they are related semantically. We pay particular attention to the structure of the global name space of program identifiers that are used for module linkage because any potential for name clashes between otherwise unrelated parts of a program can negatively affect modularity. We discuss the theoretical issues in building software hierarchically, and we describe our implementation of CM, the compilation manager for Standard ML of New Jersey.
Lazy rewriting on eager machinery
Authors: Fokkink Wan , Kamperman Jasper , Walters Pum
Published: October 2002

The article introduces a novel notion of lazy rewriting. By annotating argument positions as lazy, redundant rewrite steps are avoided, and the termination behavior of a term-rewriting system can be improved. Some transformations of rewrite rules enable an implementation using the same primitives as an implementation of eager rewriting.
From flop to megaflops
Authors: Moreira José E. , Midkiff Samuel P. , Gupta Manish
Published: October 2002

Although there has been some experimentation with Java as a language for numerically intensive computing, there is a perception by many that the language is unsuited for such work because of performance deficiencies. In this article we show how optimizing array bounds checks and null pointer checks creates loop nests on which aggressive optimizations can be used. Applying these optimizations by hand to a simple matrix-multiply test case leads to Java-compliant programs whose performance is in excess of 500 Mflops on a four-processor 332MHz RS/6000 model F50 computer. We also report in this article the effect that various optimizations have on the performance of six floating-point-intensive benchmarks. Through these optimizations we have been able to achieve with Java at least 80% of the peak Fortran performance on the same benchmarks. Since all of these optimizations can be automated, we conclude that Java will soon be a serious contender for numerically intensive computing.
Independence in CLP languages
Authors: García de la Banda María , Hermenegildo Manuel , Marriott Kim
Published: October 2002

Studying independence of goals has proven very useful in the context of logic programming. In particular, it has provided a formal basis for powerful automatic parallelization tools, since independence ensures that two goals may be evaluated in parallel while preserving correctness and efficiency. We extend the concept of independence to constraint logic programs (CLP) and prove that it also ensures the correctness and efficiency of the parallel evaluation of independent goals. Independence for CLP languages is more complex than for logic programming as search space preservation is necessary but no longer sufficient for ensuring correctness and efficiency. Two additional issues arise. The first is that the cost of constraint solving may depend upon the order constraints are encountered. The second is the need to handle dynamic scheduling. We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow different optimizations, from parallelism to intelligent backtracking. Suficient conditions for independence which can be evaluated “a priori” at run-time are also proposed. Our study also yields new insights into independence in logic programming languages. In particular, we show that search space preservation is not only a sufficient but also a necessary condition for ensuring correctness and efficiency of parallel execution.
Code Generation and Storage Allocation for Machines with Span-Dependent Instructions
Authors: Robertson Edward L.
Published: October 2002

Many machine languages have two instruction formats, one of which allows addressing of “nearby” operands with “short” (e.g. one word) instructions, while “faraway” operands require “long” format (e.g. two words). Because the distance between an instruction and its operand depends upon the formats of the intervening instructions, the formats of different instructions may be interdependent.

An efficient technique is discussed which optimally assigns formats to instructions in a given program and is practical in space as well as time. The more sophisticated problem of arranging operands within programs is discussed. Unfortunately, it is unlikely that an efficient algorithm can guarantee even a good approximation for this problem, since it is shown that
r
-approximation is NP-complete.

Finally, implications of these problems for hardware and software design are considered.
A Hierarchical Approach to Formal Semantics With Application to the Definition of PL/ CS
Authors: Constable Robert L. , Donahue James E.
Published: October 2002

We describe a means of presenting hierarchically organized formal definitions of programming languages using the denotational approach of D. Scott and C. Strachey. As an example of our approach, we give the semantics of PL/CS, an instructional variant of PL/I. We also discuss the implications of this approach to language design, pointing out some cases where the wrong choices may cause the hierarchy to collapse into chaotic rubble.
A Deterministic Attribute Grammar Evaluator Based on Dynamic Scheduling
Authors: Kennedy Ken , Ramanathan Jayashree
Published: October 2002

The problem of semantic evaluation in a compiler-generating system can be addressed by specifying language semantics in an
attribute grammar
[19], a context-free grammar augmented with “attributes” for the nonterminals and “semantic functions” to compute the attributes. A deterministic method for evaluating all attributes in a “semantic” parse tree is derived and shown to have time and space complexities which are essentially linear in the size of the tree. In a prepass through the parse tree, the method determines an
evaluation sequence
for the attributes; thus it is somewhat analogous to dynamic programming. The constructor-evaluator system described should be suitable for inclusion in a general translator-writing system.
Uniform Random Generation of Balanced Parenthesis Strings
Authors: Arnold D. B. , Sleep M. R.
Published: October 2002

The empirical testing of error repair schemes for skeletons of source programs in a block-structured language leads to the problem of generating balanced parenthesis strings in a uniform random manner. An efficient generator which works from left to right must compute the correct probability for the next symbol at each stage of the generation. The associated enumeration problem may be solved by adopting a geometric interpretation usually associated with random walk problems. This solution leads immediately to an
O
(
n
) algorithm for the generator.
Smarter recompilation
Authors: Schwanke Robert W. , Kaiser Gail E.
Published: October 2002

Tichy's Smart Recompilation
method can be made smarter by permitting benign type inconsistencies between separately compiled modules. This enhanced method helps the programmer to make far-reaching changes in small, manageable steps.
A framework for call graph construction algorithms
Authors: Grove David , Chambers Craig
Published: October 2002

A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for understanding call graph construction algorithms and an empirical comparison of a representative set of algorithms. We first present a general parameterized algorithm that encompasses many well-known and novel call graph construction algorithms. We have implemented this general algorithm in the Vortex compiler infrastructure, a mature, multilanguage, optimizing compiler. The Vortex implementation provides a "level playing field" for meaningful cross-algorithm performance comparisons. The costs and benefits of a number of call graph construction algorithms are empirically assessed by applying their Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of code) Cecil and Java programs. For many of these applications, interprocedural analysis enabled substantial speed-ups over an already highly optimized baseline. Furthermore, a significant fraction of these speed-ups can be obtained through the use of a scalable, near-linear time call graph construction algorithm.
Parametric shape analysis via 3-valued logic
Authors: Sagiv Mooly , Reps Thomas , Wilhelm Reinhard
Published: October 2002

Shape analysis concerns the problem of determining "shape invariants" for programs that perform destructive updating on dynamically allocated storage. This article presents a parametric framework for shape analysis that can be instantiated in different ways to create different shape-analysis algorithms that provide varying degrees of efficiency and precision. A key innovation of the work is that the stores that can possibly arise during execution are represented (conservatively) using 3-valued logical structures. The framework is instantiated in different ways by varying the predicates used in the 3-valued logic. The class of programs to which a given instantiation of the framework can be applied is not limited a priori (i.e., as in some work on shape analysis, to programs that manipulate only lists, trees, DAGS, etc.); each instantiation of the framework can be applied to any program, but may produce imprecise results (albeit conservative ones) due to the set of predicates employed.
The emperor has no lab coat
Authors: Olsen George
Published: October 2002

Can you achieve usable designs without a usability process, without the involvement of a usability professional? Some researchers say sure, it happens all the time. But how? According to George Olsen, those who achieve this are very good designers who bring a breadth of knowledge to their work? including user focus and sensitivity. It's usability professionals, he says, who miss seeing the usability in what these groups are doing. Usability must stop ignoring the wider context.
--- Elizabeth Buie
Initializability analysis of synchronous sequential circuits
Authors: Corno F. , Prinetto P. , Rebaudengo M. , Reorda M. Sonza , Squillero G.
Published: October 2002

This article addresses the problem of initializing synchronous sequential circuits, that is, of generating the shortest sequence able to drive the circuit to a known state, regardless of the initial state. Logic initialization is considered, being the only one compatible with current commercial tools. A hybrid Genetic Algorithm is proposed, which combines general ideas from evolutionary computation with specific techniques, well suited to the addressed problem. For the first time, experimental results provide data about the complete set of ISCAS'89 circuits, and show that, despite the inherent algorithm incompleteness, the method is capable of finding the optimum result for the considered circuits. A prototypical tool implementing the algorithm found better results than previous methods.
The proof of correctness wars
Authors: Glass Robert L.
Published: October 2002

Whether mild or raging, wars about topics ranging from programming languages to methods of indentation are healthy for our field.
Data mining standards initiatives
Authors: Grossman Robert L. , Hornick Mark F. , Meyer Gregor
Published: October 2002

Lacking standards for statistical and data mining models, applications cannot leverage the benefits of data mining.
Secure and selective dissemination of XML documents
Authors: Bertino Elisa , Ferrari Elena
Published: October 2002

XML (
eXtensible Markup Language
) has emerged as a prevalent standard for document representation and exchange on the Web. It is often the case that XML documents contain information of different sensitivity degrees that must be selectively shared by (possibly large) user communities. There is thus the need for models and mechanisms enabling the specification and enforcement of access control policies for XML documents. Mechanisms are also required enabling a secure and selective dissemination of documents to users, according to the authorizations that these users have. In this article, we make several contributions to the problem of secure and selective dissemination of XML documents. First, we define a formal model of access control policies for XML documents. Policies that can be defined in our model take into account both user profiles, and document contents and structures. We also propose an approach, based on an extension of the Cryptolope™ approach [Gladney and Lotspiech 1997], which essentially allows one to send the same document to all users, and yet to enforce the stated access control policies. Our approach consists of encrypting different portions of the same document according to different encryption keys, and selectively distributing these keys to the various users according to the access control policies. We show that the number of encryption keys that have to be generated under our approach is minimal and we present an architecture to support document distribution.
Deciding and axiomatizing weak ST bisimulation for a process algebra with recursion and action refinement
Authors: Bravetti Mario , Gorrieri Roberto
Published: October 2002

Due to the complex nature of bisimulation equivalences that express some form of history dependence, it turned out to be problematic to decide them over nontrivial classes of recursive systems. Moreover, to the best of our knowledge, the problem of axiomatizing them over such classes of systems has never been solved. In this article, we face this problem in the case of weak ST bisimulation, an equivalence that expresses the execution of an action as the combination of the two interdependent events of action start and action termination and that supports the operation of action refinement. We first consider a basic process algebra with CSP multiway synchronization and recursion and we show that a simple technique based on static names is sufficient to decide weak ST bisimulation over processes that are finite state according to the standard interleaving semantics. Then we introduce a different technique based on dynamic names and on the new idea of compositional level-wise renaming of actions (which produces semantic models via SOS such that weak ST bisimulation can be established through standard weak bisimulation) and we show that it can be applied to decide and axiomatize weak ST bisimulation over the same class of processes. Finally, we introduce a third technique based on pointers, updated according to a pseudo-stack discipline, which preserves the possibility of deciding and axiomatizing weak ST bisimulation also when an action refinement operator is considered.
Polynomial-time computation via local inference relations
Authors: Givan Robert , Mcallester David
Published: October 2002

We consider the concept of alocalset of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The local-rule-set transformation gives polynomial-time evaluation strategies for a large variety of rule sets that cannot be given terminating evaluation strategies by any other known automatic technique. This article discusses three new results. First, it is shown that every polynomial-time predicate can be defined by an (unstratified) local rule set. Second, a new machine-recognizable subclass of the local rule sets is identified. Finally, we show that locality, as a property of rule sets, is undecidable in general.
Fast generation of order statistics
Authors: Hörmann Wolfgang , Derflinger Gerhard
Published: October 2002

Generating a single order statistic without generating the full sample can be an important task for simulations. If the density and the CDF of the distribution are given, then it is no problem to compute the density of the order statistic. In the main theorem it is shown that the concavity properties of that density depend directly on the distribution itself. Especially for log-concave distributions, all order statistics have log-concave distributions themselves. So recently suggested automatic transformed density rejection algorithms can be used to generate single order statistics. This idea leads to very fast generators. For example for the normal and gamma distributions, the suggested new algorithms are between 10 and 60 times faster than the algorithms suggested in the literature.
Least squares conformal maps for automatic texture atlas generation
Authors: Lévy Bruno , Petitjean Sylvain , Ray Nicolas , Maillot Jérome
Published: October 2002

A Texture Atlas is an efficient color representation for 3D Paint Systems. The model to be textured is decomposed into charts homeomorphic to discs, each chart is parameterized, and the unfolded charts are packed in texture space. Existing texture atlas methods for triangulated surfaces suffer from several limitations, requiring them to generate a large number of small charts with simple borders. The discontinuities between the charts cause artifacts, and make it difficult to paint large areas with regular patterns.In this paper, our main contribution is a new quasi-conformal parameterization method, based on a least-squares approximation of the Cauchy-Riemann equations. The so-defined objective function minimizes angle deformations, and we prove the following properties: the minimum is unique, independent of a similarity in texture space, independent of the resolution of the mesh and cannot generate triangle flips. The function is numerically well behaved and can therefore be very efficiently minimized. Our approach is robust, and can parameterize large charts with complex borders.We also introduce segmentation methods to decompose the model into charts with natural shapes, and a new packing algorithm to gather them in texture space. We demonstrate our approach applied to paint both scanned and modeled data sets.
Motion texture
Authors: Li Yan , Wang Tianshu , Shum Heung-Yeung
Published: October 2002

In this paper, we describe a novel technique, called motion texture, for synthesizing complex human-figure motion (e.g., dancing) that is statistically similar to the original motion captured data. We define motion texture as a set of motion textons and their distribution, which characterize the stochastic and dynamic nature of the captured motion. Specifically, a motion texton is modeled by a linear dynamic system (LDS) while the texton distribution is represented by a transition matrix indicating how likely each texton is switched to another. We have designed a maximum likelihood algorithm to learn the motion textons and their relationship from the captured dance motion. The learnt motion texture can then be used to generate new animations automatically and/or edit animation sequences interactively. Most interestingly, motion texture can be manipulated at different levels, either by changing the fine details of a specific motion at the texton level or by designing a new choreography at the distribution level. Our approach is demonstrated by many synthesized sequences of visually compelling dance motion.
Physically based modeling and animation of fire
Authors: Nguyen Duc Quang , Fedkiw Ronald , Jensen Henrik Wann
Published: October 2002

We present a physically based method for modeling and animating fire. Our method is suitable for both smooth (laminar) and turbulent flames, and it can be used to animate the burning of either solid or gas fuels. We use the incompressible Navier-Stokes equations to independently model both vaporized fuel and hot gaseous products. We develop a physically based model for the expansion that takes place when a vaporized fuel reacts to form hot gaseous products, and a related model for the similar expansion that takes place when a solid fuel is vaporized into a gaseous state. The hot gaseous products, smoke and soot rise under the influence of buoyancy and are rendered using a blackbody radiation model. We also model and render the blue core that results from radicals in the chemical reaction zone where fuel is converted into products. Our method allows the fire and smoke to interact with objects, and flammable objects can catch on fire.
A scalable method for deductive generalization in the spreadsheet paradigm
Authors: Burnett Margaret , Yang Sherry , Summet Jay
Published: October 2002

The following abstracts are from recent issues and the forthcoming issue of ACM's
Transactions
o
f Computer Human Interaction
(ToCHI). They are included here to alert
interactions'
readers to what research is being done in the field of Computer Human Interaction. The complete papers, when published, can be found in ACM's Digital Library at www.acm.org/pubs/contents/journals/tochi/
Sale must end
Authors: Cockton Gilbert , Woolrych Alan
Published: October 2002

If you ask someone outside the Human-Computer Interaction (HCI) field about usability, many will mention the "classic" discount methods popularized by Jakob Nielsen and others. Discount methods have the appeal of seeming easy to do, and, more importantly for business, being inexpensive. This is especially attractive to smaller startup companies with low budgets. But are discount methods really too risky to justify the "low" cost? This month's business column authors think so, based on their research and experience. Indeed, they believe that these discount methods may actually backfire and end up discrediting the field. Following a lively discussion on the CHI-WEB listserv, we asked them to explain what they see the risks to be, and what they believe we, as a profession, can and should do about it.--- David Siegel and Susan Dray
Integrating web sites and databases
Authors: Morrison Mike , Morrison Joline , Keys Anthony
Published: October 2002

Web site developers creating 'data-based Web pages' that interact with organizational databases need to know server- and client-side processing.
The most important issues in knowledge management
Authors: King William R. , Marks Peter V. , McCoy Scott
Published: October 2002

What can KM do for corporate memory, management thinking, and IS responsibility, as well as for overall business performance?
Finding the flow in web site search
Authors: Hearst Marti , Elliott Ame , English Jennifer , Sinha Rashmi , Swearingen Kirsten , Yee Ka-Ping
Published: October 2002

Designing a search system and interface may best be served (and executed) by scrutinizing usability studies.
Multimodal human discourse
Authors: Quek Francis , McNeill David , Bryll Robert , Duncan Susan , Ma Xin-Feng , Kirbas Cemil , McCullough Karl E. , Ansari Rashid
Published: October 2002

Gesture and speech combine to form a rich basis for human conversational interaction. To exploit these modalities in HCI, we need to understand the interplay between them and the way in which they support communication. We propose a framework for the gesture research done to date, and present our work on the cross-modal cues for discourse segmentation in free-form gesticulation accompanying speech in natural conversation as a new paradigm for such multimodal interaction. The basis for this integration is the psycholinguistic concept of the coequal generation of gesture and speech from the same semantic intent. We present a detailed case study of a gesture and speech elicitation experiment in which a subject describes her living space to an interlocutor. We perform two independent sets of analyses on the video and audio data: video and audio analysis to extract segmentation cues, and expert transcription of the speech and gesture data by microanalyzing the videotape using a frame-accurate videoplayer to correlate the speech with the gestural entities. We compare the results of both analyses to identify the cues accessible in the gestural and audio data that correlate well with the expert psycholinguistic analysis. We show that "handedness" and the kind of symmetry in two-handed gestures provide effective supersegmental discourse cues.
Translation of web queries using anchor text mining
Authors: Lu Wen-Hsiang , Chien Lee-Feng , Lee Hsi-Jian
Published: October 2002

This article presents an approach to automatically extracting translations of Web query terms through mining of Web anchor texts and link structures. One of the existing difficulties in cross-language information retrieval (CLIR) and Web search is the lack of appropriate translations of new terminology and proper names. The proposed approach successfully exploits the anchor-text resources and reduces the existing difficulties of query term translation. Many query terms that cannot be obtained in general-purpose translation dictionaries are, therefore, extracted.
A comment on the presentation and testing of CALGO codes and a remark on algorithm 639
Authors: Hopkins Tim
Published: October 2002

We report on a number of coding problems that occur frequently in published CALGO software and are still appearing in new algorithm submissions. Using Algorithm 639 as an extended example, we describe how these types of faults may be almost entirely eliminated using available commercial compilers and software tools. We consider the levels of testing required to instil confidence that code performs reliably. Finally, we look at how the source code may be re-engineered, and thus made more maintainable, by taking account of advances in hardware and language development.
How deep are your links?
Authors: Weiss Aaron
Published: October 2002

"If you operate a Web site and wish to link to this Site, you may link only to the home page of the Site and not to any other page or sub-domain of us…."-- The Dallas Morning News,
www.dallasnews.com/registration/termsofservice.html
XML, web services, and XML
Authors: Treese Win
Published: October 2002

Ever since the concept of "Web services" was defined, there have been questions about their security. Early specifications for Web services paid little attention to security, other than to note that security was going to be an issue someday. Depending on whom you talk to, Web services have either forged ahead without much security or limped along over security worries. In the past few months, many more detailed proposals for Web-services security have emerged. The important questions now, of course, involve not only the efficacy of these proposed systems, but whether anyone will actually use them.
Overcoming independent extensibility challenges
Authors: Meijer Erik , Szyperski Clemens
Published: October 2002

Independent extensibility requires a strong handle on versioning through precise names.
A goal-driven approach to enterprise component identification and specification
Authors: Levi Keith , Arsanjani Ali
Published: October 2002

Mapping a business architecture to a component-based software architecture.
Web services
Authors: Stal Michael
Published: October 2002

Seeking a better solution to the application integration problem.
Proving systolic systems correct
Authors: Hennessy Matthew
Published: October 2002

A language for describing communicating systems is described. It is sufficiently expressive to describe both the desired behavior of systems, their
specifications
, and their actual
implementations
in terms of simpler components. We say
I
satisfies
S
if
1
is a correct implementation of the specification
S
. We briefly discuss a semantic treatment of this notion of satisfaction, but the main emphasis of the paper is on a proof technique for proving statements of the form
I
satisfies
S
, based on syntactic transformations and induction. Two examples are given, both systolic systems from the literature.
Incremental dynamic semantics for language-based programming environments
Authors: Kaiser G. E.
Published: October 2002

Attribute grammars are a formal notation for expressing the static semantics of programming languages—those properties that can be derived from inspection of the program text. Attribute grammars have become popular as a mechanism for generating language-based programming environments that incrementally perform symbol resolution, type checking, code generation, and derivation of other static semantic properties as the program is modified. However, attribute grammars are not suitable for expressing dynamic semantics—those properties that reflect the
history
of program execution and/or user interactions with the programming environment. This paper presents
action equations
, an extension of attribute grammars suitable for specifying the static and the dynamic semantics of programming languages. It describes how action equations can be used to generate language-based programming environments that incrementally derive static and dynamic properties as the user modifies and debugs th
e program.
A generalization of Dijkstra's calculus
Authors: Nelson Greg
Published: October 2002

Dijsktra's calculus of guarded commands can be generalized and simplified by dropping the law of the excluded miracle. This paper gives a self-contained account of the generalized calculus from first principles through the semantics of recursion. The treatment of recursion uses the fixpoint method from denotational semantics. The paper relies only on the algebraic properties of predicates; individual states are not mentioned (except for motivation). To achieve this, we apply the correspondence between programs and predicates that underlies predicative programming.

The paper is written from the axiomatic semantic point of view, but its contents can be described from the denotational semantic point of view roughly as follows: The Plotkin-Apt correspondence between wp semantics and the Smyth powerdomain is extended to a correspondence between the full wp/wlp semantics and the Plotkin powerdomain extended with the empty set.
Synchronization of asynchronous processes in CSP
Authors: Bagrodia Rajive
Published: October 2002

Many concurrent programming languages including CSP and Ada use synchronous message-passing to define communication between a pair of asynchronous processes. Suggested primitives like the generalized alternative command for CSP and the symmetric select statement for Ada allow a process to nondeterministically select one of several communication statements for execution. The communication statement may be either an input or an output statement. We propose a simple algorithm to implement the generalized alternative command and show that it uses fewer messages than existing algorithms.
Using symbolic execution for verification of Ada tasking programs
Authors: Dillon Laura K.
Published: October 2002

A method is presented for using symbolic execution to generate the verification conditions required for proving correctness of programs written in a tasking subset of Ada. The symbolic execution rules are derived from proof systems that allow tasks to be verified independently in local proofs, which are then checked for cooperation. The isolation nature of this approach to symbolic execution of concurrent programs makes it better suited to formal verification than the more traditional interleaving approach, which suffers from combinatorial problems. The criteria for correct operation of a concurrent program include partial correctness, as well as more general safety properties, such as mutual exclusion and freedom from deadlock.
Writing Larch interface language specifications
Authors: Wing Jeannette M.
Published: October 2002

Current research in specifications is emphasizing the practical use of formal specifications in program design. One way to encourage their use in practice is to provide specification languages that are accessible to both designers and programmers. With this goal in mind, the Larch family of formal specification languages has evolved to support a two-tiered approach to writing specifications. This approach separates the specification of state transformations and programming language dependencies from the specification of underlying abstractions. Thus, each member of the Larch family has a subset derived from a programming language and another subset independent of any programming languages. We call the former interface languages, and the latter the Larch Shared Language.

This paper focuses on Larch interface language specifications. Through examples, we illustrate some salient features of Larch/CLU, a Larch interface language for the programming language CLU. We give an example of writing an interface specification following the two-tiered approach and discuss in detail issues involved in writing interface specifications and their interaction with their Shared Language components.
The geometry of semaphore programs
Authors: Carson Scott D. , Reynolds Paul F.
Published: October 2002

Synchronization errors in concurrent programs are notoriously difficult to find and correct. Deadlock, partial deadlock, and unsafeness are conditions that constitute such errors.

A model of concurrent semaphore programs based on multidimensional, solid geometry is presented. While previously reported geometric models are restricted to two-process mutual exclusion problems, the model described here applies to a broader class of synchronization problems. The model is shown to be exact for systems composed of an arbitrary, yet fixed number of concurrent processes, each consisting of a straight line sequence of arbitrarily ordered semaphore operations.
Break Ins and Break Outs: Viral Interactions with the Cytoskeleton of Mammalian Cells
Authors: Smith Gregory A. , Enquist Lynn W.
Published: October 2002

▪ Abstract  The host cytoskeleton plays important roles in the entry, replication, and egress of viruses. An assortment of viruses hijack cellular motor proteins to move on microtubules toward the cell interior during the entry process; others reverse this transport during egress to move assembling virus particles toward the plasma membrane. Polymerization of actin filaments is sometimes used to propel viruses from cell to cell, while many viruses induce the destruction of select cytoskeletal filaments apparently to effect efficient egress. Indeed, the tactics used by any given virus to achieve its infectious life cycle are certain to involve multiple cytoskeletal interactions. Understanding these interactions, and their orchestration during viral infections, is providing unexpected insights into basic virology, viral pathogenesis, and the biology of the cytoskeleton.
Actin Cytoskeleton Regulation in Neuronal Morphogenesis and Structural Plasticity
Authors: Luo Liqun
Published: October 2002

▪ Abstract  The actin cytoskeleton plays a major role in morphological development of neurons and in structural changes of adult neurons. This article reviews the myriad functions of actin and myosin in axon initiation, growth, guidance and branching, in morphogenesis of dendrites and dendritic spines, in synapse formation and stability, and in axon and dendrite retraction. Evidence is presented that signaling pathways involving the Rho family of small GTPases are key regulators of actin polymerization and myosin function in the context of different aspects of neuronal morphogenesis. These studies support an emerging theme: Different aspects of neuronal morphogenesis may involve regulation of common core signaling pathways, in particular the Rho GTPases.
Altered Fibrin Clot Structure in the Healthy Relatives of Patients With Premature Coronary Artery Disease
Authors: Mills Joseph D. , Ariëns Robert A.S. , Mansfield Michael W. , Grant Peter J.
Published: October 2002

Background—

A family history of premature coronary artery disease (CAD) is an independent cardiovascular risk factor. Fibrin clots composed of dense fiber networks are found in young CAD patients and may occur in the relatives of such individuals.

Methods and Results—

The ex vivo fibrin structure of 100 healthy male relatives of patients with premature CAD and 100 age-matched control subjects was assessed by measurement of permeability (
K
s
), fiber mass-length ratio (μ), and turbidity (lag phase and maximum absorbency [max ΔAbs]). Scanning electron microscopy was performed on selected samples. Relatives and controls shared similar levels of conventional cardiovascular risk factors.
K
s
was lower in relatives than in controls, 12.2 (11.1 to 13.3) versus 15.2 (14.0 to 16.5) ×10
−9
cm
2
(
P
<0.001), associated with a smaller decrease in μ, 8.5 (7.7 to 9.2) versus 9.7 (8.9 to 10.5) × 10
13
Da/cm (
P
<0.05), respectively. Lag phase was shorter in relatives than in controls, 39 (37 to 41) versus 47 (44 to 50) seconds (
P
<0.001), and max ΔAbs was higher in relatives, 0.78 (0.74 to 0.82) versus 0.71 (0.67 to 0.74) in controls (
P
=0.02), which indicates the presence of thicker fibers in relatives. After adjustment for fibrinogen levels, lag phase and
K
s
remained significantly different between relatives and control subjects. Scanning electron microscopy images confirmed increased fiber diameter in relatives, possibly of reduced density. Factor XIII Val34Leu and fibrinogen Aα Thr312Ala and Bβ -455 G/A showed no association with clot structure.

Conclusions—

The male relatives of patients with premature CAD form fibrin clots that begin polymerization more quickly, have thicker fibers, and are less permeable than those of control subjects.