bluuebunny/crossref_metadata_2025 huggingface dataset:
Generating quadratic bilevel programming test problems
Authors: Calamai Paul H. , Vicente Luis N.
Published: July 2002

This paper describes a technique for generating sparse or dense quadratic bilevel programming problems with a selectable number of known global and local solutions. The technique described here does not require the solution of any subproblems. In addition, since most techniques for solving these problems begin by solving the corresponding relaxed quadratic program, the global solutions are constructed to be different than the global solution of this relaxed problem in a selectable number of upper- and lower-level variables. Finally, the problems that are generated satisfy the requirements imposed by all of the solution techniques known to the authors.
Remark on Algorithm 566
Authors: Averbukh Victoria Z. , Figueroa Samuel , Schlick Tamar
Published: July 2002

We report the development of second-derivative FORTRAN routines to supplement Algorithm 566 developed by J. More´ et al. (
ACM Trans. Math. Softw.
7, 14-41, 136–140, 1981). Algorithm 566 provides function and gradient subroutines of 18 test functions for multivariate minimization. Our supplementary Hessian segments enable users to test optimization software that requires second derivative information. Eigenvalue analysis throughout the minimization is now possible, with the goal of better understanding progress by different minimization algorithms and the relation of progress to eigenvalue distribution and condition number.
Certification of Algorithm 708
Authors: Brown Barry W. , Levy Lawrence B.
Published: July 2002

Algorithm 708 (BRATIO) was run on 2730 test cases. Comparison of these results with the results from an algorithm using a continued fraction of Tretter and Walster were performed using a high-precision version of the latter algorithm implemented in Maple. Accuracy of BRATIO ranged from 9.64 significant digits to a full machine double-precision, 15.65 significant digits, with the lower value occurring when
a
was nearly equal to
b
, and
a
was large.
Analysis of new variants of coalesced hashing
Authors: Chen Wen-Chin , Vitter Jeffrey Scott
Published: July 2002

The coalesced hashing method has been shown to be very fast for dynamic information storage and retrieval. This paper analyzes in a uniform way the performance of coalesced hashing and its variants, thus settling some open questions in the literature.

In all the variants, the range of the hash function is called the
address region
, and extra space reserved for storing colliders is called the
cellar
. We refer to the unmodified method, which was analyzed previously, as
late-insertion
coalesced hashing. In this paper we analyze late insertion and two new variations called
early insertion
and
varied insertion
. When there is no cellar, the early-insertion method is better than late insertion; however, past experience has indicated that it might be worse when there is a cellar. Our analysis confirms that it is worse. The varied-insertion method was introduced as a means of combining the advantages of late insertion and early insertion. This paper shows that varied insertion requires fewer probes per search, on the average, than do the other variants.

Each of these three coalesced hashing methods has a parameter that relates the sizes of the address region and the cellar. Techniques in this paper are designed for tuning the parameter in order to achieve optimum search times. We conclude with a list of open problems.
Empirical measurements of overheads in conservative asynchronous simulations
Authors: Bailey Mary L. , Pagels Michael A.
Published: July 2002

In order to make formal and analytic models more realistic, overheads which were previously ignored or vastly simplified must be included. We consider the feasibility of characterizing the overheads in conservative asynchronous simulations for such models, and we focus on a single communication structure (i.e., meshes) and use both multicomputer programs and a queueing network as example applications. We find that the two most important issues for modeling are to understand how to estimate the time spent in sending null messages and how to account for the resulting overhead due to the input waiting rule. For null messages, we estimate both the number of messages sent as well as the cost per null message. The number of messages sent can often be estimated by the application, although irregularities in communication structure and edge effects in communication can affect these estimates. A constant is valid as a first-order approximation for the time per null message, but there are secondary factors that one may wish to model, such as load balancing and communication irregularities. The overhead attributable to the input waiting rule depends on several factors: communication structure, communication frequency, and processor load balancing. Irregularity in any of these dimensions can adversely affect the performance of the conservative strategy. It appears feasible to use the factors contributing to the overheads (i.e. context switch costs; null-message costs; percentage of looping due to the conservative synchronization) in a formal model to estimate the cost of the conservative overheads.
A Fortran 90 environment for research and prototyping of enclosure algorithms for nonlinear equations and global optimization
Authors: Kearfott R. Baker
Published: July 2002

An environment for general research into and prototyping of algorithms for reliable constrained and unconstrained global nonlinear optimization and reliable enclosure of all roots of nonlinear systems of equations, with or without inequality constraints, is being developed. This environment should be portable, easy to learn, use, and maintain, and sufficiently fast for some production work. The motivation, design principles, uses, and capabilities for this environment are outlined. The environment includes an interval data type, a symbolic form of automatic differentiation to obtain an internal representation for functions, a special technique to allow conditional branches with operator overloading and interval computations, and generic routines to give interval and noninterval function and derivative information. Some of these generic routines use a special version of the backward mode of automatic differentiation. The package also includes dynamic data structures for exhaustive search algorithms.
In school or out
Authors: Rockman Saul
Published: July 2002

In January, Newt Gingrich proposed a tax credit for the poorest Americans to purchase laptop computers, forgetting for the moment that the poorest Americans do not pay taxes and thus a credit does them no good. In this case, his heart may be in the right place, even if he later called the idea “nutty.”
Ultra-structure
Authors: Long Jeffrey G. , Denning Dorothy E.
Published: July 2002

The physicist and Nobel laureate Ilya Prigogine states that “our understanding of nature is undergoing a radical change toward the multiple, the temporal, and the complex. Curiously, the unexpected complexity found in nature has not led to a slowdown in the progress of science, but on the contrary to the emergence of new conceptual structures that now appear as essential to our understanding of the physical world” [11]. We believe the challenges posed by complex systems arise primarily from the use of conceptual structures that worked well for static systems but do not work as well for more dynamic systems. We therefore propose new conceptual structures based on a different metaphysical view of the nature of complex systems.
Random number generators are chaotic
Authors: Herring Charles , Palmore Julian I.
Published: July 2002

The study of highly unstable nonlinear dynamical systems—chaotic systems—has emerged recently as an area of major interest and applicability across the mathematical, physical and social sciences. This interest has been triggered by advances in the past decade, particularly in the mathematical understanding of complex systems. An important insight that has become widely recognized in recent years is that deterministic systems can give rise to chaotic behavior. Surprisingly, many of these systems are extremely simple, yet they exhibit complex chaotic behavior.
The info superhighway
Authors: Shneiderman Ben
Published: July 2002

The opportunities are attractive, but some pavers of the Information Superhighway (ISH) are too eager to pour concrete. They risk making rough roads that will alienate the very users they seek. These technologically oriented ISH devotees may be building dramatic overpasses and painting stripes without figuring out where the highway should be going. I believe greater attention should be paid to identifying appropriate services, designing a consistent user interface, and developing a clearer model of the diverse user communities.
MASSIVE
Authors: Greenhalgh Chris , Benford Steven
Published: July 2002

We describe a prototype virtual reality teleconferencing system called MASSIVE which has been developed as part of our on-going research into collaborative virtual environments. This system allows multiple users to communicate using arbitrary combinations of audio, graphics, and text media over local and wide area networks. Communication is controlled by a so-called spatial model of interaction so that one user's perception of another user is sensitive to their relative positions and orientations. The key concept in this spatial model is the (quantitative)
awareness
which one object has of another. This is controlled by the observing object's
focus
and the observed object's
nimbus
, which describe regions of interest and projection, respectively. Each object's
aura
defines the total region within which it interacts. This is applied independently in each medium. The system (and the spatial model which it implements) is intended to provide a flexible and natural environment for the spatial mediation of conversation. The model also provides a basis for scaling to relatively large numbers of users. Our design goals include supporting heterogeneity, scalability, spatial mediation, balance of power, and multiple concurrent meetings; MASSIVE meets all of these goals. Our initial experiences show the importance of audio in collaborative VR, and they raise issues about field of view for graphical users, speed of navigation, quality of embodiment, varying perceptions of space, and scalability.
Recoverable sequence transmission protocols
Authors: Tempero Ewan D. , Ladner Richard E.
Published: July 2002

We consider the sequence transmission problem, that is, the problem of transmitting an infinite sequence of messages

x
1
x
2
x
3

… over a channel that can both lose and reorder packets. We define performance measures, ideal transmission cost and recovery cost, for protocols that solve the sequence transmission problem. Ideal transmission cost measures the number of packets needed to deliver

x
n

when the channel is behaving ideally and recovery cost measures how long it takes, in terms of number of messages delivered, for the ideal transmission cost to take hold once the channel begins behaving ideally. We also define lookahead, which measures the number of messages the sender can be ahead of the receiver in the protocol. We show that any protocol with constant recovery cost and lookahead requires linear ideal transmission cost. We describe a protocol, P
lin
, that has ideal transmission cost 2
n
, recovery cost 1, and lookahead 0.
Expected deadlock time in a multiprocessing system
Authors: Compton Kevin J. , Ravishankar Chinya
Published: July 2002

We consider multiprocessing systems where processes make independent, Poisson distributed resource requests with mean arrival time 1. We assume that resources are not released. It is shown that the expected deadlock time is never less than 1, no matter how many processes and resources are in the system. Also, the expected number of processes blocked by deadlock time is one-half more than half the number of initially active processes. We obtain expressions for system statistics such as expected deadlock time, expected total processing time, and system efficiency, in terms of Abel sums. We derive asymptotic expressions for these statistics in the case of systems with many processes and the case of systems with a fixed number of processes. In the latter, generalizations of the Ramanujan
Q
-function arise. we use singularity analysis to obtain asymptotics of coefficients of generalized
Q
-functions.
Query evaluation in deductive databases with alternating fixpoint semantics
Authors: Chen Weidong
Published: July 2002

First-order formulas allow natural descriptions of queries and rules. Van Gelder's alternating fixpoint semantics extends the well-founded semantics of normal logic programs to general logic programs with arbitrary first-order formulas in rule bodies. However, an implementation of general logic programs through the standard translation into normal logic programs does not preserve the alternating fixpoint semantics. This paper presents a direct method for goal-oriented query evaluation of general logic programs. Every general logic program is first transformed into a normal form where the body of each rule is either an existential conjunction of literals or a universal disjunction of literals. Techniques of memoing and loop checking are incorporated so that termination and polynomial-time data complexity are guaranteed for deductive databases (or function-free programs). Results of the soundness and search space completeness are established.
Evaluation of the CyberGlove as a whole-hand input device
Authors: Kessler G. Drew , Hodges Larry F. , Walker Neff
Published: July 2002

We present a careful evaluation of the sensory characteristics of the CyberGlove model CG1801 whole-hand input device. In particular, we conducted an experimental study that investigated the level of sensitivity of the sensors, their performance in recognizing angles, and factors that affected accuracy of recognition of flexion measurements. Among our results, we show that hand size differences among the subjects of the study did not have a statistical effect on the accuracy of the device. We also analyzed the effect of different software calibration approaches on accuracy of the sensors.
Industrial applications of distributed AI
Authors: Chaib-draa B.
Published: July 2002

Most work done in distributed artificial intelligence (DAI) had targeted sensory networks, including air traffic control, urban traffic control, and robotic systems. The main reason is that these applications necessitate distributed interpretation and distributed planning by means of intelligent sensors. Planning includes not only the activities to be undertaken, but also the use of material and cognitive resources to accomplish interpretation tasks and planning tasks. These application areas are also characterized by a natural distribution of sensors and receivers in space. In other words, the sensory data-interpretation tasks and action planning are inter-dependent in time and space. For example, in air traffic control, a plan for guiding an aircraft must be coordinated with the plans of other nearby aircraft to avoid collisions.
Rough sets
Authors: Pawlak Zdzislaw , Grzymala-Busse Jerzy , Slowinski Roman , Ziarko Wojciech
Published: July 2002

Rough set theory, introduced by Zdzislaw Pawlak in the early 1980s [11, 12], is a new mathematical tool to deal with vagueness and uncertainty. This approach seems to be of fundamental importance to artificial intelligence (AI) and cognitive sciences, especially in the areas of machine learning, knowledge acquisition, decision analysis, knowledge discovery from databases, expert systems, decision support systems, inductive reasoning, and pattern recognition.
Maiden voyage
Authors: Berghel Hal
Published: July 2002

Welcome to the first installment of Digital Village. This new column will be a reliable source of information on modern digital network technologies, particularly from the client side, and the use of those technologies for the betterment of society. In an attempt to provide information on cyberspace and its tools, we hope to be useful to readers in maintaining currency and perspective.
Sticky splines
Authors: van Overveld C. W. A. M. , Viaud Marie Luce
Published: July 2002

This paper describes an augmentation to the spline concept to account for topological relations between different spline curves. These topological relations include incidence relations, constraining the extremes of spline curves to other spline curves, and also more general geometric relations, for example, involving the tangents of spline curves in their extremes. To maintain these incidence relations, some spline curves may have to be transformed (translated, rotated, scaled), or even deformed (i.e., the shape of the curve may change) as a result of modifying other spline curves. A data structure and algorithms are given to implement the propagation of these transformations and deformations.

Based on the augmented spline concept, to be called
sticky splines
, both a script system to represent spline structures and an interactive system for editing drawings while automatically, maintaining their topological structure are presented.
Using local optimality criteria for efficient information retrieval with redundant information filters
Authors: Rowe Neil C.
Published: July 2002

We consider information retrieval when the data—for instance, multimedia—is computationally expensive to fetch. Our approach uses “information filters” to considerably narrow the universe of possibilities before retrieval. We are especially interested in redundant information filters that save time over more general but more costly filters. Efficient retrieval requires that decisions must be made about the necessity, order, and concurrent processing of proposed filters (an “execution plan”). We develop simple polynomial-time local criteria for optimal execution plans and show that most forms of concurrency are suboptimal with information filters. Although the general problem of finding an optimal execution plan is likely to be exponential in the number of filters, we show experimentally that our local optimality criteria, used in a polynomial-time algorithm, nearly always find the global optimum with 15 filters or less, a sufficient number of filters for most applications. Our methods require no special hardware and avoid the high processor idleness that is characteristic of massive-parallelism solutions to this problem. We apply our ideas to an important application, information retrieval of captioned data using natural-language understanding, a problem for which the natural-language processing can be the bottleneck if not implemented well.
Projecting the growth of cellular communications
Authors: Wang Michael , Kettinger William J.
Published: July 2002

The tremendous success of cellular technology has fundamentally changed the way people communicate and prompted the evolution of a new multibillion dollar wireless communications industry. Linking service areas, wireless communications has altered the way business is conducted. For instance, with a laptop computer, a PCMCIA modem and a cellular phone, a real estate agent can contact his or her office and clients, check sales listings and arrange appointments while traveling. Field service and sales people can, from customer locations, access corporate databases to check inventory status, prepare up-to-the-minute price and delivery quotes, and cut orders directly to the factory. Two-way paging services allow a firm's workforce to stay in close contact, even when traditional wired communication services are not available. Hand-held hybrids of phone-computer-fax machines feed information to wireless communication networks, allowing an executive to make decisions while watching a little league baseball game.
Automated consistency checking of requirements specifications
Authors: Heitmeyer Constance L. , Jeffords Ralph D. , Labaw Bruce G.
Published: July 2002

This article describes a formal analysis technique, called
consistency checking
, for automatic detection of errors, such as type errors, nondeterminism, missing cases, and circular definitions, in requirements specifications. The technique is designed to analyze requirements specifications expressed in the SCR (Software Cost Reduction) tabular notation. As background, the SCR approach to specifying requirements is reviewed. To provide a formal semantics for the SCR notation and a foundation for consistency checking, a formal requirements model is introduced; the model represents a software system as a finite-state automation which produces externally visible outputs in response to changes in monitored environmental quantities. Results of two experiments are presented which evaluated the utility and scalability of our technique for consistency checking in real-world avionics application. The role of consistency checking during the requirements phase of software development is discussed.
Using the SLEDGE package on Sturm-Liouville problems having nonempty essential spectra
Authors: Eastham Michael S. P. , Fulton Charles T. , Pruess Steven
Published: July 2002

We describe the performance of the Sturm-Liouville software package SLEDGE on a variety of problems having continuous spectra. The code's output is shown to be in good accord with a wide range of known theoretical results.
A remark on Bartels and Conn's linearly constrained, discrete
l
1
problems
Authors: Koenker Roger W. , Ng Pin T.
Published: July 2002

Two modifications of Bartels and Conn's algorithm for solving linearly constrained discrete
l
1
problems are described. The modifications are designed to improve performance of the algorithm under conditions of degeneracy.
Task dependence and termination in Ada
Authors: Dillon Laura K.
Published: July 2002

This article analyzes the semantics of task dependence and termination in Ada. We use a contour model of Ada tasking in examining the implications of and possible motivation for the rules that determine when procedures and tasks terminate during execution of an Ada program. The termination rules prevent the data that belong to run-time instances of scope units from being deallocated prematurely, but they are unnecessarily conservative in this regard. For task instances that are created by invoking a storage allocator, we show that the conservative termination policy allows heap storage to be managed more efficiently than a less conservative policy. The article also examines the manner in which the termination rules affect the synchronization of concurrent tasks. Master-slave and client-server applications are considered. We show that the rules for distributed termination of concurrent tasks guarantee that a task terminates only if it can no longer affect the outcome of an execution. The article is meant to give programmers a better understanding of Ada tasking and to help language designers assess the strengths and weaknesses of the termination model.
Putting the U.S. standardization system into perspective
Authors: Toth Bob
Published: July 2002

The odds are very high that an American attending an international standardization meeting or consulting in a foreign country will be asked about the U.S. standardization system. How is it organized? Who is responsible for developing standards? How many standards? Who sees to their implementation? What is the government's role? Why is there more than one standard for many commodities? Foreign engineers who are used to dealing with their national standards institute can be very critical of the decentralized U.S. system. Many are dissuades from applying U.S. standards because of real or anticipated problems in choosing, obtaining, and applying them. Many Americans raise similar questions. Some think that all standards come from the government. While most U.S. standardization specialists are familiar with the standards in their fields, few have an overview of the U.S. standardization system.
Computer professionals whose scientific freedom and human rights have been violated—1984
Authors: Minker Jack
Published: July 2002

This is the third report prepared by the ACM Committee on Scientific Freedom and Human Rights (CSFHR). The first was published in the March 1981 Communications and the second in the December 1982 issue. This report is an update. Since the committee intends to publish future updates, it would appreciate receiving further information about computer scientists whose rights have been violated. Such information should be sent to: Jack Minker, Vice-Chairman, Committee on Scientific Freedom and Human Rights, Department of Computer Science, University of Maryland, College Park, MD 29742.

Because those whose scientific freedom or human rights have been violated derive sustenance and support from contacts with their colleagues, the CSFHR has established a program in which ACM chapters “adopt” individual scientists and correspond with them. Such correspondence should touch on the personal and scientific and not discuss political matters. These letters greatly improve the morale of the recipients and are one of the few ways they can keep current with computer science and technology. This CSFHR program is directed by Helen Takacs (P.O. Drawer CS, Mississippi State, MS 39762).
Optimally adaptive, minimum-distance, circuit-switched routing in hypercubes
Authors: Mahmood Ausif , Lynch Donald J. , Shaffer Roger B.
Published: July 2002

In circuit-switched routing, the path between a source and its destination is established by incrementally reserving all required links before the data transmission can begin. If the routing algorithm is not carefully designed, deadlocks can occur in reserving these links. Deadlock-free algorithms based on dimension-ordered routing, such as the
E-cube
, exist. However,
E-cube
does not provide any flexibility in choosing a path from a source to its destination and can thus result in long latencies under heavy or uneven traffic. Adaptive, minimum-distance routing algorithms, such as the
Turn Model
and the
UP Preference
algorithms, have previously been reported. In this article, we present a new class of adaptive, provably deadlock-free, minimum-distance routing algorithms. We prove that the algorithms developed here are optimally adaptive in the sense that any further flexibility in communication will result in deadlock. We show that the
Turn Model
is actually a member of our new class of algorithms that does not perform as well as other algorithms within the new class. It creates artificial hotspots in routing the traffic and allows fewer total paths. We present an analytical comparison of the flexibility and balance in routing provided by various algorithms and a comparison based on uniform and nonuniform traffic simulations. The
Extended UP Preference
algorithm developed in this article is shown to have improved performance with respect to existing algorithms. The methodology and the algorithms developed here can be used to develop routing for other schemes such as wormhole routing, and for other recursively defined networks such as
k
-ary
n
-cubes.
Separators for sphere-packings and nearest neighbor graphs
Authors: Miller Gary L. , Teng Shang-Hua , Thurston William , Vavasis Stephen A.
Published: July 2002

A collection of
n
balls in
d
dimensions forms a
k
-ply system if no point in the space is covered by more than
k
balls. We show that for every
k
-ply system Γ, there is a sphere
S
that intersects at most
O
(
k

1/
d

n

1−1/
d

) balls of Γ and divides the remainder of Γ into two parts: those in the interior and those in the exterior of the sphere
S
, respectively, so that the larger part contains at most (1−1/(
d
+2))
n
balls. This bound of (
O
(
k

1/
d

n

1−1/
d

) is the best possible in both
n
and
k
. We also present a simple randomized algorithm to find such a sphere in
O(n)
time. Our result implies that every
k
-nearest neighbor graphs of
n
points in
d
dimensions has a separator of size
O
(
k

1/
d

n

1−1/
d

). In conjunction with a result of Koebe that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, our result not only gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions. The separator algorithm can be used for point location and geometric divide and conquer in a fixed dimensional space.
A formal basis for architectural connection
Authors: Allen Robert , Garlan David
Published: July 2002

As software systems become more complex, the overall system structure—or software architecture—becomes a central design problem. An important step toward an engineering discipline of software is a formal basis for describing and analyzing these designs. In the article we present a formal approach to one aspect of architectural design: the interactions among components. The key idea is to define architectural connectors as explicit semantic entities. These are specified as a collection of protocols that characterize each of the participant roles in an interaction and how these roles interact. We illustrate how this scheme can be used to define a variety of common architectural connectors. We further provide a formal semantics and show how this leads to a system in which architectural compatibility can be checked in a way analogous to type-checking in programming languages.
Generating box-constrained optimization problems
Authors: Facchinei Francisco , Júdice Joaquim , Soares João
Published: July 2002

We present a method for generating box-constrained nonlinear programming test problems. The technique allows the user to control some properties of the generated test problems that are know to influence the behavior of algorithms for their solution. A corresponding set of Fortran 77 routines is described in a companion algorithm (774).
Delta algorithms
Authors: Hunt James J. , Vo Kiem-Phong , Tichy Walter F.
Published: July 2002

Delta algorithms compress data by encoding one file in terms of another. This type of compression is useful in a number of situations: strong multiple versions of data, displaying differences, merging changes, distributing updates, storing backups, transmitting video sequences, and others. This article studies the performance parameters of several delta algorithms, using a benchmark of over 1,300 pairs of files taken from two successive releases of GNU software. Results indicate that modern delta compression algorithms based on Ziv-Lempel techniques significantly outperform
diff
, a popular but older delta compressor, in terms of compression ratio. The modern compressors also correlate better with the actual difference between files without sacrificing performance.
An efficient algorithm for the “optimal” stable marriage
Authors: Irving Robert W. , Leather Paul , Gusfield Dan
Published: July 2002

In an instance of size
n
of the stable marriage problem, each of
n
men and
n
women ranks the members of the opposite sex in order of preference. A stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. It is well known [2] that at least one stable matching exists for every stable marriage instance. However, the classical Gale-Shapley algorithm produces a marriage that greatly favors the men at the expense of the women, or vice versa. The problem arises of finding a stable matching that is optimal under some more equitable or egalitarian criterion of optimality. This problem was posed by Knuth [6] and has remained unsolved for some time. Here, the objective of maximizing the average (or, equivalently, the total) “satisfaction” of all people is used. This objective is achieved when a person's satisfaction is measured by the position of his/her partner in his/her preference list. By exploiting the structure of the set of all stable matchings, and using graph-theoretic methods, an
O
(
n
4
) algorithm for this problem is derived.
Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP
Authors: Resende Mauricio G. C. , Feo Thomas A. , Smith Stuart H.
Published: July 2002

Let G=(V, E) be an undirected graph where V and E are the sets of vertices and edges of G, respectively. A subset of the vertices S ⊆ V is independent if all of its members are pairwise nonadjacent, i.e., have no edge between them. A solution to the NP-hard maximum independent set problem is an independent set of maximum cardinality. This article describes gmis, a set of Fortran subroutines to find an approximate solution of a maximum independent set problem. A greedy randomized adaptive search procedure (GRASP) is used to produce the solutions. The algorithm is described in detail. Implementation and usage of the package is outlined, and computational experiments are reported, illustrating solution quality as a function of running time.
Transforming cabbage into turnip
Authors: Hannenhalli Sridhar , Pevzner Pavel A.
Published: July 2002

Genomes frequently evolve by reversals ρ(
i,j
) that transform a gene order π
1
… π

i

π

i
+1

… π

j
-1

π

j

… π

n

into π
1
… π

i

π

j
-1

… π

i
+1

π

j

… π

n

. Reversal distance between permutations π and σis the minimum number of reversals to transform π into Α. Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions between the species of
Drosophilia
. Analysis of genomes evolving by inversions leads to a combinatorial problem of
sorting by reversals
studied in detail recently. We study sorting of
signed
permutations by reversals, a problem that adequately models rearrangements in a small genomes like chloroplast or mitochondrial DNA. The previously suggested approximation algorithms for sorting signed permutations by reversals compute the
reversal distance
between permutations with an astonishing accuracy for both simulated and biological data. We prove a duality theorem explaining this intriguing performance and show that there exists a “hidden” parameter that allows one to compute the reversal distance between signed permutations in polynomial time.
The specification and enforcement of authorization constraints in workflow management systems
Authors: Bertino Elisa , Ferrari Elena , Atluri Vijay
Published: July 2002

In recent years, workflow management systems (WFMSs) have gained popularity in both research and commercial sectors. WFMSs are used to coordinate and streamline business processes. Very large WFMSs are often used in organizations with users in the range of several thousands and process instances in the range of tens and thousands. To simplify the complexity of security administration, it is common practice in many businesses to allocate a role for each activity in the process and then assign one or more users to each role—granting an authorization to roles rather than to users. Typically, security policies are expressed as constraints (or rules) on users and roles;
separation of duties
is a well-known constraint. Unfortunately, current role-based access control models are not adequate to model such constraints. To address this issue we (1) present a language to express both static and dynamic authorization constraints as clauses in a logic program; (2) provide formal notions of constraint consistency; and (3) propose algorithms to check the consistency of constraints and assign users and roles to tasks that constitute the workflow in such a way that no constraints are violated.
Two-stage multiple-comparison procedures for steady-state simulations
Authors: Damerdji Halim , Nakayama Marvin K.
Published: July 2002

Procedures for multiple comparisons with the best are investigated in the context of steady-state simulation, whereby a number
k
of different systems (stochastic processes) are compared based upon their (asymptotic) means μ

i

(
i
= 1,2,…,
k
). The variances of these (asymptotically stationary) processes are assumed to be unknown and possibly unequal. We consider the problem of constructing simultaneous confidence intervals for μ
i
-max
j≠i
μ
j
( i=1,2,…,k) which is known as multiple comparisons with the best (MCB). Our intervals are constrained to contain 0, and so are called constrained MCB intervals. In particular, two-stage procedures for construction of absolute- and relative-width confidence intervals are presented. Their validity is addressed by showing that the confidence intervals cover the parameters with probability of at least some user-specified threshold value, as the confidence intervals' width parameter shrinks to 0. The general assumption about the processes is that they satisfy a functional central limit theorem. The simulation output analysis procedures are based on the method of standardized time series (the batch means method is a special case). The techniques developed here extend to other multiple-comparison procedures such as unconstrained MCB, multiple comparisons with a control, and all-pairwise comparisons. Although simulation is the context in this paper, the results naturally apply to (asymptotically) stationary time series.
Use of graph-theoretic models for optimal relational database accesses to perform join
Authors: Pramanik Sakti , Ittner David
Published: July 2002

A graph model is presented to analyze the performance of a relational join. The amount of page reaccesses, the page access sequence, and the amount of buffer needed are represented in terms of graph parameters. By using the graph model formed from the index on the join attributes, we determine the relationships between these parameters. Two types of buffer allocation strategies are studied, and the upper bound on the buffer size with no page reaccess is given. This bound is shown to be the maximum cut value of a graph. Hence, the problem of computing this upper bound is NP-hard. We also give algorithms to determine a page access sequence requiring a near optimal buffer size with no page reaccess. The optimal page access sequence for a fixed buffer size has also been considered.
A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor
Authors: Kaminski Michael
Published: July 2002

An algorithm is presented to compute the residue of a polynomial over a finite field of degree
n
modulo a polynomial of degree
O
(log
n
) in
O
(
n
) algebraic operations. This algorithm can be implemented on a Turing machine. The implementation is based on
Turing machine
procedure that divides a polynomial of degree
n
by a sparse polynomial with
k
nonzero coefficients in
O
(
kn
) steps. This algorithm can be adapted to compute the residue of a number of length
n
modulo a number of length
O
(log
n
) in
O
(
n
) bit operations.
CASDAL
Authors: Su Stanley Y. W. , Emam Ahmed
Published: July 2002

CASDAL is a high level data language designed and implemented for the database machine CASSM. The language is used for the manipulation and maintenance of a database using an unnormalized (hierarchically structured) relational data model. It also has facilities to define, modify, and maintain the data model definition. The uniqueness of CASDAL lies in its power to specify complex operations in terms of several new language constructs and its concepts of tagging or marking tuples and of matching values when walking from relation to relation. The language is a result of a top-down design and development effort for a database machine in which high level language constructs are directly supported by the hardware. This paper (1) gives justifications for the use of an unnormalized relational model on which the language is based, (2) presents the CASDAL language constructs with examples, and (3) describes CASSM's architecture and hardware primitives which match closely with the high level language constructs and facilitate the translation process. This paper also attempts to show how the efficiency of the language and the translation task can be achieved and simplified in a system in which the language is the result of a top-down system design and development.
Distance browsing in spatial databases
Authors: Hjaltason Gísli R. , Samet Hanan
Published: July 2002

We compare two different techniques for browsing through a collection of spatial objects stored in an R-tree spatial data structure on the basis of their distances from an arbitrary spatial query object. The conventional approach is one that makes use of a
k
-nearest neighbor algorithm where
k
is known prior to the invocation of the algorithm. Thus if
m
<
k
neighbors are needed, the
k
-nearest neighbor algorithm has to be reinvoked for
m
neighbors, thereby possibly performing some redundant computations. The second approach is incremental in the sense that having obtained the
k
nearest neighbors, the
k
+ 1

st

neighbor can be obtained without having to calculate the
k
+ 1 nearest neighbors from scratch. The incremental approach is useful when processing complex queries where one of the conditions involves spatial proximity (e.g., the nearest city to Chicago with population greater than a million), in which case a query engine can make use of a pipelined strategy. We present a general incremental nearest neighbor algorithm that is applicable to a large class of hierarchical spatial data structures. This algorithm is adapted to the R-tree and its performance is compared to an existing
k
-nearest neighbor algorithm for R-trees [Rousseopoulos et al. 1995]. Experiments show that the incremental nearest neighbor algorithm significantly outperforms the
k
-nearest neighbor algorithm for distance browsing queries in a spatial database that uses the R-tree as a spatial index. Moreover, the incremental nearest neighbor algorithm usually outperforms the
k
-nearest neighber algorithm when applied to the
k
-nearest neighbor problem for the R-tree, although the improvement is not nearly as large as for distance browsing queries. In fact, we prove informally that at any step in its execution the incremental nearest neighbor algorithm is optimal with respect to the spatial data structure that is employed. Furthermore, based on some simplifying assumptions, we prove that in two dimensions the number of distance computations and leaf nodes accesses made by the algorithm for finding
k
neighbors is
O
(
k
+
k
).
Specialized merge processor networks for combining sorted lists
Authors: Hollaar Lee A.
Published: July 2002

In inverted file database systems, index lists consisting of pointers to items within the database are combined to form a list of items which potentially satisfy a user's query. This list merging is similar to the common data processing operation of combining two or more sorted input files to form a sorted output file, and generally represents a large percentage of the computer time used by the retrieval system. Unfortunately, a general purpose digital computer is better suited for complicated numeric processing rather than the simple combining of data. The overhead of adjusting and checking pointers, aligning data, and testing for completion of the operation overwhelm the processing of the data.

A specialized processor can perform most of these overhead operations in parallel with the processing of the data, thereby offering speed increases by a factor from 10 to 100 over conventional computers, depending on whether a higher speed memory is used for storing the lists. These processors can also be combined into networks capable of directly forming the result of a complex expression, with another order of magnitude speed increase possible. The programming and operation of these processors and networks is discussed, and comparisons are made with the speed and efficiency of conventional general purpose computers.
On The Ambiguity Problem of Backus Systems
Authors: Cantor David G.
Published: July 2002

Backus [1] has developed an elegant method of defining well-formed formulas for computer languages such as ALGOL. It consists of (our notation is slightly different from that of Backus):

A finite alphabet:
a
1
,
a
2
, …,

a
t

;

Predicates:
P
1
,
P
2
, …,
P
ϵ
;

Productions, either of the form (a)

a
j

∈

P
i

;
Single-Scan Techniques for the Translation of Arithmetic Expressions in ALGOL 60
Authors: Randell B. , Russell L. J.
Published: July 2002

The first section of the paper contains a brief description of the well-known technique of using a stack, or pushdown store, to re-order the operators of an arithmetic expression, as defined in ALGOL 60, in order to transform the expression into Reverse Polish parenthesis-free form. It is shown that improvements to this Reverse Polish form can be made quite simply, by extending the use of the stack to include information about the operands of the expression. Firstly, information gained from the declarations of the operands can be used to control the generation of real-integer conversion instructions. Secondly, operators whose operands are numerical constants can be computed during translation, using the partially generated Reverse Polish object program as a second stack.
Realization of Input-Output Relations by Sequential Machines
Authors: Gill A.
Published: July 2002

This paper deals with the synthesis of sequential machines (without a distinguished initial state) which satisfies a specified list of input sequences and corresponding output sequences. Readily testable necessary and sufficient conditions are given for such a list to result in a realizable machine, and an algorithm is formulated for constructing the machine when these conditions are fulfilled.
Analysis of Two Time-Sharing Algorithms Designed for Limited Swapping
Authors: Coffman E. G.
Published: July 2002

The necessity for swapping in the operation of modern time-sharing systems constitutes the major reason for the latter's inefficiency compared to batch-processing systems. Time-sharing algorithms are discussed which are designed primarily for the reduction of swapping without intolerable changes in the waiting time distributions. A particular class of such algorithms in which conventional procedures are modified by making the quantum allocation dependent on input activity is given a more detailed treatment. In particular, queueing models corresponding to these algorithms are devised and then analyzed for the purpose of obtaining the mean waiting times conditioned on the service required. These results are then compared to those obtained for the conventional models and the comparison subsequently measured against the swapping requirements of the two classes of algorithms.
The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
Authors: Griffiths T. V.
Published: July 2002

It is shown that the equivalence problem for A-free nondeterministic generalized machines is unsolvable, and it is observed that this result implies the unsolvability of the equality problem for
c
-finite languages.
Properties of Programs and the First-Order Predicate Calculus
Authors: Manna Zohar
Published: July 2002

This paper is concerned with the relationship of the termination problem for programs and abstract programs to the validity of certain formulas in the first-order predicate calculus. By exploiting this relationship, subclasses of abstract programs for which the termination problem is decidable can be isolated. Moreover, known proof procedures for the first-order predicate calculus (e.g. resolution) can be applied to prove the termination of both programs and abstract programs. The correctness and equivalence problems of abstract programs are shown to be reducible to the termination problem.