bluuebunny/crossref_metadata_2025 huggingface dataset:
CLOSED SUBGROUPS IN PRO-V TOPOLOGIES AND THE EXTENSION PROBLEM FOR INVERSE AUTOMATA
Authors: MARGOLIS S. , SAPIR M. , WEIL P.
Published: July 2002

We relate the problem of computing the closure of a finitely generated subgroup of the free group in the pro-V topology, where V is a pseudovariety of finite groups, with an extension problem for inverse automata which can be stated as follows: given partial one-to-one maps on a finite set, can they be extended into permutations generating a group in V? The two problems are equivalent when V is extension-closed. Turning to practical computations, we modify Ribes and Zalesskiĭ's algorithm to compute the pro-p closure of a finitely generated subgroup of the free group in polynomial time, and to effectively compute its pro-nilpotent closure. Finally, we apply our results to a problem in finite monoid theory, the membership problem in pseudovarieties of inverse monoids which are Mal'cev products of semilattices and a pseudovariety of groups.

Résumé: Nous établissons un lien entre le problème du calcul de l'adhéerence d'un sous-groupe finiment engendré du groupe libre dans la topologie pro-V, oú V est une pseudovariété de groupes finis, et un probléme d'extension pour les automates inversifs qui peut être énoncé de la faç con suivante: étant données des transformations partielles injectives d'un ensemble fini, peuvent-elles être étendues en des permutations qui engendrent un groupe dans V? Les deux problèmes sont équivalents si V est fermée par extensions. Nous intéressant ensuite aux calculs pratiques, nous modifions l'algorithme de Ribes et Zalesskiĭ pour calculer l'adhérence pro-p d'un sous-groupe finiment engendré du groupe libre en temps polynomial et pour calculer effectivement sa clôture pro-nilpotente. Enfin nous appliquons nos résultats à un problème de théorie des monoïdes finis, celui de de l'appartenance dans les pseudovariétés de monoïdes inversifs qui sont des produits de Mal'cev de demi-treillis et d'une pseudovariété de groupes.
ON THE SPECTRAL DECOMPOSITION OF EMPIRICAL CORRELATION MATRICES
Authors: FORZANI LILIANA , TOLMASKY CARLOS F.
Published: July 2002

One of the most widely used methods to build yield curve models is to use principal components analysis on the correlation matrix of the innovations. R. Litterman and J. Scheinkman found that three factors are enough to explain most of the moves in the case of the US treasury curve. These factors are level, steepness and curvature. Working in the context of commodity futures, G. Cortazar and E. Schwartz found that the spectral structure of the correlation matrices is strikingly similar to those found by R. Litterman and J. Scheinkman. We observe that in both cases the correlation between two different contracts maturing at times t and s is roughly of the form ρ|t-s|, for a certain (fixed) 0≤ρ≤1. Assuming this correlation structure we prove that the observed factors are perturbations of cosine waves.
Kauffman Monoids
Authors: BORISAVLJEVIĆ MIRJANA , DOŠEN KOSTA , PETRIĆ ZORAN
Published: July 2002

This paper gives a self-contained and complete proof of the isomorphism of freely generated monoids extracted from Temperley-Lieb algebras with monoids made of Kauffman's diagrams.
MODEL STUDY OF FACTORS INFLUENCING STEADY STATE CLEARANCE FOR LIPOPHILIC TOXICANTS IN AQUATIC MICROCOSMS
Authors: VENTURINO ANDRÉS , ROVEDATTI MARÍA GABRIELA , GAUNA LIDIA , LOEWY MIRIAM , DE D'ANGELO ANA MARÍA PECHEN
Published: July 2002

We have studied the distribution and bioelimination of the organophosphorus pesticide parathion in a native microcosm consisting of water, sediment, bivalves and aquatic plants. A common apparent clearance constant for biotic and abiotic components was suggested from the analysis of parathion accumulation and degradation.

In this work we developed a global model explaining the toxicokinetics of a lipophilic compound and particurlarly the common steady state degradation in an aquatic microcosm, using a set of linear differential equations. We simulated the distribution and degradation of the compound in the microcosm, and fitted single-compartment equation models to data, estimating the apparent sorption and elimination constants. We verified the existence of a common apparent degradation constant for all the compartments. We infer from the mathematical expressions and corroborate from the simulated data that the apparent degradation constant is equal to the sum of the metabolization rates at each biotic compartment multiplied by the compound mass ratios established at steady state between the biotic and the abiotic compartments.

Product kinetics simulation showed that steady state might also be achieved in the different compartments, with the same apparent constant as that obtained for toxicant clearance. As a practical result, the total radioactivity in water would serve to calculate the global clearance constant in a simple experimental way if a radiotracer is used. Physical and chemical degradation and chemical loss due to volatilization and CO 2 diffusion were analyzed in the microcosm model. The assessments of the cases where these factors affect the clearance process as well as the implications emerged are discussed.
A NEW GENERALIZATION OF Cpm FOR PROCESSES WITH ASYMMETRIC TOLERANCES
Authors: CHEN K. S. , PEARN W. L. , LIN P. C.
Published: July 2002

Greenwich and Jahr-Schaffrath9 introduced the incapability index C pp , which is a simple transformation of the index [Formula: see text] proposed by Chan et al.3 Chen10 considered the incapability index [Formula: see text], a generalization of C pp , to handle processes with asymmetric tolerances. Based on the same idea on [Formula: see text], we consider a new generalization [Formula: see text], which is a modification of the process capability index C pm . In the cases of symmetric tolerances, the new generalization [Formula: see text] reduces to the original index C pm . The new generalization [Formula: see text] not only takes the proximity of the target value into consideration, like those of C pm and [Formula: see text], but also takes into account the asymmetry of the specification limits. We compare the new generalization [Formula: see text] with C pa (1, 3) and C pa (0, 4), two special cases of C pa (u, v) recommended by Vännman7 for asymmetric tolerances. We also investigate the statistical properties of the natural estimator [Formula: see text], assuming the process is normally distributed. We obtain the exact distribution and an explicit form of the probability density function of [Formula: see text]. In addition, we compute the rth moment-expected value, variance of [Formula: see text], and analyze the bias as well as the MSE of [Formula: see text].
CALCULATION OF SLOW POSITRON YIELD FROM METAL SURFACES
Authors: SHRIVASTAVA S. B. , UPADHYAY ATUL
Published: July 2002

The fraction of positrons emitted from a metal surface having a negative work function for positrons has been calculated as a function of incident positron energy and temperature. The model employed considers the diffusion of positrons, trapping into the surface state and in near surface defects. The calculated results in Cu(111) have been compared with the experiments. The maximum yield for positrons in Mo(111) has been found to occur at 600 K for 1 keV positrons.
DEADLINE ALLOCATION IN A TIME-CONSTRAINED WORKFLOW
Authors: SON JIN HYUN , KIM JUNG HOON , KIM MYOUNG HO
Published: July 2002

Workflow management systems should efficiently manage workflow constraints such as time, resource, and cost during workflow executions. Especially, workflow time management is important in timely scheduling of workflow process execution, avoiding deadline violations, and improving the workflow throughput. Though there have been some studies on the dynamic deadline management in a workflow, the importance of the static deadline management has not been much addressed in the past.

We first describe our workflow model considered in this paper. Then, we propose a static deadline allocation method that can facilitate an efficient workflow processing. The proposed method can achieve high workflow throughput by analyzing the interrelated workflow components. We also present various experimental results that show the usefulness and efficiency of the method.
HYPERDEFINABLE GROUPS IN SIMPLE THEORIES
Authors: WAGNER FRANK
Published: July 2002

We study hyperdefinable groups, the most general kind of groups interpretable in a simple theory. After developing their basic theory, we prove the appropriate versions of Hrushovski's group quotient theorem and the Weil–Hrushovski group chunk theorem. We also study locally modular hyperdefinable groups and prove that they are bounded-by-Abelian-by-bounded. Finally, we analyze hyperdefinable groups in supersimple theories.
NOWHERE PRECIPITOUSNESS OF THE NON-STATIONARY IDEAL OVER ${\mathcal P}_\kappa \lambda$
Authors: MATSUBARA YO , SHELAH SAHARON
Published: July 2002

We prove that if λ is a strong limit singular cardinal and κ a regular uncountable cardinal < λ, then NSκλ, the non-stationary ideal over [Formula: see text], is nowhere precipitous. We also show that under the same hypothesis every stationary subset of [Formula: see text] can be partitioned into λκ disjoint stationary sets.
(AVERAGE-) CONVEXITY OF COMMON POOL AND OLIGOPOLY TU-GAMES
Authors: DRIESSEN THEO S. H. , MEINHARDT HOLGER
Published: July 2002

The paper studies both the convexity and average-convexity properties for a particular class of cooperative TU-games called common pool games. The common pool situation involves a cost function as well as a (weakly decreasing) average joint production function. Firstly, it is shown that, if the relevant cost function is a linear function, then the common pool games are convex games. The convexity, however, fails whenever cost functions are arbitrary. We present sufficient conditions involving the cost functions (like weakly decreasing marginal costs as well as weakly decreasing average costs) and the average joint production function in order to guarantee the convexity of the common pool game. A similar approach is effective to investigate a relaxation of the convexity property known as the average-convexity property for a cooperative game. An example illustrates that oligopoly games are a special case of common pool games whenever the average joint production function represents an inverse demand function.
THE GIERER & MEINHARDT SYSTEM: THE BREAKING OF HOMOCLINICS AND MULTI-BUMP GROUND STATES
Authors: del PINO MANUEL , KOWALCZYK MICHAŁ , CHEN XINFU
Published: July 2002

In this paper we study ground-states of the Gierer & Meinhardt system on the line, namely solutions of the problem [Formula: see text] We prove that given any number N, there exists a solution to this problem exhibiting exactly Nbumps in its u-component, separated from each other at a distance O(| log σ|), whenever σ is sufficiently small. These bumps resemble the shape of the unique solution of [Formula: see text]
ROOK PLACEMENTS AND CLASSIFICATION OF PARTITION VARIETIES B\ Mλ
Authors: DING KEQUAN
Published: July 2002

Let M be the set of m by n complex matrices of rank m. Let λ = (λ1,…,λm) be a partition with λi ≥ λi + 1 for 1 ≤ i ≤ m - 1 and λ1 = n. A Ferrers board Fλ is a right justified subarray in a m by n matrix with the length of the ith row being λi, and define Mλ={a ∈ M|ai,j = 0 if (i,j) ∉ Fλ}. Let B be the Borel subgroup of the general linear group GLm (C) consisting of upper triangular matrices. Define B\Mλ={Ba|a∈ Mλ}. The quotient space B\Mλ is a projective variety called a partition variety associated to λ. In this note, we classify partition varieties B\Mλ according to their homology and cohomology groups (up to isomorphisms).
VIBRATIONS OF AXIALLY LOADED CONTINUOUS BEAMS
Authors: BUSOOL WISAM , EISENBERGER MOSHE
Published: July 2002

The effect of a constant axial load either tensile or compressive on the natural frequencies of uniform multi-span beams is presented. The proposed solution is based on the exact dynamic stiffness matrix for the member, for any desired precision. The natural frequencies are found as the frequencies that cause the determinant of the stiffness matrix to become zero. The influence of the axial load and variation of span ratios on the vibration frequencies for beams with up to 4 spans are studied, and presented in graphical forms.
TIME SERIES ANALYSIS IN RECONSTRUCTED STATE SPACES
Authors: KANTZ HOLGER
Published: July 2002

Concepts for the analysis of observed scalar time series data in reconstructed vector valued phase spaces are reviewed. Originally exclusively designed for data from deterministic chaotic systems, phase space methods were recently extended to usage for nonlinear stochastic and for nonstationary processes.
STOCHASTICALLY PERTURBED FLOWS: DELAYED AND INTERRUPTED EVOLUTION
Authors: BALAKRISHNAN V. , VAN DEN BROECK C. , BENA I.
Published: July 2002

We present analytical expressions for the time-dependent and stationary probability distributions corresponding to a stochastically perturbed one-dimensional flow with critical points, in two physically relevant situations: delayed evolution, in which the flow alternates with a quiescent state in which the dynamical variable remains frozen at its current value for random intervals of time; and interrupted evolution, in which the variable is also reset in the quiescent state to a random value drawn from a fixed distribution. In the former case, the effect of the delay upon the first passage time statistics is analyzed. In the latter case, the conditions under which an extended stationary distribution can exist as a consequence of the competition between an attractor in the flow and the random resetting are examined. We elucidate the role of the normalization condition in eliminating the singularities arising from the unstable critical points of the flow, and present a number of representative examples. A simple formula is obtained for the stationary distribution and interpreted physically. A similar interpretation is also given for the known formula for the stationary distribution in a full-fledged dichotomous flow.
AUTOMORPHISMS OF TOROIDAL LIE ALGEBRAS AND THEIR CENTRAL QUOTIENTS
Authors: PIANZOLA A.
Published: July 2002

We describe the structure of the group of automorphisms of Lie algebras of the form [Formula: see text] when R has trivial Picard group. We also look at the group of automorphisms of central quotients of the universal covering algebra of [Formula: see text] as well as conjugacy questions.
Toward an open shared workspace
Authors: Ishii Hiroshi , Miyake Naomi
Published: July 2002

Groupware is intended to create a shared workspace that supports dynamic collaboration in a work group over space and time constraints. To gain the collective benefits of groupware use, the groupware must be accepted by a majority of workgroup members as a common tool. Groupware must overcome the hurdle of
critical mass
.
Algorithm 706: DCUTRI: an algorithm for adaptive cubature over a collection of triangles
Authors: Berntsen Jarle , Espelid Terje O.
Published: July 2002

An adaptive algorithm for computing an approximation to the integral of each element in a vector function
f(x,y)
over a two-dimensional region made up of triangles is presented. A FORTRAN implementation of the algorithm is included. The basic cubature rule used over each triangle is a 37-point symmetric rule of degree 13. Based on the same evaluation points the local error for each element in the approximation vector and for each triangle is computed using a sequence of null rule evaluations. A sophisticated error-estimation procedure tries, in a cautious manner, to decide whether we have asymptotic behavior locally for each function. Different actions are taken depending on that decision, and the procedure takes advantage of the basic rule's polynomial degree when computing the error estimate in the asymptotic case.
Cooperative shared memory
Authors: Hill Mark D. , Larus James R. , Reinhardt Steven K. , Wood David A.
Published: July 2002

We believe the paucity of massively parallel, shared-memory machines follows from the lack of a shared-memory programming performance model that can inform programmers of the cost of operations (so they can avoid expensive ones) and can tell hardware designers which cases are common (so they can build simple hardware to optimize them). Cooperative shared memory, our approach to shared-memory design, addresses this problem.

Our initial implementation of cooperative shared memory uses a simple programming model, called Check-In/Check-Out (CICO), in conjunction with even simpler hardware, called Dir1SW. In CICO, programs bracket uses of shared data with a check_in directive terminating the expected use of the data. A cooperative prefetch directive helps hide communication latency. Dir1SW is a minimal directory protocol that adds little complexity to message-passing hardware, but efficiently supports programs written within the CICO model.
The management of end-user computing
Authors: Brancheau James C. , Brown Carol V.
Published: July 2002

The development of computing applications by the people who have direct need for them in their work has become commonplace. During the 1980s, development of applications by “end users” accelerated and became a key management and research concern. Known as “end-user computing,” the phenomena and research associated with this trend cross a variety of disciplines. This article critically surveys the published literature on end-user computing (EUC) management according to a comprehensive research model. The article introduces the EUC management research model, identifies prior research contributions, and offers guideline for the future. The focal points of the model are two EUC management components which represent two different levels of theorizing found in the literature. The first level focuses on the organization factors of strategy, technology, and management action. The second level focuses on the individual factors of end user, task, tool, and end-user action. The remainder of the model includes factors typically investigated as the antecedents (context) and consequences (outcomes) of EUC. More than 90 English-language articles published from 1983-1990 are mapped into the model. Specific variables for each factor are identified; research streams are interpreted; findings are synthesized; and gaps in our knowledge are highlighted. We then raise a number of substantive and methodological issues that need to be addressed and suggest two themes we envision as important for EUC management research in the 1990s: EUC as an extension of organizational computing and EUC as a social learning phenomenon. Guidance is offered for using these theme to inform future research.
Corrigendum: Algorithm 730: An implementation of a divide and conquer algorithm for the unitary eigenproblem
Authors: Ammar G. S. , Reichel L. , Sorensen D. C.
Published: July 2002

We present a FORTRAN implementation of a divide-and-conquer method for computing the spectral resolution of a unitary upper Hessenberg matrix H. Any such matrix H of order
n
, normalized so that its subdiagonal elements are nonnegative, can be written as a product of
n
–1 Givens matrices and a diagonal matrix. This representation, which we refer to as the
Schur parametric form
of H, arises naturally in applications such as in signal processing and in the computation of Gauss-Szego¨ quadrature rules. Our programs utilize the Schur parametrization to compute the spectral decomposition of H without explicitly forming the elements of H. If only the eigenvalues and first components of the eigenvectors are desired, as in the applications mentioned above, the algorithm requires only

O(n
2
)

arithmetic operations. Experimental results presented indicate that the algorithm is reliable and competitive with the general QR algorithm applied to this problem. Moreover, the algorithm can be easily adapted for parallel implementation.
On randomization in sequential and distributed algorithms
Authors: Gupta Rajiv , Smolka Scott A. , Bhaskar Shaji
Published: July 2002

Probabilistic, or randomized, algorithms are fast becoming as commonplace as conventional deterministic algorithms. This survey presents five techniques that have been widely used in the design of randomized algorithms. These techniques are illustrated using 12 randomized algorithms—both sequential and distributed— that span a wide range of applications, including:primality testing(a classical problem in number theory),interactive probabilistic proof systems(a new method of program testing),dining philosophers(a classical problem in distributed computing), andByzantine agreement(reaching agreement in the presence of malicious processors). Included with each algorithm is a discussion of its correctness and its computational complexity. Several related topics of interest are also addressed, including the theory of probabilistic automata, probabilistic analysis of conventional algorithms, deterministic amplification, and derandomization of randomized algorithms. Finally, a comprehensive annotated bibliography is given.
Eliminating the boundary effect of a large-scale personal communication service network simulation
Authors: Lin Yi-Bing , Mak Victor W.
Published: July 2002

Eliminating the boundary effects is an important issue for a large-scale personal communication service (PCS) network simulation. A PCS network is often modeled by a network of hexagonal cells. The boundary may significantly bias the ouput statistics if the number of hexagonal cells is small in a PCS network simulation. On the other hand, if the simulation is to be completed within a reasonable time on the available computing resources, the number of cells in the simulation cannot be too large. To avoid the inaccuracy caused by the boundary effect for a PCS network simulation with limited computing resources, we propose wrapping the hexagonal mesh into a homogeneous graph (i.e., all nodes in the graph are topologically identical). We show that by using the wrapped hexagonal mesh, the inaccuracy of the output measures can be limited even though the number of cells in the simulation is small. We can thus obtain the same statistical accuracy while using significantly less computation power than required for a simulation without cell wrapping.
RAID: high-performance, reliable secondary storage
Authors: Chen Peter M. , Lee Edward K. , Gibson Garth A. , Katz Randy H. , Patterson David A.
Published: July 2002

Disk arrays were proposed in the 1980s as a way to use parallelism between multiple disks to improve aggregate I/O performance. Today they appear in the product lines of most major computer manufacturers. This article gives a comprehensive overview of disk arrays and provides a framework in which to organize current and future work. First, the article introduces disk technology and reviews the driving forces that have popularized disk arrays: performance and reliability. It discusses the two architectural techniques used in disk arrays: striping across multiple disks to improve performance and redundancy to improve reliability. Next, the article describes seven disk array architectures, called RAID (Redundant Arrays of Inexpensive Disks) levels 0–6 and compares their performance, cost, and reliability. It goes on to discuss advanced research and implementation topics such as refining the basic RAID levels to improve performance and designing algorithms to maintain data consistency. Last, the article describes six disk array prototypes of products and discusses future opportunities for research, with an annotated bibliography disk array-related literature.
Formal aspects of concurrency control in long-duration transaction systems using the NT/PV model
Authors: Korth Henry F. , Speegle Greg
Published: July 2002

In the typical database system, an execution is correct if it is equivalent to some serial execution. This criterion, called serializability, is unacceptable for new database applications which require long-duration transactions. We present a new transaction model which allows correctness criteria more suitable for these applications. This model combines three enhancements to the standard model: nested transactions, explicit predicates, and multiple versions. These features yield the name of the new model, nested transactions with predicates and versions, or NT/PV.

The modular nature of the NT/PV model allows a straightforward representation of simple systems. It also provides a formal framework for describing complex interactions. The most complex interactions the model allows can be captured by a protocol which exploits all of the semantics available to the NT/PV model. An example of these interactions is shown in a CASE application. The example shows how a system based on the NT/PV model is superior to both standard database techniques and unrestricted systems in both correctness and performance.
Designing programs that check their work
Authors: Blum Manuel , Kannan Sampath
Published: July 2002

A
program correctness checker
is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that instance is correct. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class FP of functions computable in polynomial time. Problems in FP for which checkers are presented in this paper include Sorting, Matrix Rank and GCD. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations.

Two structural theorems are proven here. One is a characterization of problems that can be checked. The other theorem establishes equivalence classes of problems such that whenever one problem in a class is checkable, all problems in the class are checkable.
Using visual texture for information display
Authors: Ware Colin , Knight William
Published: July 2002

Results from vision research are applied to the synthesis of visual texture for the purposes of information display. The literature surveyed suggests that the human visual system processes spatial information by means of parallel arrays of neurons that can be modeled by Gabor functions. Based on the Gabor model, it is argued that the fundamental dimensions of texture for human perception are orientation, size (1/frequency), and contrast. It is shown that there are a number of trade-offs in the density with which information can be displayed using texture. Two of these are (1) a trade-off between the size of the texture elements and the precision with which the location can be specified, and (2) the precision with which texture orientation can be specified and the precision with which texture size can be specified. Two algorithms for generating texture are included.
Online tracking of mobile users
Authors: Awerbuch Baruch , Peleg David
Published: July 2002

This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic concept ofregional matching, and demonstrates how finding a regional matching with certain parameters enables efficient tracking. The communication overhead of our tracking mechanism is within a polylogarithmic factor of the lower bound.
Rule-based versus structure-based models for explaining and generating expert behavior
Authors: Dhar Vasant , Pople Harry E.
Published: July 2002

Flexible representations are required in order to understand and generate expert behavior. Although production rules with quantifiers can encode experiential knowledge, they often have assumptions implicit in them, making them brittle in problem scenarios where these assumptions do not hold. Qualitative models achieve flexibility by representing the domain entities and their interrelationships explicitly. However, in problem domains where assumptions underlying such models change periodically, it is necessary to be able to synthesize and maintain qualitative models in response to the changing assumptions. In this paper we argue for a representation that contains partial model components that are synthesized into qualitative models containing entities and relationships relevant to the domain. The model components can be replaced and rearranged in response to changes in the task environment. We have found this "model constructor" to be useful in synthesizing models that explain and generate expert behavior, and have explored its ability to support decision making in the problem domain of business resource planning, where reasoning is based on models that evolve in response to changing external conditions or internal policies.
Data compression on a database system
Authors: Cormack Gordon V.
Published: July 2002

A general-purpose data-compression routine—implemented on the IMS database system—makes use of context to achieve better compression than Huffman's method applied character by character. It demonstrates that a wide variety of data can be compressed effectively using a single, fixed compression routine with almost no working storage.
Accountability and computer decision systems
Authors: Johnson Deborah G. , Mulvey John M.
Published: July 2002

Are designers responsible for all of the uses of the systems they create?
Rejection-inversion to generate variates from monotone discrete distributions
Authors: Hörmann W. , Derflinger G.
Published: July 2002

For discrete distributions a variant of reject from a continuous hat function is presented. The main advantage of the new method, called
rejection-inversion
, is that no extra uniform random number to decide between acceptance and rejection is required, which means that the expected number of uniform variates required is halved. Using rejection-inversion and a squeeze, a simple universal method for a large class of monotone discrete distributions is developed. It can be used to generate variates from the tails of most standard discrete distributions. Rejection-inversion applied to the Zipf (or zeta) distribution results in algorithms that are short and simple and at least twice as fast as the fastest methods suggested in the literature.
The STATEMATE semantics of statecharts
Authors: Harel David , Naamad Amnon
Published: July 2002

We describe the semantics of statecharts as implemented in the STATEMATE system. This was the first executable semantics defined for the language and has been in use for almost a decade. In terms of the controversy around whether changes made in a given step should take effect in the current step or in the next one, this semantics adopts the latter approach.
Multiresolution analysis for surfaces of arbitrary topological type
Authors: Lounsbery Michael , DeRose Tony D. , Warren Joe
Published: July 2002

Multiresolution analysis and wavelets provide useful and efficient tools for representing functions at multiple levels of detail. Wavelet representations have been used in a broad range of applications, including image compression, physical simulation, and numerical analysis. In this article, we present a new class of wavelets, based on subdivision surfaces, that radically extends the class of representable functions. Whereas previous two-dimensional methods were restricted to functions difined onR2, the subdivision wavelets developed here may be applied to functions defined on compact surfaces of arbitrary topological type. We envision many applications of this work, including continuous level-of-detail control for graphics rendering, compression of geometric models, and acceleration of global illumination algorithms. Level-of-detail control for spherical domains is illustrated using two examples: shape approximation of a polyhedral model, and color approximation of global terrain data.
SpeechSkimmer
Authors: Arons Barry
Published: July 2002

Listening to a speech recording is much more difficult than visually scanning a document because of the transient and temporal nature of audio. Audio recordings capture the richness of speech, yet it is difficult to directly browse the stored information. This article describes techniques for structuring, filtering, and presenting recorded speech, allowing a user to navigate and interactively find information in the audio domain. This article describes the SpeechSkimmer system for interactively skimming speech recordings. SpeechSkimmer uses speech-processing techniques to allow a user to hear recorded sounds quickly, and at several levels of detail. User interaction, through a manual input device, provides continuous real-time control of the speed and detail level of the audio presentation. SpeechSkimmer reduces the time needed to listen by incorporating time-compressed speech, pause shortening, automatic emphasis detection, and nonspeech audio feedback. This article also presents a multilevel structural approach to auditory skimming and user interface techniques for interacting with recorded speech. An observational usability test of SpeechSkimmer is discussed, as well as a redesign and reimplementation of the user interface based on the results of this usability test.
An optimal algorithm for expanding the composition of polynomials
Authors: Liu Wayne , Mann Stephen
Published: July 2002

A runtime analysis is made of a previously published algorithm for polynomial composition. The relationship between this composition algorithm and Sablonnie`re's algorithm is explored. This composition algorithm is then made optimal aby first performing a change of basis.
Hands-on practice in learning to use software
Authors: Wiedenbeck Susan , Zila Patti L.
Published: July 2002

This research addresses two issues in the domain of computer training (1) whether learners are able to use exploration-based practice methods effectively to learn to use software and (2) whether some minimal computing background is necessary to be successful with minimalist training and exploration practice. An empirical study was carried out to compare exploration, exercises, and a combined format consisting of an exercise followed by exploration. Subjects of both high and low computer experience were included in the study. It was thought that the combined format might lead to superior training outcomes because it would both structure learning through an exercise and allow learners to go beyond the simple procedures in the training manual through exploration. The results showed that the performance of the low-experience subjects at test did not differ based on the type of practice. However, high-experience subjects who were trained using exercises or the combined format did significantly better than those trained using exploration alone. The similarity of performance of subjects in the exercise and combined practice conditions suggests that the exercise component of the practice explains their success.
How to use expert advice
Authors: Cesa-Bianchi Nicolò , Freund Yoav , Haussler David , Helmbold David P. , Schapire Robert E. , Warmuth Manfred K.
Published: July 2002

We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, calledexperts. Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. We measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictins. We show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. Our upper and lower bounds have matching leading constants in most cases. We then show how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context. We also compare our analysis to the case in which log loss is used instead of the expected number of mistakes.
Exploiting process lifetime distributions for dynamic load balancing
Authors: Harchol-Balter Mor , Downey Allen B.
Published: July 2002

We consider policies for CPU load balancing in networks of workstations. We address the question of whether preemptive migration (migrating active processes) is necessary, or whether remote execution (migrating processes only at the time of birth) is sufficient for load balancing. We show that resolving this issue is strongly tied to understanding the process lifetime distribution. Our measurements indicate that the distribution of lifetimes for a UNIX process is Pareto (heavy-tailed), with a consistent functional form over a variety of workloads. We show how to apply this distribution to derive a preemptive migration policy that requires no hand-tuned parameters. We used a trace-driven simulation to show that our preemptive migration strategy is far more effective than remote execution, even when the memory transfer cost is high.
Algorithm 773
Authors: Renka Robert J.
Published: July 2002

SSRFPACK is a Fortran 77 software package that constructs a smooth interpolatory or approximating surface to data values associated with arbitrarily distributed points on the surface of a sphere. It employs automatically selected tension factors to preserve shape properties of the data and avoid overshoot and undershoot associated with steep gradients.
The string B-tree
Authors: Ferragina Paolo , Grossi Roberto
Published: July 2002

We introduce a new text-indexing data structure, the
String B-Tree
, that can be seen as a link between some traditional external-memory and string-matching data structures. In a short phrase, it is a combination of B-trees and Patricia tries for internal-node indices that is made more effective by adding extra pointers to speed up search and update operations. Consequently, the String B-Tree overcomes the theoretical limitations of inverted files, B-trees, prefix B-trees, suffix arrays, compacted tries and suffix trees. String B-trees have the same worst-case performance as B-trees but they manage unbounded-length strings and perform much more powerful search operations such as the ones supported by suffix trees. String B-trees are also effective in main memory (RAM model) because they improve the online suffix tree search on a dynamic set of strings. They also can be successfully applied to database indexing and software duplication.
On the discrepancy of GFSR pseudorandom numbers
Authors: Tezuka Shu
Published: July 2002

A new summation formula based on the orthogonal property of Walsh functions is devised. Using this formula, the
k
-dimensional discrepancy of the generalized feedback shift register (GFSR) pseudorandom numbers is derived. The relation between the discrepancy and
k
-distribution of GFSR sequences is also obtained. Finally the definition of optimal GPSR pseudorandom number generators is introduced.
The functional data model and the data languages DAPLEX
Authors: Shipman David W.
Published: July 2002

DAPLEX is a database language which incorporates:

This paper presents and motivates the DAPLEX language and the underlying data model on which it is based.
Transformation of data traversals and operations in application programs to account for semantic changes of databases
Authors: Su Stanley Y. W. , Lam Herman , Lo Der Her
Published: July 2002

This paper addresses the problem of application program conversion to account for changes in database semantics that result in changes in the schema and database contents. With the observation that the existing data models can be viewed as alternative ways of modeling the same database semantics, a methodology of application program analysis and conversion based on an existing-DBMS-model-and schema-independent representation of both the database and programs is presented. In this methodology, the source and target databases are described in terms of the association types of a semantic association model. The structural properties, the integrity constraints, and the operational characteristics (storage operation behaviors) of the association types are more explicitly defined to reveal the semantics that is generally hidden in application programs. The explicit descriptions of the source and target databases are used as the basis for program analysis and conversion. Application programs are described in terms of a small number of “access patterns” which define the data traversals and operations of the programs. In addition to the methodology, this paper (1) describes a model of a generalized application program conversion system that serves as a framework for research, (2) presents an analysis of access patterns that serve as the primitives for program description, (3) delineates some meaningful semantic changes to databases and their corresponding transformation rules for program conversion, (4) illustrates the application of these rules to two different approaches to program conversion problems, and (5) reports on the development effort undertaken at the University of Florida.
Experiments on the determination of the relationships between terms
Authors: Raghavan Vijay V. , Yu C. T.
Published: July 2002

The retrieval effectiveness of an automatic method that uses relevance judgments for the determination of positive as well as negative relationships between terms is evaluated. The term relationships are incorporated into the retrieval process by using a generalized similarity function that has a term match component, a positive term relationship component, and a negative term relationship component. Two strategies, query partitioning and query clustering, for the evaluation of the effectiveness of the term relationships are investigated. The latter appears to be more attractive from linguistic as well as economic points of view. The positive and the negative relationships are verified to be effective both when used individually, and in combination. The importance attached to the term relationship components relative to that of term match component is found to have a substantial effect on the retrieval performance. The usefulness of discriminant analysis as a technique for determining the relative importance of these components is investigated.
On the Consistency of Precedence Matrices
Authors: Harary Frank
Published: July 2002

The consistency of precedence matrices is studied in the very natural geometric setting of the theory of directed graphs. An elegant recent procedure (Marimont [7]) for checking consistency is further justified by means of a graphical lemma. In addition, the “direction of future work” mentioned in [7] (to which the present communication may be regarded as a sequel) is developed here using graph theoretic methods. This is based on the relationship between the occurrence of directed cycles and the recognition of “strongly connected components” in a directed graph. An algorithm is included for finding these components in any directed graph. This is necessarily more complicated than determining whether there do not exist any directed cycles, i.e., whether or not a given precedence matrix is consistent.
Queueing Analysis of the IBM 2314 Disk Storage Facility
Authors: Abate Joseph , Dubner Harvey , Weinberg Sheldon B.
Published: July 2002

In this paper the use of the techniques of queueing theory in analyzing the performance of a mass storage device in a real-time environment is demonstrated; concern is with the tradeoff experienced in practice between throughput of a stochastic service device and the response time for each service request. For concreteness, the analysis is applied to the IBM 2314 disk storage facility. The results are presented in a series of graphs showing the file system response time versus the throughput for several distributions of record length and arm movement. The queueing model and the theoretical tools used are described in sufficient detail to permit the reader to apply the techniques to other systems. In particular, any disk whose seek time characteristic can be approximated by a piecewise linear continuous function may be analyzed by the methods presented.
Set Covering by an All Integer Algorithm
Authors: Koncal Ronald D. , Salkin Harvey M.
Published: July 2002

Computational experience with a modified linear programming method for the inequality or equality set covering problem (i.e. minimize
cx
subject to
Ex
≥
e
or
Ex
=
e
,

x
i

= 0 or 1, where
E
is a zero-one matrix,
e
is a column of ones, and
c
is a nonnegative integral row) is presented. The zero-one composition of the constraint matrix and the right-hand side of ones suggested an algorithm in which dual simplex iterations are performed whenever unit pivots are available and Gomory all integer cuts are adjoined when they are not. Applications to enumerative and heuristic schemes are also discussed.
Best Least Squares Solutions to Finite Difference Equations Using the Generalized Inverse and Tensor Product Methods
Authors: Dalphin John F. , Lovass-Nagy Victor
Published: July 2002

A direct (noniterative) method for solving some singular systems of equations arising from finite difference approximations to partial differential equations is developed. The Moore-Penrose generalized inverse of some large tensor product matrices is expressed in terms of smaller matrices. Some techniques are given to improve computational efficiency.
On the complexity of edge traversing
Authors: Papadimitriou Christos H.
Published: July 2002

It is shown that the Chinese Postman Problem, although tractable in the totally directed and the totally undirected cases, is NP-complete in the mixed case. A simpler version of the same problem is shown algorithmically equivalent to the max-flow problem with unit edge capacities.
Lower Bounds on Merging Networks
Authors: Yao Andrew Chi-Chih , Yao Foong Frances
Published: July 2002

Let
M
(
m, n
) be the minimum number or comparators needed in an (
m, n
)-merging network. It is shown that
M
(
m, n
) ≥
n
(lg(
m
+ 1))/2, which implies that Batcher's merging networks are optimal up to a factor of 2 + ε for almost all values of
m
and
n
. The limit
r
m
= lim
n→∞
M
(
m, n
)/
n
is determined to within 1. It is also proved that
M
(2,
n
) = [3
n
/2].
The use of regression methodology for the compromise of confidential information in statistical databases
Authors: Palley Michael A. , Simonoff Jeffrey S.
Published: July 2002

A regression methodology based technique can be used to compromise confidentiality in a statistical database. This holds true even when the DBMS prevents application of regression methodology to the database. Existing inference controls, including cell restriction, perturbation, and table restriction approaches, are shown to be generally ineffective against this compromise technique. The effect of incomplete supplemental knowledge on the regression methodology based compromise technique is examined. Finally, some potential complicators of this disclosure scheme are introduced.