bluuebunny/crossref_metadata_2025 huggingface dataset:
EVCS — A COMPLETE ELECTRONIC VIRTUAL CONFERENCE SYSTEM
Authors: SHIH TIMOTHY K. , HUANG JIUNG-YAO , HUNG JASON C.
Published: July 2002

Electronic activities are realized on the Internet due to the growth of the Internet. As conference organization is getting more popular, we proposed an electronic virtual conference system (EVCS) to handle all activities of real-world conferences. The EVCS includes a virtual conference management system (VCMS) and a mobile conferencing system (MCS). Video conferencing is a trend of future communications. With the improvement of broadband network technologies, video conferencing becomes possible in the global society. It is feasible to use video conferencing technologies to organize future international conferences. As such, transportation and accommodation costs are saved. This paper proposed a total solution toward virtual conferencing. We use a mobile server/storage pre-broadcasting technique, as well as a communication network optimization algorithm, which is based on a graph computation mechanism. The system also relies on a network bandwidth reservation facility as well as a multicasting control function. With the assistance of the virtual conference management system, the system is able to support virtual conferencing in the future academic society.
STABILIZERS OF TRANSITIVE ACTIONS ON LOCALLY FINITE GRAPHS
Authors: NEKRASHEVYCH VOLODYMYR
Published: July 2002

We prove a criterion for a group to be representable as a vertex stabilizer of a transitive action on a locally finite graph. We show that actions with finite vertex stabilizers are open in a natural topology.
KNUTH–BENDIX FOR GROUPS WITH INFINITELY MANY RULES
Authors: EPSTEIN D. B. A. , SANDERS P. J.
Published: July 2002

We introduce a new class of groups with solvable word problem, namely groups specified by a confluent set of short-lex-reducing Knuth–Bendix rules which form a regular language. This simultaneously generalizes short-lex-automatic groups and groups with a finite confluent set of short-lex-reducing rules. We describe a computer program which looks for such a set of rules in an arbitrary finitely presented group. Our main theorem is that our computer program finds the set of rules, if it exists, given enough time and space. (This is an optimistic description of our result — for the more pessimistic details, see the body of the paper.)

The set of rules is embodied in a finite state automaton in two variables. A central feature of our program is an operation, which we call welding, used to combine existing rules with new rules as they are found. Welding can be defined on arbitrary finite state automata, and we investigate this operation in abstract, proving that it can be considered as a process which takes as input one regular language and outputs another regular language.

In our programs we need to convert several nondeterministic finite state automata to deterministic versions accepting the same language. We show how to improve somewhat on the standard subset construction, due to special features in our case. We axiomatize these special features, in the hope that these improvements can be used in other applications.

The Knuth–Bendix process normally spends most of its time in reduction, so its efficiency depends on doing reduction quickly. Standard data structures for doing this can become very large, ultimately limiting the set of presentations of groups which can be so analyzed. We are able to give a method for rapid reduction using our much smaller two variable automaton, encoding the (usually infinite) regular language of rules found so far. Time taken for reduction in a given group is a small constant times the time taken for reduction in the best schemes known (see [5]), which is not too bad since we are reducing with respect to an infinite set of rules, whereas known schemes use a finite set of rules.

We hope that the method described here might lead to the computation of automatic structures in groups for which this is currently infeasible.

Some proofs have been omitted from this paper in the interests of brevity. Full details are provided in [4].
GROUPS AND SEVERAL EQUATIONS IN ONE VARIABLE
Authors: CLIFFORD ANDREW
Published: July 2002

This paper addresses the question of simultaneously solving a set of equations in one variable over torsion-free groups.
DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
Authors: HASHIGUCHI KOSABURO , ISHIGURO KENICHI , JIMBO SHUJI
Published: July 2002

A finance automaton is a sixtuple <Σ,Q,δ,S,F,f>, where <Σ,Q,δ,S,F> is a (non-deterministic) finite automaton, f : Q × Σ × Q → R ∪ {-∞} is a finance function, R is the set of real numbers and f(q,a,q′) = -∞ if and only if q′∉δ(q,a). The function f is extended to f : 2Q × Σ* × 2Q → R ∪ {-∞} by the plus-max principle. For any w ∈ Σ*, f (S,w,F) is the profit of w. It is shown that the equivalence problem for finitely ambiguous finance automata is decidable.
ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS
Authors: BIRGET JEAN-CAMILLE , MARGOLIS STUART W. , MEAKIN JOHN
Published: July 2002

We prove that the word problem for the free product with amalgamation S *UT of monoids can be undecidable, even when S and T are finitely presented monoids with word problems that are decidable in linear time, the factorization problems for U in each of S and T, as well as other problems, are decidable in polynomial time, and U is a free finitely generated unitary submonoid of both S and T. This is proved by showing that the equality problem for the tensor product S ⊗UT is undecidable and using known connections between tensor products and amalgams. We obtain similar results for semigroups, and by passing to semigroup rings, we obtain similar results for rings as well. The proof shows how to simulate an arbitrary Turing machine as a communicating pair of two deterministic pushdown automata and is of independent interest. A similar idea is used in a paper by E. Bach to show undecidability of the tensor equality problem for modules over commutative rings.
IMAGE-BASED EVALUATION OF VASCULAR RESIDUAL STRAIN
Authors: KIA OMID E. , VOSSOUGHI JAFAR , LOPEZ GERALD G. , SIROHEY SAAD A.
Published: July 2002

We propose a method that aids in the evaluation of residual strain in blood vessels. Strain measurement is important in stress analysis of cardiovascular tissues. Since its introduction in 1983, arterial residual strain is evaluated manually which is a lengthy process. This involved photography, film development, printing of large photographs, and finally digitization of the edges of the vascular rings before and after cut using a flatbed digitizing tablet. These processes are highly labor intensive and time consuming, in the order of days. In this paper we introduce an image analysis and processing technique in which arterial residual strain can be evaluated efficiently and reliably. To insure portability, a JAVA-based application is developed which is designed for a semi-automatic operation in evaluating residual strain values. The use of the image-based evaluation technique is validated by comparison of arterial residual strain evaluated using photographs and digitizing tablet.
AN UNKNOTTING OPERATION ON RIBBON 2-KNOTS
Authors: KANENOBU TAIZO
Published: July 2002

We define a local move on a ribbon 2-knot diagram, called an HC-move. We show that it is an unknotting operation for a ribbon 2-knot, and that the application of a single HC-move to a ribbon 2-knot changes the second derivative at t=1 of its normalized Alexander polynomial by either ±2 or 0. This result is applied to the calculation of the HC-unknotting numbers of ribbon 2-knots. We also consider a relation with a 1-handle unknotting operation.
COSMOLOGICAL CONSTANT AND THE SPEED OF LIGHT
Authors: MIGUEL W. R. ESPÓSITO , PEREIRA J. G.
Published: July 2002

By exploring the relationship between the propagation of electromagnetic waves in a gravitational field and the light propagation in a refractive medium, it is shown that, in the presence of a positive cosmological constant, the velocity of light will be smaller than its special relativity value. Then, restricting again to the domain of validity of geometrical optics, the same result is obtained in the context of wave optics. It is argued that this phenomenon and the anisotropy in the velocity of light in a gravitational field are produced by the same mechanism.
A PREY-PREDATOR-SUPERPREDATOR SYSTEM
Authors: MEHIDI NOUREDDINE
Published: July 2002

We consider a prey-predator-superpredator model. Assuming that the growth rates of the three populations are highly diversified, we prove that under some conditions on the parameters of the model, the three populations can coexist through a cycle for which we give the period. Besides, we give the laws (entrance-exit functions) that govern the prey and predator regeneration when they tend to extinction.
THE USE OF THE ABOAV-WEAIRE LAW TO ESTIMATE A BIOLOGICAL CONSTRAINT
Authors: JEUNE BERNARD , BARABÉ DENIS
Published: July 2002

Developmental processes may impose limitations and directionality in the mode of development of a particular structure. The main problem is to determine the nature and the respective effects of physical and biological constraints in the development of organisms. The Aboav-Weaire law is a semi-empirical law developed to explain the topological structure of physical materials. In the present paper, we make a formal analysis of the quantitative relationships between physical and biological constraints in biological structures by using the inflorescence of the Araceae as a case study. The Aboav-Weaire law permits to obtain a quantitative estimate of the biological constraint acting on the inflorescences of this family. In the case of the Araceae, the empirical curve presents a constant deviation with respect to the Aboav-Weaire law. This deviation is due to the presence of a biological constraint as opposed to a physical constraint. The biological constraint tends to decrease the variance of the number of sides while it is the inverse situation for the physical constraint. The results obtained using the Araceae model can be used to study the interrelationships between biological and physical constraints in any organism or biological structure.
MATHEMATICAL SIMULATION IN DIFFRACTION ACOUSTICAL TOMOGRAPHY WITH MULTIELEMENT TRANSCEIVER
Authors: OSETROV ALEXANDER V. , KHRENOV ANDREW P.
Published: July 2002

The parameters of diffraction tomography methods for inhomogeneity reconstruction is investigated. For a two-dimensional case with linear multi-element transceiver one single frequency and two multi-frequency measurement schemes are introduced. For these schemes the data regions in the spatial frequency domain of inhomogeneities function are presented. The new two-stage approach is developed for resolution investigation and image quality estimation. In the first stage, it is proposed to find the resolution for ideal measurement conditions (infinite measurement aperture, ideal transducers). Then in the second stage for real measurement conditions, it is enough to determine only the degradation factor which is calculated for all measurement schemes dependent on measurement parameters. For examination of this approach also the images for complicated inhomogeneity model are calculated. It is shown that resolution and point spread functions cannot fully describe image quality, especially for complicated data regions in the spatial frequency domain of the inhomogeneities function. Many numerical examples are presented.
TWO SECTIONAL MODELS INVOLVING TWO WEIBULL DISTRIBUTIONS
Authors: JIANG RENYAN , ZUO MING J. , MURTHY D. N. P.
Published: July 2002

In this paper, we study two sectional models, each involving two Weibull distributions. Characterization of the plot on Weibull plotting paper (WPP) for each model is carried out. We also study the shapes of the probability density and the failure rate functions. These are useful in determining if a given failure data set can be modeled by such a model. We discuss the estimation of model parameters based on the WPP plot and illustrate through two examples involving real data.
ON THE POSSIBILITY OF KONDO EFFECT ON THE SURFACE OF MAGNETIC SUBSTANCE
Authors: KONDO SHIN-ICHIRO
Published: July 2002

We theoretically discuss and examine spin polarization of the electrons scattered on the surface of a magnetic dilute alloy with a very small amount of 3d magnetic impurities when the incident electron, the energy of which is as low as Fermi level, has exchange interaction with the localized spin existing on the surface. It is found that exchange interaction between the incident electron and localized spin can be regarded as s–d interaction in the case of the energy of the incident electron as low as Fermi level and that scattering polarization asymmetry Λ includes the term of ln T associated with the many-body interaction between incident and d electron by the calculation of second order perturbation. Accordingly it seems possible that the dependence of Λ on the term of ln T, as observed in Kondo effect, may be expected to appear.
QUANTITATIVE ANALYSIS OF NONCONTINUOUS THIN FILMS BY EELS
Authors: MATOLÍN V. , STARÁ I.
Published: July 2002

Reflection electron energy loss spectroscopy (EELS) operated at low primary electron energy Ep (~ 500 eV) can be used as a coverage-sensitive probe in the case of supported noncontinuous layers. Quantitative analysis by EELS is substantially complicated by the fact that EEL intensity depends on two material factors: K(E), differential cross section for energy loss of E, and electron backscattering factor η(Ep). Both factors were determined experimentally using deposit and substrate reference samples. The contribution of pure substrate and pure deposit EEL curves to composed EEL spectra of the investigated deposit/substrate system has been found by fitting it with combination of reference K(E)λ curves (λ stands for IMFP). The fit results corrected using η(Ep) factors permitted one to evaluate the deposit coverage. The method was tested using the reference Au fractional deposit on the sapphire substrate.
DIFFERENTIAL OF SENSIBILITY OF THE HAND USING SEMMES-WEINSTEIN MONOFILAMENTS
Authors: Hage J. Joris , Ahmed A. Kalam J. , de Groot Peter J. M. , de Boer E.
Published: July 2002

Because the distribution of the range of normal sensibility in a large series of non-injured subjects is poorly documented, a study was designed to quantitate the distribution of human pressure perception for static constant-touch of the palmar side of the hand in a sample of 51 healthy subjects. This study further sought to establish a sensibility difference between the ulnar and median nerves by comparison of touch sensibility between the ulnar and median side of the ring finger in 57 healthy subjects. The distribution of light touch-deep pressure in the hands shows a gaussian pattern around a 2.44 10 log 0.1 mg peak. No difference in ulnar versus median nerve sensibility threshold was found. To establish the differential in the normal range of touch, or in ulnar versus median nerve threshold within the hand, a 5 filament minikit will not suffice.
REAL EXCHANGE RATE BEHAVIOUR UNDER HONG KONG'S LINKED EXCHANGE RATE SYSTEM: AN EMPIRICAL INVESTIGATION
Authors: ZHANG ZHICHAO
Published: July 2002

In a behavioural equilibrium exchange rate model, this study investigates the movements of the real exchange rate of the Hong Kong dollar under the currency board arrangement from 1984 to 1998. Cointegration analysis based on Johansen approach is applied to derive the equilibrium real exchange rate in behavioural sense for the Hong Kong dollar. Evidence shows that during the period under investigation, the Hong Kong dollar was initially undervalued when the currency board arrangement was installed. It moved in closer line with the equilibrium rate after 1985 and generally remained moderately undervalued until 1993. Then the currency became overvalued following the upsurge of domestic demand and lingered into 1995 before an adjustment took place latter that year. But except for a few quarters, the overvaluation was not substantial and chronic. On the whole, the Hong Kong dollar seemed to have performed well in the period under examination. In most cases, the currency was actually undervalued. When the Asian financial crisis broke out, the currency was in effect already in a process of adjustment, depreciating form an overvalued level.
STEREOSCOPIC VIDEO CODING USING A FAST AND ROBUST AFFINE MOTION SEARCH
Authors: CHIANG TIHAO , ZHANG YA-QIN
Published: July 2002

This paper presents a stereoscopic video compression scheme using a novel fast affine motion estimation technique. A temporal scalable approach is used to achieve backward compatibility with a standard definition TV. We use an adaptive mode selection scheme from three temporal locations in both channels. Both block-based and affine-motion based approaches are used to achieve two levels of improvements with different complexities. An innovative motion estimation technique using Gauss–Newton optimization and pyramid processing is implemented to efficiently estimate affine parameters. Unlike other Gauss–Newton approaches, our search technique uses only addition, subtraction and multiplication and it converges within four iterations, which implies great complexity reduction. An efficient and robust affine motion prediction yields significant over the disparity-based approach. Part of the disparity-based approach has been tested in the rigorous MPEG-2 bitstream exchange process, and adopted in the MPEG-2 Multi-View Profile (MVP).
SPECTRAL REGULARIZATION, DATA COMPLEXITY AND AGENT BEHAVIOR
Authors: ILYINSKY ALEXANDER
Published: July 2002

The simple and efficient procedure of trend identification in economic time series using the FFT method has been proposed. The effect of trend identification on the behavior of agents on stock markets has been considered. The spectral decomposition of economic data as ill-posed problems has been studied. Connection of trend identification with data smoothing and regularization for numerical differentiation of empirical data has been discussed. Relations among data subjective complexity, spectral regularization parameter and temporal preferences of agent have been shown. The selection of the cut-off frequency for data smoothing should correspond to the investment horizon of the economic agent.
INTEGRATION OF REAL-TIME CONTROL SIMULATION TO A VIRTUAL MANUFACTURING ENVIRONMENT
Authors: MIN BYUNG-KWON , HUANG ZHENGDONG , PASEK ZBIGNIEW J. , YIP-HOI DEREK , HUSTED FORBES , MARKER STEPHEN
Published: July 2002

This paper presents a new integrated approach for simulation developed to improve the accuracy of virtual manufacturing environments. While machine tool simulation and virtual manufacturing for factory simulation have been frequently used in early stage plant development, each of these technique has been researched and implemented separately. This paper focuses on the utilization of real-time simulation of machine tools or active axes in manufacturing systems and integration of this simulation capability with virtual manufacturing environments. Machine-level simulation results are generated in real-time with a real machine tool controller and are fed to a virtual manufacturing environment. To integrate these two simulation techniques, system-level software is utilized as a communication platform. This system-level software was originally developed to control and configure whole manufacturing systems. The method has been successfully implemented within a testbed with full-scale machine tools. The results demonstrate that the proposed method advances the virtual manufacturing environments toward improved accuracy of factory level simulation, reduced effort for modeling and expanded functionality of machine-level simulations.
DECISION MAKING AND STRATEGIC ENVIRONMENTAL ASSESSMENT
Authors: NILSSON MÅNS , DALKMANN HOLGER
Published: July 2002

Strategic Environmental Assessment aims to incorporate environmental and sustainability considerations into strategic decision making processes, such as the formulation of policies, plans and programmes. In order to be effective, the assessment must take the real decision making process as the departure point. Existing SEA approaches are frequently tailored after an EIA model conceived from a rational perspective on decision making. However, there are good reasons to assume that most strategic decision making processes are characterised by a bounded rationality. Furthermore, the predictability of environmental consequences generally becomes weaker at strategic levels than at the project level and complexity increases in terms of the numbers of actors involved in the decision. This paper examines various theoretical perspectives to decision making and discusses the implications for decision support in general and SEA in particular. The authors argue that the design of the SEA must be more sensitive to the real characteristics of the decision making context.
COMBINING REGRESSION ESTIMATORS: GA-BASED SELECTIVE NEURAL NETWORK ENSEMBLE
Authors: ZHOU ZHI-HUA , WU JIAN-XIN , TANG WEI , CHEN ZHAO-QIAN
Published: July 2002

Neural network ensemble is a learning paradigm where a collection of neural networks is trained for the same task. In this paper, the relationship between the generalization ability of the neural network ensemble and the correlation of the individual neural networks constituting the ensemble is analyzed in the context of combining neural regression estimators, which reveals that ensembling a selective subset of trained networks is superior to ensembling all the trained networks in some cases. Based on such recognition, an approach named GASEN is proposed. GASEN trains a number of individual neural networks at first. Then it assigns random weights to the individual networks and employs a genetic algorithm to evolve those weights so that they can characterize to some extent the importance of the individual networks in constituting an ensemble. Finally it selects an optimum subset of individual networks based on the evolved weights to make up the ensemble. Experimental results show that, comparing with a popular ensemble approach, i.e., averaging all, and a theoretically optimum selective ensemble approach, i.e. enumerating, GASEN has preferable performance in generating ensembles with strong generalization ability in relatively small computational cost. This paper also analyzes the working mechanism of GASEN from the view of error-ambiguity decomposition, which reveals that GASEN improves generalization ability mainly through reducing the average generalization error of the individual neural networks constituting the ensemble.
An efficient algorithm for a task allocation problem
Authors: Billionnet A. , Costa M. C. , Sutter A.
Published: July 2002

This paper presents an efficient algorithm to solve one of the task allocation problems. Task assignment in an heterogeneous multiple processors system is investigated. The cost function is formulated in order to measure the intertask communication and processing costs in an uncapacited network. A formulation of the problem in terms of the minimization of a submodular quadratic pseudo-Boolean function with assignment constraints is then presented. The use of a branch-and-bound algorithm using a Lagrangean relaxation of these constraints is proposed. The lower bound is the value of an approximate solution to the Lagrangean dual problem. A zero-duality gap, that is, a saddle point, is characterized by checking the consistency of a pseudo-Boolean equation. A solution is found for large-scale problems (e.g., 20 processors, 50 tasks, and 200 task communications or 10 processors, 100 tasks, and 300 task communications). Excellent experimental results were obtained which are due to the weak frequency of a duality gap and the efficient characterization of the zero-gap (for practical purposes, this is achieved in linear time). Moreover, from the saddle point, it is possible to derive the optimal task assignment.
Principles of database buffer management
Authors: Effelsberg Wolfgang , Haerder Theo
Published: July 2002

This paper discusses the implementation of a database buffer manager as a component of a DBMS. The interface between calling components of higher system layers and the buffer manager is described; the principal differences between virtual memory paging and database buffer management are outlined; the notion of referencing versus addressing of database pages is introduced; and the concept of fixing pages in the buffer to prevent uncontrolled replacement is explained.

Three basic tasks have to be performed by the buffer manager: buffer search, allocation of frames to concurrent transactions, and page replacement. For each of these tasks, implementation alternatives are discussed and illustrated by examples from a performance evaluation project of a CODASYL DBMS.
The complexity of logic-based abduction
Authors: Eiter Thomas , Gottlob Georg
Published: July 2002

Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about
logic-based abduction
. Candidates for abductive explanations are usually subjected to minimality criteria such as subset-minimality, minimal cardinality, minimal weight, or minimality under prioritization of individual hypotheses. This paper presents a comprehensive complexity analysis of relevant decision and search problems related to abduction on propositional theories. Our results indicate that abduction is harder than deduction. In particular, we show that with the most basic forms of abduction the relevant decision problems are complete for complexity classes at the second level of the polynomial hierarchy, while the use of prioritization raises the complexity to the third level in certain cases.
Constructing 1-writer multireader multivalued atomic variables from regular variables
Authors: Haldar S. , Vidyasankar K.
Published: July 2002

A simple wait-free construction of 1-writer multireader multivalued atomic variable from multireader regular variables is presented in this paper. A key point of the construction is the use of an elegant forwarding technique to overcome the new-old inversion property inherent in regular variables.

Another construction, using a different forwarding technique, is also given. This technique is a refinement of one proposed in the literature.

Formal correctness proofs for both the constructions are short and easy to follow.
Using video to re-present the user
Authors: Brun-Cottan Francoise , Wall Patricia
Published: July 2002

Advocates of user-centered design and participatory design, also referred to as “work practice practitioners” include computer scientists, systems designers, software engineers, social scientists, industrial and graphic designers, marketing, sales, and service personnel. Working singly or in teams, we have been identifying and combining effective techniques and methods of: gathering data, interacting with user participants, representing activities and observations, and integrating findings with the design and construction of new technologies.
Power over users
Authors: Markus M. Lynne , Bjørn-Andersen Niels
Published: July 2002

Analysis and awareness of the types of power that IS professionals exercise over users can improve the productivity of both parties.
Algorithm 751: TRIPACK
Authors: Renka R. J.
Published: July 2002

TRIPACK is a Fortran 77 software package that employs an incremental algorithm to construct a constrained Delaunay traingulation of a set of points in the plane (nodes). The triangulation covers the convex hull of the nodes but may include polygonal constraint regions whose triangles are distinguishable from those in the remainder of the triangulation. This effectively allows for a nonconvex or multiply connected triangulation (the complement of the union of constraint regions) while retaining the efficiency of searching and updating a convex triangulation. The package provides a wide range of capabilities including an efficient means of updating the triangulation with nodal additions or deletions. For
N
nodes, the storage requirement is 13
N
integer storage locations in addition to the 2
N
nodal coordinates.
Four dark corners of requirements engineering
Authors: Zave Pamela , Jackson Michael
Published: July 2002

Research in requirements engineering has produced an extensive body of knowledge, but there are four areas in which the foundation of the discipline seems weak or obscure. This article shines some light in the “four dark corners,” exposing problems and proposing solutions. We show that all descriptions involved in requirements engineering should be descriptions of the environment. We show that certain control information is necessary for sound requirements engineering, and we explain the close association between domain knowledge and refinement of requirements. Together these conclusions explain the precise nature of requirements, specifications, and domain knowledge, as well as the precise nature of the relationships among them. They establish minimum standards for what information should be represented in a requirements language. They also make it possible to determine exactly what it means for requirements and engineering to be successfully completed.
Specification matching of software components
Authors: Zaremski Amy Moormann , Wing Jeannette M.
Published: July 2002

Specification matching is a way to compare two software components, based on descriptions of the component's behaviors. In the context of software reuse and library retrieval, it can help determine whether one component can be substituted for another or how one can be modified to fit the requirements of the other. In the context of object-oriented programming, it can help determine when one type is a behavioral subtype of another. We use formal specifications to describe the behavior of software components and, hence, to determine whether two components match. We give precise definitions of not just exact match, but, more relevantly, various flavors of relaxed match. These definitions capture the notions of generalization, specialization, and substitutability of software components. Since our formal specifications are pre- and postconditions written as predicates in first-order logic, we rely on theorem proving to determine match and mismatch. We give examples from our implementation of specification matching using the Larch Prover.
Efficient descriptor-vector multiplications in stochastic automata networks
Authors: Fernandes Paulo , Plateau Brigitte , Stewart William J.
Published: July 2002

This paper examines numerical issues in computing solutions to networks of stochastic automata. It is well-known that when the matrices that represent the automata contain only constant values, the cost of performing the operation basic to all iterative solution methods, that of matrix-vector multiply, is given by

ρ
N
= Π
N
i-1
n
i
× Σ
N
i=1
n
i
,

where

n
i

is the number of states in the
i
th automaton and
N
is the number of automata in the network. We introduce the concept of a generalized tensor product and prove a number of lemmas concerning this product. The result of these lemmas allows us to show that this relatively small number of operations is sufficient in many practical cases of interest in which the automata contain functional and not simply constant transitions. Furthermore, we show how the automata should be ordered to achieve this.
Fast address lookups using controlled prefix expansion
Authors: Srinivasan V. , Varghese G.
Published: July 2002

Internet (IP) address lookup is a major bottleneck in high-performance routers. IP address lookup is challenging because it requires a
longest matching prefix
lookup. It is compounded by increasing routing table sizes, increased traffic, higher-speed links, and the migration to 128-bit IPv6 addresses. We describe how IP lookups and updates can be made faster using a set of of transformation techniques. Our main technique,
controlled prefix expansion
, transforms a set of prefixes into an equivalent set with fewer prefix lengths. In addition, we use optimization techniques based on dynamic programming, and local transformations of data structures to improve cache behavior. When applied to trie search, our techniques provide a range of algorithms (
Expanded Tries
) whose performance can be tuned. For example, using a processor with 1MB of L2 cache, search of the MaeEast database containing 38000 prefixes can be done in 3 L2 cache accesses. On a 300MHz Pentium II which takes 4 cycles for accessing the first word of the L2 cacheline, this algorithm has a worst-case search time of 180 nsec., a worst-case insert/delete time of 2.5 msec., and an average insert/delete time of 4 usec. Expanded tries provide faster search
and
faster insert/delete times than earlier lookup algirthms. When applied to Binary Search on Levels, our techniques improve worst-case search times by nearly a factor of 2 (using twice as much storage) for the MaeEast database. Our approach to algorithm design is based on measurements using the VTune tool on a Pentium to obtain dynamic clock cycle counts. Our techniques also apply to similar address lookup problems in other network protocols.
A new normal form for the design of relational database schemata
Authors: Zaniolo Carlo
Published: July 2002

This paper addresses the problem of database schema design in the framework of the relational data model and functional dependencies. It suggests that both Third Normal Form (3NF) and Boyce-Codd Normal Form (BCNF) supply an inadequate basis for relational schema design. The main problem with 3NF is that it is too forgiving and does not enforce the separation principle as strictly as it should. On the other hand, BCNF is incompatible with the principle of representation and prone to computational complexity. Thus a new normal form, which lies between these two and captures the salient qualities of both is proposed. The new normal form is stricter than 3NF, but it is still compatible with the representation principle. First a simpler definition of 3NF is derived, and the analogy of this new definition to the definition of BCNF is noted. This analogy is used to derive the new normal form. Finally, it is proved that Bernstein's algorithm for schema design synthesizes schemata that are already in the new normal form.
Extending the database relational model to capture more meaning
Authors: Codd E. F.
Published: July 2002

During the last three or four years several investigators have been exploring “semantic models” for formatted databases. The intent is to capture (in a more or less formal way) more of the meaning of the data so that database design can become more systematic and the database system itself can behave more intelligently. Two major thrusts are clear.

In this paper we propose extensions to the relational model to support certain atomic and molecular semantics. These extensions represent a synthesis of many ideas from the published work in semantic modeling plus the introduction of new rules for insertion, update, and deletion, as well as new algebraic operators.
Scheduling Parallel Computations
Authors: Reiter Raymond
Published: July 2002

A model for parallel computations is given as a directed graph in which nodes represent elementary operations, and branches, data channels. The problem considered is the determination of an admissible schedule for such a computation; i.e. for each node determine a sequence of times at which the node initiates its operation. These times must be such that each node, upon initiation, is assured of having the necessary data upon which to operate. Necessary and sufficient conditions that a schedule be admissible are given. The computation rate of a given admissible schedule is defined and is shown to have a limiting value 1/π where π is a parameter dependent upon the cycles in the graph. Thus, the computation cannot proceed at a rate exceeding 1/π. For γ ≥ π, the class of all periodic admissible schedules with period γ is characterized by the solution space of a certain system of linear inequalities. In particular, then, the maximum computation rate of 1/π is attainable under a periodic admissible schedule with period π. A class of all-integer admissible schedules is given. Finally, an algorithm is given for the determination of the number of initiations of each node in the graph defining a parallel computation.

An example for a system of difference equations is given in detail.
The transport layer
Authors: Iren Sami , Amer Paul D. , Conrad Phillip T.
Published: July 2002

Transport layer protocols provide for end-to-end communication between two or more hosts. This paper presents a tutorial on transport layer concepts and terminology, and a survey of transport layer services and protocols. The transport layer protocol TCP is used as a reference point, and compared and contrasted with nineteen other protocols designed over the past two decades. The service and protocol features of twelve of the most important protocols are summarized in both text and tables.
Computing connected components on parallel computers
Authors: Hirschberg D. S. , Chandra A. K. , Sarwate D. V.
Published: July 2002

We present a parallel algorithm which uses
n
2
processors to find the connected components of an undirected graph with
n
vertices in time
O
(log
2
n
). An
O
(log
2
n
) time bound also can be achieved using only
n
⌈
n
/⌈log
2
n
⌉⌉ processors. The algorithm can be used to find the transitive closure of a symmetric Boolean matrix. We assume that the processors have access to a common memory. Simultaneous access to the same location is permitted for fetch instructions but not for store instructions.
The evolution of the DECsystem 10
Authors: Bell C. G. , Kotok A. , Hastings T. N. , Hill R.
Published: July 2002

The DECsystem 10, also known as the PDP-10, evolved from the PDP-6 (circa 1963) over five generations of implementations to presently include systems covering a price range of five to one. The origin and evolution of the hardware, operating system, and languages are described in terms of technological change, user requirements, and user developments. The PDP-10's contributions to computing technology include: accelerating the transition from batch oriented to time sharing computing systems; transferring hardware technology within DEC (and elsewhere) to minicomputer design and manufacturing; supporting minicomputer hardware and software development; and serving as a model for single user and timeshared interactive minicomputer/microcomputer systems.
Order-
n
correction for regular languages
Authors: Wagner Robert A.
Published: July 2002

A method is presented for calculating a string
B
, belonging to a given regular language
L
, which is “nearest” (in number of edit operations) to a given input string
α
.
B
is viewed as a reasonable “correction” for the possibly erroneous string
α
, where
α
was originally intended to be a string of
L
. The calculation of
B
by the method presented requires time proportional to |
α
|, the number of characters in
α
. The method should find applications in information retrieval, artificial intelligence, and spelling correction systems.
The basic side of tape labeling
Authors: Logan William A.
Published: July 2002

Once an installation has determined that it would be advantageous to be able to internally identify the contents of each reel of tape on hand and to be able to check those identifications by programming, consideration is given to a Tape. Labeling Routine. The parameters of such a routine are limited only by the inventiveness of the programmers of the installation as they request (and frequently demand) that the label on the tape contain block counts, can numbers, pass tallies, messages, reminders, first names, last names, number of tape inches available, security classifications, unit the tape is to be mounted on, and hundreds of other “necessary” pieces of data which will serve to illustrate the complexity of data processing. The routine which is to translate these labels is oftentimes encumbered with brilliant formulas which enable it (if it can ever be completely debugged) to manipulate the information and make decisions of astounding magnitude. What little core memory space remains is then used to process the data in the file which the label identified.
Compiling connectives
Authors: Swift Charles J.
Published: July 2002

The connectives “and”, “or” and their alternatives can be used to connect words, phrases or clauses in natural English. In the specifications for the FACT language for the Honeywell 800
(1)
, authors attempted to include as many of these uses as possible while still retaining simple rules as to what was allowable. The compiler operates on connectives by expanding the original source statements, using repetitions, until there has been generated an equivalent statement in which the connectives connect only complete conditional or imperative clauses. This paper describes the methods employed by the compiler for part of this expansion.
Role of interface manipulation style and scaffolding on cognition and concept learning in learnware
Authors: Sedig Kamran , Klawe Maria , Westrom Marvin
Published: July 2002

This research investigates the role of interface manipulation style on reflective cognition and concept learning through a comparison of the effectiveness of three verisons of a software application for learning two-dimensional transformation geometry. The three versions respectively utilize a Direct Object Manipulation (DOM) interface in which the user manipulates the visual representation of objects being transformed; a Direct Concept Manipulation (DCM) interface in which the user manipulates the visual representation of the transformation being applied to the object; and a Reflective Direct Concept Manipulation (RDCM) interface in which the DCM approach is extended with scaffolding. Empirical results of a study showed that grade-6 students using the RDCM version learned significantly more than those using the DCM version, who is turn learned significantly more than those using the DOM version. Students using the RDCM version had to process information consciously and think harder than those using the DCM and DOM versions. Despite the relative difficulty when using the RDCM interface style, all three groups expressed a similar (positive) level of liking for the software. This research suggests that some of the educational deficiencies of Direct Manipulation (DM) interfaces are not necessarily caused by their “directness,” but by what they are directed at—in this case directness toward objects rather than embedded educational concepts being learned. This paper furthers our understanding of how the DM metaphor can be used in learning- and knowledge-centered software (i.e., learnware) by proposing a new DM metaphor (i.e., DCM), and the incorporation of scaffolding to enhance the DCM approach to promote reflective cognition and deep learning.
XRel
Authors: Yoshikawa Masatoshi , Amagasa Toshiyuki , Shimura Takeyuki , Uemura Shunsuke
Published: July 2002

This article describes XRel, a novel approach for storage and retrieval of XML documents using relational databases. In this approach, an XML document is decomposed into nodes on the basis of its tree structure and stored in relational tables according to the node type, with path information from the root to each node. XRel enables us to store XML documents using a fixed relational schema without any information about DTDs and also to utilize indices such as the

B
+

-tree and the
R
-tree supported by database management systems. Thus, XRel does not need any extension of relational databases for storing XML documents. For processing XML queries, we present an algorithm for translating a core subset of XPath expressions into SQL queries. Finally, we demonstrate the effectiveness of this approach through several experiments using actual XML documents.
Signal processing in SETI
Authors: Cullers D. K. , Linscott Ivan R. , Oliver Bernard M.
Published: July 2002

The Search for Extraterrestrial Intelligence (SETI), now being planned at NASA, will require a prodigious amount of highly concurrent signal processing to be done in real time by special-purpose hardware.
Extended algebra and calculus for nested relational databases
Authors: Roth Mark A. , Korth Herry F. , Silberschatz Abraham
Published: July 2002

Relaxing the assumption that relations are always in First-Normal-Form (1NF) necessitates a reexamination of the fundamentals of relational database theory. In this paper we take a first step towards unifying the various theories of ¬1NF databases. We start by determining an appropriate model to couch our formalisms in. We then define an extended relational calculus as the theoretical basis for our ¬1NF database query language. We define a minimal extended relational algebra and prove its equivalence to the ¬1NF relational calculus. We define a class of ¬1NF relations with certain “good” properties and extend our algebra operators to work within this domain. We prove certain desirable equivalences that hold only if we restrict our language to this domain.
Managing your total IT cost of ownership
Authors: David Julie Smith , Schuff David , St. Louis Robert
Published: July 2002

Though the TCO of end-user workstations can always be reduced by sacrificing end-user service, careful planning can reduce the costs without the sacrifice.
A geometric characterization of parametric cubic curves
Authors: Stone Maureen C. , DeRose Tony D.
Published: July 2002

In this paper, we analyze planar parametric cubic curves to determine conditions for loops, cusps, or inflection points. By expressing the curve to be analyzed as a linear combination of control points, it can be transformed such that three of the control points are mapped to specific locations on the plane. We call this image curve the
canonical curve
. Affine maps do not affect inflection points, cusps, or loops, so the analysis can be applied to the canonical curve instead of the original one. Since the first three points are fixed, the canonical curve is completely characterized by the position of its fourth point. The analysis therefore reduces to observing which region of the canonical plane the fourth point occupies. We demonstrate that for all parametric cubes expressed in this form, the boundaries of these regions are tonics and straight lines. Special cases include Bézier curves, B-splines, and Beta-splines. Such a characterization forms the basis for an easy and efficient solution to this problem.
Fast line scan-conversion
Authors: Rokne J. G. , Wyvill Brian , Wu Xiaolin
Published: July 2002

A major bottleneck in many graphics displays is the time required to scan-convert straight line segments. Most manufacturers use hardware based on Bresenham's [5] line algorithm. In this paper an algorithm is developed based on the original Bresenham scan-conversion together with the symmetry first noted by Gardner [18] and a recent double-step technique [31]. This results in a speed-up of scan-conversion by a factor of approximately 4 as compared to the original Bresenham algorithm. Hardware implementations are simple and efficient since the property of using only shift and increment operations is preserved.
VIRUS-CELL AND CELL-CELL FUSION
Authors: Hernandez L. D. , Hoffman L. R. , Wolfsberg T. G. , White J. M.
Published: July 2002

▪ Abstract  Significant progress has been made in elucidating the mechanisms of viral membrane fusion proteins; both those that function at low, as well as those that function at neutral, pH. For many viral fusion proteins evidence now suggests that a triggered conformational change that exposes a previously cryptic fusion peptide, along with a rearrangement of the fusion protein oligomer, allows the fusion peptide to gain access to the target bilayer and thus initiate the fusion reaction. Although the topologically equivalent process of cell-cell fusion is less well understood, several cell surface proteins, including members of the newly described ADAM gene family, have emerged as candidate adhesion/fusion proteins.