bluuebunny/crossref_metadata_2025 huggingface dataset:
THE THERMAL MINORITY GAME
Authors: CAVAGNA ANDREA , GARRAHAN JUAN P. , GIARDINA IRENE , SHERRINGTON DAVID
Published: July 2002

New continuous and stochastic extensions of the Minority Game, devised as a fundamental model for a market of competitive agents, are introduced and studied in the context of statistical physics. The new formulation reproduces the key features of the original model, without the need for some of its special assumptions and, most importantly, it demonstrates the crucial role of stochastic decision-making. Furthermore, this formulation provides the exact but novel nonlinear equations for the dynamics of the system.
Financial Liberalization and Tests of Capital Flow Mobility in Taiwan
Authors: Wen Yin K.
Published: July 2002

Taiwan's financial policies played a vital role in promoting its relatively rapid post-war industrialization, a process that involved the use of different financial strategies to accommodate different stages of economic development. This paper aims to examine the process of Taiwan's financial liberalization and the relationship of this process to the opening up of Taiwan's capital account, which can be viewed as the last reform stage for the entire financial liberalization process. The first section briefly introduces the evolution of Taiwan's financial policies during different stages of development, giving primary focus to her efforts at financial liberalization starting in the 1980s. During this period, mid-1987, the time when Taiwan's government promulgated a new law to deregulate foreign exchange control, counts as a watershed for Taiwan's exchange rate market. The second section uses the conventional interest rate parity method to compare the extent of capital flow mobility before and after mid-1987. The results of the comparison show only a slight improvement in capital flow mobility after mid-1987. The author argues that the interest rate parity method may, for various reasons, be inadequate for testing capital mobility in Taiwan's case. Evidence, in the form of measures that the Taiwan's government has taken over time as described in the first section and Appendix, shows that Taiwan's financial markets have become increasingly open and more market-oriented as the financial liberalization process progresses. Although the government is still intervening in both interest rate and exchange rate markets, the trend is toward less intervention, except for a brief period during the 1998-99 Asian Financial Crisis. The final section presents a brief conclusion and directions for further research.
COMPUTING LINE INTERSECTIONS
Authors: GAVRILOVA M. , ROKNE J.
Published: July 2002

The main result of the paper is a new and efficient algorithm to compute the closest possible representable intersection point between two lines in the plane. The coordinates of the points that define the lines are given as single precision floating-point numbers. The novelty of the algorithm is the method for deriving the best possible representable floating point numbers: instead of solving the equations to compute the line intersection coordinates exactly, which is a computationally expensive procedure, an iterative binary search procedure is applied. When the required precision is achieved, the algorithm stops. Only exact comparison tests are needed. Interval arithmetic is applied to further speed up the process. Experimental results demonstrate that the proposed algorithm is on the average ten times faster than an implementation of the line intersection computation subroutine using the CORE library exact arithmetic.
THE APPLICATION OF FEEDFORWARD NEURAL NETWORKS IN VLSI FABRICATION PROCESS OPTIMIZATION
Authors: XIANGDONG WANG , SHOUJUE WANG
Published: July 2002

In this paper, we present a neural-based manufacturing process control system for semiconductor factories to improve the die yield. A model based on neural networks is proposed to simulate Very Large-Scale Integrated (VLSI) manufacturing process. Learning from the historical processing lists with Radial Basis Function (RBF), we simulate the functional relationship between the wafer probing parameters and the die yield. Then we use a gradient-descent method to search a set of 'optimal' parameters that lead to the maximum yield of the model. At last, we adjust the specification in the practical semiconductor manufacturing process. The average die yield increased from 51.7% to 57.5% after the system had been applied in Huajing Corporation.
MODULAR CONNECTIONIST MODELLING AND CLASSIFICATION APPROACHES FOR LOCAL DIAGNOSIS IN TELECOMMUNICATION TRAFFIC MANAGEMENT
Authors: BENNANI YOUNÈS , BOSSAERT FABRÌCE
Published: July 2002

In Neural Networks (NN) applications, it is common practice to train several different networks and select the best one on the basis of performance on a validation set. There is a major disadvantage of such an approach: the network with the best performance on the validation set might not be the best one on new test data. In fact, the generalization performance on the validation set has a random component that is due to the data noise. An alternative approach to this problem is to use a combination of multiple NN classifiers. It is well known that such combinations can produce better performance than the best single network used in isolation. Several studies in different fields of the pattern recognition have experimentally shown that an appropriate combination of NN classifiers allows to capture complex phenomena, and to make decisions even with a great deal of information.3,11,12 The combination of multiple classifiers is a general problem in the pattern recognition area. Several methods for combining the outputs of multiple classifiers have been proposed: ensemble methods,14 boosting approaches,9 stacking techniques,27 multi-expert systems,2,16 and multi-modular architectures.3,13,18 A very rich synthesis of different methods of combining classifiers can be found in Ref. 28. An analytical framework to quantify the improvements in classification results that is due to combining classifiers is provided in Ref. 26.

In this paper some contributions in combining multiple NN classifiers are presented. We give a combinational approach based on multi-modular systems for local diagnosis problem in the telephone network. In addition, we propose a combinational method for discrimination task using a fusion. The system validation will be performed on a disturbance identification problem.
COMPENSATION COMPETITIVE LEARNING
Authors: LIU ZHI-QIANG , ZHANG YAJUN
Published: July 2002

In general, in competitive learning the requirement for the initial number of prototypes is a difficult task, as we do not usually know the number of clusters in the input data a priori. The behavior and performance of the competitive algorithms are very sensitive to the initial locations and number of the prototypes. In this paper after investigating several important competitive learning paradigms, we present compensation techniques for overcoming the problems in competitive learning. Our experimental results show that competition with compensation can improve the performance of the learning algorithm.
CO-EVOLUTION: GUEST EDITORS' INTRODUCTION
Authors: DARWEN PAUL J. , YAO XIN
Published: July 2002

Any sufficiently expressive construction kit — expert systems, decision trees, neural networks, to name a few — with enough design work, can perform practically any set of behaviors. And when the required behaviors are not known, interviewing human experts (if available) is a workable but labor-intensive method.
Device-directed rendering
Authors: Glassner Andrew S. , Fishkin Kenneth P. , Marimont David H. , Stone Maureen C.
Published: July 2002

Rendering systems can produce images that include the entire range of visible colors. Imaging hardware, however, can reproduce only a subset of these colors: the device gamut. An image can only be correctly displayed if all of its colors lie inside of the gamut of the target device. Current solutions to this problem are either to correct the scene colors by hand, or to apply gamut mapping techniques to the final image. We propose a methodology called
device-directed rendering
that performs scene color adjustments automatically. Device-directed rendering applies classic minimization techniques to a symbolic representation of the image that describes the relationship of the scene lights and surfaces to the pixel colors. This representation can then be evaluated to produce an image that is guaranteed to be in gamut. Although our primary application has been correcting out-of-gamut colors, this methodology can be generally applied to the problem of adjusting a scene description to accommodate constraints on the output image pixel values.
On the average communication complexity of asynchronous distributed algorithms
Authors: Tsitsiklis John N. , Stamoulis George D.
Published: July 2002

We study the communication complexity of asynchronous distributed algorithms. Such algorithms can generate excessively many messages in the worst case. Nevertheless, we show that, under certain probabilistic assumptions, the expected number of messages generated per time unit is bounded by a polynomial function of the number of processors under a very general model of distributed computation. Furthermore, for constant-degree processor graphs, the expected number of generated messages is only
O(nT)
, where
n
is the number of processors and
T
is the running time. We conclude that (under our model) any asynchronous algorithm with good time complexity will also have good communication complexity, on the average.
Algorithm 764: Cubpack++
Authors: Cools Ronald , Pluym Luc , Laurie Dirk
Published: July 2002

In this article, software for the numerical approximation of
double integrals over a variety of regions is described. The
software was written in C++. Classes for a large number of shapes
are provided. A global adaptive integration algorithm is used based
on transformations and subdivisions of regions.
Corpus-based stemming using cooccurrence of word variants
Authors: Xu Jinxi , Croft W. Bruce
Published: July 2002

Stemming is used in many information retrieval (IR) systems to reduce variant word forms to common roots. It is one of the simplest applications of natural-language processing to IR and is one of the most effective in terms of user acceptance and consistency, though small retrieval improvements. Current stemming techniques do not, however, reflect the language use in specific corpora, and this can lead to occasional serious retrieval failures. We propose a technique for using corpus-based word variant cooccurrence statistics to modify or create a stemmer. The experimental results generated using English newspaper and legal text and Spanish text demonstrate the viability of this technique and its advantages relative to conventional approaches that only employ morphological rules.
A role-based access control model and reference implementation within a corporate intranet
Authors: Ferraiolo David F. , Barkley John F. , Kuhn D. Richard
Published: July 2002

This paper describes NIST's enhanced RBAC model and our approach to designing and implementing RBAC features for networked Web servers. The RBAC model formalized in this paper is based on the properties that were first described in Ferraiolo and Kuhn [1992] and Ferraiolo et al. [1995], with adjustments resulting from experience gained by prototype implementations, market analysis, and observations made by Jansen [1988] and Hoffman [1996]. The implementation of RBAC for the Web (RBAC/Web) provides an alternative to the conventional means of administering and enforcing authorization policy on a server-by-server basis. RBAC/Web provides administrators with a means of managing authorization data at the enterprise level, in a manner consistent with the current set of laws, regulations, and practices.
Authentication metric analysis and design
Authors: Reiter Michael K. , Stubblebine Stuart G.
Published: July 2002

Authentication using a path of trusted intermediaries, each able to authenicate the next in the path, is a well-known technique for authenicating entities in a large-scale system. Recent work has extended this technique to include multiple paths in an effort to bolster authentication, but the success of this approach may be unclear in the face of intersecting paths, ambiguities in the meaning of certificates, and interdependencies in the use of different keys. Thus, several authors have proposed metrics to evaluate the confidence afforded by a set of paths. In this paper we develop a set of guiding principles for the design of such metrics. We motivate our principles by showing how previous approaches failed with respect to these principles and what the consequences to authentication might be. We then propose a new metric that appears to meet our principles, and so to be a satisfactory metric of authenticaiton.
Monotone versus positive
Authors: Ajtai Miklos , Gurevich Yuri
Published: July 2002

In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula
P
(
P
) is (semantically) monotone in a predicate symbol
P
on finite structures. Is
P
(
P
) necessarily equivalent on finite structures to a first-order formula with only positive occurrences of
P
? In this paper, this question is answered negatively. Moreover, the counterexample naturally gives a uniform sequence of constant-depth, polynomial-size, monotone Boolean circuits that is not equivalent to any (however nonuniform) sequence of constant-depth, polynomial-size, positive Boolean circuits.
PILOT—A New Multiple Computer System
Authors: Leiner A. L. , Notz W. A. , Smith J. L. , Weinberger A.
Published: July 2002

The PILOT data processor is a high-speed multiple computer system, more than 100 times faster than SEAC. It contains three interconnected computers for rapid processing of data, and also contains multiple input-output channels for rapid transfer of data into and out of the system. All of these units operate concurrently in a coordinated fashion. A summary description is given of the over-all logical plan of the system, including the principal characteristics of the first computer, the second computer, the third computer, the internal controls, and the external controls.

The system combines internal processing capabilities that are fast and versatile with external communication capabilities that are exceptionally flexible. This combination permits the internal power of the machine to be exploited readily by the outside world,—either by other automatic devices or by human operators.
On the Boolean Matrix Equation M
′
=ν
i=1
M
i
Authors: Simões Pereira J. M. S.
Published: July 2002

The equation
M′
= V

d

i
-1

M
i

where
M′
is supposed to be given is discussed. First it is proved that there is a necessary and sufficient condition for the existence of a solution and, simultaneously, that under such condition,
M′
will itself be a solution. However, the main aim is precisely to present an algorithm which gives the so-called minimal solutions: Boolean matrices
M
satisfying the equation with the least possible number of unity entries. This is proved by the last theorem.

The subject may be studied in the context of graph theory and it seems of interest in various fields of operational research.
The Placement of Computer Logic Modules
Authors: Mamelak J. S.
Published: July 2002

The object of the work described was to develop a procedure for the allocation of logic to cards, boards, platters and so on which utilize modular circuit design and etched wiring techniques.

A chain of logic elements is a set of interconnected (logic) elements two of which connect to, at least, the remaining elements of this set. Every logic diagram has a characteristic set of chains. A subset of these chains is selected to initiate the determination of the locations of each element on a card. The elements of a chain are assigned to one row or column of platter locations. The positions of the chains in relation to one another are determined by such criteria as total wire length reduction, proximity requirements between gates based on electrical considerations and the proximity requirements between elements and pins based on timing considerations.

The effectiveness of the automatic procedure was tested during the design of small cards (mounting 16 modules, up to 64 gates). In these circumstances human experience and insight are at their best. The layouts of experienced technicians and engineers were compared with the layouts produced by the program. Significant similarities between the determinations were found in all cases tested.
Statistical Discrimination of the Synonymy/Antonymy Relationship Between Words
Authors: Lewis P. A. W. , Baxendale P. B. , Bennett J. L.
Published: July 2002

A basic hypothesis is stated about the contextual and co-occurrence properties of synonymous words. On the basis of this hypothesis, several statistics are derived for use in discriminating between pairs of words which are synonymous and pairs of words which are nonsynonymous. The discriminating power of these statistics is tested on a corpus consisting of titles of physics theses. The tests indicate that two of the derived statistics have relatively high discriminating power. The results are interpreted and the possibility of obtaining better discriminating power is discussed.
Samplesort: A Sampling Approach to Minimal Storage Tree Sorting
Authors: Frazer W. D. , McKellar A. C.
Published: July 2002

The methods currently in use and previously proposed for the choice of a root in minimal storage tree sorting are in reality methods for making inefficient statistical estimates of the median of the sequence to be sorted. By making efficient use of the information in a random sample chosen during input of the sequence to be sorted, significant improvements over ordinary minimal storage tree sorting can be made.

A procedure is proposed which is a generalization of minimal storage tree sorting and which has the following three properties: (a) There is a significant improvement (over ordinary minimal storage tree sorting) in the expected number of comparisons required to sort the input sequence. (b) The procedure is statistically insensitive to bias in the input sequence. (c) The expected number of comparisons required by the procedure approaches (slowly) the information-theoretic lower bound on the number of comparisons required. The procedure is, therefore, “asymptotically optimal.”
Recent Studies in Automatic Text Analysis and Document Retrieval
Authors: Salton G.
Published: July 2002

Many experts in mechanized text processing now agree that useful automatic language analysis procedures are largely unavailable and that the existing linguistic methodologies generally produce disappointing results. An attempt is made in the present study to identify those automatic procedures which appear most effective as a replacement for the missing language analysis.

A series of computer experiments is described, designed to simulate a conventional document retrieval environment. It is found that a simple duplication, by automatic means, of the standard, manual document indexing and retrieval operations will not produce acceptable output results. New mechanized approaches to document handling are proposed, including document ranking methods, automatic dictionary and word list generation, and user feedback searches. It is shown that the fully automatic methodology is superior in effectiveness to the conventional procedures in normal use.
Retiming-based factorization for sequential logic optimization
Authors: Bommu Surendra , O'Neill Niall , Ciesielski Maciej
Published: July 2002

Current sequential optimization techniques apply a variety of logic transformations that mainly target the combinational logic component of the circuit. Retiming is typically applied as a postprocessing step to the gate-level implementation obtained after technology mapping. This paper introduces a new sequential logic transformation which integrates retiming with logic transformations at the technology-independent level. This transformation is based on implicit retiming across logic blocks and fanout stems during logic optimization. Its application to sequential network synthesis results in the optimization of logic across register boundaries. It can be used in conjunction with any measure of circuit quality for which a fast and reliable gain estimation method can be obtained. We immplemented our new technique within the SIS framework and demonstrated its effectiveness in terms of cycle-time minimization on a set sequential benchmark circuits.
MUX, a simple approach to on-line computing
Authors: Christman Ronald D.
Published: July 2002

An on-line system operating as part of a normal batch system for the CDC 6600 computer is described. The system, which required one man-year for initial software implementation, although basically simple, provides the necessary elements to input and modify files, submit them for batch execution, and provide results at the user's terminal. A multiplexer designed and developed as part of the project cost one man-year for design and checkout, and $16,000 for parts and fabrication. All aspects of the system are described, including design criteria, implementation, cost, overhead, and user reactions.
On-line Text Editing: A Survey
Authors: van Dam Andries , Rice David E.
Published: July 2002

This paper is a survey of current methods for the on-line creation and editing of computer programs and of ordinary manuscripts text. The characteristics of on-line editing systems are examined and examples of various implementations are described in three categories: program editors, text editors, and terminals with local editing facilities.
Identifying potential to acquire programming skill
Authors: Mazlack Lawrence J.
Published: July 2002

Over several years, a large number of students took the same introductory programming course. The students were drawn from all academic disciplines and academic experience levels. Low correlations were found between success in the course or its evaluation components when posed against academic program, gender, or semester in school. Additionally, when the IBM Programmer's Aptitude Test was administered, the predictive value of the test was found to be low.
Some ideas on data types in high-level languages
Authors: Gries David , Gehani Narain
Published: July 2002

A number of issues are explored concerning the notion that a data type is a set of values together with a set of primitive operations on those values. Among these are the need for a notation for iterating over the elements of any finite set (instead of the more narrow for i := 1 to n notation), the use of the domain of an array as a data type, the need for a simple notation for allowing types of parameters to be themselves parameters (but in a restrictive fashion), and resulting problems with conversion of values from one type to another.
Median split trees
Authors: Sheil B. A.
Published: July 2002

Split trees are a new technique for searching sets of keys with highly skewed frequency distributions. A split tree is a binary search tree each node of which contains two key values—a
node
value which is a maximally frequent key in that subtree, and a
split
value which partitions the remaining keys (with respect to their lexical ordering) between the left and right subtrees. A
median
split tree (MST) uses the lexical median of a node's descendents as its split value to force the search tree to be perfectly balanced, achieving both a space efficient representation of the tree and high search speed. Unlike frequency ordered binary search trees, the cost of a successful search of an MST is log
n
bounded and very stable around minimal values. Further, an MST can be built for a given key ordering and set of frequencies in time
n
log
n
, as opposed to
n
2
for an optimum binary search tree. A discussion of the application of MST's to dictionary lookup for English is presented, and the performance obtained is contrasted with that of other techniques.
Abstraction and verification in Alphard
Authors: Shaw Mary , Wulf William A. , London Ralph L.
Published: July 2002

The Alphard “form” provides the programmer with a great deal of control over the implementation of abstract data types. In this paper the abstraction techniques are extended from simple data representation and function definition to the iteration statement, the most important point of interaction between data and the control structure of the language itself. A means of specializing Alphard's loops to operate on abstract entities without explicit dependence on the representation of those entities is introduced. Specification and verification techniques that allow the properties of the generators for such iterations to be expressed in the form of proof rules are developed. Results are obtained that for common special cases of these loops are essentially identical to the corresponding constructs in other languages. A means of showing that a generator will terminate is also provided.
A process for the determination of addresses in variable length addressing
Authors: Frieder Gideon , Saal Harry J.
Published: July 2002

An algorithm is presented for the assignment of instruction addresses and formats under the following conditions: (1) the length of the instruction varies as a function of the distance of the instruction from its target; (2) there exists an optimality criterion which implies some preferential choices subject to the addressing constraints. This may be, for example, achieving the smallest number of long instructions, in which case the total code length is minimized, or minimizing the assigned address of a specified point in the program. The algorithm is suitable for arbitrary program structure and a choice of optimization criteria.
Tridiagonalization by permutations
Authors: Gibbs Norman E. , Poole William G.
Published: July 2002

Tridiagonalizing a matrix by similarity transformations is an important computational tool in numerical linear algebra. Consider the class of sparse matrices which can be tridiagonalized using only row and corresponding column permutations. The advantages of using such a transformation include the absence of round-off errors and improved computation time when compared with standard transformations. A graph-theoretic algorithm which examines an arbitrary
n
×
n
matrix and determines whether or not it can be permuted into tridiagonal form is given. The algorithm requires no arithmetic while the number of comparisons, the number of assignments, and the number of increments are linear in
n
. This compares very favorably with standard transformation methods. If the matrix is permutable into tridiagonal form, the algorithm gives the explicit tridiagonal form. Otherwise, early rejection will occur.
Production systems
Authors: Ledgard Henry F.
Published: July 2002

Since the development of BNF, the definition of the syntax of programming languages has been almost universally associated with context-free requirements. Yet numerous interesting and difficult issues in syntax stem from the context-sensitive requirements, notably the compatibility between the declaration of an identifier and its uses, the correspondence between actual and formal parameters, and issues arising from block structure.

This paper explores the use of a formal notation called Production Systems in providing a
readable
and
complete
formal definition of syntax. As a practical illustration, a small but significant subset of PL/I is considered. A more detailed presentation, as well as the application to define abstract syntax and translations between languages, is given in a previous paper by the author.
A system for interprocess communication in a resource sharing computer network
Authors: Walden David C.
Published: July 2002

A system of communication between processes in a time-sharing system is described and the communication system is extended so that it may be used between processes distributed throughout a computer network. The hypothetical application of the system to an existing network is discussed.
The effects of multiplexing on a computer-communications system
Authors: Pack Charles D.
Published: July 2002

A study is made of the way in which asynchronous time division multiplexing changes the stochastic nature of the arrival process from a user to the computer and, consequently, affects the performance of a time-shared computer-communications system. It is concluded that while, for certain values of system parameters, there is noticeable improvement in the performance of the computer (model), in the sense that time-shared scheduling delays are reduced, these improvements are offset by the transmission delays imposed by multiplexing so that there may be little or no change in the computer-communications system performance.

Analytical and simulation results are based on the model of the computer-communications system being an M/D/1 queue (the multiplexor) in tandem with a single exponential server (the computer). Analytical results include a general description of the output process of an M/D/1 queue and the conditions under which this output process is approximately Poisson.
Computational algorithms for closed queueing networks with exponential servers
Authors: Buzen Jeffrey P.
Published: July 2002

Methods are presented for computing the equilibrium distribution of customers in closed queueing networks with exponential servers. Expressions for various marginal distributions are also derived. The computational algorithms are based on two-dimensional iterative techniques which are highly efficient and quite simple to implement. Implementation considerations such as storage allocation strategies and order of evaluation are examined in some detail.
An interactive command generating facility
Authors: Grant Charles A.
Published: July 2002

A facility to permit conversationally controlled tasks to be executed in a noninteractive environment is proposed. A means by which programs can generate interactive time-sharing commands and receive the corresponding output response is presented. The commands will be invoked as if they had been typed at a console keyboard. It is argued that this facility will help overcome some of the current limitations in man-computer communication.

A set of functions to accomplish the above which could be embedded into any string processing language is suggested, and necessary information pertinent to implementation of the facility on existing time-sharing systems is given.
Conversational access to a 2048-word machine
Authors: Wilkes Mary Allen
Published: July 2002

LAP6 is an on-line system running on a 2048-word LINC which provides full facilities for text editing, automatic filing and file maintenance, and program preparation and assembly. It focuses on the preparation and editing of continuously displayed 23,040-character text strings (manuscripts) which can be positioned anywhere by the user and edited by simply adding and deleting lines as though working directly on an elastic scroll. Other features are available through a uniform command set which itself can be augmented by the user.

The machine, although small, aids program design by providing display scope and premarked randomly addressable LINC tapes as standard items, in an environment similar to that of a sophisticated terminal. The tapes are logically similar to a disk. Priority was given to the design of efficient tape algorithms to minimize the limitations of the small memory. Techniques developed for handling scroll editing, filing, and the layered system structure are outlined.

LAP6 is used by about 2000 people in 11 countries. Its design was strongly influenced by performance criteria established in interviews held with the LINC users themselves during the specification period.
The mobile programming system
Authors: Waite W. M.
Published: July 2002

STAGE2 is the second level of a bootstrap sequence which is easily implemented on any computer. It is a flexible, powerful macro processor designed specifically as a tool for constructing machine-independent software. In this paper the features provided by STAGE2 are summarized, and the implementation techniques which have made it possible to have STAGE2 running on a new machine with less than one man-week of effort are discussed. The approach has been successful on over 15 machines of widely varying characteristics.
Automated printed circuit routing with a stepping aperture
Authors: Lass Stanley E.
Published: July 2002

A computer program for routing interconnections on a two-sided printed circuit board with a regular pattern of lines, pins (terminals), and vias (feed-through holes) is described.

In this program, each interconnection is given a planned routing—typically, down from the upper pin, through a via, and horizontally to the lower pin. From the top, a virtual aperture (i.e. a long horizontal slit) is stepped down the board. The planned routing is the basis for rerouting interconnections within the aperture to resolve conflicts for lines and vias below the aperture and to maximize the effective line usage. If a conflict has not been resolved before the aperture arrives at the lower pin, interconnections are deleted to resolve the conflict.

Extensions of this technique to the control of crosstalk between routed interconnections and to the problem of obtaining 100 percent interconnect are also discussed.
The simplex method of linear programming using LU decomposition
Authors: Bartels Richard H. , Golub Gene H.
Published: July 2002

Standard computer implementations of Dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. These implementations have bad round-off error properties. This paper gives the theoretical background for an implementation which is based upon the LU decomposition, computed with row interchanges, of the basic matrix. The implementation is slow, but has good round-off error behavior. The implementation appears as CACM Algorithm 350.
Dynamic space-sharing in computer systems
Authors: Belady L. A. , Kuehner C. J.
Published: July 2002

A formalization of relationships between space-sharing, program behavior, and processor efficiency in computer systems is presented. Concepts of value and cost of space allocation per task are defined and then value and cost are combined to develop a single parameter termed value per unit cost.

The intent is to illustrate a possible analytic approach to the investigation of the problems of space-sharing and to demonstrate the method on sample problems.
On multiprogramming, machine coding, and computer organization
Authors: Wirth Niklaus
Published: July 2002

The author feels that the interrupt feature which is available in most modern computers is a potent source of programming pitfalls and errors, and that it therefore may heavily contribute to the unreliability of programs making use of it. A programming scheme is presented which avoids the concept of the interrupt and permits the specification of concurrent (or pseudoconcurrent) activities in a supposedly more perspicuous manner. It is intended to serve as a basis for the construction of operating systems, which are prime examples of programs with concurrent activities. The scheme includes a set of basic instructions for the generation, termination, and synchronization of parallel processes. A set of routines representing these instructions and thereby simulating a hypothetical machine organization has been implemented and tested on the IBM System/360. Two programs using these instructions, written in PL360, are presented.
A language independent macro processor
Authors: Waite William M.
Published: July 2002

A macro processor is described which can be used with almost any source language. It provides all features normally associated with a macro facility, plus the ability to make arbitrary transformations of the argument strings. The program is used at the Basset Computing Department, University of Sydney, Sydney, Australia, to process text for eight different compilers.
Programming Languages: Boolean matrix methods for the detection of simple precedence grammars
Authors: Martin David F.
Published: July 2002

The use of decision tables as a tool in systems analysis and for program specification is now becoming accepted. Rules on redundancy, contradiction, and completeness for limited entry tables were published in 1963. These are usually used for checking, preceded if necessary by a conversion from extended to limited entry form. Processors which automatically translate tables to more conventional program usually base their diagnostic facilities on these rules. In this paper it is suggested that these rules are unsatisfactory and that the important aspect of checking is to eliminate ambiguity from tables. Ambiguity is defined and discussed, and a procedure for producing checked-out decision tables is proposed. The theoretical basis of the algorithm used is established. The importance of well-designed diagnostic facilities in decision table processors is emphasized.
The implementation of a BASIC system in a multiprogramming environment
Authors: Braden Helen V. , Wulf William A.
Published: July 2002

A mechanical procedure is derived for determining whether a given context-free phrase structure grammar is a simple precedence grammar. This procedure consists of elementary operations on suitably defined Boolean matrices. Application of the procedure to operator grammars is also given.
A note on a relevance estimate and its improvement
Authors: Korfhage Robert R.
Published: July 2002

In this paper the effect of iterating the improvement procedure is examined. It is shown that applications of the improvement factor beyond the first time are ineffectual, and that the factor is but a scale factor.
Some techniques used in the ALCOR ILLINOIS 7090
Authors: Gries D. , Paul M. , Wiehle H. R.
Published: July 2002

An ALGOL compiler has been written by the ALCOR group for the IBM 7090. Some little known but significant techniques in compiler writing, together with organizational details of this compiler, are described. Timing estimates and an indication of compiler requirements are also given.
Verifying security protocols as planning in logic programming
Authors: Carlucci Aiello Luigia , Massacci Fabio
Published: July 2002

We illustrate

AL
SP

(Action Language for Security Protocol), a declarative executable specification language for planning attacks to security protocols.

AL
SP

is based on logic programming with negation as failure, and with stable model semantics. In

AL
SP

we can give a declarative specification of a protocol with the natural semantics of send and receive actions which can be performed in parallel. By viewing a protocol trace as a plan to achieve a goal, attacks are (possibly parallel) plans achieving goals that correspond to security violations. Building on results from logic programming and planning, we map the existence of an attack into the existence of a model for the protocol that satisfies the specification of an attack. We show that our liberal model of parallel actions can adequately represent the traditional Dolev-Yao trace-based model used in the formal analysis of security protocols. Specifications in

AL
SP

are executable, as we can automatically search for attacks via an efficient model generator (smodels), implementing the stable model semantics of normal logic programs.
An unknown key-share attack on the MQV key agreement protocol
Authors: Kaliski Burton S.
Published: July 2002

The MQV key agreement protocol, a technique included in recent standards, is shown in its basic form to be vulnerable to an unknown key-share attack. Although the attack's practical impact on security is minimal---a key confirmation step easily prevents it---the attack is noteworthy in the principles it illustrates about protocol design. First, minor “efficiency improvements” can significantly alter the security properties of a protocol. Second, protocol analysis must consider potential interactions with all parties, not just those that are normally online. Finally, attacks must be assessed in terms of system requirements, not just in isolation.
On balancing the load in a clustered web farm
Authors: Wolf Joel L. , Yu Philip S.
Published: July 2002

In this article we propose a novel, yet practical, scheme which attempts to optimally balance the load on the servers of a clustered Web farm. The goal in solving this performance problem is to achieve minimal average response time for customer requests, and thus ultimately achieve maximal customer throughput. The article decouples the overall problem into two related but distinct mathematical subproblems, one static and one dynamic. We believe this natural decoupling is one of the major contributions of our article. The
static
component algorithm determines good assignments of sites to potentially overlapping servers. These cluster assignments, which, due to overhead, cannot be changed too frequently, have a major effect on achievable response time. Additionally, these assignments must be palatable to the sites themselves. The
dynamic
component algorithm is designed to handle real-time load balancing by routing customer requests from the network dispatcher to the servers. This algorithm must react to fluctuating customer request load while respecting the assignments of sites to servers determined by the static component. The static and dynamic components both employ in various contexts the same so-called
goal setting
algorithm. This algorithm determines the theoretically optimal load on each server, given hypothetical cluster assignments and site activity. We demonstrate the effectiveness of the overall load-balancing scheme via a number of simulation experiments.
Too much of a good thing
Authors: Munro Neil
Published: July 2002

The contested balance of civil liberties vs. police power was never more apparent than on September 11.
How to turn around `turnover culture' in IT
Authors: Moore Jo Ellen , Burke Lisa A.
Published: July 2002

To stem the flight of valued IT professionals, recognize how the social contagion of changing jobs to overcome workplace dissatisfaction can infect even the most loyal and productive IT employees. Then listen.
Recognizing circle graphs in polynomial time
Authors: Gabor Csaba P. , Supowit Kenneth J. , Hsu Wen-Lian
Published: July 2002

The main result of this paper is an
0
([
V
] x [
E
]) time algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. The algorithm utilizes two new graph-theoretic results, regarding necessary induced subgraphs of graphs having neither articulation points nor similar pairs of vertices. Furthermore, as a substep of the algorithm, it is shown how to find in
0
([
V
] x [
E
]) time a decomposition of a graph into prime graphs, thereby improving on a result of Cunningham.
Using a global name space for parallel execution of UNIX tools
Authors: Fleckenstein Charles J. , Hemmendinger David
Published: July 2002

A parallel make utility that executes on multiple workstations and achieves a significant real-time speedup makes work with distributed computing easy to conduct.
Residual hermite normal form computations
Authors: Domich Paul D.
Published: July 2002

This paper extends the class of Hermite normal form solution procedures that use modulo determinant arithmetic. Given any relatively prime factorization of the determinant value, integral congruence relations are used to compute the Hermite normal form. A polynomial-time complexity bound that is a function of the length of the input string exists for this class of procedures. Computational results for this new approach are given.
A fast mutual exclusion algorithm
Authors: Lamport Leslie
Published: July 2002

A new solution to the mutual exclusion problem is presented that, in the absence of contention, requires only seven memory accesses. It assumes atomic reads and atomic writes to shared registers.
Software safety: why, what, and how
Authors: Leveson Nancy G.
Published: July 2002

Software safety issues become important when computers are used to control real-time, safety-critical processes. This survey attempts to explain why there is a problem, what the problem is, and what is known about how to solve it. Since this is a relatively new software research area, emphasis is placed on delineating the outstanding issues and research topics.
MATCH—a new high-level relational operator for pattern matching
Authors: Held James P. , Carlis John V.
Published: July 2002

Pattern matching is a common and fundamental operation of many applications, such as expert systems (ES). With continued growth the knowledge bases of such systems will need database management systems (DBMS) support. Providing this support will require extending DBMS to meet the needs of these systems. We have developed an operator that extends the relational data model to do pattern matching with very complex stored patterns.
Lessons from the design of the Eiffel libraries
Authors: Meyer Bertrand
Published: July 2002

The nature of programming is changing. Most of the software engineering literature still takes for granted a world of individual projects, where the sole aim is to produce specific software systems in response to particular requirements, little attention being paid to each system's relationship to previous or subsequent efforts. This implicit model seems unlikely to allow drastic improvements in software quality and productivity.

Such order-of-magnitude advances will require a process of industrialization, not unlike what happened in those disciplines which have been successful at establishing a production process based on the reuse of quality-standardized components. This implies a shift to a “new culture” [14] whose emphasis is not on projects but instead on components.

The need for such a shift was cogently expressed more than 20 years ago by Doug McIlroy in his contribution, entitled Mass-Produced Software Components [10], to the now-famous first conference on software engineering:

Software production today appears in the scale of industrialization somewhere below the more backward construction industries. I think its proper place is considerably higher, and would like to investigate the prospects for mass-production techniques in software. [...]

My thesis is that the software industry is weakly founded [in part because of] the absence of a software components subindustry [...] A components industry could be immensely successful.

Although reuse has enjoyed modest successes since this statement was made, by all objective criteria McIlroy's prophecy has not been fulfilled yet; many technical and non-technical issues had to be addressed before reuse could become a reality on the scale he foresaw. (See [1] and [20] for a survey of current work on reuse.) One important development was needed to make this possible: the coming age of object-oriented technology, which provides the best known basis for reusable software construction. (That the founding document of object-oriented methods, the initial description of Simula 67, was roughly contemporary with McIlroy's paper tends to confirm a somewhat pessimistic version of Redwine and Riddle's contention [18] that “it takes on the order of 15 to 20 years to mature a technology to the point that it can be popularized to the technical community at large.”) Much of the current excitement about object-oriented software construction derives from the growing realization that the shift is now technically possible.

This article presents the concerted efforts which have been made to advance the cause of component-based software development in the Eiffel environment [12, 17] through the construction of the Basic Eiffel Libraries.

After a brief overview of the libraries, this article reviews the major language techniques that have made them possible (with more background about Eiffel being provided by the sidebar entitled “Major Eiffel Techniques”); it then discusses design issues for libraries of reusable components, the use of inheritance hierarchies, the indexing problem, and planned developments.