bluuebunny/crossref_metadata_2025 huggingface dataset:
Enhanced simulated annealing for globally minimizing functions of many-continuous variables
Authors: Siarry Patrick , Berthiau Gérard , Durdin François , Haussy Jacques
Published: July 2002

A new global optimization algorithm for functions of many continuous variables is presented, derived from the basic Simulated annealing method. Our main contribution lies in dealing with high-dimensionality minimization problems, which are often difficult to solve by all known minimization methods with or without gradient. In this article we take a special interest in the variables discretization issue. We also develop and implement several complementary stopping criteria. The original Metropolis iterative random search, which takes place in a Euclidean space
R

n

, is replaced by another similar exploration, performed within a succession of Euclidean spaces
R

p

, with
p
<<
n
. This Enhanced Simulated Annealing (ESA) algorithm was validated first on classical highly multimodal functions of 2 to 100 variables. We obtained significant reductions in the number of function evaluations compared to six other global optimization algorithms, selected according to previously published computational results for the same set of test functions. In most cases, ESA was able to closely approximate known global optima. The reduced ESA computational cost helped us to refine further the obtained global results, through the use of some local search. We have used this new minimizing procedure to solve complex circuit design problems, for which the objective function evaluation can be exceedingly costly.
Object normal forms and dependency constraints for object-oriented schemata
Authors: Tari Zahir , Stokes John , Spaccapietra Stefano
Published: July 2002

We address the development of a normalization theory for object-oriented data models that have common features to support objects. We first provide an extension of functional dependencies to cope with the richer semantics of relationships between objects, called
path dependency, local dependency,
and
global dependency
constraints. Using these dependency constraints, we provide normal forms for object-oriented data models based on the notions of
user interpretation
(user-specified dependency constraints) and
object model
. In constrast to conventional data models in which a normalized object has a unique interpretation, in object-oriented data models, an object may have many multiple interpretations that form the model for that object. An object will then be in a normal form if and only if the user's interpretation is derivable from the model of the object. Our normalization process is by nature iiterative, in which objects are restructured until their models reflect the user's interpretation.
Elastic time
Authors: Srinivasan Sudhir , Reynolds Paul F.
Published: July 2002

We introduce a new class of synchronization protocols for parallel discrete event simulation, those based on
near-perfect state information
(NPSI). NPSI protocols are adaptive dynamically controlling the rate at which processes constituting a parallel simulation proceed with the goal of completing a simulation efficiently. We show by analysis that a class of adaptive protocols (that includes NPSI and several others) can both arbitrarily outperform and be arbitrarily outperformed by the Time Warp synchronization protocol. This mixed result both substantiates the promising results we and other adaptive protocol designers have observed, and cautions those who might assume that any adaptive protocol will always be better than any nonadaptive one. We establish in an experimental study that a particular NPSI protocol, the
Elastic Time Algorithm
, outperforms Time Warp, both temporally and spatially on every workload tested. Although significant options remain with respect to the design of ETA, the work presented here establishes the class of NPSI protocols as a very promising approach.
New applications of failure functions
Authors: Hirschberg D. S. , Larmore L. L.
Published: July 2002

Presented are several algorithms whose operations are governed by a principle of failure functions: When searching for an extremal value within a sequence, it suffices to consider only the subsequence of items each of which is the first possible improvement of its predecessor. These algorithms are more efficient than their more traditional counterparts.
On the crossing distribution problem
Authors: Song Xiaoyu , Wang Yuke
Published: July 2002

VLSI layout design is typically decomposed into four steps:
placement, global routing, routing region definition, and detailed routing.
The crossing distribution problem occurs prior to detailed routing [Groenveld 1989; Mared-Sadowska and Sarrafzadeh 1995; Wang and Shung 1992]. A
crossing
is defined as the intersection of two nets. The problem of net crossing distribution is important in layout design, such as design of dense chips, multichip modules (MCM), critical net routing, and analog circuits [Groenveld 1989; Sarrafzadah 1995; Wang and Shung 1992]. It is observed that nets crossing each other are more difficult to route than those that do not cross. The layout of crossing nets has to be realized in more than two layers and requires a larger number of
vias
In this paper we study the crossing distribution problem of two-terminal nets between two regions. We present an optimal O(n2) time algorithm for two-sided nets, where n is the number of nets. Our results are superior to previous ones [Markek-Sadowska and Sarrafzadeh 1995; Wang and Shung 1992]. We give an optimal O(n
2
) time algorithm for the crossing distribution problem with one-sided nets. We solve optimally the complete version of the crossing distribution problem for two-terminal nets in two regions that has not been studied before.
Manual and cognitive benefits of two-handed input
Authors: Leganchuk Andrea , Zhai Shumin , Buxton William
Published: July 2002

One of the recent trends in computer input is to utilize users' natural bimanual motor skills. This article further explores the potential benefits of such two-handed input. We have observed that bimanual manipulation may bring two types of advantages to human-computer interaction: manual and cognitive. Manual benefits come from increased time-motion efficiency, due to the twice as many degrees of freedom simultaneously available to the user. Cognitive benefits arise as a result of reducing the load of mentally composing and visualizing the task at an unnaturally low level which is imposed by traditional unimanual techniques. Area sweeping was selected as our experimental task. It is representative of what one encounters, for example, when sweeping out the bounding box surrounding a set of objects in a graphics program. Such tasks cannot be modeled by Fitts' Law alone and have not been previously studied in the literature. In our experiments, two bimanual techniques were compared with the conventional one-handed GUI approach. Both bimanual techniques employed the two-handed “stretchy” technique first demonstrated by Krueger in 1983. We also incorporated the “Toolglass” technique introduced by Bier et al. in 1993. Overall, the bimanual techniques resulted in significantly faster performance than thestatus quoone-handed technique, and these benefits increased with the difficulty of mentally visualizing the task, supporting our bimanual cognitive advantage hypothesis. There was no significant difference between the two bimanual techniques. This study makes two types of contributions to the literature. First, practically we studied yet another class of transaction where significant benefits can be realized by applying bimanual techniques. Furthermore, we have done so using easily available commercial hardware in the context to our understanding of why bimanual interaction techniques have an advantage over unimanual techniques. A literature review on two-handed computer input and some of the relevant bimanual human mototr control studies is also included.
Parallel streams of linear random numbers in the spectral test
Authors: Entacher Karl
Published: July 2002

This paper reports analyses of subsequences of linear congruential pseudorandom numbers by means of the spectral test. Such subsequences occur in particular simulation setups or as methods to obtain parallel streams of pseudorandom numbers for parallel and distributed simulation. Especially in the latter case, two kinds of substreams are of special interest: lagged random numbers with step sizes
k
, and consecutive streams of random numbers of length
l
. We show how to analyze correlations within and between lagged subsequences with arbitrary step sizes
k
. Analyzing consecutive streams with the spectral test is related to the well-known long-range correlation analysis of linear congruential generators. Whereas the latter was carried out to show correlations between pairs of processors only, the spectral test provides a convenient method to study correlations between larger numbers of parallel streams as well.
RecPlay
Authors: Ronsse Michiel , De Bosschere Koen
Published: July 2002

This article presents a practical solution for the cyclic debugging of nondeterministic parallel programs. The solution consists of a combination of record/replay with automatic on-the-fly data race detection. This combination enables us to limit the record phase to the more efficient recording of the synchronization operations, while deferring the time-consuming data race detection to the replay phase. As the record phase is highly efficient, there is no need to switch it off, hereby eliminating the possibility of Heisenbugs because tracing can be left on all the time. This article describes an implementation of the tools needed to support RecPlay.
The theory of joins in relational databases
Authors: Aho A. V. , Beeri C. , Ullman J. D.
Published: July 2002

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the join of several relations has the intuitively expected value (is
lossless
) and to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.
On searching transposed files
Authors: Batory D. S.
Published: July 2002

A transposed file is a collection of nonsequential files called subfiles. Each subfile contains selected attribute data for all records. It is shown that transposed file performance can be enhanced by using a proper strategy to process queries. Analytic cost expressions for processing conjunctive, disjunctive, and batched queries are developed and an effective heuristic for minimizing query processing costs is presented. Formulations of the problem of optimally processing queries for a particular family or transposed files are shown to be NP-complete. Query processing performance comparisons of multilist, inverted, and nonsequential files with transposed files are also considered.
Decomposition—a strategy for query processing
Authors: Wong Eugene , Youssefi Karel
Published: July 2002

Strategy for processing multivariable queries in the database management system INGRES is considered. The general procedure is to decompose the query into a sequence of one-variable queries by alternating between (a) reduction: breaking off components of the query which are joined to it by a single variable, and (b) tuple substitution: substituting for one of the variables a tuple at a time. Algorithms for reduction and for choosing the variable to be substituted are given. In most cases the latter decision depends on estimation of costs; heuristic procedures for making such estimates are outlined.
Multivalued dependencies and a new normal form for relational databases
Authors: Fagin Ronald
Published: July 2002

A new type of dependency, which includes the well-known functional dependencies as a special case, is defined for relational databases. By using this concept, a new (“fourth”) normal form for relation schemata is defined. This fourth normal form is strictly stronger than Codd's “improved third normal form” (or “Boyce-Codd normal form”). It is shown that every relation schema can be decomposed into a family of relation schemata in fourth normal form without loss of information (that is, the original relation can be obtained from the new relations by taking joins).
SNOBOL , A String Manipulation Language
Authors: Farber D. J. , Griswold R. E. , Polonsky I. P.
Published: July 2002

SNOBOL is a programming language for the manipulation of strings of symbols. A statement in the SNOBOL language consists of a rule that operates on symbolically named strings. The basic operations are string formation, pattern matching and replacement. Facilities for integer arithmetic, indirect referencing, and input-output are included. In the design of the language, emphasis has been placed on a format that is simple and intuitive. SNOBOL has been implemented for the IBM 7090.
Programming Language for Automata
Authors: Knuth Donald E. , Bigelow Richard H.
Published: July 2002

The techniques of automatic programming are useful for constructive proofs in automata theory. A formal definition of an elementary programming language for a stack automaton is given, and it is shown how this may be readily adapted to other classes of automata. The second part of this paper shows how this programming language can be applied to automata theory, as we prove there are non-context-sensitive languages accepted by a stack automaton.
Mechanical Theorem-Proving by Model Elimination
Authors: Loveland Donald W.
Published: July 2002

A proof procedure based on a theorem of Herbrand and utilizing the matching technique of Prawitz is presented. In general, Herbrand-type proof procedures proceed by generating over increasing numbers of candidates for the truth-functionally contradictory statement the procedures seek. A trial is successful when some candidate is in fact a contradictory statement. In procedures to date the number of candidates developed before a contradictory statement is found (if one is found) varies roughly exponentially with the size of the contradictory statement. (“Size” might be measured by the number of clauses in the conjunctive normal form of the contradictory statement.) Although basically subject to the same rate of growth, the procedure introduced here attempts to drastically trim the number of candidates at an intermediate level of development. This is done by retaining beyond a certain level only candidates already “partially contradictory.” The major task usually is finding the partially contradictory sets. However, the number of candidate sets required to find these subsets of the contradictory set is generally much smaller than the number required to find the full contradictory set.
Experiments With Some Programs That Search Game Trees
Authors: Slagle James R. , Dixon John E.
Published: July 2002

Many problems in artificial intelligence involve the searching of large trees of alternative possibilities—for example, game-playing and theorem-proving. The problem of efficiently searching large trees is discussed. A new method called “dynamic ordering” is described, and the older minimax and Alpha-Beta procedures are described for comparison purposes. Performance figures are given for six variations of the game of kalah. A quantity called “depth ratio” is derived which is a measure of the efficiency of a search procedure. A theoretical limit of efficiency is calculated and it is shown experimentally that the dynamic ordering procedure approaches that limit.
A Note on Star-Free Events
Authors: Meyer Albert R.
Published: July 2002

It is shown that a short proof of the equivalence of star-free and group-free regular events is possible if one is willing to appeal to the Krohn-Rhodes machine decomposition theorem.
Bounds for Some Functions Concerning Dynamic Storage Allocation
Authors: Robson J. M.
Published: July 2002

The amount of store necessary to operate a dynamic storage allocation system, subject to certain constraints, with no risk of breakdown due to storage fragmentation, is considered. Upper and lower bounds are given for this amount of store, both of them stronger than those established earlier. The lower bound is the exact solution of a related problem concerning allocation of blocks whose size is always a power of 2.
Simple and efficient bounded concurrent timestamping and the traceable use abstraction
Authors: Dwork Cynthia , Waarts Orli
Published: July 2002

In atimestamping system, processors repeatedly choose timestamps so that the order of the timestamps obtained reflects the real-time order in which they were requested.Concurrent timestamping systemspermit requests by multiple processors to be issued concurrently; inbounded timestamping systemsthe sizes of the timestamps and the size and number of shared variables are bounded. An algorithm iswait-freeif there exists ana prioribound on the number of steps a processor must take in order to make progress, independent of the action or inaction of other processors. Lettingndenote the number of procesors, we construct a simple wait-free bounded concurrent timestamping system requiringO(n) steps (accesses to shared memory) for a processor to read the current timestamps and determine the order among them, andO(n) steps to generate a timestamp, independent of the actions of the other processors. In addition, we introduce and implement thetraceable useabstraction, a new primitive providing “inventory control” over values introduced by processors in the course of an algorithm execution. This abstraction has proved to be of great value in converting unbounded algorithms to bounded ones {Attiya and Rachman 1998; Dwork et al. 1992; 1993].
Existential second-order logic over strings
Authors: Eiter Thomas , Gottlob Georg , Gurevich Yuri
Published: July 2002

Existential second-order logic (ESO) and monadic second-order logic(MSO) have attracted much interest in logic and computer science. ESO is a much expressive logic over successor structures than MSO. However, little was known about the relationship between MSOand syntatic fragments of ESO. We shed light on this issue by completely characterizing this relationship for the prefix classes of ESO over strings, (i.e., finite successor structures). Moreover, we determine the complexity of model checking over strings, for all ESO-prefix classes. Let ESO(
Q
) denote the prefix class containing all sentences of the shape ∃
R
Q
4 , where
R
is a list of predicate variables,
Q
is a first-order predicate qualifier from the prefix set
Q
and 4 is quantifier-free. We show that ESO( ∃
*
∀∃∃∃
*
) and ESO( ∃
*
∀∀ ) are the maximal standard ESO-prefix classes contained in MSO, thus expressing only regular languages. We further prove the following dichotomy theorem: An ESO prefix-class either expresses only regular languages (and is thus in MSO), or it expresses some NP-complete languages. We also give a precise characterization of those ESO-prefix classes that are
equivalent
to MSO over strings, and of the ESO-prefix classes which are closed under complementation on strings.
Programming languages and systems for prototyping concurrent applications
Authors: Hasselbring Wilhelm
Published: July 2002

Concurrent programming is conceptually harder to undertake and to
understand than sequential programming, because a programmer has to manage the coexistence and coordination of multiple concurrent activities. To alleviate this task several high-level approaches to concurrent programming have been developed. For some high-level programming approaches,
prototyping
for facilitating early evaluation of new ideas is a central goal.

Prototyping is used to explore the essential features of a proposed
system through practical experimentation before its actual implementation to make the correct design choices early in the process of software development. Approaches to prototyping
concurrent
applications with very high-level programming systems intend to alleviate the development in different ways. Early experimentation with alternate design choices or problem decompositions for concurrent applications is suggested to make concurrent programming easier.

This paper presents a survey of programming languages and systems for prototyping concurrent applications to review the state of the art in this area. The surveyed approaches are classified with respect to the prototyping process.
801 storage: architecture and programming
Authors: Chang Albert , Mergen Mark F.
Published: July 2002

Based on novel architecture, the 801 minicomputer project has developed a low-level storage manager that can significantly simplify storage programming in subsystems and applications. The storage manager embodies three ideas: (1)
large virtual storage
, to contain all temporary data and permanent files for the active programs; (2) the innovation of
database storage
, which has implicit properties of access serializability and atomic update, similar to those of database transaction systems; and (3) access to all storage, including files, by the usual operations and types of a high-level
programming language
.

The IBM RT PC implements the hardware architecture necessary for these storage facilities in its storage controller (MMU). The storage manager and language elements required, as well as subsystems and applications that use them, have been implemented and studied in a prototype operating system called CPR, that runs on the RT PC. Low cost and good performance are achieved in both hardware and software. The design is intended to be extensible across a wide performance/cost spectrum.
Iterative dynamic programming
Authors: Kossmann Donald , Stocker Konrad
Published: July 2002

The query optimizer is one of the most important components of a database system. Most commercial query optimizers today are based on a dynamic-programming algorithm, as proposed in Selinger et al. [1979]. While this algorithm produces good optimization results (i.e, good plans), its high complexity can be prohibitive if complex queries need to be processed, new query execution techniques need to be integrated, or in certain programming environments (e.g., distributed database systems). In this paper, we present and thoroughly evaluate a new class of query optimization algorithms that are based on a principle that we calliterative dynamic programming, or IDP for short. IDP has several important advantages: First, IDP-algorithms produce the best plans of all known algorithms in situations in which dynamic programming is not viable because of its high complexity. Second, some IDP variants are adaptive and produce as good plans as dynamic programming if dynamic programming is viable and as good-as possible plans if dynamic programming turns out to be not viable. Three, all IDP-algorithms can very easily be integrated into an existing optimizer which is based on dynamic programming.
Natural command names and initial learning
Authors: Landauer T. K. , Galotti K. M. , Hartwell S.
Published: July 2002

In the first of two studies of “naturalness” in command names, computer-naive typists composed instructions to “someone else” for correcting a sample text. There was great variety in their task-descriptive lexicon and a lack of correspondence between both their vocabulary and their underlying conceptions of the editing operations and those of some computerized text editors. In the second study, computer-naive typists spent two hours learning minimal text-editing systems that varied in several ways. Lexical naturalness (frequency of use in Study 1) made little difference in their performance. By contrast, having different, rather than the same names for operations requiring different syntax greatly reduced difficulty. It is concluded that the design of user-compatible commands involves deeper issues than are captured by the slogan “naturalness.” However, there are limitations to our observations. Only initial learning of a small set of commands was at issue and generalizations to other situations will require further testing.
New methods to color the vertices of a graph
Authors: Brélaz Daniel
Published: July 2002

This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared.
Is “sometime” sometimes better than “always”?
Authors: Manna Zohar , Waldinger Richard
Published: July 2002

This paper explores a technique for proving the correctness and termination of programs simultaneously. This approach, the
intermittent-assertion method
, involves documenting the program with assertions that must be true at some time when control passes through the corresponding point, but that need not be true every time. The method, introduced by Burstall, promises to provide a valuable complement to the more conventional methods.

The intermittent-assertion method is presented with a number of examples of correctness and termination proofs. Some of these proofs are markedly simpler than their conventional counterparts. On the other hand, it is shown that a proof of correctness or termination by any of the conventional techniques can be rephrased directly as a proof using intermittent assertions. Finally, it is shown how the intermittent-assertion method can be applied to prove the validity of program transformations and the correctness of continuously operating programs.
Use of the LRU stack depth distribution for simulation of paging behavior
Authors: Turner Rollins , Strecker Bill
Published: July 2002

Two families of probability distributions were needed for use by a virtual memory simulation model: headway between page fault distributions, and working set size distributions. All members of both families can be derived from the LRU stack depth distribution. Simple expressions for the computation of both kinds of distributions are given. Finally, examples are given of both families of distributions as computed from a published stack depth distribution.
What can we do about the unnecessary diversity of notation for syntactic definitions?
Authors: Wirth Niklaus
Published: July 2002

The population of programming languages is steadily growing, and there is no end of this growth in sight. Many language definitions appear in journals, many are found in technical reports, and perhaps an even greater number remains confined to proprietory circles. After frequent exposure to these definitions, one cannot fail to notice the lack of “common denominators.” The only widely accepted fact is that the language structure is defined by a syntax. But even notation for syntactic description eludes any commonly agreed standard form, although the underlying ancestor is invariably the Backus-Naur Form of the Algol 60 report. As variations are often only slight, they become annoying for their very lack of an apparent motivation.
MIN—an optimal variable-space page replacement algorithm
Authors: Prieve Barton G. , Fabry R. S.
Published: July 2002

A criterion for comparing variable space page replacement algorithms is presented. An optimum page replacement algorithm, called VMIN, is described and shown to be optimum with respect to this criterion. The results of simulating VMIN, Denning's working set, and the page partitioning replacement algorithms on five virtual memory programs are presented to demonstrate the improvement possible over the known realizable variable space algorithms.
The synthesis of solids bounded by many faces
Authors: Braid I. C.
Published: July 2002

A technique is presented which allows a class of solid objects to be synthesized and stored using a computer. Synthesis begins with primitive solids like a cube, wedge, or cylinder. Any solid can be moved, scaled, or rotated. Solids may also be added together or subtracted. Two algorithms to perform addition are described. For practical designers, the technique has the advantage that operations are concise, readily composed, and are given in terms of easily imagined solids. Quite short sequences of operations suffice to build up complex solids bounded by many faces.
A large semaphore based operating system
Authors: Lauesen Søren
Published: July 2002

The paper describes the internal structure of a large operating system as a set of cooperating sequential processes. The processes synchronize by means of semaphores and extended semaphores (queue semaphores). The number of parallel processes is carefully justified, and the various semaphore constructions are explained. The system is proved to be free of “deadly embrace” (deadlock). The design principle is an alternative to Dijkstra's hierarchical structuring of operating systems. The project management and the performance are discussed, too. The operating system is the first large one using the RC 4000 multiprogramming system.
Algorithm 420: hidden-line plotting program [J6]
Authors: Williamson Hugh
Published: July 2002

HIDE
produces a two-dimensional representation of a surface or figure by plotting segments of a succession of curves; each curve is plotted where it is not hidden by any of the curves previously plotted (that is, where it does not fall below any of them as they appear in the two-dimensional representation).
A proposal to establish a pseudo virtual memory via writable overlays
Authors: Spacek Thomas R.
Published: July 2002

Many computer systems solve executable storage size problems for large programs by using overlays. However, it appears that no one overlay scheme contains a well-balanced combination of the most useful capabilities which are found in various existing techniques. A proposal is presented which utilizes several of the best capabilities from existing schemes and is complemented by several additional features, e.g. writable overlays. The writable overlay capability provides a virtual memory effect, although the programmer may still be required to design the overlay configuration. Since overlay structuring is a complex task, several tools (including a graphic display) are included in the proposal in order to aid the programmer in the design. The content of overlays is briefly discussed, and it is noted that many of the details of the final overlay configuration may be decided after the fact.
A western view of computer history
Authors: Sprague Richard E.
Published: July 2002

Many U.S. histories of the digital computer field have tended to be impersonal, with heavy emphasis on eastern universities and commercial developments. This article records the events of the early years in a personal way. The people, organizations, technologies, and computers of the 1945-55 period in the western part of the United States are described as they happened.
Algorithm 405: roots of matrix pencils
Authors: Dell Alice M. , Weil Roman L. , Thompson Gerald L.
Published: July 2002

* This work was supported by the US National Aeronautics and Space Administration, by the National Science Foundation under Grant GS-2703 to the University of Chicago, and by the US Office of Naval Research under Grant NONR 760(24) NR 047-048 to Carnegie-Mellon University. Computations were done on the University of Chicago's Maniac III computer and were supported by the US Atomic Energy Commission under grants AT (11-1)-614 and AT (11-1)-2094.
The instrumentation of multics
Authors: Saltzer Jerome H. , Gintell John W.
Published: July 2002

An array of measuring tools devised to aid in the implementation of a prototype computer utility is discussed. These tools include special hardware clocks and data channels, general purpose programmed probing and recording tools, and specialized measurement facilities. Some particular measurements of interest in a system which combines demand paging with multiprogamming are described in detail. Where appropriate, insight into effectiveness (or lack thereof) of individual tools is provided.
Clarification of Fortran standards—second report
Authors: Kerpelman C.
Published: July 2002

In 1966, after four years of effort, Fortran became the first programming language standardized in the United States. Since that initial achievement, study and application of the standard specifications have revealed the need for maintenance of the standards. As the result of work initiated in 1967, an initial set of clarifying interpretations was prepared and this clarification was published in Communications of the ACM in May 1969. That work has continued and has resulted in the preparation of this second set of clarifying interpretations. The nature of the maintenance and the new set of corrections to and interpretations of the standard specifications are reported.
Algorithm 415: Algorithm for the assignment problem (rectangular matrices)
Authors: Bourgeois F. , Lassalle J. C.
Published: July 2002

This algorithm is a companion to [3] where the theoretical background is described.
On the design of display processors
Authors: Myer T. H. , Sutherland I. E.
Published: July 2002

The flexibility and power needed in the channel for a computer display are considered. To work efficiently, such a channel must have a sufficient number of instruction that it is best understood as a small processor rather than a powerful channel. As it was found that successive improvements to the display processor design lie on a circular path, by making improvements one can return to the original simple design plus one new general purpose computer for each trip around. The degree of physical separation between display and parent computer is a key factor in display processor design.
A format language
Authors: Perlis A. J.
Published: July 2002

One of the most primitive parts of a formula language is its specification of input-output actions within the framework of the language. While the specification is intrinsically more complex, say, than the evaluation of an arithmetic expression, most of the difficulties associated with input-output specification arise from the fact that the desired operations have not been properly defined using the framework of a
programming language
. Indeed, the complexity largely disappears when a programming language is constructed to specify input-output actions. The point to be made here is that the definition of an appropriate programming language makes more rational and simpler all three phases of the input-output programming cycle: (i) source program construction, (ii) object program construction, (iii) object program execution.
Scientific Applications: Computer synthesis of Holograms for 3-D display
Authors: Lesem L. B. , Hirsch P. M. , Jordan J. A.
Published: July 2002

Optical and digital holography are reviewed. The mathematical model and computational techniques of the authors' digital holographic process are discussed, and applications of computer holography are suggested.

Computer holograms have been made of three-dimensional objects which give faithful reconstructions, even in white light. A new approach based on point apertures for the image is discussed. Photographs of the images reconstructed from digital holograms are presented
A rapid method for digital filtering
Authors: Whittlesey John R. B.
Published: July 2002

Since much of the computer time spent in time-series analysis is used for multiplications, a minimum multiplication method was devised for digital filtering, with the expectation that it would be useful in the online, real-time analysis of biological data. The filters are constructed from a succession of readily analyzable components in a manner that facilitates cascading. The repertoire of frequency response curves includes relatively good low-pass and band-pass designs. Programs are available for implementing both the synthesis of these filters, and their application on computers whose assemblers allow the definition of recursive macros.
High speed compilation of efficient object code
Authors: Gear C. W.
Published: July 2002

A three-pass compiler with the following properties is briefly described: The last two passes scan an intermediate language produced by the preceding pass in essentially the reverse of the order in which it was generated, so that the first pass is the only one which has to read the relatively bulky problem-oriented input. The double scan, one in either direction, performed by the first two passes, allows the compiler to remove locally constant expressions and recursively calculable expressions from loops and to do the important part of common subexpression recognition. Optimization such as the effective use of index registers, although as important, is not discussed since the object code which would be most efficient is highly machine dependent. The discussion is in terms of a FORTRAN-like language, although the technique is applicable to most algebraic languages.
Conversion of decision tables to computer programs by rule mask techniques
Authors: King P. J. H.
Published: July 2002

The rule mask technique is one method of converting limited entry decision tables to computer programs. Recent discussion suggests that in many circumstances it is to be preferred to the technique of constructing networks or trees. A drawback of the technique as hitherto presented is its liability to produce object programs of longer run time than necessary. In this paper a modification of the technique is discussed which takes into account both rule frequencies and the relative times for evaluating conditions. This can materially improve object program run time.
An introduction to quantum computing for non-physicists
Authors: Rieffel Eleanor , Polak Wolfgang
Published: July 2002

Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers.

In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques.

The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.
Drag-and-drop versus point-and-click mouse interaction styles for children
Authors: Inkpen Kori M.
Published: July 2002

This research investigates children's use of two common mouse interaction styles, drag-and-drop and point-and-click, to determine whether the choice of interaction style impacts children's performance in interactive learning environments. The interaction styles were experimentally compared to determine if either method was superior to the other in terms of speed, error rate, or user preference, for children. The two interaction styles were also compared based on children's achievement and motivation, within a commercial software environment. Experiment I used an interactive learning environment as children played two versions of an educational puzzle-solving game, each version utilizing a different mouse interaction style; experiment II used a mouse-controlled software environment modeled after the educational game. The results were similar to previous results reported for adults: the point-and-click interaction style was faster; fewer errors were committed using it; and it was preferred over the drag-and-drop interaction style. Within the context of the puzzle-solving game, the children solved significantly fewer puzzles, and they were less motivated using the version that utilized a drag-and-drop interaction style as compared to the version that utilized a point-and-click interaction style. These results were also explored through the use of state-transition diagrams and GOMS models, both of which supported the experimental data gathered.
Using a theoretical multimedia taxonomy framework
Authors: Heller Rachelle S. , Martin C. Dianne , Haneef Nuzi , Gievska-Krliu Sonja
Published: July 2002

Multimedia (MM) is a polysemous term, a term with many definitions, and in this case, many roots. In this paper, multimedia is defined as the seamless integration of two or more media. Each ancestor brings another requirement, muddying the field and making it difficult to work through. A multimedia taxonomy based on a previous media taxonomy is proposed to help organize the discipline. The taxonomy helps to classify the space called multimedia and to draw attention to difficult issues. The paper outlines the forms contributing to multimedia—text, sound, graphics, and motion—and aligns them with probable formats—elaboration, representation, and abstraction— and sets them within a context—audience, discipline, interactivity, quality, usefulness, and aesthetics. The contexts are more clearly defined in two areas: interactivity and the information basis for a discipline. Examples are presented describing the use of the taxonomy in the design and evaluation of student projects in a computer science-based multimedia course.
Temporal statement modifiers
Authors: Böhlen Michael H. , Jensen Christian S. , Snodgrass Richard Thomas
Published: July 2002

A wide range of database applications manage time-varying data. Many temporal query languages have been proposed, each one the result of many carefully made yet subtly interacting design decisions. In this article we advocate a different approach to articulating a set of requirements, or desiderata, that directly imply the syntactic structure and core semantics of a temporal extension of an (arbitrary) nontemporal query language. These desiderata facilitate transitioning applications from a nontemporal query language and data model, which has received only scant attention thus far.

The paper then introduces the notion of
statement modifiers
that provide a means of systematically adding temporal support to an existing query language. Statement modifiers apply to all query language statements, for example, queries, cursor definitions, integrity constraints, assertions, views, and data manipulation statements. We also provide a way to systematically add temporal support to an existing implementation. The result is a temporal query language syntax, semantics, and implementation that derives from first principles.

We exemplify this approach by extending SQL-92 with statement modifiers. This extended language, termed ATSQL, is formally defined via a denotational-semantics-style mapping of temporal statements to expressions using a combination of temporal and conventional relational algebraic operators.
Implicit coscheduling
Authors: Arpaci-Dusseau Andrea Carol
Published: July 2002

In modern distributed systems, coordinated time-sharing is required for communicating processes to leverage the performance of switch-based networks and low-overhead protocols. Coordinated time-sharing has traditionally been achieved with gang scheduling or explicit coscheduling, implementations of which often suffer from many deficiencies: multiple points of failure, high context-switch overheads, and poor interaction with client-server, interactive, and I/O -intensive workloads.
Implicit coscheduling
dynamically coordinates communicating processes across distributed machines without these structural deficiencies. In implicit coscheduling, no communication is required across operating systems schedulers; instead, cooperating processes achieve coordination by reacting to
implicit information
carried by communication existing within the parallel application. The implementation of this approach is simple and allows participating nodes to act autonomously. We introduce two key mechanisms in implicit coscheduling. The first is
conditional two-phase waiting,
a generalization of traditional two-phase waiting in which spin-time may be increased depending upon events occuring while the process waits. The second is an extension to stride scheduling that provides preemption and is fair to processes that block. To demonstrate that implicit coscheduling performs well, we show results from an extensive set of simulation and implementation experiments. To exercise the conditional two-phase waiting algorithm, we examine three workloads: bulk-synchronous and continuous-communication synthetic applications and application kernels written in the Split-C language. To exercise the local scheduler, we examine competing jobs with different communication characteristics. We demonstrate that our implementation scales well with the number of jobs and workstations and is robust to process placement. Our experiments show that implicit coscheduling is effective and fair for a wide range of workloads; most perform within 30% of an idealized model of gang scheduling.
The physical mapping problem for parallel architectures
Authors: Heath Lenwood S. , Rosenberg Arnold L. , Smith Bruce T.
Published: July 2002

The problem of realizing an idealized parallel architecture on a (possibly fault-laden) physical architecture is studied. Our formulation performs the mapping in the light of the algorithm that one wants to implement on the idealized architecture. A version of the mapping algorithm suggested by the DIOGENES methodology for designing fault-tolerant VLSI processor arrays is settled definitely. Two quality metrics for mappings are considered, the first embodying an idealized notion of
average delay
, which relates to power consumption, and the second being the
length of the longest run of wire
. For the average-delay measure, four algorithms that optimally assign the
m
vertices of the embedded graph to the
n
fault-free processors that have been fabricated are presented. The most general algorithm makes no assumptions about the structure of the array or the physical format of the processors; it runs in time
O
(
m
· (
n
-
m
)
2
). The other algorithms assume that the processors are laid out in such a way that interprocessor distances obey the triangle equality; they run in times ranging from time
O
(max{
m
,
n
-
m
} · log min {
m, n - m
}) for certain array structures, including linear arrays, to time
O
(max{
m, n - m
}) for a narrow class of array structures, including pyramid arrays. For the max-wire-run cost measure, it is shown that the problem of finding cost-optimal vertex-to-processor assignments is NP-complete. However, an algorithm is presented that yields, in time
O
(
m
· (
n - m
)
2
), vertex-to-processor assignments that are within a factor of 3 of optimal (they are optimal when the input graph-embedding is outplanar). This algorithm can easily be converted to one that yields, in time
O
(
m
· (
n - m
)
3
), vertex-to-processor assignments that are within a factor of 2 of optimal. Finally, an algorithm that yields optimal assignments when the interprocessor distances obey the triangle equality is presented; this algorithm operates in time
O
(
m
· (
n - m
) · log(
m
· (
n - m
)) · log
M
), where
M
is the largest interprocessor distance.