bluuebunny/crossref_metadata_2025 huggingface dataset:
PERCOLATION MODELS OF FINANCIAL MARKET DYNAMICS
Authors: STAUFFER DIETRICH
Published: July 2002

Microscopic models dealing with the decisions of traders on the market have tried to reproduce real market behaviour. Possibly the simplest of these models is the herding approach of Cont and Bouchaud. Variations include letting the concentration varying between zero and unity (or zero and percolation threshold); changing the price proportionally not to the difference between demand and supply, but to the square root of this difference; influencing the buy/sell decisions by the actual price and price change. As a result, the probability to find a market change greater than some R was found to vary as R-2.9; this distribution gets wings which might correspond to outliers like the 1929 crash on Wall Street; bubbles lead to sharp peaks separated by flat valleys; and the log-periodic variations after the Japanese crash of 1990 were reproduced to get rich from the prediction made in January 1999 by Johansen and Sornette that Nikkei will rise appreciably during 1999. As it did.
INORGANIC SEMICONDUCTOR NANOWIRES
Authors: YANG PEIDONG , WU YIYING , FAN RONG
Published: July 2002

One-dimensional (1D) nanostructures are ideal systems for investigating the dependence of electrical transport, optical properties and mechanical properties on size and dimensionality. They are expected to play an important role as both interconnects and functional components in the fabrication of nanoscale electronic and optoelectronic devices. This article presents an overview of current research activities that center on nanowires whose lateral dimensions fall anywhere in the range of 1–200 nm. It is organized into three parts: The first part discusses various methods that have been developed for generating nanowires with tightly controlled dimensions, orientations, and well-defined properties. The second part highlights a number of strategies that are being developed for the hierarchical assembly of nanowire building blocks. The third part surveys some of the novel physical properties (e.g., optical, electrical, and mechanical) of these nanostructures. Finally, we conclude with some personal perspectives on the future research directions in this field.
WHAT'S THIS "TOSH"?: INNOVATION NETWORKS AND NEW PRODUCT DEVELOPMENT AS A POLITICAL PROCESS
Authors: McLOUGHLIN IAN , KOCH CHRISTIAN , DICKSON KEITH
Published: July 2002

Innovation is increasingly seen as best conducted in networks and understood through a synthesis of evolutionary economic and sociological perspectives. This article contributes to this understanding by seeking to apply a political process perspective to collaboration between organisations engaged in new product development. It argues that the building of collaborative networks is a power-process and requires political action. Contrary to conventional views, power and politics are treated as an omnipresent feature of the creation of collaborative networks. It is concluded that mastering the political is central element of the eventual success of any product development endeavour. This argument is illustrated by drawing upon the findings of an international study on collaboration in new product development (BiCoN). Here we focus on a UK and a Danish case of software development where two contrasting forms of collaboration between the software supplier, intermediaries and end user/customers are evident.
A NEURAL NETWORK-BASED IMAGE RETRIEVAL USING NONLINEAR COMBINATION OF HETEROGENEOUS FEATURES
Authors: LEE HYOUNG K. , YOO SUK I.
Published: July 2002

In content-based image retrieval (CBIR), content of an image can be expressed in terms of different features such as color, texture, shape, or text annotations. Retrieval based on these features can be various by the way how to combine the feature values. Most of the existing approaches assume a linear relationship between different features, and the usefulness of such systems was limited due to the difficulty in representing high-level concepts using low-level features.

In this paper, we introduce Neural Network-based Flexible Image Retrieval (NNFIR) system, a human-computer interaction approach to CBIR using Radial Basis Function (RBF) network to combine the values of the heterogeneous features. By using the RBF network, this approach determines nonlinear relationship between features so that more accurate similarity comparison between images can be supported. The experimental results show that the proposed approach has the superior retrieval performance than the existing linear combining method, the rank-based method and the BackPropagation-based method. Although the proposed retrieval model is for CBIR, it can be easily expanded to handle other media types, such as video and audio.
Structural testing of rule-based expert systems
Authors: Kiper James D.
Published: July 2002

Testing of rule-based expert systems has become a high priority for many organizations as the use of such systems proliferates. Traditional software teting techniques apply to some components of rule-based systems, e.g., the inference engine. However, to structurally test the rule base component requires new techniques or adaptations of existing ones. This paper describes one such adaptation: an extension of data flow path selection in which a graphical representation of a rule base is defined and evaluated. This graphical form, called a logical path graph, captures logical paths through a rule base. These logical paths create precisely the abstractions needed in the testing process. An algorithm for the construction of logical path graphs are analyzed.
Perfectly secure message transmission
Authors: Dolev Danny , Dwork Cynthia , Waarts Orli , Yung Moti
Published: July 2002

This paper studies the problem of perfectly secure communication in general network in which processors and communication lines may be faulty. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms are obtained that operate with this connectivity and rely on no complexity-theoretic assumptions. These are the first algorithms for secure communication in a general network to simultaneously achieve the three goals of perfect secrecy, perfect resiliency, and worst-case time linear in the diameter of the network.
A fast normal random number generator
Authors: Leva Joseph L.
Published: July 2002

A method is presented for generating pseudorandom numbers with a normal distribution. The technique uses the ratio of uniform deviates method discovered by Kinderman and Monahan with an improved set of bounding curves. An optimized quadratic fit reduces the expected number of logarithm evaluations to 0.012 per normal deviate. The method gives a theoretically correct distribution and can be implemented in 15 lines of FORTRAN. Timing and source size comparisons are made with other methods for generating normal deviates. The proposed algorithm compares favorably with some of the better algorithms.
Structural analysis of hypertexts
Authors: Botafogo Rodrigo A. , Rivlin Ehud , Shneiderman Ben
Published: July 2002

Hypertext users often suffer from the “lost in hyperspace” problem: disorientation from too many jumps while traversing a complex network. One solution to this problem is improved authoring to create more comprehensible structures. This paper proposes several authoring tools, based on hypertext structure analysis.

In many hypertext systems authors are encouraged to create hierarchical structures, but when writing, the hierarchy is lost because of the inclusion of cross-reference links. The first part of this paper looks at ways of recovering lost hierarchies and finding new ones, offering authors different views of the same hypertext. The second part helps authors by identifying properties of the hypertext document. Multiple metrics are developed including
compactness
and
stratum
. Compactness indicates the intrinsic connectedness of the hypertext, and stratum reveals to what degree the hypertext is organized so that some nodes must be read before others.

Several existing hypertexts are used to illustrate the benefits of each technique. The collection of techniques provides a multifaceted view of the hypertext, which should allow authors to reduce undesired structural complexity and create documents that readers can traverse more easily.
Unreachable procedures in object-oriented programming
Authors: Srivastava Amitabh
Published: July 2002

Unreachable procedures are procedures that can never be invoked. Their existence may adversely affect the performance of a program. Unfortunately, their detection requires the entire program to be present. Using a long-time code modification system, we analyze large, linked, program modules of C++, C, and Fortran. We find that C++ programs using object-oriented programming style contain a large fraction of unreachable procedure code. In contrast, C and Fortran programs have a low and essentially constant fraction of unreachable code. In this article, we present our analysis of C++, C, and Fortran programs, and we discuss how object-oriented programming style generates unreachable procedures.
Amalgamating knowledge bases
Authors: Subrahmanian V. S.
Published: July 2002

The integration of knowledge for multiple sources is an important aspect of automated reasoning systems. When different knowledge bases are used to store knowledge provided by multiple sources, we are faced with the problem of integrating multiple knowledge bases: Under these circumstances, we are also confronted with the prospect of inconsistency. In this paper we present a uniform theoretical framework, based on
annotated logics
, for amalgamating multiple knowledge bases when these knowledge bases (possibly) contain inconsistencies, uncertainties, and nonmonotonic modes of negation. We show that annotated logics may be used, with some modifications, to
mediate
between different knowledge bases. The multiple knowledge bases are amalgamated by a transformation of the individual knowledge bases into new annotated logic programs, together with the addition of a new axiom scheme. We characterize the declarative semantics of such amalgamated knowledge bases and study how the semantics of the amalgam is related to the semantics of the individual knowledge bases being combined.
—Author's Abstract
Synthesis of extended transaction models using ACTA
Authors: Chrysanthis Panos K. , Ramamritham Krithi
Published: July 2002

ACTA is a comprehensive transaction framework that facilitates the formal description of properties of extended transaction models. Specifically, using ACTA, one can specify and reason about (1) the effects of transactions on objects and (2) the interactions between transactions. This article presents ACTA
as a tool for the synthesis of extended transaction models
, one which supports the development and analysis of new extended transaction models in a systematic manner. Here, this is demonstrated by deriving new transaction definitions (1) by modifying the specifications of existing transaction models, (2) by combining the specifications of existing models, and (3) by starting from first principles. To exemplify the first, new models are synthesized from
atomic transactions
and
join transactions
. To illustrate the second, we synthesize a model that combines aspect of the
nested
- and
split-transaction
models. We demonstrate the latter by deriving the specification of an
open-nested-transaction
model from high-level requirements.
User interface specification using an enhanced spreadsheet model
Authors: Hudson Scott E.
Published: July 2002

This paper describes a new interactive environment for user interface specification which is based on an enhanced spreadsheet model of computation. This environment allows sophisticated graphical user interfaces with dynamic feedback to be implemented with little or no explicit programming. Its goal is to support user interface specification by nonprogramming experts in human factors, visual design, or the application domain. In addition, the system is designed to allow sophisticated end-users to modify and customize their own interfaces. The system is based on a data flow model of computation. This model is presented to the interface designer in the form of a spreadsheet enhanced with new constructs for easier programming and reuse. These constructs include an improved interactive programming environment, a prototype-instance-based inheritance system, support for composition, abstraction, and customization using indirect references, the addition of support for graphical inputs and outputs, and support for the encapsulation of application data structures and routines within system objects.
Toward visual debugging
Authors: Mukherjea Sougata , Stasko John T.
Published: July 2002

Much of the recent research in software visualization has been polarized toward two opposite domains. In one domain that we call
data structure and program visualization
, low-level canonical views of program structures are generated automatically. These types of views, which do not require programmer input or intervention, can be useful for testing and debugging software. Often, however, their generic, low-level views are not expressive enough to convey adequately how a program functions. In the second domain called
algorithm animation
, designers handcraft abstract, application-specific views that are useful for program understanding and teaching. Unfortunately, since algorithm animation development typically requires time-consuming design with a graphics package, it will not be used for debugging, where timeliness is a necessity. However, we speculate that the application-specific nature of algorithm animation views could be a valuable debugging aid for software developers as well, if only the views could be easy and rapid to create. We have developed a system called
Lens
that occupies a unique niche between the two domains discussed above and explores the capabilities that such a system may offer. Lens allows programmers to build rapidly (in minutes) algorithm animation-style program views without requiring any sophisticated graphics knowledge and without using textual coding. Lens also is integrated with a system debugger to promote iterative design and exploration.
An empirical study of a wide-area distributed file system
Authors: Spasojevic Mirjana , Satyanarayanan M.
Published: July 2002

The evolution of the Andrew File System (AFS) into a wide-area distributed file system has encouraged collaboration and information dissemination on a much broader scale than ever before. We examine AFS as a provider of wide-area file services to over 100 organizations around the world. We discuss usage characteristics of AFS derived from empirical measurements of the system. Our observations indicate that AFS provides robust and efficient data access in its current configuration, thus confirming its viability as a design point for wide-area distributed file systems.
Algorithm 761: Scattered-data surface fitting that has the accuracy of a cubic polynomial
Authors: Akima Hiroshi
Published: July 2002

An algorithm for smooth surface fitting for scattered data has been presented. It has the accuracy of a cubic polynomial in most cases and is a local, triangle-based algorithm.
A survey of three dialogue models
Authors: Green Mark
Published: July 2002

A dialogue model is an abstract model that is used to describe the structure of the dialogue between a user and an interactive computer system. Dialogue models form the basis of the notations that are used in user interface management systems (UIMS). In this paper three classes of dialogue models are investigated. These classes are transition networks, grammars, and events. Formal definitions of all three models are presented, along with algorithms for converting the notations into an executable form. It is shown that the event model has the greatest descriptive power. Efficient algorithms for converting from the transition diagram and grammar models to the event model are presented. The implications of these results for the design and implementation of UIMSs are also discussed.
Users and standardization—worlds apart? The example of electronic mail
Authors: Jakobs Kai , Procter Rob , Williams Robin
Published: July 2002

We report on and analyze the views of long-standing active members of standards-setting working groups in electronic communications. We focus in particular on their experiences of, and attitudes towards, user participation in standardization. The results reveal attitudes that differ considerably from the official statement. To complement the views of standards professionals, we explore the attitude of large corporate email users towards standardization in general, the impact standards have on their apparent reluctance to play an active role in standardization. This includes a closer look at the ways in which email has emerged in organizations, and on what corporate users actually expect email of offer. A typical pattern can be identified, which in turn helps explain the reluctance of corporate users to actively participate in standards setting. Finally, we consider the implications of this and conclude with some recommendations on how the current situation could be improved.
Analysis of RC interconnections under ramp input
Authors: Kahng Andrew B. , Muddu Sudhakar
Published: July 2002

We give new methods for calculating the time-domain response for a finite-length distributed
RC
line that is stimulated by a ramp input. The following are our contributions. First, we obtain the solution of the diffusion equation for a seminfinite distributed
RC
line with ramp input. We then present a general and, in the limit,
exact
approach to compute the time-domain response for finite-length
RC
lines under ramp input by summing distinct diffusions starting at either end of the line. Next, we obtain analytical expressions for the finite time-domain voltage response for an open-ended finite
RC
line and for a finite
RC
line with capacitive load. The delay estimates using this method are very close to SPICE-computing delays. Finally, we present a general recursive equation for computing the higher-order diffusion components due to reflections at the source and load ends. Future work extends our method to response computations in general interconnection trees by modeling both reflection and transmission coefficients at discontinuities.
Real-time computing with lock-free shared objects
Authors: Anderson James H. , Ramamurthy Srikanth , Jeffay Kevin
Published: July 2002

This article considers the use of lock-free shared objects within hard real-time systems. As the name suggests,lock-freeshared objects are distinguished by the fact that they are accessed without locking. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this article is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the article, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free shared objects often incur less overhead than object implementations based on wait-free algorithms or lock-based schemes. In the last part of the article, this conclusion is validated experimentally through work involving a real-time desktop videoconferencing system.
Performance and reliability analysis of relevance filtering for scalable distributed interactive simulation
Authors: Bassiouni Mostafa A. , Chiu Ming-Hsing , Loper Margaret , Garnsey Michael , Williams Jim
Published: July 2002

Achieving the real-time linkage among multiple, geographically-distant, local area networks that support distributed interactive simulation (DIS) requires tremendous bandwidth and communication resources. Today, meeting the bandwidth and communication requirements of DIS is one of the major challenges facing the design and implementation of large scale DIS training exercises. In this article, we discuss the DIS scalability problem, briefly overview the major bandwidth reduction techniques currently being investigated and implemented in contemporary DIS systems, and present a detailed analysis on the performance and reliability of relevance filtering—a promising technique to improve the scalability of distributed simulation. The idea of relevance filtering is to analyze the semantic contents of the state update messages of a simulated entity (vehicle) and transmit only the ones found to be relevant to other entities. We present our entity-based model for relevance filtering and discuss the implementation of filtering-at-transmission and filtering-at-reception. We introduce the concept of filtering reliability and present different methods to eliminate or reduce filtering errors. Methods that can ensure complete filtering reliability while providing significant bandwidth reduction are developed. Performance evaluation results of relevance filtering and of the filtering reliability methods are presented. The insight gained from our work and the challenges still facing the design of large scale DIS training exercises are discussed.
Probabilistic checking of proofs
Authors: Arora Sanjeev , Safra Shmuel
Published: July 2002

We give a new characterization of NP: the class NP contains exactly those languages
L
for which membership proofs (a proof that an input
x
is in
L
) can be verified probabilistically in polynomial time using
logarithmic
number of random bits and by reading
sublogarithmic
number of bits from the proof.

We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.
Proof verification and the hardness of approximation problems
Authors: Arora Sanjeev , Lund Carsten , Motwani Rajeev , Sudan Madhu , Szegedy Mario
Published: July 2002

We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a
constant
number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided “proof” with probability at least 1/2. Our result builds upon and improves a recent result of Arora and Safra [1998] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length).

As a consequence, we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP = P. The class MAX SNP was defined by Papadimitriou and Yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show that there exists a positive ε such that approximating the maximum clique size in an
N
-vertex graph to within a factor of
N
ε
is NP-hard.
Models and languages for parallel computation
Authors: Skillicorn David B. , Talia Domenico
Published: July 2002

We survey parallel programming models and languages using six criteria to assess their suitability for realistic portable parallel programming. We argue that an ideal model should by easy to program, should have a software development methodology, should be architecture-independent, should be easy to understand, should guarantee performance, and should provide accurate information about the cost of programs. These criteria reflect our belief that developments in parallelism must be driven by a parallel software industry based on portability and efficiency. We consider programming models in six categories, depending on the level of abstraction they provide. Those that are very abstract conceal even the presence of parallelism at the software level. Such models make software easy to build and port, but efficient and predictable performance is usually hard to achieve. At the other end of the spectrum, low-level models make all of the messy issues of parallel programming explicit (how many threads, how to place them, how to express communication, and how to schedule communication), so that software is hard to build and not very portable, but is usually efficient. Most recent models are near the center of this spectrum, exploring the best tradeoffs between expressiveness and performance. A few models have achieved both abstractness and efficiency. Both kinds of models raise the possibility of parallelism as part of the mainstream of computing.
Open Shop Scheduling to Minimize Finish Time
Authors: Gonzalez Teofilo , Sahni Sartaj
Published: July 2002

A linear time algorithm to obtain a minimum finish time schedule for the two-processor open shop together with a polynomial time algorithm to obtain a minimum finish time preemptive schedule for open shops with more than two processors are obtained. It is also shown that the problem of obtaining minimum finish time nonpreemptive schedules when the open shop has more than two processors is NP-complete.
NEOS and Condor
Authors: Ferris Michael C. , Mesnier Michael P. , Moré Jorge J.
Published: July 2002

We discuss the use of Condor, a distributed resource management system, as a provider of computational resources for NEOS, an environment for solving optimization problems over the Internet. We also describe how problems are submitted and processed by NEOS, and then scheduled and solved by Condor on available (idle) workstations
SHARE information available to nonmembers
Authors: Galler Bernard A.
Published: July 2002

It is unfortunate that almost all of the presently used algebraic languages do not provide the capability of linear algebra. Operations such as the inner product of vectors, the product of two matrices, and the multiplication of a matrix by a scaler must inevitably be written out in detail in terms of the individual components. The reasons usually given for avoiding linear algebra in these languages are (1) the difficulties which would arise in scanning linear algebraic expressions, and (2) the uncertainty involved as to the amount of temporary storage needed during the evaluation of linear algebraic expressions when the program is executed. The purpose of this paper is to show how these two types of difficulties can be overcome. Although suggestions have been made for even further increasing the general capability of ALGOL such as including the ability to form a matrix from a collection of vectors, we shall be content here to consider the ordinary operations of linear algebra. Even if this much becomes available in algebraic languages, considerable progress will have been made. The following remarks constitute a suggestion for the addition to ALGOL of linear algebraic expressions.
Legal implications of computer use
Authors: Freed Roy N.
Published: July 2002

This paper points out a variety of ways computer systems used in business and industry can be involved in legal entanglements and suggests that computer specialists have a responsibility to call for assistance in forestalling or minimizing those entanglements during the planning stage. Techniques are suggested for making legal clearance effective with the least burden on the new technology and for achieving a favorable legal climate for it generally. Computer specialists also are alerted to potential opportunities to interpret to lawyers the technical aspects of computer systems involved in legal situations.
An alternate checksum method
Authors: Newhall N. S.
Published: July 2002

To increase reliability of transmission between magnetic tape and core storage on an IBM 7090/7094, blocks or records of data are often assigned a word called a logical checksum. This is a number derived from the block by some simple algorithm and as unique to it as possible. The method most commonly used to form a checksum is to add together every datum in the block by the ACL (add and carry logical) instruction.
Formal parsing systems
Authors: Greibach Sheila A.
Published: July 2002

Automatic syntactic analysis has recently become important for both natural language data processing and syntax-directed compilers. A formal parsing system
G
= (
V, μ, T, R
) consists of two finite disjoint vocabularies,
V
and
T
, a many-many map,
μ
, from
V
onto
T
, and a recursive set
R
of strings in
T
called syntactic sentence classes. Every program for automatic syntactic analysis determines a formal parsing system.

A directed production analyzer (
I, T, X, ρ
) is a nondeterministic pushdown-store machine with internal vocabulary
I
, input vocabulary
T
, and all productions of
ρ
in the form: (
Z, a
) →
aY
1
···

Y
m
, Z, Y
i
ε I, a ε T

. Every context-free language can be analyzed by a directed production analyzer.
Inductive methods for proving properties of programs
Authors: Manna Zohar , Ness Stephen , Vuillemin Jean
Published: July 2002

There are two main purposes in this paper: first, clarification and extension of known results about computation of recursive programs, with emphasis on the difference between the theoretical and practical approaches; second, presentation and examination of various known methods for proving properties of recursive programs. Discussed in detail are two powerful inductive methods, computational induction and structural induction, including examples of their applications.
A correction to Brelaz's modification of Brown's coloring algorithm
Authors: Peemöller Jürgen
Published: July 2002

Brelaz's modification of Brown's exact coloring algorithm contains two errors as demonstrated in two examples. A correct version of the algorithm and a proof of the exactness are given. Finally, Brown's look-ahead rule is built into this algorithm.
Cooperation is key
Authors: Steier Rosalie
Published: July 2002

The most innovative and audacious among the U.S. responses to Japan's Fifth Generation Project is that of the Microelectronics and Computer Technology Corp. MCC is a consortium of thirteen companies formed to conduct long range research and development in advanced computers. The member companies are investing in MCC projects in return for a three-year lead in implementing the resulting technology.

The President of MCC, retired Admiral B. R. Inman, must chart this new course for U.S. industrial research: a course of cooperation among competitors whose goal is to achieve U.S. supercomputer dominance in the 1990s marketplace.
A simple database language for personal computers
Authors: Watanabe Tan , Ohsawa Tsuneharu , Suzuki Takaji
Published: July 2002

A simple database language for personal computers has been implemented by selecting a subset of the ANS MUMPS language and enhancing it so as to meet the requirements of microcomputer end-users who are unfamiliar with computers. This database language is named Micro MUMPS. Its database is based on a modified prefix B-tree having parameters for adjusting its data organization according to the requirements of space and time efficiency. Experience with Micro MUMPS has demonstrated a remarkable reduction in programming time.
The future of programming
Authors: Wasserman Anthony I. , Gutz Steven
Published: July 2002

The nature of programming is changing. These changes will accelerate as improved software development practices and more sophisticated development tools and environments are produced. This paper surveys the most likely changes in the programming task and in the nature of software over the short term, the medium term, and the long term.

In the short term, the focus is on gains in programmer productivity through improved tools and integrated development environments. In the medium term, programmers will be able to take advantage of libraries of software components and to make use of packages that generate programs automatically for certain kinds of common systems. Over the longer term, the nature of programming will change even more significantly as programmers become able to describe desired functions in a nonprocedural way, perhaps through a set of rules or formal specification languages. As these changes occur, the job of the application programmer will become increasingly analysis-oriented and software developers will be able to attack a large number of application areas which could not previously be addressed effectively.
Automatic data structure selection
Authors: Low James R.
Published: July 2002

The use of several levels of abstraction has proved to be very helpful in constructing and maintaining programs. When programs are designed with abstract data types such as sets and lists, programmer time can be saved by automating the process of filling in low-level implementation details. In the past, programming systems have provided only a single general purpose implementation for an abstract type. Thus the programs produced using abstract types were often inefficient in space or time. In this paper a system for automatically choosing efficient implementations for abstract types from a library of implementations is discussed. This process is discussed in detail for an example program. General issues in data structure selection are also reviewed.
An English language question answering system for a large relational database
Authors: Waltz David L.
Published: July 2002

By typing requests in English, casual users will be able to obtain explicit answers from a large relational database of aircraft flight and maintenance data using a system called PLANES. The design and implementation of this system is described and illustrated with detailed examples of the operation of system components and examples of overall system operation. The language processing portion of the system uses a number of augmented transition networks, each of which matches phrases with a specific meaning, along with
context registers
(history keepers) and
concept case frames;
these are used for judging meaningfulness of questions, generating dialogue for clarifying partially understood questions, and resolving ellipsis and pronoun reference problems. Other system components construct a formal query for the relational database, and optimize the order of searching relations. Methods are discussed for handling vague or complex questions and for providing browsing ability. Also included are discussions of important issues in programming natural language systems for limited domains, and the relationship of this system to others.
Incorporating origin shifts into the QR algorithm for symmetric tridiagonal matrices
Authors: Stewart G. W.
Published: July 2002

The QR iteration for the eigenvalues of a symmetric tridiagonal matrix can be accelerated by incorporating a sequence of origin shifts. The origin shift may be either subtracted directly from the diagonal elements of the matrix or incorporated by means of an implicit algorithm. Both methods have drawbacks: the direct method can unnecessarily degrade small eigenvalues, while the implicit method can effectively loose the shift and thereby retard the convergence. This paper presents a new method which has neither drawback.
Data communications control procedures for the USA standard code for information interchange
Authors: Lohse E. L.
Published: July 2002

This proposed American Standard has been accepted for publication by USA Standards Committee X3, Computers and Information Processing. In order that the final version of the proposed standard reflect the largest public consensus, X3 authorized publication of this document to elicit comment and general public reaction, with the understanding that such a working document is an intermediate result in the standardization process and is subject to change, modification, or withdrawal in part or in whole. Comments should be addressed to the X3 Secretary, Business Equipment Manufacturers Association, 235 East 42 Street, New York, NY 10017.—E. L.
A global parser for context-free phrase structure grammars
Authors: Unger Stephen H.
Published: July 2002

An algorithm for analyzing any context-free phrase structure grammar and for generating a program which can then parse any sentence in the language (or indicate that the given sentence is invalid) is described. The parser is of the “top-to-bottom” type and is recursive. A number of heuristic procedures whose purpose is to shorten the basic algorithm by quickly ascertaining that certain substrings of the input sentence cannot correspond to the target nonterminal symbols are included. Both the generating algorithm and the parser have been implemented in RCA SNOBOL and have been tested successfully on a number of artificial grammars and on a subset of ALGOL. A number of the routines for extracting data about a grammar, such as minimum lengths of N-derivable strings and possible prefixes, are given and may be of interest apart from their application in this particular context.
Education: Expenditures, sources of funds, and utilization of digital computers for research and instruction in higher education: 1964-65 with projections for 1968-69
Authors: Hamblen John W.
Published: July 2002

The Southern Regional Education Board published a complete report on a survey it conducted to determine the funding and characterize the utilization of computers used for research and instruction in institutions of higher education in the United States. The sampling survey is described and the estimates for this total population are presented.
A note on computing approximations to the exponential function
Authors: Cody W. J. , Ralston Anthony
Published: July 2002

Two methods are discussed which result in near minimax rational approximations to the exponential function and at the same time retain the desirable property that the approximation for negative values of the argument is the reciprocal of the approximation for corresponding positive values. These methods lead to approximations which are much superior to the commonly used convergents of the Gaussian continued fraction for the exponential. Coefficients and errors are given for the intervals [-1/2 ln 2, 1/2 ln 2] and [-ln 2, ln 2].

Two methods are discussed which result in near minimax rational approximations to the exponential function and at the same time retain the desirable property that the approximation for negative values of the argument is the reciprocal of the approximation for corresponding positive values. These methods lead to approximations which are much superior to the commonly used convergents of the Gaussian continued fraction for the exponential. Coefficients and errors are given for the intervals [-1/2 ln 2, 1/2 ln 2] and [-ln 2, ln 2].
On context and ambiguity in parsing
Authors: Ross Douglas T.
Published: July 2002

This note is by way of commentary on the notions of “bounded context” of Floyd [1] and “structural connections” of Irons [2], as these notions relate to as yet unpublished researches growing out of the development of the author's Algorithmic Theory of Language [3, 4]. In the closing paragraphs of [3], the author made comments concerning further developments of the theory which would include “context dependence” and “resolution of apparent syntactic ambiguities.” The work on parsing reported here was carried out in early September, 1962 (an earlier version in March, 1962), but has not been polished or reduced to final form because, for the purpose of the total theory, parsing should not be considered separately, and the complexities of the proper treatment of the “precedence string” (which relates to semantic structure as distinct from syntactic structure of parsing) have not yet been satisfactorily resolved.
Experimental evaluation of information retrieval through a teletypewriter
Authors: Rubinoff Morris , Bergman Samuel , Franks Winifred , Rubinoff Elayne R.
Published: July 2002

Experiments designed to evaluate the capabilities of mechanized information retrieval systems, with emphasis on interactive (man-machine) language and on some of the mechanical and psychological limitations in their design, were conducted at the Moore School Information Systems Laboratory. The basic assumption of the research is that an information retrieval system that provides for man-machine dialogue at a remote inquiry terminal should provide a searcher with many of the tools which would be available to him were he actually performing his search at a library or repository of documents. Factors involved in evaluation of such a system include ease of use, learning time, and effectiveness of actual retrieval. Three experiments and the conclusions resulting from them are detailed.
Computational Linguistics: Graphical input/output of nonstandard characters
Authors: Hayashi Hideyuki , Duncan Sheila , Kuno Susumu
Published: July 2002

A system developed at Harvard for graphically inputting and outputting nonstandard characters on a computer is printed. In principle, the system can deal with any orthography, although at present it is limited to 4000 Chinese characters and some mathematical symbols. New characters can be added to the repertoire of the system by graphical input on a display scope. Text inputting is accomplished via a display scope or a Rand Tablet.

The organization and operation of the current system are described, and a discussion of the relative merits of such a system is given. Illustrations of the computer input and output of Chinese characters are included.
Programming analysis of variance by sequences of operators and isomorphic mappings
Authors: Peng K. C.
Published: July 2002

A special operator calculus developed by Hartley in 1956 together with a new mapping scheme has been found to be efficient in programming analysis of variance for multifactor experiments. The operator calculus and the mapping scheme are described in detail.
Theoretical considerations in information retrieval systems
Authors: Belzer Jack , Goffman W.
Published: July 2002

A method for automatic loading of library subroutines, which can be adapted to operate in conjunction with any conventional two-pass assembler is described. The method is specifically designed to cope with a nested library structure.
A note on starting the Newton-Raphson method
Authors: Beyer W. A.
Published: July 2002

Determination of a suitable initial estimate for a root of an equation ƒ(
x
) = 0 by means of computing the roots of a sequence of related equations is described.
Extension of existing compilers by sophisticated use of macros
Authors: Bennett Richard K. , Neumann H. David
Published: July 2002

A description is presented of an application in which macros and string concatenation were employed to add a new facility to BELFAP.
Multilevel operating systems
Authors: Orchard-Hays William
Published: July 2002

The basic software for all newer computers is built on the well-established need for standard operating systems. This implies that all applications—no matter how large, complex or time consuming—must operate under (or, more precisely, on top of) the standard system.

Large applications require supervisory monitors which handle problems similar to those of the operating systems, but at a different level. Sometimes, still a third or even a fourth such level is required or desirable. This leads naturally to the concept of multilevel systems—similar vertically, but different horizontally. Proper division of responsibility between levels leads to greater efficiency and less logical complexity, while actually enhancing capability.
Simulation of computer logic by Fortran arithmetic
Authors: Weingarten Fred W.
Published: July 2002

During the preliminary logical design of the NEBULA computer for the Oregon State University Department of Mathematics, it was decided to simulate the logic equations on one of the computers available on campus. Thus most of the logic could be debugged prior to backwiring.
The self-judgment method of curve fitting
Authors: de Maine P. A. D.
Published: July 2002

A computer-oriented method for processing and communicating numerical data is described. The Instrument Reliability Factors (IRF), which exactly define the limits of reliability of each measured item of information, are used to compute the Maximum Permitted Error (MPE) associated with each value of each ordinate. The Self-Judgment Principle (SJP) is used to discard wrong information and to compute mean values of the parameters and their MPE's in terms of the IRF. Data compatibility tests with any number of different equations can be made quickly. Otherwise intractable problems are easily solved, and the design of many experiments is greatly simplified.

The computational and mathematical techniques used to reduce bias in the SJP are discussed. Inadequacies in the statistical and graphical methods of curve fitting are noted.
A final solution to the Dangling else of ALGOL 60 and related languages
Authors: Abrahams Paul W.
Published: July 2002

The dangling else problem consists of a class of potential ambiguities in ALGOL-like conditional statements whose basic form is “if
B
1 then if
B
2 then
S
1 else
S
2” where
B
1 and
B
2 are Boolean expressions and
S
1 and
S
2 are basic statements. The difficulty lies in whether to attach the else to the first if or to the second one. Existing solutions to the problem are either ambiguous or unnecessarily restrictive. Let
S
and
S
1 be statements. We define
S
to be
closed
if “
S
else
S
1” is not a statement, and to be
open
if “
S
else
S
1” is a statement. Thus an unconditional statement is a closed statement. Open and closed conditional statements are defined by syntax equations in such a way as to preserve openness and closure. In each case, an else must always be preceded by a closed statement. It is shown that the syntax equations are unambiguous, and that any change in the statement types required within the syntax equations would lead to either ambiguity or unnecessary restriction.
Extracting usability information from user interface events
Authors: Hilbert David M. , Redmiles David F.
Published: July 2002

Modern window-based user interface systems generate user interface events as natural products of their normal operation. Because such events can be automatically captured and because they indicate user behavior with respect to an application's user interface, they have long been regarded as a potentially fruitful source of information regarding application usage and usability. However, because user interface events are typically voluminos and rich in detail, automated support is generally required to extract information at a level of abstraction that is useful to investigators interested in analyzing application usage or evaluating usability. This survey examines computer-aided techniques used by HCI practitioners and researchers to extract usability-related information from user interface events. A framework is presented to help HCI practitioners and researchers categorize and compare the approaches that have been, or might fruitfully be, applied to this problem. Because many of the techniques in the research literature have not been evaluated in practice, this survey provides a conceptual evaluation to help identify some of the relative merits and drawbacks of the various classes of approaches. Ideas for future research in this area are also presented. This survey addresses the following questions: How might user interface events be used in evaluating usability? How are user interface events related to other forms of usability data? What are the key challenges faced by investigators wishing to exploit this data? What approaches have been brought to bear on this problem and how do they compare to one another? What are some of the important open research questions in this area?