bluuebunny/crossref_metadata_2025 huggingface dataset:
ANALYTICITY AND ASYMPTOTIC PROPERTIES OF THE MAXWELL OPERATOR'S DISPERSION CURVES
Authors: SOCCORSI E.
Published: July 2002

The fibers of the elliptic Maxwell operator M in an infinite cylindrical wave guide are not of type (B) in Kato's sense. In spite of this phenomenon, which apparently does not appear with the other operators of mathematical physics, we prove that the dispersion curves (λn)n≥1 of M are real analytic functions. Nevertheless, it is not yet known if they are monotone. Therefore, we define the thresholds of M as the stationary points of p↦λn(p), for any n≥1. This approach generalizes the common definition of the thresholds used in acoustics. Next, the asymptotic behavior of the dispersion curves with respect to parameters p and n allow us to deduce a limiting absorption principle for M, which remains valid at the thresholds.
HOMOGENIZATION OF THE DIRAC-LIKE SYSTEM
Authors: JIANG JIANN-SHENG , LIN CHI-KUN
Published: July 2002

The homogenization of the Dirac-like system is studied. It generates memory effects. The memory (or nonlocal) kernel is described by the Volterra integral equation. When the coefficient is independent of time, the memory kernel can be characterized explicitly in terms of Young's measure. The homogenized equation can be reformulated in the kinetic form by introducing the kinetic variable. We also characterize the memory kernel when the coefficient is of separable variable.
STABILITY OF ABSTRACT LINEAR THERMOELASTIC SYSTEMS WITH MEMORY
Authors: GIORGI CLAUDIO , PATA VITTORINO
Published: July 2002

An abstract linear thermoelastic system with memory is here considered. Existence, uniqueness, and continuous dependence results are given. In presence of regular and convex memory kernels, the system is shown to be exponentially stable. An application to the Kirchhoff plate equation is given.
A GENERAL OUTPUT BOUND RESULT: APPLICATION TO DISCRETIZATION AND ITERATION ERROR ESTIMATION AND CONTROL
Authors: PATERA ANTHONY T. , RØNQUIST EINAR M.
Published: July 2002

We present a general adjoint procedure that, under certain hypotheses, provides inexpensive, rigorous, accurate, and constant-free lower and upper asymptotic bounds for the error in "outputs" which are linear functionals of solutions to linear (e.g. partial-differential or algebraic) equations. We describe two particular instantiations for which the necessary hypotheses can be readily verified. The first case — a re-interpretation of earlier work — assesses the error due to discretization: an implicit Neumann-subproblem finite element a posteriori technique applicable to general elliptic partial differential equations. The second case — new to this paper — assesses the error due to solution, in particular, incomplete iteration: a primal-dual preconditioned conjugate-gradient Lanczos method for symmetric positive-definite linear systems, in which the error bounds for the output serve as stopping criterion; numerical results are presented for additive-Schwarz domain-decomposition-preconditioned solution of a spectral element discretization of the Poisson equation in three space dimensions. In both instantiations, the computational savings are significant: since the error in the output of interest can be precisely quantified, very fine meshes, and extremely small residuals, are no longer required to ensure adequate accuracy; numerical uncertainty, though certainly not eliminated, is greatly reduced.
SPATIAL DECAY FOR SOLUTIONS OF CAUCHY PROBLEMS FOR PERTURBED HEAT EQUATIONS
Authors: SONG J. C.
Published: July 2002

This paper investigates the decay of solutions of four different perturbations of the heat equation in a semi-infinite cylinder when it is heated at the finite end. In each case a bound for the decay of "energy" is obtained, with an explicit exponential decay rate which depends on the perturbation parameter.
EXISTENCE OF STATIONARY SOLUTIONS TO AN ENERGY DRIFT-DIFFUSION MODEL FOR SEMICONDUCTOR DEVICES
Authors: FANG WEIFU , ITO KAZUFUMI
Published: July 2002

We analyze a mathematical model for semiconductors derived from the hydrodynamic model under the massless assumption. This model augments the classical drift-diffusion model by including temperature as a dependent variable. We establish the existence of stationary solutions near the equilibrium state.
ON THE INF–SUP CONDITION OF MIXED FINITE ELEMENT FORMULATIONS FOR ACOUSTIC FLUIDS
Authors: BAO WEIZHU , WANG XIAODONG , BATHE KLAUS-JÜRGEN
Published: July 2002

The objective of this paper is to present a study of the solvability, stability and optimal error bounds of certain mixed finite element formulations for acoustic fluids. An analytical proof of the stability and optimal error bounds of a set of three-field mixed finite element discretizations is given, and the interrelationship between the inf–sup condition, including the numerical inf–sup test, and the eigenvalue problem pertaining to the natural frequencies is discussed.
VIBRATIONS OF A THICK PERIODIC JUNCTION WITH CONCENTRATED MASSES
Authors: MEL'NYK TARAS A.
Published: July 2002

The asymptotic behavior (as ε→0) of eigenvalues and eigenfunctions of a mixed boundary-value problem for the Laplace operator in a plane thick periodic junction with concentrated masses is investigated. This junction consists of the junction's body and a large number N=O(ε-1) of thin rods. The density of the junction is order O(ε-α) on the rods (the concentrated masses if α>0), and O(1) outside. The results depend on the value of the parameter α(α<2, α=2, or α>2). There are three kinds of vibrations, which are present in each of these cases: vibrations, whose energy is concentrated in the junction's body; vibrations, whose energy is concentrated on the thin rods; and vibrations (pseudovibrations), in which each thin rod can have its own frequency. The frequency range, where pseudovibrations can be present, is indicated. The asymptotic estimates for the corresponding eigenfunctions and eigenvalues are proved.
SOME MAXIMUM PRINCIPLES AND SYMMETRY RESULTS FOR A CLASS OF BOUNDARY VALUE PROBLEMS INVOLVING THE MONGE-AMPÈRE EQUATION
Authors: PHILIPPIN G. A. , SAFOUI A.
Published: July 2002

In this paper we investigate a class of boundary value problems for the Monge-Ampère equation [Formula: see text] where Ω is a strictly convex bounded domain in RN, N≥2. When f=g(u)h(|∇u|2) with g and h satisfying the differential inequality [Formula: see text] we show in Sec. 2 that the function [Formula: see text] takes its maximum value on the boundary ∂Ω. This maximum principle generalizes a recent result of Ma who investigated the case f= const in R2. In Sec. 3 we investigate symmetry properties of u under specific boundary conditions or geometry of Ω.
THE HIGH FIELD ASYMPTOTICS FOR DEGENERATE SEMICONDUCTORS
Authors: ABDALLAH N. BEN , CHAKER H.
Published: July 2002

The high field limit for the semiconductor Boltzmann equation with Pauli exclusion terms is investigated. The limit problem is shown to have a unique solution for every given density. The proof relies on a linearization procedure together with a continuation argument. The density is finally proven to converge in the high field limit towards the solution of a nonlinear hyperbolic equation.
TIME SCALES IN A NON-AUTONOMOUS LINEAR DISCRETE MODEL
Authors: SANZ LUIS , DE LA PARRA RAFAEL BRAVO
Published: July 2002

In this work we extend approximate aggregation methods in time discrete linear models to the case of time varying environments. Approximate aggregation consists of describing some features of the dynamics of a general system involving many coupled variables in terms of the dynamics of a reduced system with a few "global" variables.

We present a time varying discrete model in which we distinguish two processes with different time scales. By defining the global variables as appropriate linear combinations of the state variables, we transform the system into a reduced one. The variables corresponding to the original and reduced systems can be related, therefore allowing one the study of the former in terms of the latter. The property of weak ergodicity, which has to do with the capacity of a system to become asymptotically independent of initial conditions, is explored for the original and reduced systems.

The general method is also applied to aggregate a time-dependent multiregional model which appears in the field of population dynamics in two different cases: Fast migration with respect to demography and fast demography with respect to migration.
ON A NEW SCALING FOR SEMICONDUCTOR DEVICE EQUATIONS AND ITS ASYMPTOTIC ANALYSIS
Authors: HENRY J. , LOURO B. , VIEL A. , YVON J. P.
Published: July 2002

The aim of this paper is to present a new scaling which is appropriate for modeling reverse biased semiconductor devices with moderately high applied potential and its asymptotic analysis. This scaling was motivated by the modeling of oxygen sensors. It is compared to the ones leading to (a) electroneutrality, (b) the existence of a depletion zone. With our scaling such a zone may appear within a boundary layer. A particular attention is paid to the qualitative dependence of the asymptotic solution to the boundary value of the concentration of carrier.
HODGE DECOMPOSITIONS ON THE BOUNDARY OF NONSMOOTH DOMAINS: THE MULTI-CONNECTED CASE
Authors: BUFFA A.
Published: July 2002

This paper concerns the characterization of tangential traces for the space H(curl, Ω), when Ω is a Lipschitz polyhedron in ℝ3 under general topology assumptions. Suitable spaces of tangential vector fields are introduced and characterized. Hodge decompositions are provided and they involve the first cohomology space of the boundary Γ. Such a space is characterized and a basis is furnished.
A GENERALIZED MEAN FIELD APPROACH TO THE POLARON
Authors: NIETO J.
Published: July 2002

In this paper we introduce a generalized mean field model to describe the motion of an electron in a lattice of charged ions with long range electrostatic interaction. The local and global in time existence and uniqueness of this model and its variational formulation are analyzed.
EXISTENCE RESULTS FOR L1 DATA OF SOME QUASI-LINEAR PARABOLIC PROBLEMS WITH A QUADRATIC GRADIENT TERM AND SOURCE
Authors: ANDREU F. , DE LÉON S. SEGURA , BOCCARDO L. , ORSINA L.
Published: July 2002

In this paper we deal with a Cauchy–Dirichlet quasilinear parabolic problem containing a gradient lower order term; namely, ut - Δu + |u|2 γ-2u |∇u|2 = |u|p-2u. We prove that if p ≥ 1, γ ≥ ½ and p < 2 γ + 2, then there exists a global weak solution for all initial data in L1 (Ω). We also see that there exists a non-negative solution if the initial datum is non-negative.
NUMERICAL APPROACH OF THERMOMECHANICAL COUPLED PROBLEMS WITH MOVING BOUNDARIES IN THEORETICAL GLACIOLOGY
Authors: CALVO N. , DURANY J. , VÁZQUEZ C.
Published: July 2002

In this work we propose a new numerical method for solving a thermomechanical coupled problem which arises as a mathematical model for the evolution of ice sheets profiles and the corresponding temperatures. From the accumulation–ablation ratio, the atmospheric temperature and the geothermic flux, the ice sheet profile is the solution of a moving boundary problem governed by a nonlinear convection–diffusion equation. Moreover, the mathematical model which governs the temperature distribution involves three nonlinearities: a reaction term due to the viscous dissipation, a Signorini boundary condition associated to the geothermic flux and an enthalpy term issued from the two-phase Stefan formulation of the polythermal regime. The problems are discretized in time with upwind characteristics schemes and in space with finite elements. The nonlinearities are solved either by fixed point methods or by duality techniques. Several numerical simulation examples involving real data sets issued from the Antartic ice sheet are shown.
JUMP PROCESSES UNDER PARTIAL OBSERVATIONS: FINITE STATE APPROXIMATION
Authors: GERARDI A. , TARDELLI P.
Published: July 2002

A filtering problem when the pair state-observations is a Markov process is analyzed. Extending a Kunita result to our frame, strong uniqueness for the filtering equation is obtained. In the discrete case, a finite state approximation for the filter is considered and an estimate of the approximation error is given.
CLASSICAL SOLVABILITY OF THE TWO-PHASE STEFAN PROBLEM IN A VISCOUS INCOMPRESSIBLE FLUID FLOW
Authors: KUSAKA YOSHIAKI , TANI ATUSI
Published: July 2002

In this paper we study the two-phase Stefan problem for a viscous incompressible fluid which is a model of melting a solid to a liquid or of soldificating a liquid to a solid with a liquid flowing. The unique solvability is established in Hölder spaces locally in time. The method of the proof is rather standard, however the result obtained is completely new: the existence in the Hölder spaces with the same Hölder exponents as the data and the uniqueness also in the same Hölder spaces.
DISCRETE AND CONTINUOUS COMPARTMENTAL MODELS OF CELLULAR POPULATIONS
Authors: PRIMICERIO M. , TALAMUCCI F.
Published: July 2002

We consider a biological system where several families of cells, differentiated by their activity state and reaction to external factors acting on the system, are present. The dynamics of cell populations is modelled by a compartmental approach, starting from the case of finite number of classes and passing to the continuum range of the variables. In a frame of special attention devoted to the mass balance, the evolution of the system is described by the variation of mass of each species. The well-posedness of the mathematical models is proved.
A NUMERICAL METHOD FOR SOLVING NONLINEAR PROBLEMS
Authors: RAMM A. G.
Published: July 2002

A nonlinear equation on a Banach space is written as a linear equation with a linear operator depending on the unknown solution. Inverting this linear operator by one of the known methods, one obtains an equation which, in some cases, is much better for the numerical solution than the original equation. Some theorems about convergence of an iterative process for solving the transformed equation are proved. Examples of applications are given.
DIMENSIONAL REDUCTION FOR THE BEAM IN ELASTICITY ON AN UNBOUNDED DOMAIN
Authors: LIU KANG-MAN
Published: July 2002

The dimensional reduction method is investigated for solving boundary value problems of the beam in elasticity on domain Ωd:=ℝ×(-d,d) by replacing the problems with systems of equations in ℝ. The basic tool to analyze the dimensional reduction technique for problems in an unbounded domain Ωd is using of Fourier transformation. The error estimates between the exact solution and the dimensionally reduced solution in a Hilbert space are obtained when d and N are given. The rates of convergence depend on the smoothness of the data on the faces.
A QUASI-STATIC TWO-DIMENSIONAL INDUCTION HEATING PROBLEM II: NUMERICAL ANALYSIS
Authors: PARIETTI C. , RAPPAZ J.
Published: July 2002

We consider a nonlinear elliptic–parabolic system which stems from the modelling of heat induction processes in which a sinusoidal electromagnetic field is applied at the boundary of the inductor. The magnetic field satisfies an elliptic equation whereas the temperature equation is parabolic. These two equations are coupled due to the Joule effect and to the conductivity dependence on temperature. A Galerkin method for our problem is analyzed and shown to yield error estimates in L2 and H1.
SUPERCELL RHEED CALCULATIONS
Authors: MAKSYM P. A.
Published: July 2002

Efficient calculational techniques for reflection high energy electron diffraction (RHEED) are reported for surfaces with large periodic supercells. A fast Fourier transform approach enables the computer time scaling of a conventional RHEED calculation to be reduced to n2 log (n), where n is the number of diffracted beams used in the calculation. The special technique needed to implement this for arbitrary incident azimuths with symmetry optimization is detailed. A Green's function method is also introduced which is particularly suitable for calculations for imperfect surfaces. This combines the conventional approach to RHEED for dealing with substrate diffraction with a Green's function treatment for an imperfect surface of supercells and has n log (n) time scaling. Techniques for matching the results of the conventional and Green's function treatments at the substrate–surface interface are given. In addition, numerical procedures for solving the resulting equations are described and a selection of illustrative results is presented.
DIFFERENTIAL-REFLECTANCE SPECTROSCOPY AND REFLECTANCE-ANISOTROPY SPECTROSCOPY ON SEMICONDUCTOR SURFACES
Authors: CHIARADIA P. , SOLE R. DEL
Published: July 2002

The development and the state of the art of surface methods based on the reflection of light are briefly reviewed. A short account is given of the main experimental and theoretical results obtained on semiconductor surfaces over about three decades.
COMPOSITIONAL VERIFICATION OF MULTI-AGENT SYSTEMS: A FORMAL ANALYSIS OF PRO-ACTIVENESS AND REACTIVENESS
Authors: JONKER CATHOLIJN M. , TREUR JAN
Published: July 2002

A compositional method is presented for the verification of multi-agent systems. The advantages of the method are the well-structuredness of the proofs and the reusability of parts of these proofs in relation to reuse of components. The method is illustrated for an example multi-agent system, consisting of co-operative information gathering agents. This application of the verification method results in a formal analysis of pro-activeness and reactiveness of agents, and shows which combinations of pro-activeness and reactiveness in a specific type of information agents lead to a successful cooperation.
MEAN-VARIANCE HEDGING FOR PARTIALLY OBSERVED DRIFT PROCESSES
Authors: PHAM HUYÊN
Published: July 2002

We consider the mean-variance hedging when an investor observes just the stock prices. We explain how the theory developed in Gouriéroux, Laurent and Pham (1998) and Rheinländer and Schweizer (1997) can be extended to this framework. We then focus to a diffusion model when drift of stock prices are not observed directly but only through a measurement process. By using filtering techniques, we obtain explicit formulae for optimal mean-variance hedging strategies and for the associated minimal risk. Closed-form expressions are provided in the case of a Bayesian investor and when the stock drift is modelled as a linear Gaussian process.
Converting nested algebra expressions into flat algebra expressions
Authors: Paredaens Jan , Van Gucht Dirk
Published: July 2002

Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive power of the nested algebra relative to its operation on flat relational databases. We show that the flat relational algebra is rich enough to extract the same “flat information” from a flat database as the nested algebra does. Theoretically, this result implies that recursive queries such as the transitive closure of a binary relation cannot be expressed in the nested algebra. Practically, this result is relevant to (flat) relational query optimization.
Lexical ambiguity and information retrieval
Authors: Krovetz Robert , Croft W. Bruce
Published: July 2002

Lexical ambiguity is a pervasive problem in natural language processing. However, little quantitative information is available about the extent of the problem or about the impact that it has on information retrieval systems. We report on an analysis of lexical ambiguity in information retrieval test collections and on experiments to determine the utility of word meanings for separating relevant from nonrelevant documents. The experiments show that there is considerable ambiguity even in a specialized database. Word senses provide a significant separation between relevant and nonrelevant documents, but several factors contribute to determining whether disambiguation will make an improvement in performance. For example, resolving lexical ambiguity was found to have little impact on retrieval effectiveness for documents that have many words in common with the query. Other uses of word sense disambiguation in an information retrieval context are discussed.
Algorithm 717: Subroutines for maximum likelihood and quasi-likelihood estimation of parameters in nonlinear regression models
Authors: Bunch David S. , Gay David M. , Welsch Roy E.
Published: July 2002

We present FORTRAN 77 subroutines that solve statistical parameter estimation problems for general nonlinear models, e.g., nonlinear least-squares, maximum likelihood, maximum quasi-likelihood, generalized nonlinear least-squares, and some robust fitting problems. The accompanying test examples include members of the generalized linear model family, extensions using nonlinear predictors (“nonlinear GLIM”), and probabilistic choice models, such as linear-in-parameter multinomial probit models. The basic method, a generalization of the NL2SOL algorithm for nonlinear least-squares, employs a model/trust-region scheme for computing trial steps, exploits special structure by maintaining a secant approximation to the second-order part of the Hessian, and adaptively switches between a Gauss-Newton and an augmented Hessian approximation. Gauss-Newton steps are computed using a corrected seminormal equations approach. The subroutines include variants that handle simple bounds on the parameters, and that compute approximate regression diagnostics.
RE2C: a more versatile scanner generator
Authors: Bumbulis Peter , Cowan Donald D.
Published: July 2002

It is usually claimed that lexical analysis routines are still coded by hand, despite the widespread availability of scanner generators, for efficiency reasons. While efficiency is a consideration, there exist freely available scanner generators such as GLA [Gray 1988] that can generate scanners that are faster than most hand-coded ones. However, most generated scanners are tailored for a particular environment, and retargeting these scanners to other environments, if possible, is usually complex enough to make a hand-coded scanner more appealing. In this paper we describe RE2C, a scanner generator that not only generates scanners that are faster (and usually smaller) than those produced by any other scanner generator known to the authors, including GLA, but that also adapt easily to any environment.
Why looking isn't always seeing
Authors: Petre Marian
Published: July 2002

Many believe that visual programming techniques are quite close to developers. This article reports on some fascinating research focusing on understanding how textual and visual representations for software differ in effectiveness. Among other things, it is determined that the differences lie not so much in the textual-visual distinction as in the degree to which specific representations support the conventions experts expect.
WordNet
Authors: Miller George A.
Published: July 2002

Because meaningful sentences are composed of meaningful words, any system that hopes to process natural languages as people do must have information about words and their meanings. This information is traditionally provided through dictionaries, and machine-readable dictionaries are now widely available. But dictionary entries evolved for the convenience of human readers, not for machines. WordNet
1
provides a more effective combination of traditional lexicographic information and modern computing. WordNet is an online lexical database designed for use under program control. English nouns, verbs, adjectives, and adverbs are organized into sets of synonyms, each representing a lexicalized concept. Semantic relations link the synonym sets [4].
The building blocks for specifying communication behavior of complex objects
Authors: Liu Ling , Meersman Robert
Published: July 2002

Communication behavior represents dynamic evolution and cooperation of a group of objects in accomplishing a task. It is an important feature in object-oriented systems. We propose the concept of activity as a basic building block for declarative specification of communication behavior in object-oriented database systems, including the temporal ordering of message exchanges within object communication and the behavioral relationships between activity executions. We formally introduce two kinds of activity composition mechanisms:activity specializationand activityaggregationfor abstract implementation of communication behavior. The former is suited for behavioral refinement of existing activities into specialized activities. The latter is used for behavioral composition of simpler activities into complex activities, and ultimately, into the envisaged database system. We use first-order temporal logic as an underlying formalism for specification of communication constraints. The well known Air-traffic-control case is used as a running example to highlight the underlying concepts, to illustrate the usefulness, and to assess the effectiveness of the activity model for declarative specification of communication behavior in the relevant universe of discourse. We also propose a methodological framework for integrating activity schema with entity schema in an object-oriented design environment.
Software protection and simulation on oblivious RAMs
Authors: Goldreich Oded , Ostrovsky Rafail
Published: July 2002

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this paper, we provide theoretical treatment of software protection. We reduce the problem of software protection to the problem of efficient simulation on
oblivious
RAM.

A machine is
oblivious
if thhe sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, the movement is independent of the actual input.)
What is the slowdown in the running time of a machine, if it is required to be oblivious?
In 1979, Pippenger and Fischer showed how a two-tape
oblivious
Turing Machine can simulate, on-line, a one-tape Turing Machine, with a logarithmic slowdown in the running time. We show an analogous result for the random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of an arbitrary RAM by a probabilistic
oblivious
RAM with a polylogaithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound.
Closure properties of constraints
Authors: Jeavons Peter , Cohen David , Gyssens Marc
Published: July 2002

Many combinatorial search problems can be expressed as “constraint satisfaction problems” and this class of problems is known to be NP-complete in general. In this paper, we investigate the subclasses that arise from restricting the possible constraint types. We first show that any set of constraints that does not give rise to an NP-complete class of problems must satisfy a certain type of algebraic closure condition. We then investigate all the different possible forms of this algebraic closure property, and establish which of these are sufficient to ensure tractability. As examples, we show that all known classes of tractable constraints over finite domains can be characterized by such an algebraic closure property. Finally, we describe a simple computational procedure that can be used to determine the closure properties of a given set of constraints. This procedure involves solving a particular constraint satisfaction problem, which we call an “indicator problem.”
Variance reduction applied to product form multiclass queuing networks
Authors: Tuffin Bruno
Published: July 2002

Performance of product-form multiclass queuing networks can be determined from normalization constants. For large models, the evaluation of these performance metrics is not possible because of the required amount of computer resources (either by using normalization constants or by using MVA approaches). Such large models can be evaluated with Monte Carlo summation and integration methods. This article proposes two cluster sampling Monte Carlo techniques to deal with such models. First, for a particular type of network, we propose a variance reduction technique based on antithetic variates. It leads to an improvement of Ross, Tsang and Wang's algorithm which is designed to analyze the same family of models. Second, for a more general class of models, we use a mixture of Monte Carlo and quasi-Monte Carlo methods to improve the estimate with respect to Monte Carlo alone.
Arithmetic coding revisited
Authors: Moffat Alistair , Neal Radford M. , Witten Ian H.
Published: July 2002

Over the last decade, arithmetic coding has emerged as an important compression tool. It is now the method of choice for adaptive coding on myltisymbol alphabets because of its speed, low storage requirements, and effectiveness of compression. This article describes a new implementation of arithmetic coding that incorporates several improvements over a widely used earlier version by Witten, Neal, and Cleary, which has become a
de facto
standard. These improvements include fewer multiplicative operations, greatly extended range of alphabet sizes and symbol probabilities, and the use of low-precision arithmetic, permitting implementation by fast shift/add operations. We also describe a modular structure that separates the coding, modeling, and probability estimation components of a compression system. To motivate the improved coder, we consider the needs of a word-based text compression program. We report a range of experimental results using this and other models. Complete source code is available.
The multilevel relational (MLR) data model
Authors: Sandhu Ravi , Chen Fang
Published: July 2002

Many multilevel relational models have been proposed; different models offer different advantages. In this paper, we adapt and refine several of the best ideas from previous models and add new ones to build the new Multilevel Relational (MLR) data model. MLR provides multilevel relations with element-level labeling as a natural extension of the traditional relational data model. MLR introduces several new concepts (notably, data-borrow integrity and the UPLEVEL statement) and significantly redefines existing concepts (polyinstantiation and referential integrity as well as data manipulation operations). A central contribution of this paper is proofs of soundness, completeness, and security of MLR. A new
data-based
semantics is given for the MLR data model by combining ideas from SeaView, belief-based semantics, and LDV. This new semantics has the advantages of both eliminating ambiguity and retaining upward information flow. MLR is secure, unambiguous, and powerful. It has five integrity properties and five operations for manipulating multilevel relations. Soundness, completeness, and security show that any of the five database manipulation operations will keep database states legal (i.e., satisfy all integrity properties), that every legal database state can be constructed, and that MLR is noninterfering. The expressive power of MLR also compares favorably with several other models.
Minimum cost adaptive synchronization
Authors: Mascarenhas Edward , Knop Felipe , Pasquini Reuben , Rego Vernon
Published: July 2002

We present a novel adaptive synchronization algorithm, called the minimum average cost (MAC) algorithm, in the context of the parasol parallel simulation system. ParaSol is a multithreaded system for parallel simulation on shared- and distributed-memory environments, designed to support domain-specific Simulation Object Libraries. The proposed MAC algorithm is based on minimizing the cost of synchronization delay and rollback at a process, whenever its simulation driver must decide whether to either proceed optimistically or to delay processing. In the former case the risk is rollback cost, in the event of a straggler's arrival. In the latter case the risk is unnecessary delay, in the event a latecomer is not a straggler. In addition to the MAC algorithm and an optimal delay computation model, we report on some early experiments comparing the performance of MAC-based adaptive synchronization to optimistic synchronization.
Estimation of software reliability by stratified sampling
Authors: Podgurski Andy , Masri Wassim , McCleese Yolanda , Wolff Francis G. , Yang Charles
Published: July 2002

A new approach to software reliability estimation is presented that combines operational testing with stratified sampling in order to reduce the number of program executions that must be checked manually for conformance to requirements. Automatic cluster analysis is applied to execution profiles in order to stratify captured operational executions. Experimental results are reported that suggest this approach can significantly reduce the cost of estimating reliability.
Answering queries without revealing secrets
Authors: Sicherman George L. , De Jonge Wiebren , Van de Riet Reind P.
Published: July 2002

Question-answering systems must often keep certain information secret. This can be accomplished, for example, by sometimes refusing to answer a query. Here the danger of revealing a secret by refusing to answer a query is investigated. First several criteria that can be used to decide whether or not to answer a query are developed. Then it is shown which of these criteria are safe if the questioner knows nothing at all about what is kept secret. Furthermore, it is proved that one of these criteria is safe even if the user of the system knows which information is to be kept secret.
On the Truncation Error of Discrete Approximations to the Solutions of Dirichlet Problems in a Domain with Corners
Authors: Laasonen Pentti
Published: July 2002

The solution for a Dirichlet problem on a given plane domain and with given boundary values is usually approximated in numerical computation by its discrete analog defined and determined on an approximating set of net points. It can be proved that the approximation thus obtained converges to the exact solution, when the net becomes denser indefinitely, independently of the domain and the boundary values subject to rather weak conditions. Nevertheless, the irregularity of the boundary curve and of the boundary values affects strongly the convergence rate. For instance, if both are analytic and if a proper boundary interpolation scheme is used, then the simplest net analog leads to an error which decreases asymptotically at least proportional to the square of the mesh constant
h
, as proved by Gerschgorin [2] and Collatz [1]:δ

h

=
O
(

h
2

).
Generation of Spherical Bessel Functions in Digital Computers
Authors: Corbató Fernando J. , Uretsky Jack L.
Published: July 2002

A method of computation for spherical Bessel functions of real and imaginary argument is given which is especially suitable for high speed digital computers. The accuracy and convergence are examined and criterion formulas are given. A procedure based on the Wronskian is used to simplify the final normalization.
Empirical Tests of an Additive Random Number Generator
Authors: Green Bert F. , Smith J. E. Keith , Klem Laura
Published: July 2002

Several empirical tests were made of the apparent randomness of numbers generated by the additive process

X
j

= (
X

j
-1

+
X

j
-n

) mod 1, where the X's are positive fractions. The results show that the numbers are uniformly distributed on the unit interval and that there is no significant serial correlation in the sequence. However, for
n
< 16, a test of run lengths indicates nonrandomness. This difficulty can be overcome by discarding alternate numbers.
Tables of the Generalized Stirling Numbers of the First Kind
Authors: Pickard William F.
Published: July 2002

The generalized Stirling numbers of the first kind are defined, certain of their basic properties are discussed, and tables are given for the square grid
k
= 0(1)10 and
j
= 0(1)10 with
l
= -10(1)10.
Statistical Estimation of the Numerical Solution of a Fredholm Integral Equation of the First Kind
Authors: Strand Otto Neall , Westwater Ed. R.
Published: July 2002

A method for the numerical solution of a Fredholm integral equation of the first kind is derived and illustrated. The method employs an a priori constraint vector together with covariances of both the constraint vector and the measurement errors. The method automatically incorporates an optimum amount of smoothing in the sense of maximum-likelihood estimation. The problem of obtaining optimum basis vectors is discussed. The trace of the covariance matrix of the error in the solution is used to estimate the accuracy of the results. This trace is used to derive a quality criterion for a set of measurements and a given set of constraint statistics. Examples are given in which the behavior of the solution as obtained from a specific integral equation is studied by the use of random input errors to simulate measurement errors and statistical sampling. The quality criterion and behavior of the trace of the error covariance matrix for various bases is also illustrated for the equation being considered.
A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance
Authors: Montanari U.
Published: July 2002

The problem of obtaining the skeleton of a digitized figure is reduced to an optimal policy problem. A hierarchy of methods of defining the skeleton is proposed; in the more complicated ones, the skeleton is relatively invariant under rotation. Two algorithms for computing the skeleton are defined, and the corresponding computer programs are compared. A criterion is proposed for determining the most significant skeleton points.
The Complexity of Near-Optimal Graph Coloring
Authors: Garey M. R. , Johnson D. S.
Published: July 2002

Graph coloring problems, in which one would like to color the vertices of a given graph with a small number of colors so that no two adjacent vertices receive the same color, arise in many applications, including various scheduling and partitioning problems. In this paper the complexity and performance of algorithms which construct such colorings are investigated. For a graph
G
, let χ(
G
) denote the minimum possible number of colors required to color
G
and, for any graph coloring algorithm
A
, let
A
(
G
) denote the number of colors used by
A
when applied to
G
. Since the graph coloring problem is known to be “NP-complete,” it is considered unlikely that any efficient algorithm can guarantee
A
(
G
) = χ(
G
) for all input graphs. In this paper it is proved that even coming close to khgr;(
G
) with a fast algorithm is hard. Specifically, it is shown that if for some constant
r
< 2 and constant
d
there exists a polynomial-time algorithm
A
which guarantees
A
(
G
) ≤
r
·χ(
G
) +
d
, then there also exists a polynomial-time algorithm
A
which guarantees
A
(
G
) = χ(
G
).
Public-key cryptography and password protocols
Authors: Halevi Shai , Krawczyk Hugo
Published: July 2002

We study protocols for strong authentication and key exchange in asymmetric scenarios where the authentication server possesses ~a pair of private and public keys while the client has only a weak human-memorizable password as its authentication key. We present and analyze several simple password authentication protocols in this scenario, and show that the security of these protocols can be formally proven based on standard cryptographic assumptions. Remarkably, our analysis shows optimal resistance to off-line password guessing attacks under the choice of suitable public key encryption functions. In addition to user authentication, we describe ways to enhance these protocols to provide two-way authentication, authenticated key exchange, defense against server's compromise, and user anonymity. We complement these results with a proof that strongly indicates that public key techniques are unavoidable for password protocols that resist off-line guessing attacks.

As a further contribution, we introduce the notion ofpublic passwordsthat enables the use of the above protocols in situations where the client's machine does not have the means to validate the server's public key. Public passwords serve as "hand-held certificates" that the user can carry without the need for specal computing devices.
On the foundations of the universal relation model
Authors: Maier David , Ullman Jeffrey D. , Vardi Moshe Y.
Published: July 2002

The universal relation model aims at achieving complete access-path independence in relational databases by relieving the user of the need for logical navigation among relations. We clarify the assumptions underlying it and explore the approaches suggested for implementing it.

The essential idea of the universal relation model is that access paths are embedded in attribute names. Thus attribute names must play unique “roles.” Furthermore, it assumes that for every set of attributes there is a basic relationship that the user has in mind. The user's queries refer to these basic relationships rather than to the underlying database.

Two fundamentally different approaches to the universal relation model have been taken. According to the first approach, the user's view of the database is a universal relation or many universal relations, about which the user poses queries. The second approach sees the model as having query-processing capabilities that relieve the user of the need to specify the logical access path. Thus, while the first approach gives a denotational semantics to query answering, the second approach gives it an operational semantics. We investigate the relationship between these two approaches.
Why are some diagrams easier to work with? Effects of diagrammatic representation on the cognitive intergration process of systems analysis and design
Authors: Hahn Jungpil , Kim Jinwoo
Published: July 2002

Various diagrams have been used heavily in systems analysis and design without proper verification of their usability. However, different diagrammatic representations of the same information may vary in the computational efficiency of working with these diagrams. The objective of this research was to explore the effects of diagrammatic representations on the task of integrating multiple diagrams. The domain of systems analysis and design was used to generate examples and test the theory. A cognitive model of diagram integration was proposed, and an experimental study was conducted, both to explore the effects of representa-tional features of diagrams on the cognitive process of diagram integration. Results of the experiment show that the representational features of the diagrams acted as the criteria for selecting among various methods for analyzing and designing the integrated diagram. In addition, the difference in the selected methods resulted in different task performances in terms of analysis and design errors. This article concludes with the implications of the results for the development of cognitively compelling diagrams.
On Hoare logic and Kleene algebra with tests
Authors: Kozen Dexter
Published: July 2002

We show that Kleene algebra with tests (KAT) subsumes propositional Hoare logic (PHL). Thus the specialized syntax and deductive apparatus of Hoare logic are inessential and can be replaced by simple equational reasoning. In addition, we show that all relationally valid inference rules are derivable in KAT and that deciding the relational validity of such rules is
PSPACE
-complete.
Hardware protection against software piracy
Authors: Maude Tim , Maude Derwent
Published: July 2002

A system that prevents illicit duplication of proprietary software is suggested. It entails the customization of the programs for each computer by encryption. The use of a public key cryptogram for this purpose means that anyone can customize programs, but neither other programmers nor the people having complete access to the target computer can obtain copies that will run on other machines. A possible implementation of the system is considered in some detail. It is based on a hardware security unit that is attached to the computer and that decrypts and obeys some parts of the program.
Time, clocks, and the ordering of events in a distributed system
Authors: Lamport Leslie
Published: July 2002

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.
Illumination for computer generated pictures
Authors: Phong Bui Tuong
Published: July 2002

The quality of computer generated images of three-dimensional scenes depends on the shading technique used to paint the objects on the cathode-ray tube screen. The shading algorithm itself depends in part on the method for modeling the object, which also determines the hidden surface algorithm. The various methods of object modeling, shading, and hidden surface removal are thus strongly interconnected. Several shading techniques corresponding to different methods of object modeling and the related hidden surface algorithms are presented here. Human visual perception and the fundamental laws of optics are considered in the development of a shading rule that provides better quality and increased realism in generated images.
Efficient string matching
Authors: Aho Alfred V. , Corasick Margaret J.
Published: July 2002

This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
A note on minimal length polygonal approximation to a digitized contour
Authors: Montanari U.
Published: July 2002

A method for extracting a smooth polygonal contour from a digitized image is illustrated. The ordered sequence of contour points and the connection graph of the image are first obtained by a modified Ledley algorithm in one image scan. A minimal perimeter polygon subjected to specified constraints is then chosen as the approximating contour. The determination of the minimal polygon can be reduced to a nonlinear programming problem, solved by an algorithm which takes into account the weak bonds between variables. Some examples are presented, and the corresponding computing times are listed.