bluuebunny/crossref_metadata_2025 huggingface dataset:
AN ENTROPY-BASED FINITE DIFFERENCE METHOD FOR THE ENERGY TRANSPORT SYSTEM
Authors: RINGHOFER CHRISTIAN
Published: July 2002

This paper is concerned with the spatial discretization of the energy transport model for charged particles. A finite difference method is given which dissipates the entropy of the system on the discrete level, thus exhibiting the correct long-time behavior of the solution. This method represents a generalization of the Scharfetter–Gummel exponential fitting method for the drift-diffusion system.
NUMERICAL ANALYSIS OF SOME DECOUPLING TECHNIQUES FOR THE APPROXIMATION OF THE UNSTEADY FLUID STRUCTURE INTERACTION
Authors: GRANDMONT C. , GUIMET V. , MADAY Y.
Published: July 2002

This paper deals with the numerical analysis of some algorithms for the simulation of the interaction between a fluid and a structure in the case where the deformation of the structure induces an evolution in the fluid domain. This is a highly nonlinear problem and the algorithms of time decoupling are very numerous and not completely well understood. We study three of them for a one-dimensional representative problem. We prove that the considered algorithms are stable and we also prove that one of them is convergent.
ON THE ZERO THICKNESS LIMIT OF THIN FERROMAGNETIC FILMS WITH SURFACE ANISOTROPY ENERGY
Authors: HAMDACHE K. , TILIOUA M.
Published: July 2002

We discuss the behaviour, when the thickness ε tends to 0, of thin ferromagnetic films with surface anisotropy energy. The model equations are given by the Landau–Lifshitz equation coupled to Maxwell equations with magnetic polarization. We consider two types of materials: flat and slender cylinders. Two scalings for the surface anisotropy coefficient are used. In the first one it is assumed that the coefficient is of order ε while in the second one we suppose that it is of order 1. We prove global existence of solutions and show that the zero-thickness limit induces new effects. For example, for slender media we get a nonlocal effect for the magnetic excitation while for flat media we obtain a one-dimensional magnetic field.
LONG TIME ASYMPTOTICS FOR THE SEMICONDUCTOR VLASOV–POISSON–BOLTZMANN EQUATIONS
Authors: CARPIO A. , CEBRIAN E. , MUSTIELES F. J.
Published: July 2002

In this paper we analyze the long time behavior of solutions to the one-dimensional Vlasov–Poisson–Boltzmann (VPB) equations for semiconductors in unbounded domains when only one type of carriers (electrons) are considered. We prove that the distribution of electrons tends for large times to a steady state of the VPB equations with vanishing collision term and the same total charge as the initial data. In the proof of the main result, the conservation law of charge, the balance of energy and entropy inequalities are rigorously derived. An important argument in the proof is to use a Lyapunov-type functional related to these physical quantities.
GENERALIZED DISCRETE VELOCITY MODELS
Authors: GÖRSCH D.
Published: July 2002

Starting from a mesoscopic principle of moment conservation, discrete Boltzmann collision operators Jh are constructed, which both converge to bounded collision operators JΩ and have the same collision invariants as the original Boltzmann collision operator J. The crucial point of this construction is the application of a weak formulation of the gain operator to remove the post-collision velocities from it as well as the development of moment conserving integration formulas for the approximation of surface integrals over the unit sphere. Finally two applications for the discrete operators are presented.
BASIC ESTIMATES FOR A FRONT TRACKING ALGORITHM FOR GENERAL 2×2 CONSERVATION LAWS
Authors: ANCONA F. , MARSON A.
Published: July 2002

We analyze a front tracking algorithm for 2×2 systems of conservation laws with non-genuinely nonlinear characteristic fields. The convergence of the corresponding approximate Riemann solvers is established and the basic interaction estimates for the front tracking approximate solutions are provided.
NUMERICAL EVALUATION OF FEM WITH APPLICATION TO THE 1-D ADVECTION–DIFFUSION PROBLEM
Authors: SANGALLI GIANCARLO
Published: July 2002

In this paper we present a numerical procedure to evaluate the efficiency of finite element numerical methods. We improve some of the ideas proposed in previous works and give a partly theoretical, partly empirical justification in a general framework. The proposed procedure performs an eigenvalue computation, and requires the knowledge of the behavior of the exact operator in order to choose proper norms for the evaluations. In the experiments we focus our attention on the 1-D advection–diffusion problem: we show that our numerical procedure actually gives very sharp indications about the optimality of the tested numerical methods.
NUMERICAL BLOW-UP FOR A NONLINEAR PROBLEM WITH A NONLINEAR BOUNDARY CONDITION
Authors: FERREIRA RAÚL , GROISMAN PABLO , ROSSI JULIO D.
Published: July 2002

In this paper we study numerical approximations for positive solutions of a nonlinear heat equation with a nonlinear boundary condition. We describe in terms of the nonlinearities when solutions of a semidiscretization in space exist globally in time and when they blow up in finite time. We also find the blow-up rates and the blow-up sets. In particular we prove that regional blow-up is not reproduced by the numerical scheme. However, in the appropriate variables we can reproduce the correct blow-up set when the mesh parameter goes to zero.
ACOUSTIC DIFFRACTION BY A PLATE IN A UNIFORM FLOW
Authors: BONNET-BENDHIA A. S. , DAHI L. , LUNEVILLE E. , PAGNEUX V.
Published: July 2002

We present a mathematical framework for the problem of the acoustic diffraction by a plate located in a duct, in the presence of a uniform flow. The model is based on a velocity potential representation outside a vortex sheet which is induced by the trailing edge of the plate. Using limiting absorption techniques and singular functions decompositions, we show how to get a theoretical and numerical well-suited formulation.
UNIFORM INF–SUP CONDITIONS FOR THE SPECTRAL DISCRETIZATION OF THE STOKES PROBLEM
Authors: BERNARDI C. , MADAY Y.
Published: July 2002

In standard spectral discretizations of the Stokes problem, error estimates on the pressure are slightly less accurate than the best approximation estimates, since the constant of the Babuška–Brezzi inf–sup condition is not bounded independently of the discretization parameter. In this paper, we propose two possible discrete spaces for the pressure: for each of them, we prove a uniform inf–sup condition, which leads in particular to an optimal error estimate on the pressure.
MODELLING THREE-DIMENSIONAL GROWTH OF BRAIN TUMOURS FROM TIME SERIES OF SCANS
Authors: TRACQUI PHILIPPE , MENDJELI MAHIDINE
Published: July 2002

The development of brain tumours, after diagnosis, is routinely recorded by different medical imaging techniques like computerised tomography (CT) or magnetic resonance imaging (MRI). However, it is only through the formulation of mathematical models that an analysis of the spatio-temporal tumour growth revealed on each patient serial scans can lead to a quantification of parameters characterising the proliferative and expensive dynamic of the brain tumour. This paper reviews some of the results and limitations encountered in modelling the different stages of a brain tumour growth, namely before and after diagnosis and therapy. It extends an original two-dimensional approach by considering three-dimensional growth of brain tumours submitted to the spatial constraints exerted by the skull and ventricles boundaries. Considering the dynamic of both the pre- and post-diagnosis stages, the tumour growth patterns obtained with various combinations of nonlinear growth rates and cellular diffusion laws are considered and compared to real MRI scans taken in a patient with a glioblastoma and having undergone radiotherapy. From these simulations, we characterise the effects of different therapies on survival durations, with special attention to the effect of cell diffusion inside the resected brain region when surgical resection of the tumour is carried out.
PARTIAL SELECTIVE REDUCED INTEGRATION SCHEMES AND KINEMATICALLY LINKED INTERPOLATIONS FOR PLATE BENDING PROBLEMS
Authors: AURICCHIO FERDINANDO , LOVADINA CARLO
Published: July 2002

Some finite elements for the approximation to the solution of the Reissner–Mindlin plate problem are presented. All of them take advantage of a stabilization technique recently proposed by Arnold and Brezzi. Moreover, a kinematically linked interpolation approach has been used to improve the convergence features. A general theoretical analysis of stability and convergence is also provided, together with extensive numerical tests.
TRANSMISSION PROBLEMS FOR THE LAPLACE AND ELASTICITY OPERATORS: REGULARITY AND BOUNDARY INTEGRAL FORMULATION
Authors: NICAISE SERGE , SÄNDIG ANNA-MARGARETE
Published: July 2002

This paper is devoted to some transmission problems for the Laplace and linear elasticity operators in two- and three-dimensional nonsmooth domains. We investigate the behaviour of harmonic and linear elastic fields near geometrical singularities, especially near corner points or edges where the interface intersects with the boundaries. We give a short overview about the known results for 2-D problems and add new results for 3-D problems. Numerical results for the calculation of the singular exponents in the asymptotic expansion are presented for both two- and three-dimensional problems. Some spectral properties of the corresponding parameter depending operator bundles are also given. Furthermore, we derive boundary integral equations for the solution of the transmission problems, which lead finally to "local" pseudo-differential operator equations with corresponding Steklov–Poincaré operators on the interface. We discuss their solvability and uniqueness. The above regularity results are used in order to characterize the regularity of the solutions of these integral equations.
SOME ASYMPTOTICS FOR A REACTIVE NAVIER–STOKES–POISSON SYSTEM
Authors: DUCOMET B.
Published: July 2002

We prove global existence and stability of solutions for a spherical model of reactive compressible self-gravitating fluid when a rigid core is present. In the absence of core, we show that no global solution of positive energy can exist.
THE PROJECTIONS OF n-KNOTS WHICH ARE NOT THE PROJECTION OF ANY UNKNOTTED KNOT
Authors: Ogasa Eiji
Published: July 2002

Let n be any integer greater than two. We prove that there exists a projection P having the following properties. (1) P is not the projection of any unknotted knot. (2) The singular point set of P consists of double points. (3) P is the projection of an n-knot which is diffeomorphic to the standard sphere.

We prove there exists an immersed n-sphere (⊂ℝn+1×{0}) which is not the projection of any n-knot (n>2). Note that the second theorem is different from the first one.
TWO-COMPONENT DRESSED-BAG MODEL FOR NN INTERACTION: DEUTERON STRUCTURE AND PHASE SHIFTS UP TO 1 GeV
Authors: KUKULIN V. I. , OBUKHOVSKY I. T. , POMERANTSEV V. N. , FAESSLER AMAND
Published: July 2002

A two-component model is developed for the intermediate-range NN interaction based on a new mechanism with an intermediate symmetric six-quark bag "dressed" by σ and other fields. To calculate the transition amplitude, the microscopic six-quark shell-model in combination with the 3P0-quark pion production mechanism is used. As a result, an effective energy-dependent NN interaction is constructed. The new quark–meson model for the NN interaction has been demonstrated to result in a new type of NN tensor force at intermediate ranges, which is crucially important for the treatment of tensor mixing at intermediate energies. The suggested model is able to describe NN phase shifts in a broad energy range from low energy up to 1 GeV, and the deuteron structure. The generalization of the model results in new spin-orbit 2N and 3N forces and new meson-exchange currents induced by intermediate dressed bag components, and also in the enhancement of a collective σ-field in nuclei.
ADAPTIVE DEVELOPMENT OF ANTIBODY REPERTOIRE UNDER STRUCTURAL MATCHING AND SYSTEM CONSTRAINTS
Authors: JOSHI RAJANI R.
Published: July 2002

A comprehensive model of the immune classifier system is presented where the affinity between the epitope- paratope pairs is defined in terms of structural matching and compatibility with respect to important physicochemical and geometrical parameters. Effects of medium interactions (energy constraints) on adaptive maturation of affinity and clonal selection are also simulated in terms of certain cost functions. Results of implementation on some real data are presented focussing on the nonlinear effects of the probability and strength of binding interactions and the metadynamics of variation in system parameters. Importance and scope of the approach in understanding the complexity of the associated nonlinear stochastic (bio)system is highlighted.
MODELS FOR FRACTIONAL RIESZ-BESSEL MOTION AND RELATED PROCESSES
Authors: ANH V. V. , LEONENKO N. N. , MCVINISH R.
Published: July 2002

This paper presents some stationary and stationary increment models for fractional Riesz-Bessel motion which permits the study of the effects of long-range dependence and second-order intermittency simultaneously. These effects are important features of data in finance and turbulence.
COTS-BASED FAULT TOLERANCE IN DEEP SPACE: A CASE STUDY ON IEEE 1394 APPLICATION
Authors: TAI ANN T. , CHAU SAVIO N. , ALKALAI LEON
Published: July 2002

Among the COTS applications in the X2000 architecture for deep-space missions, the use of commercial bus standards is the highest-payoff COTS application since a bus interface has a global impact on system cost and capability. While COTS bus standards enable significant cost reductions, it is a great challenge for us to deliver a highly-reliable long-term survivable system employing COTS standards that are not developed for mission-critical applications. The essence of our solution to the problem is to exploit the pertinent standard features of a COTS product to circumvent its shortcomings, including those standard features that are not originally designed for reliability purpose. In this paper, we discuss our experiences and findings on the design and assessment of an IEEE 1394 compliant fault-tolerant bus architecture. We first derive and qualitatively analyze a "stack-tree topology" that not only complies with IEEE 1394 but also enables the implementation of a fault-tolerant bus architecture without node redundancy. We then present a quantitative evaluation that demonstrates significant reliability improvement resulting from the COTS-based fault tolerance. We also describe the benefits from using COTS intellectual properties for hardware implementation of the bus architecture and discuss our general approach to COTS-based fault tolerance.
K-PROCESSOR RELIABILITY OF LARGE-SCALE RING-BASED HIERARCHICAL INTERCONNECTIONS
Authors: AL-ROUSAN M. , AL-JARRAH O. , MOWAFI M.
Published: July 2002

Recently, connecting thousands of processors via interconnection networks based on multiple (hierarchical) rings has an increased interest. This is due to the large acceptance and success of the Scalable Coherent Interface (SCI) technology. The inherently weak behavior of ring architecture has led interconnection designers to consider various choices to improve the overall network reliability. An interesting choice is to use braided rings instead of the single (basic) rings in the hierarchy. In this paper, we present new formulas for computing K-processor reliability of SCI ring-based hierarchical networks in the context of large-scale multiprocessor systems. The derived formulas are general and applicable to any given systems size consisting of an arbitrary number of levels. The reliability of hierarchical systems based on the basic and braided rings is evaluated and analyzed using the derived formulas. The results show that hierarchical systems based on braided rings significantly improve the reliability of hierarchies constructed of basic rings. The results are general and not limited to systems of SCI rings; the analysis is valid for any type of rings architecture such as token and slotted rings.
ENDOSCOPIC CARPAL TUNNEL RELEASE: SINGLE OR DOUBLE PORTAL?
Authors: Wicks Malcolm H.
Published: July 2002

This report outlines my experience with 20 patients who underwent bilateral endoscopic carpal tunnel releases: one side by a uni-portal (Unit-Cut) release, the other by a two portal (modified Chow) technique at the same time. All patients were treated as out-patients, the operations being performed under local anaesthesia with light sedation, no tourniquet inflated, and with pressure bandage applied for twelve hours only. The patients underwent an accelerated rehabilitation programme beginning the same day, and were encouraged to use their hands as soon as possible. Grip and pinch strength return was similar for both techniques, the single portal being slightly quicker. Return to work averaged 8.5 days (range 3–25 days) and full activities returned by 14.3 days (range 1–40 days). When asked, the patient strongly preferred the single portal technique, i.e., 18 out of 20 patients.
STABILISATION OF THE DISTAL ULNA USING EXTENSOR CARPI ULNARIS TENODESIS AFTER HEMIRESECTION — INTERPOSITION TECHNIQUE
Authors: Masada Kazuhiro , Fuji Takeshi , Fujita Satoru
Published: July 2002

A new stabilisation technique has been developed by the authors for the prevention of instability of the distal ulna after performance of Bower's hemiresection-interposition technique in rheumatoid patients, is described. This technique consists of the transfer of the extensor carpi ulnaris over the dorsal aspect of the distal ulna and suturing it to the soft tissue over the distal ulna. Operation was performed in 16 rheumatoid patients with 20 wrist joints. The results were evaluated in terms of both subjective (pain during rotation, pain on compression of the ulna) and objective evaluations (wrist/forearm range of motion, grip strength). After the operation, the pain almost disappeared in all but two cases which had insufficient bone excision. Wrist extension/flexion and pronation/supination improved after operation. Average grip strengths also improved. None of the cases showed instability of the distal ulna after the operation. Wrist extension strength did not decrease after operation in spite of tenodesis of the extensor carpi ulnaris. This technique is simple and useful for prevention of instability of the distal ulna after hemiresection-interposition technique has been carried out in rheumatoid patients.
EXPERIMENTAL STUDY OF THE HISTOLOGIC FINDINGS OF THE NEOENDOTHELIALIZATION ACCORDING TO LENGTH OF POLYTETRAFLUOROETHYLENE
Authors: Lee Kwang Suk , Kang Ki Hoon , Kim Young Sik
Published: July 2002

The purpose of this study was to investigate the patency rates and the histologic findings of neoendothelialization according to the length of implanted polytetrafluoroethylene (PTFE) with an internal diameter of 3 mm. Under the operating microscope, grafts of 8 and 24 mm in length were implanted in the right carotid arteries of rabbits. All implanted grafts were 25 μm in fibril length and 0.39 mm in wall thickness. All the grafts were harvested at different intervals and observed for the patency rates and histologic findings with light microscope and scanning electron microscope. There was no difference in patency rates according to the length of implanted PTFE. Histologically the formation of neointima and subintim was delayed and incomplete in longer implanted PTFE.
Sitaram Textiles Limited
Authors: Velayudhan Sanal Kumar
Published: July 2002

Sitaram Textiles is a state-owned textile mill in India. It serves a regional market with a limited product-line of cotton fabric. The mill was set up as an integrated textile mill. Severe price-competition from the unorganised powerloom sector has restricted its operations to producing yarn and processing of grey cloth. The weaving activity is contracted out to the small powerloom units. Competition for certain types of fabric is from large players. Changes in the environment have an adverse effect on its performance. New channel arrangements, evolving consumer tastes and an increase in competition are the noticeable changes in the environment. It has not been able to fully utilise its processing capacity. This has affected its profitability. The mill is planning modernisation of its facilities and is examining the option of entry into blended fabric market. The case examines the influences on product line decisions. The product line decisions are influenced by Sitaram Textiles' ability to compete, the requirements of the market and company objectives.
PATTERNS OF THORACIC DISC DEGENERATION FROM MRI: AGE, GENDER AND SPINAL LEVEL INFLUENCES
Authors: TAN CELIA I. C. , SONG SWITHIN , EDMONDSTON STEPHEN J. , SINGER KEVIN P.
Published: July 2002

The present retrospective study reviewed and examined the prevalence of thoracic disc degeneration, end-plate lesions and osteophytes in the thoracic spine using T2-weighted sagittal magnetic resonance images (MRI). The sample comprised 216 thoracic spine cases (101 males and 115 females), aged from 1 to 85 years (mean age = 42±19.7 years). Nuclear and anular degeneration, end-plate lesions and osteophytes were graded using a 3-point scale.

The prevalence of degeneration was highest in the nucleus (86%) and lowest in the end-plates (63%). Males had a higher prevalence of degeneration in the nucleus, anulus and end-plates, and a lower prevalence of osteophytes compared to females. Increasing cranio-caudal trends in the prevalence of degeneration in the nucleus, anulus and end-plates were observed, and these trends were statistically significant (p<0.01). Vertebral body osteophytes were most prevalent in the mid thoracic region. Osteophytes and degenerative changes in the nucleus and anulus increased significantly with age (p<0.05). These regional and age-related degenerative trends may influence the interpretation of thoracic spine pathology from MRI investigations.
STATISTICAL PROPERTIES OF STATISTICAL ENSEMBLES OF STOCK RETURNS
Authors: LILLO FABRIZIO , MANTEGNA ROSARIO N.
Published: July 2002

We select n stocks traded in the New York Stock Exchange and form a statistical ensemble of daily stock returns for each of the k trading days of our database from the stock price time series. We analyze each ensemble of stock returns by extracting its first four central moments. We observe that these moments are fluctuating in time and are stochastic processes themselves. We characterize the statistical properties of central moments by investigating their probability density function and temporal correlation properties.
GAMES OF CROWDING
Authors: ALPERN STEVE , REYNIERS DIANE
Published: July 2002

We introduce the notion of a "crowding game", where individuals choose to locate themselves among finitely many compartments, each with a capacity (size) and a cost (price). Individuals have a common notion of physical comfort (freedom from crowding), which is increasing in the size of their compartment, decreasing in the number (or mass) of other individuals choosing it. Where individuals differ is in their sensitivity to the cost of the compartment. Under these assumptions, we find unique equilibria in which no individual wishes to change compartments. After dealing with these notions of equilibrium play in games of crowding, we discuss the optimal design of such games by a supplier who can choose the capacities and costs of the compartments. The supplier's objective might be profit or welfare maximisation, or perhaps the maximisation of the number of individuals who enter some compartment.
GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY
Authors: KABADI SANTOSH N.
Published: July 2002

One of the first and perhaps the most well-known polynomially solvable special case of the traveling salesman problem (TSP) is the Gilmore-Gomory case (G-G TSP). Gilmore and Gomory presented an interesting patching algorithm for this case with a fairly non-trivial proof of its validity. Their work has motivated a great deal of research in the area leading to various generalisations of their results and thereby identification of fairly large polynomially solvable subclasses of the TSP. These results form a major portion of the literature on solvable cases of the TSP. In this paper, we survey the main results on solvable cases of the TSP which are direct generalisations of the G-G TSP and/or the Gilmore-Gomory patching scheme.
SEIBERG–WITTEN INVARIANTS OF 4-MANIFOLDS WITH FREE CIRCLE ACTIONS
Authors: BALDRIDGE SCOTT
Published: July 2002

The main results of this paper describes a formula for the Seiberg–Witten invariant of a 4-manifold which admits a nontrivial free circle action. We use this theorem to produce a nonsymplectic 4-manifold with a free circle action whose orbit space fibers over circle. We also describe a nontrivial 3-manifold which is not the orbit space of any symplectic 4-manifold with a free circle action. A corollary of the main theorem is a formula for the 3-dimensional Seiberg–Witten invariants of the total space of a circle bundle over a surface.
DISTRIBUTED ALGORITHM FOR MULTIMESSAGE MULTICASTING
Authors: GONZALEZ TEOFILO F.
Published: July 2002

We consider the multimessage multicasting over the n processor complete (or fully connected) static network when the forwarding of messages is allowed, and initially each processor only knows the messages it needs to send and their destinations. We present an efficient distributed algorithm to route the messages for every degree d problem instance with total expected communication time O(d + log n), where d is the maximum number of messages that each processor may send (or receive). Our routing algorithm consists of three phases. In the first phase the processors exchange messages to learn some basic global information. In the second phase each processor forwards its messages to transform the problem to a multimessage unicasting problem of degree d. The third phase uses a well known distributed algorithm to transmit all the resulting unicasting messages.
RELEVANT CYCLES IN CHEMICAL REACTION NETWORKS
Authors: GLEISS PETRA M. , STADLER PETER F. , WAGNER ANDREAS , FELL DAVID A.
Published: July 2002

We characterize the distributions of short cycles in a large metabolic network previously shown to have small world characteristics and a power law degree distribution. Compared with three classes of random networks, including Erdős–Rényi random graphs and synthetic small world networks of the same connectivity, both the metabolic network and models for the chemical reaction networks of planetary atmospheres have a particularly large number of triangles and a deficit in large cycles. Short cycles reduce the length of detours when a connection is clipped, so we propose that long cycles in metabolism may have been selected against in order to shorten transition times and reduce the likelihood of oscillations in response to external perturbations.
A comparative study of parallel algorithms for simulating continuous time Markov chains
Authors: Nicol David M. , Heidelberger Philip
Published: July 2002

This article describes methods for simulating continuous time Markov chain models, using parallel architectures. The basis of our method is the technique of uniformization; within this framework there are a number of options concerning optimism and aggregation. We describe four different variations, paying particular attention to an adaptive method that optimistically assumes upper bounds on the
rate
at which one processor affects another in simulation time, and recovers from violations of this assumption using global checkpoints. We describe our experiences with these methods on a variety of Intel multiprocessor architectures, including the Touchstone Delta, where excellent speedups of up to 220 using 256 processors are observed.
Implementing deductive databases by mixed integer programming
Authors: Bell Colin , Nerode Anil , Ng Raymond T. , Subrahmanian V. S.
Published: July 2002

Existing and past generations of Prolog compilers have left deduction to run-time and this may account for the poor run-time performance of existing Prolog systems. Our work tries to minimize run-time deduction by shifting the deductive process to compile-time. In addition, we offer an alternative inferencing procedure based on translating logic to mixed integer programming. This makes available for research and implementation in deductive databases, all the theorems, algorithms, and software packages developed by the operations research community over the past 50 years. The method keeps the same query language as for disjunctive deductive databases, only the inferencing procedure changes. The language is purely declarative, independent of the order of rules in the program, and independent of the order in which literals occur in clause bodies. The technique avoids Prolog's problem of infinite looping. It saves run-time by doing primary inferencing at compile-time. Furthermore, it is incremental in nature. The first half of this article translates disjunctive clauses, integrity constraints, and database facts into Boolean equations, and develops procedures to use mixed integer programming methods to compute equations, and develops procedures to use mixed integer programming methods to compute equations, and develops procedures to use mixed integer programming methods to compute equations, and develops procedures to use mixed integer programming methods to compute

—least models of definite deductive databases, and

—minimal models and the Generalized Closed World Assumption of disjunctive databases.
Predicting document access in large multimedia repositories
Authors: Recker Margaret M. , Pitkow James E.
Published: July 2002

Network-accessible multimedia databases, repositories, and libraries are proliferating at a rapid rate. A crucial problem for these repositories remains timely and appropriate document access. In this article, we borrow a model from psychological research on human memory, which has long studied retrieval of memory items based on frequency and recency rates of past item occurrences. Specifically, the model uses frequency and recency rates of prior document accesses to predict future document requests. The model is illustrated by analyzing the log file of document accesses to the Georgia Institute of Technology World Wide Web (WWW) repository, a large multimedia respository exhibiting high access rates. Results show that the model predicts document access rates with a reliable degree of accuracy. We describe extensions to the basic approach that combine the recency and frequency analyses and which incorporate respository structure and document type. These results have implications for the formulation of descriptive user models of information access in large repositories. In addition, we sketch applications in the areas of design of information systems and interfaces and their document-caching algorithms.
The simplest subdivision scheme for smoothing polyhedra
Authors: Peters Jörg , Reif Ulrich
Published: July 2002

Given a polyhedron, construct a new polyhedron by connecting every edge-midpoint to its four neighboring edge-midpoints. This refinement rule yields a
C
1
surface and the surface has a piecewise quadratic parametrozation except at a finite number of isolated points. We analyze and improve the construction.
Texture mapping 3D models of real-world scenes
Authors: Weinhaus Frederick M. , Devarajan Venkat
Published: July 2002

Texture mapping has become a popular tool in the computer graphics industry in the last few years because it is an easy way to achieve a high degree of realism in computer-generated imagery with very little effort. Over the last decade, texture-mapping techniques have advanced to the point where it is possible to generate real-time perspective simulations of real-world areas by texture mapping every object surface with texture from photographic images of these real-world areas. The techniques for generating such perspective transformations are variations on traditional texture mapping that in some circles have become known as the
Image Perspective Transformation
or IPT technology. This article first presents a background survey of traditional texture mapping. It then continues with a description of the texture-mapping variations that achieve these perspective transformations of photographic images of real-world scenes. The style of the presentation is that of a resource survey rather thatn an in-depth analysis.
Algorithm 794
Authors: Wieder Thomas
Published: July 2002

The numerical evaluation of the Hankel transform poses the problems of both infinite integration and Bessel function calculation. Using the corresponding numerical program routines from the literature, a Fortran program has been written to perform the Hankel transform for real functions, given either in analytical form as subroutines or in discrete form as tabulated data.
On the Efficiency of Algorithms
Authors: Pager David
Published: July 2002

A definition is given of the efficiency of an algorithm considered as a whole. This immediately raises the question of whether it is possible to find the most efficient or “optimum” algorithm. It is shown that an optimization problem of this kind is effectively solvable if and only if the set of arguments with which one is concerned is a finite one. Next, conditions under which an optimum algorithm does or does not exist are considered, and a limiting recursive process for finding it when it does is produced. Finally, some observations are made about the best space-time measure for algorithms which can be expected in certain cases. The results and proofs are couched in terms of Turing machines but may be adapted without difficulty to apply to other infinite digital machines such as the extensions of actual computers obtained by adding an infinite memory, or to the computations involved in other theoretical formulations of partial recursive functions such as those provided by Kleene's systems of equations or the URM's of Shepherdson and Sturgis.
Sequencing Jobs with Stochastic Task Structures on a Single Machine
Authors: Bruno John L.
Published: July 2002

A sequencing problem wherein there is a single processor and a finite number of jobs needing service is considered. Each job consists of a sequence of tasks generated probabilistically by a finite state Markov chain. Each state in the Markov chain is identified with a task and has a service-time requirement and a deferral cost, both of which are random variables. The goal is to minimize the expected value of the sum of the weighted finishing times of all the tasks. The sequencing discipline is nonpreemptive. It is shown that there exists an optimal priority sequencing rule based on a rank defined for each task; an efficient algorithm for calculating the rank is given.
Bessel functions of integral order and complex argument
Authors: Gray Marion C.
Published: July 2002

The FORTRAN II source language [1, 2] places rather severe restrictions on the form a subscript may take, primarily because of the manner in which indices are incremented in iterative loops. In the process of constructing a compiler for a medium-sized (8008-word memory) computer which will accept the FORTRAN II source language, it became clear that the “recursive address calculation” scheme, as used in the FORTRAN compilers to minimize object-program running time, was probably not the best one to use. This system, described in some detail by Samelson and Bauer [3], requires that the subscript expression be a linear function of the subscripting variable. The alternative, which requires complete evaluation of the “storage mapping function”, is usually rejected because of the time required for the object program to perform the necessary address calculation.
An algorithm for exhaustive generation of building floor plans
Authors: Galle Per
Published: July 2002

The combinatorial complexity of most floor plan design problems makes it practically impossible to obtain a systematic knowledge of possible solutions using pencil and paper. The objective of this paper is to contribute to the development of computer methods providing such knowledge for the designer. The paper describes an algorithm which generates all possible rectangular plans on modular grids with congruent cells, subject to constraints on total area, room areas, wall lengths, room adjacencies, and room orientations. To make room sizes regular and limit the solution set only such grids are used which minimize the number of cells in the smallest room. The description is sufficiently detailed to serve as a basis for programming. Test results for a Pascal implementation of the algorithm are reported. Realistic problems of up to ten rooms have been solved in modest lengths of computer time. The results indicate that the approach of exhaustive generation may prove to be more fruitful than generally assumed.
A more general algorithm for computing closed semiring costs between vertices of a directed graph
Authors: Fletcher John G.
Published: July 2002

This note describes a generalization of an algorithm given by Aho, Hopcroft, and Ullman [1], originally derived from the work of Kleene [2] and McNaughton and Yamada [3]. The algorithm is used to compute the total cost of all paths between each pair of vertices in a directed graph when the cost of each edge is known. The cost of a path is defined as the product of the costs of the edges forming it, and the total cost of a set of paths is the sum of their individual costs. If there are
n
vertices labeled 1 through
n
and
E
[
i, j
] is the cost of the edge from vertex
i
to vertex
j
(or is zero when there is no such edge), then the total cost
T
[
i, j
] of all paths from
i
to
j
is the solution of the equation
T
[
i, j
] = δ[
i, j
] + ∑

n

k
-1

E
[
i, k
]·
T
[
k, j
], (1) where δ[
i, i
] = 1 (the cost of the path of no edges from
i
to
i
) and δ[
i, j
] = 0 if
i
≠
j
. To assure that
T
[
i, j
] is always well-defined, costs are required to be elements from an algebraic structure called a closed semiring.
Discrimination in the employment of women in the computer industry
Authors: Weber Richard E. , Gilchrist Bruce
Published: July 2002

It has been more than ten years since the passage of the Equal Pay Act and Title VII of the 1964 Civil Rights Act, which were intended to end employment and wage discrimination against women. Thus it seems an appropriate time for the computer industry to examine its own employment practices with respect to women.
A note on the generation of rosary permutations
Authors: Read Ronald C.
Published: July 2002

Harada [1] has given a method of generating rosary permutations, and of associating an integer with each such permutation in a one-to-one manner. In this note we show that both these ends can be achieved more easily than by Harada's method.
The use of quadratic residue research
Authors: Radke Charles E.
Published: July 2002

Some of the problems of simulating discrete event systems, particularly computer systems, on a conventional digital computer are dealt with. The systems are assumed to be described as a network of interconnected sequential processes. Briefly reviewed are the common techniques used to handle such simulations when simultaneous events do not occur, can be ignored, or can be handled by simple priority rules. Following this, the problem of dealing with simultaneous events in separate processes is introduced. An abstraction of this problem is developed which admits solution for a majority of commonly encountered problems. The technique will either find a method of simulating the parallel events or report that none can be found. In some of the latter cases it is shown to be possible to find a solution by extending the information available to the solution technique, but in many cases the technique becomes computationally unfeasible when the additional information is provided.
On the problem of communicating complex information
Authors: Pager David
Published: July 2002

The nature of the difficulty involved in communicating mathematical results between scientists using a computer based information retrieval system is examined. The problem is analyzed in terms of psychological and information-processing processes, and what turns out to be a vicious circle of effects is described. The paper then considers how the presentation of information by a computer-based information retrieval system, or by other media, can be improved. Some trade-offs which affect the design of the presentation are mentioned, and a number of ideas for improvement are described. These include ways of augmenting written natural language by various notational and linguistic devices, the exhibition of the structure inherent in the information we are communicating, and a sophisticated interactive system controlled by computer.
Programming by questionnaire
Authors: Low David W.
Published: July 2002

Programming by questionnaire combines aspects of decision table programming and general purpose programming by using decision tables to construct an application program through the selection of certain source statements from a predefined file. It is proposed that programming by questionnaire is a useful compromise between general and special purpose programming for a significant class of large scale problems. The elements of the approach are discussed and an existing application is described.
Minimal event-node network of project precedence relations
Authors: Corneil D. G. , Gotlieb C. C. , Lee Y. M.
Published: July 2002

A procedure for constructing a minimal event-node network to represent a set of precedence relations without parallel activities is presented. A minimal event-node network is an event-node network in which both the number of nodes and the number of arcs are the minima to preserve the given precedence relations. Counterexamples are given to show that the algorithm presented by A.C. Fisher, J.S. Liebman, and G.L. Nemhauser (1968) produces event-node networks which are not minimal. Since our procedure includes the set-covering problem, the time required may grow exponentially with the number of given activities.
A nonrecursive list moving algorithm
Authors: Reingold Edward M.
Published: July 2002

An efficient, nonrecursive algorithm is given for moving any LISP-type list. In particular, the algorithm requires no storage other than the new nodes into which the lists is to be moved, and no additional bits per node for marking; the algorithm runs in time proportional to the number of nodes in the list. The original list structure is destroyed as it is moved.
The linear quotient hash code
Authors: Bell James R. , Kaman Charles H.
Published: July 2002

A new method of hash coding is presented and is shown to possess desirable attributes. Specifically, the algorithm is simple, efficient, and exhaustive, while needing little time per probe and using few probes per lookup. Performance data and implementation hints are also given.
Two subroutines for symbol manipulation with an algebraic compiler
Authors: Carr J. W. , Hanson J. W.
Published: July 2002

The current University of North Carolina version of the IT Compiler [1, 2], as well as the GAT Compiler of Arden and Graham of the University of Michigan [3], have special “alphabetic read” and “alphabetic type” statements. On the UNIVAC 1105 these features allow the direct input or output of six-symbol words, each symbol being either an alphanumeric or special character. Internally, each symbol is represented by a six-bit binary coded decimal code. On the IBM 650, five-symbol words are processed, with each symbol represented internally by a two-digit decimal code.
Comment on a paper on parallel processing
Authors: Nekora M. R.
Published: July 2002

The article by Lynn Yarbrough on Parallel Processing in the October
Communications
is interesting since it attracts attention to a subject which needs to be given increased consideration. His indictment of manufacturers for failing to provide what he feels is minimal to realizing the advantages of multi-programming is not applicable to STRETCH, however. It may be recalled that his specific complaint concerns the lack of protection of any program or monitor from the unpredictable actions of any other program. On page 15 of the STRETCH Data Processing System Reference Manual, we read: Address monitoring facilities are provided … The upper and lower boundaries of the storage area to be defined are placed in two address boundary registers. An alarm will be given when an address falls either inside or outside the defined area, whichever is desired. Storing in protected areas is normally suppressed.
A methodology for testing spreadsheets
Authors: Rothermel Gregg , Burnett Margaret , Li Lixin , Dupuis Christopher , Sheretov Andrei
Published: July 2002

Spreadsheet languages, which include commercial spreadsheets and various research systems, have had a substantial impact on end-user computing. Research shows, however, that spreadsheets often contain faults; thus, we would like to provide at least some of the benefits of formal testing methodologies to the creators of spreadsheets. This article presents a testing methodology that adapts data flow adequacy criteria and coverage monitoring to the task of testing spreadsheets. To accommodate the evaluation model used with spreadsheets, and the interactive process by which they are created, our methodology is incremental. To accommodate the users of spreadsheet languages, we provide an interface to our methodology that does not require an understanding of testing theory. We have implemented our testing methodology in the context of the Forms/3 visual spreadsheet language. We report on the methodology, its time and space costs, and the mapping from the testing strategy to the user interface. In an empirical study, we found that test suites created according to our methodology detected, on average, 81% of the faults in a set of faulty spreadsheets, significantly outperforming randomly generated test suites.
An indirect chaining method for addressing on secondary keys
Authors: Johnson L. R.
Published: July 2002

Methods for entering random-access files on the basis of one key are briefly surveyed. The widely used chaining method, based on a pseudo-random key transformation, is reviewed in more detail. An efficient generalization of the chaining method which permits recovery on additional keys is then presented.
A procedure for inverting large symmetric matrices
Authors: Busing William R. , Levy Henri A.
Published: July 2002

In the least squares method for simultaneous adjustment of several parameters, the coefficients of the normal equations are the elements of a symmetric positive-definite matrix. In order to solve the normal equations and evaluate the precision measures of the resulting parameters, inversion of this matrix of coefficients is required. Many available procedures for matrix inversion do not take advantage of the symmetry. Thus, when programmed for a high-speed computer, all
n
2
elements must be stored and manipulated, whereas only
n
(
n
+ 1)/2 of them are independent. In order to allow a computer of given memory capacity to handle a large matrix, the following procedure for inverting a symmetric matrix has been devised.
1
Proof-complexity results for nonmonotonic reasoning
Authors: Egly Uwe , Tompits Hans
Published: July 2002

It is well-known that almost all nonmonotonic formalisms have a higher worst-case complexity than classical reasoning. In some sense, this observation denies one of the original motivations of nonmonotonic systems, which was the expectation taht nonmonotonic rules should help to
speed-up
the reasoning process, and not make it more difficult. In this paper, we look at this issue from a proof-theoretical perspective. We consider analytic calculi for certain nonmonotonic logis and analyze to what extent the presence of nonmonotonic rules can simplify the search for proofs. In particular, we show that there are classes of first-order formulae which have only extremely long “classical” proofs, i.e., proofs without applications of nonmonotonic rules, but there are short proofs using nonmonotonic inferences. Hence,despite the increase of complexity in the worst case, there are instances where nonmonotonic reasoning can be much simpler than classical (cut-free) reasoning.