bluuebunny/crossref_metadata_2025 huggingface dataset:
Combining decision rules in a decision table
Authors: Shwayder Keith
Published: July 2002

The techniques for minimizing logic circuits are applied to the simplification of decision tables by the combining of decision rules. This method is logically equivalent to the Quine-McCluskey method for finding prime implicants. If some of the decision rules implied in the
ELSE
Rule occur with low frequency, then the
ELSE
Rule can be used to further simplify the decision table.

Several objectives merit consideration in optimizing a decision table:

reducing machine execution time;

reducing preprocessing time;

reducing required machine memory;

reducing the number of decision rules. (This often improves the clarity of the decision table to a human reader.)

It will be shown that objectives (3) and (4) can be furthered with the above methods. Objective (1) is also attained if overspecified decision rules are not combined. Objective (2) must be compared against the potential benefits of objectives (1), (3), and (4) in deciding whether to use the above methods.
The equivalence of reducing transition languages and deterministic languages
Authors: Schkolnick Mario
Published: July 2002

The class of reducing transition languages introduced by Eickel, Paul, Bauer, and Samelson was shown by Morris to be a proper superclass of the simple precedence languages. In this paper this result is extended, showing that, in fact, the first class is equivalent to the class of deterministic context free languages.
On the complexity of LR(k) testing
Authors: Hunt Harry B. , Szymanski Thomas G. , Ullman Jeffrey D.
Published: July 2002

The problem of determining whether an arbitrary context-free grammar is a member of some easily parsed subclass of grammars such as the LR(k) grammars is considered. The time complexity of this problem is analyzed both when k is considered to be a fixed integer and when k is considered to be a parameter of the test. In the first case, it is shown that for every k there exists an O(n
k+2
) algorithm for testing the LR(k) property, where n is the size of the grammar in question. On the other hand, if both k and the subject grammar are problem parameters, then the complexity of the problem depends very strongly on the representation chosen for k. More specifically, it is shown that this problem is NP-complete when k is expressed in unary. When k is expressed in binary the problem is complete for nondeterministic exponential time. These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), and strong LC(k) grammars.
Pictorial pattern recognition and the phase problem of x-ray crystallography
Authors: Lesk Arthur M.
Published: July 2002

The availability of interactive, three-dimensional, computer graphics systems coupled to powerful digital computers encourages the development of algorithms adapted to this environment. Pictorial pattern recognition techniques make possible a number of approaches to X-ray structure determination based on molecular model building, i.e. the use of chemical information to frame “structural hypotheses” which can computationally be tested and refined by reference to the experimental data.

Application of standard pattern recognition algorithms is hindered by the fact that the cross-correlation between a model and the correct structure cannot be computed because of a fundamental incompleteness in the measured data. However, it is possible to compute an upper bound to such a cross-correlation. A simple example demonstrates that this information can be the basis of a technique for structure determination that can make effective use of an interactive graphics system.

Model building by cross-correlations has intrinsic advantages over usual crystallographic techniques based on the autocorrelation or Patterson function, especially for large structures. This is significant, for crystallography of biological macromolecules has been and will continue to be a field of intense interest.
A proposal for a computer-based interactive scientific community
Authors: Pager David
Published: July 2002

Because of the problems created by the explosion of papers in the mathematical sciences and the drawbacks that this places on research, it is suggested that a tree of all mathematical results and terminology be maintained in a multiterminal computer system. Users of the system can store in the computer an updated file of their current knowledge, and on selecting a paper to read, they can obtain from the computer the minimum subtree of theorems required to bring them from what they already know to the background knowledge which the paper assumes. Under certain conditions, means are also provided for the contribution of useful comments by the readers of a work and for interaction between commentators and with the author. This paper describes how the system can be organized and the role required of readers, writers, and commentators.
An experimental laboratory for pattern recognition and signal processing
Authors: Herbst N. M. , Will P. M.
Published: July 2002

An interactive computer-controlled scanning and display system has been in operation at the IBM Thomas J. Watson Research Center for three years. The system includes two flying-spot scanners and a TV camera specially interfaced to a process control digital computer, dot-mode and vector displays, analog input and output facilities, and a variety of other experimental equipment. The system design and programming support are described and typical applications in scanner control, optical character recognition, and image processing are presented.
Toward an automata theory of brains
Authors: Arbib Michael A.
Published: July 2002

A source of ideas for automata theory—the study of the brain—has been pushed aside in mathematical development of the theory. This paper suggests the ways in which automata theory might evolve over the next 25 years if it is to contribute to an understanding of how the brain processes information.
The role of computer system models in performance evaluation
Authors: Kimbleton Stephen R.
Published: July 2002

Models constitute a useful means of investigating computer system performance. This paper examines the interrelationships between models and other methods for evaluating the performance of computer systems and establishes circumstances under which the use of a model is appropriate.
Index ranges for matrix calculi
Authors: Bayer R. , Witzgall C.
Published: July 2002

The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code.

The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with “indexing by position.” The relationship of “indexing by name” and “indexing by position” is discussed.
A new method for the solution of the Cauchy problem for parabolic equations
Authors: Moore John , Robinson Prentiss
Published: July 2002

partial differential equations. When the equations are defined in unbounded domains, as in the initial value (Cauchy) problem, the solution of the integral equation by the method of successive approximation has inherent advantages over other methods. Error bounds for the method are of order h
3/2
and h
7/2
(h is the increment size) depending on the finite difference approximations involved.
A heuristic approach to inductive inference in fact retrieval systems
Authors: Skinner C. William
Published: July 2002

Heuristic procedures are presented which have been developed to perform inferences by generalizing from available information. The procedures make use of a similarity structure which is imposed on the data base using nonnumerical clustering algorithms. They are implemented in a model fact retrieval system which uses a formal query language and a property-list data structure. A program of experiments is described wherein the procedures are used with test data bases which are altered by deleting part of the data and by purposely introducing false data. It is found that the system can infer the correct response under a variety of conditions involving incomplete and inconsistent data.
A note on when to chain overflow items within a direct-access table
Authors: Bays Carter
Published: July 2002

This note supplements the paper by V.Y. Lum [2] and elaborates on Table II in McIlroy [3].
The quadratic quotient method
Authors: Bell James R.
Published: July 2002

Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its eliminiation is presented. Comparisons with previous methods are made both analytically and empirically.
Cubic spline solutions to fourth-order boundary value problems
Authors: Hoskins W. D.
Published: July 2002

The cubic spline approximation to the fourth-order differential equation

y
iυ

+
p
(
x
)
y
″ +
q
(
x
)
y
′ +
r
(
x
)
y
=
t
(
x
) is shown to reduce to the solution of a five-term recurrence relationship. For some special cases the approximation is shown to be simply related to a finite difference representation with a local truncation error of order (1/720)
δ
8
y
.
Comment on multiprogramming under a page on demand strategy
Authors: Smith J. L.
Published: July 2002

It has been brought to my attention that Figure 5 in my paper [1] is not consistent with Figure 2 in the paper [2], as it was meant to be. In the former the ordinate is defined as the incremental number of instructions executed between page demands, but the curve corresponds to the cumulative measure given in the latter.
A note on information organization and storage
Authors: Huang J. C.
Published: July 2002

Since the logical structure of a data base can be represented by a tree or graph, it is quite natural for us to view the process of designing a data base as that of constructing a tree or a graph. A general method for constructing such a tree or graph is provided. There are three important elements in this general construction method; namely, a set of binary relations, an algorithm for constructing subsets of a set, and an algorithm for selecting an element from the given set of objects. The use of different relations and algorithms results in different information structures, as list, tree, ring, etc. Thus the problem of information organization and storage is reduced to that of defining relations and formulating algorithms under a given set of constraints. The results presented may be valuable to designers as useful design concepts, and may serve as a basis for developing a formal theory on the subject.
Computer science—seminars for undergraduates
Authors: Kandel Abraham
Published: July 2002

In recent years a number of curricula for computer science education have been proposed. Most notable among these are [1-4]. The results from these four studies were unbalanced oriented educational programs each with a different primary emphasis on various aspects of computer science and its application. None offered a prescription within the undergraduate framework for a satisfactory synthesis of hardware, software, and abstract theory.
A simple technique for structured variable lookup
Authors: Gates Geoffrey W. , Poplawski David A.
Published: July 2002

A simple technique for the symbol-table lookup of structured variables based on simple automata theory is presented. The technique offers a deterministic solution to a problem which is currently handled in a nondeterministic manner in PL/I and COBOL compilers.
Comment on the conversion of decision tables to computer programs
Authors: Pollack Solomon L.
Published: July 2002

In their article [2] C. R. Muthukrishnan and V. Rajaraman have developed two excellent algorithms for conversion of limited entry and mixed entry decision tables to computer programs. I must, however, take issue with their contention that “…in general, the conditions may be very complicated and a compile time analysis will not be possible.” They then cite the following example in Figure 1(b).
Storage utilization in a memory hierarchy when storage assignment is performed by a hashing algorithm
Authors: Williams John G.
Published: July 2002

The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given that
N
entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level store. This expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store.
Comments on a paper by Lowe
Authors: Sattley Kirk , Millstein Robert
Published: July 2002

We have read with much interest the paper “Automatic Segmentation of Cyclic Program Structures Based on Connectivity and Processor Timing” by T. C. Lowe [
Comm. ACM 13
, 1 (Jan. 1970), 3-6, 9], and we congratulate the author on the clarity of his exposition. However, we're afraid we must question the technique he describes.
A comment on axiomatic approaches to programming
Authors: Hunt B. R.
Published: July 2002

Reference is made to the paper by C. A. R. Hoare [1] which discusses the fundamentals of an axiomatic approach to computer programming. One advantage for an axiomatic system proposed by Hoare is that an axiomatic description of computer programs would allow the application of deductive inference to formally and conclusively prove that a computer program performs the computation the designer intended. The purpose of this short communication is to discuss the relationship between Hoare's concepts and an approach in a book by Wymore [2].
President's letter to the ACM membership: The journal
Authors: Galler Bernard A.
Published: July 2002

A great deal of concern has been expressed to me and to members of the Executive Committee and the Editorial Board about the new status of the
Journal
. Obviously, the concern is not over the $3 needed to subscribe to the
Journal
in the future. Those who are worried about the change, which substituted the new
Computing Surveys
for the
Journal
, see it as one more step in a process of change within ACM that has been going on for some time. They argue that the Association began as an academic, scientific, professional organization concerned with the more formal mathematical and scientific aspects of information processing, and their concern that the organization has changed character is quite legitimate.
On ACM special interest groups and committees
Authors: Denning Peter J.
Published: July 2002

This report has been written to explain the nature, purposes, and organization of the Special Interest Groups (SIGS) and Special Interest Committees (SICS) of ACM, and to summarize SIG/SIC activity during the period August 1, 1970, to August 1, 1971.
Editorial: on the ACM publications
Authors: Gotlieb C. C.
Published: July 2002

It is proper that a professional organization periodically review its publication policy to ensure that it is fully meeting its responsibilities to its members To this purpose the President of ACM has asked the Editorial Board to formulate a five-year policy for recommendation to the Council and an ad hoc commitee of the Editorial Board is examining the question.

Professor Gotlieb, through his distinguished editorial service over the past years as Editor-as-Chief of the Journal and also of Communications, has helped shape the development of ACM publications, and we are pleased to present his views in this invited editorial —M. Stuart Lynn, Editor-in-Chief
Analysis of boolean program models for time-shared, paged environments
Authors: Lowe Thomas C.
Published: July 2002

Directed graphs or their associated matrices are frequently used to represent the logical structure of sequences of computer instructions. Such techniques are used and, in addition, data references are represented in a nondirected model. The complete structural specification of a program is represented by a combined model. A transformation of the combined model yields a new model in which additional timing information is also contained. Analysis of these models prior to execution yields information valuable in determining segmentation of instructions and data for a time-shared environment, as well as for initial page loading; during execution, the analysis may be used for “look ahead” control of page turning.
Degree of multiprogramming in page-on-demand systems
Authors: Wallace V. L. , Mason D. L.
Published: July 2002

A simple stochastic model is described which offers a base for understanding the relationship between the number of programs permitted to share memory (the degree of multiprogramming), drum traffic rates, and central processing unit utilization in page-on-demand, multiprogrammed, time-shared computer systems. The model preserves, as a key feature, the property of page-demand statistics which implies a “burst” of page demands at the beginning of any job or quantum execution.

The model, a Markov chain, is analyzed numerically and the results are presented graphically for a wide range of key environment-descriptive parameters. Implications of the results to time-shared system design and programming are discussed, and a calculation of the optimal degree of multiprogramming for a wide range of parameters is presented graphically.
Generation of optimal code for expressions via factorization
Authors: Breuer Melvin A.
Published: July 2002

Given a set of expressions which are to be compiled, methods are presented for increasing the efficiency of the object code produced by first factoring the expressions, i.e. finding a set of subexpressions each of which occurs in two or more other expressions or subexpressions. Once all the factors have been ascertained, a sequencing procedure is applied which orders the factors and expressions such that all information is computed in the correct sequence and factors need be retained in memory a minimal amount of time. An assignment algorithm is then executed in order to minimize the total number of temporary storage cells required to hold the results of evaluating the factors. In order to make these techniques computationally feasible, heuristic procedures are applied, and hence global optimal results are not necessarily generated. The factorization algorithms are also applicable to the problem of factoring Boolean switching expressions and of factoring polynomials encountered in symbol manipulating systems.
Some techniques for using pseudorandom numbers in computer simulation
Authors: Donnelly T.
Published: July 2002

An alogorithm is described by which uniform pseudorandom integers may be used to construct binary “numbers” in which the probability that each bit in the word is a 1-bit and can assume any desired parameter value.

Techniques for making use of such “numbers” in simulation programming are described.
A new method for determining linear precedence functions for precedence grammars
Authors: Bell James R.
Published: July 2002

The precedence relations of a precedence grammar can be precisely described by a two-dimensional precedence matrix. Often the information in the matrix can be represented more concisely by a pair of vectors, called linear precedence functions. A new algorithm is presented for obtaining the linear precedence functions when given the precedence matrix; this algorithm is shown to possess several computational adavantages.
A comment on optimal tree structures
Authors: Stanfel Larry E.
Published: July 2002

In Y.N. Patt's paper “Variable Length Tree Structures Having Minimum Average Search Time” [
Comm
.
ACM 12
(Feb. 1969)], the tree structures obtained are not actually optimal with respect to the two-dimensional chaining devised by Sussenguth in his 1963 paper. This note points out that the result can be described as “optimal” only under the constraint—which Patt implicity assumes—that no key be allowed to prefix another.
Use of a conditional base number system for encoding sequences of correlated characters
Authors: Brown Richard M.
Published: July 2002

A procedure is described for the relatively efficient encoding of sequences of characters which have predecessor-successor selection rules. The procedure is shown to assign a unique integer to each sequence and to generate a reasonably compact set of values.
On the numerical solution of an N-point boundary value problem for linear ordinary differential equations
Authors: Day James T.
Published: July 2002

A method for the numerical solution of the
n
-point boundary value problem for homogeneous linear ordinary differential equations is developed. The method requires two Runge-Kutta integrations over the interval under consideration and the solution of a linear system of equations with
n
-1 unknowns.
On the numerical solution of boundary value problems for linear ordinary differential equations
Authors: Day James T. , Collins George W.
Published: July 2002

A numerical method is presented for the solution of boundary value problems involving linear ordinary differential equations. The method described is noniterative and makes use of any one-step numerical integration scheme to reduce the problem from one of boundary values to one of initial values. Comments are made concerning some numerical results of applying the method to a specific problem. In addition an extension of the algorithm described to more general problems is discussed.
Polyphase sorting with overlapped rewind
Authors: McAllester R. L.
Published: July 2002

A variation of the polyphase merge technique of sorting is described which permits one tape at a time to be rewound while the merge is continued on the remaining tapes. The result is the overlapping of a major portion of the rewind time.

The technique should be considered whenever a sort is written to operate on five or more tapes that cannot be read backwards. The savings of the overlap method appear to increase as the number of available tapes is increased.
A Fourier series method for the numerical solution of a class of parabolic partial differential equations
Authors: Forrington C. V. D.
Published: July 2002

A Fourier series method is described which, when applied to a certain class of parabolic partial differential equations, reduces the problem to a system of ordinary differential equations. An application is given for which the method shows a considerable advantage over conventional finite difference methods.
Computer programs are patentable
Authors: Hamlin Kenneth B.
Published: July 2002

It is not surprising that computer programs are not listed in the patent statutes as one of the categories of patentable invention. When these categories were defined many years ago, computers and computer programs were unknown. Therefore, if computer programs are to be patentable within the framework of existing patent law they must fall within one of the specifically defined categories of processes, machines, manufactures or compositions of matter.
Multiple-precision arithmetic and the exact calculation of the 3-
j
and 9-
j
symbols
Authors: Baer Robert M. , Redlich Martin G.
Published: July 2002

Described in this paper is a system of general-purpose multiple-precision fixed-point routines and their use in subroutines which calculate exactly the quantum-mechanical 3-
j
, 6-
j
and 9-
j
symbols of large arguments.
Determining a computing center environment
Authors: Rosin Robert F.
Published: July 2002

An investigation is described in which several generally unavailable parameters descriptive of a computing center environment are obtained. The actual data collection and reduction is described, and the results of one month of this collection are tabulated and summarized.
Online programming
Authors: Schwartz Jules I.
Published: July 2002

When the transition has been made from offline to online programming, there are a number of changes in the working conditions noted. These changes in the environment make necessary corresponding changes in the processes related to producing and checking out programs. In the main, it is not the programming language itself which must be changed to provide a facility for the online user; it is the system surrounding the programming language. In this paper the online environment and its effect on programming are discussed.
A computer center simulation project
Authors: Hutchinson George K.
Published: July 2002

Today's computation centers are based on rapidly changing technologies of hardware and software systems. It is difficult, therefore, to base decisions on experience; in most instances, the benefits of comparable experience for a given problem situation are not available. In this paper, a mathematical model of the Lockheed Central Computer Center is formulated that describes the operation of a computation center in terms of information nets, decision processes, and control functions. Experiments performed with this model, the results of the experiments, and the application of the results are discussed.
UPLIFTS—University of Pittsburgh linear file tandem system
Authors: Canter J. D. , Donaghey C. E.
Published: July 2002

A series of computer programs has been developed and is now operational for processing the National Aeronautics and Space Administration linear file system on an IBM 1401-7090 combined data processing system. The programs are noteworthy in that they create fixed length logical records and fixed length blocks from variable length source data, and format the output for optimization of processing on the IBM 7090 system. The programs are completely self-checking and test for both validity and accuracy of the input materials as provided by the National Aeronautics and Space Administration.
Solutions of systems of polynomial equations by elimination
Authors: Moses Joel
Published: July 2002

The elimination procedure as described by Williams has been coded in LISP and FORMAC and used in solving systems of polynomial equations. It is found that the method is very effective in the case of small systems, where it yields all solutions without the need for initial estimates. The method, by itself, appears inappropriate, however, in the solution of large systems of equations due to the explosive growth in the intermediate equations and the hazards which arise when the coefficients are truncated. A comparison is made with difficulties found in other problems in non-numerical mathematics such as symbolic integration and simplification.
Mathematics for undergraduate computer scientists
Authors: Atchison William F.
Published: July 2002

The mathematical requirements for an undergraduate program in Computer Science are a subject of debate. The Association for Computing Machinery's Curriculum Committee, however, believes that these requirements are essentially the same as the mathematical content of physical sciences undergraduate programs. The Committee believes that these requirements should assure the student of a broad mathematical background and should enable him to take a wide variety of courses in other scientific disciplines. The Committee's concern is to develop a solid scientific approach to Computer Science.
Computer planned collates
Authors: French Norman C.
Published: July 2002

Little effort has been directed toward the creation of efficient, easy-to-use file merging routines. This lack of effort undoubtedly stems from the feeling that a process as simple and straightforward as merging two or more files does not lend itself to sophisticated techniques.
Sorting nonredundant files—techniques used in the FACT compiler
Authors: Glore John B.
Published: July 2002

Some typical file structures, including some called “non-redundant,” are examined, and the methods used in FACT to sort such files are discussed.
Organization and structure of data on disk file memory systems for efficient sorting and other data processing programs
Authors: Goetz Martin A.
Published: July 2002

An approach to the organization and structure of data on Bryant Disc File Memory Systems for sorting and performing other data processing functions is presented. The following areas are covered: characteristics of Bryant Disc File Systems on the Bendix G-20 and RCA 301; two proposed “chaining” structures for data; and functions of a Disk File Executive Routine. The concepts for sorting and performing file maintenance processing using the proposed structure and executive routine are discussed. Additionally, it is shown that sorting can be accomplished without the use of disk storage work areas.
A computer program for analysis of variance for a 2-level factorial design
Authors: Britton Catherine , Wagner I. F.
Published: July 2002

Although many computer programs exist for handling analysis of variance, most of them employ the conventional methods described in statistics books for finding the sums of squares.
Manned simulation research in complex control systems
Authors: Geisler M. A. , Steger W. A.
Published: July 2002

Two purposes guide the studies currently in progress in the RAND Logistics Systems Laboratory: one is to aid the Air Force in a substantive management or control problem, such as operations-support control of the ICBM force, or control and allocation of resources to perform the short-term job of procuring, repairing and distributing the Air Force's supply assets; and the second is to improve the RAND use of abstract (primarily, manned computer-assisted) simulations in designing and evaluating alternative, complex control systems.
A 48-bit pseudo-random generator
Authors: Kuehn Heidi G.
Published: July 2002

A new 48-bit pseudo-random number generator, suitable for several computers, was tested statistically for randomness to determine its adequacy for use in Monte Carlo programs. Frequency tests, distributions of certain low-order moments, runs up and down, and runs above and below the mean were applied to one-half million generated numbers lying within the interval (0, 1) and to three sets of integers obtained from specified bits within the generated numbers. These tests substantiated the randomness of all numbers except for the set of integers coming from the least significant bits.
Inefficiency of the use of Boolean functions for information retrieval systems
Authors: Verhoeff J. , Goffman W. , Belzer Jack
Published: July 2002

In this note we attempt to point out why boolean functions are, in general, not applicable in information retrieval systems.
A note on the use of the Abacus in number conversion
Authors: Kanner H.
Published: July 2002

Conversion of integers in both directions between the base ten and any desired base can be accomplished with remarkable simplicity by use of the abacus. In fact, the conversion procedures are far more cumbersome on the electric desk calculator, for reasons which will be apparent.
Decoding combinations of the first
n
integers taken
k
at a time
Authors: Brown Richard M.
Published: July 2002

The following problem arose in connection with some studies involving game programming: the representation of any position in the game tree was formed by a sequence of
k
different integers selected from the first
n
integers. It was desired to decode any of these representations to a unique memory address such that all such addresses formed a compact group in the memory. Mathematically, the problem was to find a transformation of the representation such that any of the
n
!/(
n
-
k
)! sequences transformed uniquely to one of the set of integers from 0 to [
n
!/(
n
-
k
)! - 1]. A procedure for this is described here.
Rapidly convergent expressions for evaluating e
x
Authors: Berin A.
Published: July 2002

Rapidly converted subject expressions for

e
x

can be derived by utilization of existing infinite series for log.
A simple technique for coding differential equations
Authors: Sefton P. , Vaillancourt R.
Published: July 2002

A computer program that will solve an arbitrary system of first-order differential equations according to some conventional numerical method may be considered to have two distinct parts. The main program performs all of the operations of input-output, initialization, choice of step-size, and actual solution of the equations. This part of the program is independent of the functional equations relating the derivatives to the variables. A subsidiary program evaluates the derivatives according to the given functional relationships, and this subprogram or subroutine has to be written for each new system of equations [1].
A comparison of 650 programming methods
Authors: Curtz T. B. , Riordan J. F. , Spohn M.
Published: July 2002

An evaluation of an automatic programming method can be made from many points of view. Two recent articles give evaluations of two compilers for the IBM 650 based on the method of decomposition of compiler statements into machine language [1, 2]. This paper briefly describes these two compilers, appraises them for the ease with which they can be used and for the efficiency of the programs they produce. While this approach is of less theoretical interest than the evaluations presented in the referenced articles, it is of substantially more practical significance to a programmer or to an installation which is seeking to answer the following questions: Should a compiler be used? If so, which compiler? It will be noted that no universal answers are possible since such factors as relative costs and availability of machine time and programmer time, the skill and predilections of programmers, and the type of problems are of major importance. Nevertheless, the results presented below, we believe, provide the best available guide for arriving at reasonable answers.
Closing out a print tape
Authors: Moore Donald P.
Published: July 2002

Some computer operating systems have a bad habit of inserting tape marks into the output stream willy-nilly. This often results in loss of output when a tape is scratched after its first file has been printed. Other operating systems, notably those recently distributed by IBM for use with the 7090, put tape marks on print tapes only on command, so that frequently a print tape is removed from the computer without any tape mark, and extraneous material is printed.
On the approximate solution of Δ
u
=
F(u)
Authors: Greenspan D. , Yohe M.
Published: July 2002

Three-dimensional Dirichlet problems for Δ
u
=
F
(
u
),

F
u

≧ 0, are treated numerically by an exceptionally fast, exceptionally accurate numerical method. Programming details, numerous examples and mathematical theory are supplied. Extension of the method in a natural way to
n
-dimensional problems is indicated by means of a 4-dimensional example.
An experiment in automatic verification of programs
Authors: Weinberg G. M. , Gressett G. L.
Published: July 2002

How effective is a compiler at replacing explicit verification, and what is the cost of this technique?
An automatic data acquisition and inquiry system using disk files
Authors: Edwards James D.
Published: July 2002

Lockheed Missiles and Space Company has installed a large-scale Automatic Data Acquisition (ADA) system which ties together the Company's manufacturing facilities located in Van Nuys and Sunnyvale, California. The system includes over 200 Remote Input Stations which collect and transmit Company operating data to a central Data Processing Center. Two RCA 301 EDP Systems are used to record and control the flow of data transmitted to the Data Processing Center. A large capacity RCA 366 Data Disc File is used to store information required to provide up-to-date information in response to inquiries received from remotely located Inquiry Stations. In addition to storage of data on the disk files, the system automatically records all incoming and outgoing data on magnetic tape to be used as input to the Company's conventional off-line business data processing applications.
A dispersion pass algorithm for the polyphase merge
Authors: Mendoza Armando G.
Published: July 2002

This paper presents a new manner of dispersing strings for a Polyphase merge. If the number of strings dispersed is between two levels acceptable by Polyphase merge, a more economical technique of reaching the next level for Polyphase merge is shown and proved.
A mapping algorithm for computer-assisted exploration in the design of embedded systems
Authors: Mariatos E. P. , Birbas A. N. , Birbas M. K.
Published: July 2002

We present a technique for automatic exploration of architectural alternatives in the design of complex electronic embedded systems and systems-on-a-chip. The technique transforms the problem into a set of simple model-to-model operations and a mapping algorithm that becomes the core of the entire design process. The mapping algorithm is formulated as an assignment-type problem (ATP), which is, in turn, solved by a straightforward optimization method. The result is a design assistance tool, which is demonstrated through a telecommunication systems example.
How to optimize proof-search in modal logics
Authors: Voronkov Andrei
Published: July 2002

We present a bottom-up decision procedure for propositional modal logic K based on the inverse method. The procedure is based on the “inverted” version of a sequent calculus. To restrict the search space, we prove a number of redundancy criteria for derivations in the sequent calculus. We introduce
a new technique
of proving redundancy criteria, based on the analysis of tableau-based derivations in K. Moreover, another new technique is based on so-called
traces
. A new search with a strong notion of subsumption. This technique is based on so-called
traces
. A new formalization of the inverse method in the form of a
path calculus
considerably simplifies all proofs as compared to the previously published presentations of the inverse method. Experimental results demonstrate that our method is competitive with many state-of-the-art implementations of K.
Verifying sequential equivalence using ATPG techniques
Authors: Huang Shi-Yu , Cheng Kwang-Ting , Chen Kuang-Chien
Published: July 2002

In this paper we address the problem of verifying the equivalence of two sequential circuits. State-of-the-art sequential optimization techniques such as retiming and sequential redundancy removal can handle designs with up to hundreds or even thousands of flip-flops. However, the BDD-based approaches for verifying sequential equivalence can easily run into memory explosion for such designs. In an attempt to handle larger circuits, we modify test pattern-generation techniques for verification. The suggested approach utilizes the popular efficient backward-justification technique used in most sequential ATPG programs. We present several techniques to enhance the efficiency of this approach by (1) identifying equivalent flip-flop pairs using an induction-based algorithm, and (2) generalizing the idea of exploring the structural similarity between circuits to perform verification in stages. This ATPG-based framework is suitable for verifying circuits either with or without a reset state. In order to extend this approach to verify retimed circuits, we introduce a delay-compensation-based algorithm for preprocessing the circuits. The experimental results of verifying the correctness of circuits after sequential redundancy removal and retiming with up to several hundred flip-flops are presented.
Performance and fluid simulations of a novel shared buffer management system
Authors: Kumaran Krishnan , Mitra Debasis
Published: July 2002

We consider a switching system that has multiple ports that share a common buffer, in which there is a FIFO logical queue for each port. Each port may support a large number of flows or connections, which are approximately homogeneous in their statistical characteristics, with common QoS requirements in cell loss and maximum delay. Heterogeneity may exist across ports. Our first contribution is a buffer management scheme based on Buffer Admission Control, which is integrated with Connection Admission Control at the switch. At the same time, this scheme is fair, efficient, and robust in sharing the buffer resources across ports. Our scheme is based on the resource-sharing technique of Virtual Partitioning. Our second major contribution is to advance the practice of discrete-event fluid simulations. Such simulations are approximations to cell-level simulations and offer orders of magnitude speed-up. A third contribution of the paper is the formulation and solution of a problem of optimal allocation of bandwidth and buffers to each port having specific delay bounds, in a lossless multiplexing framework. Finally, we report on extensive simulation results. The scheme is found to be effective, efficient, and robust.
Fuzzy functional dependencies and lossless join decomposition of fuzzy relational database systems
Authors: Raju K. V. S. V. N. , Majumdar Arun K.
Published: July 2002

This paper deals with the application of fuzzy logic in a relational database environment with the objective of capturing more meaning of the data. It is shown that with suitable interpretations for the fuzzy membership functions, a fuzzy relational data model can be used to represent ambiguities in data values as well as impreciseness in the association among them. Relational operators for fuzzy relations have been studied, and applicability of fuzzy logic in capturing integrity constraints has been investigated. By introducing a fuzzy resemblance measure EQUAL for comparing domain values, the definition of classical functional dependency has been generalized to fuzzy functional dependency (ffd). The implication problem of ffds has been examined and a set of sound and complete inference axioms has been proposed. Next, the problem of lossless join decomposition of fuzzy relations for a given set of fuzzy functional dependencies is investigated. It is proved that with a suitable restriction on EQUAL, the design theory of a classical relational database with functional dependencies can be extended to fuzzy relations satisfying fuzzy functional dependencies.
Reasoning with worlds and truth maintenance in a knowledge-based programming environment
Authors: Filman Robert
Published: July 2002

In traditional knowledge-based system development environments, the fundamental representational building blocks are mechanisms such as frames, rules, and attached procedures. The KEE system has been extended to include both a context (worlds) system and a truth maintenance system.
The parallel complexity of exponentiating polynomials over finite fields
Authors: Fich Faith E. , Tompa Martin
Published: July 2002

Modular integer exponentiation (given
a, e,
and
m
, compute
a
e
mod
m
) is a fundamental problem in algebraic complexity for which no efficient parallel algorithm is known. Two closely related problems are modular polynomial exponentiation (given
a
(
x
),
e
, and
m
(
x
), compute (
a
(
x
))
e
mod
m
(
x
)) and polynomial exponentiation (given
a
(
x
),
e
. and
t
, compute the coefficient of

x
t

in (
a
(
x
))
e
). It is shown that these latter two problems are in
NC
2
when
a
(
x
) and
m
(
x
) are polynomials over a finite field whose characteristic is polynomial in the input size.
Meager and replete failures of relative completeness
Authors: Leivant Daniel , Fernando Tim
Published: July 2002

The nature of programming languages that fail to have a relatively complete proof formalism is discussed. First, it is shown that such failures may be due to the meagerness of the programming language, rather than to the presence of complex control structures as in the cases studied so far. The failure of relative completeness is then derived for two languages with a rich control structure, using simple simulations of general recursive functions by procedure call mechanisms.
An inheritance-based technique for building simulation proofs incrementally
Authors: Keidar Idit , Khazan Roger I. , Lynch Nancy , Shvartsman Alex
Published: July 2002

This paper presents a formal technique for
incremental
construction of system specifications, algorithm descriptions, and
simulation proofs
showing that algorithms meet their specifications.The technique for building specifications and algorithms incrementally allows a child specification or algorithm to inherit from its parent by two forms of incremental modification: (a)
signature extension
, where new actions are added to the parent, and (b)
specialization
(subtyping), where the child's behavior is a specialization (restriction) of the parent's behavior. The combination of signature extension and specialization provides a powerful and expressive incremental modification mechanism for introducing new types of behavior without overriding behavior of the parent; this mechanism corresponds to the subclassing for extension form of inheritance.In the case when incremental modifications are applied to both a parent specification S and a parent algorithm A, the technique allows a simulation proof showing that the child algorithm A′ implements the child specification S′ to be constructed incrementally by extending a simulation proof that algorithm A implements specification S. The new proof involves reasoning about the modifications only, without repeating the reasoning done in the original simulation proof.The paper presents the technique mathematically, in terms of automata. The technique has been used to model and verify a complex middleware system; the methodology and results of that experiment are summarized in this paper.
HCI down under
Authors: Murphy John
Published: July 2002

Australia
is a vast land about the same size as the United States, but with only 20 million people. Behind its well-recognized reputation for sun, sand, surf, crocodiles, and prawns on the barbecue, Australia supports an active and thriving HCI community.
Hijacking the web
Authors: Berghel Hal
Published: July 2002

Cookies revisited: Continuing the dialogue on personal security and underlying privacy issues.
Multiplicative complexity of polynomial multiplication over finite fields
Authors: Kaminski Michael , Bshouty Nader H.
Published: July 2002

Let
M
q
(
n
) denote the number of multiplications required to compute the coefficients of the product of two polynomials of degree
n
over a
q
-element field by means of bilinear algorithms. It is shown that

M
q

(
n
) ≱ 3
n
-
o
(
n
). In particular, if
q
/2 <
n
⪇
q
+ 1, we establish the tight bound

M
q

(
n
) = 3
n
+ 1 [
q
/2].The technique we use can be applied to analysis of algorithms for multiplication of polynomials modulo a polynomial as well.
An improved primal simplex variant for pure processing networks
Authors: Chang Michael D. , Chen Chou-Hong J. , Engquist Michael
Published: July 2002

In processing networks, ordinary network constraints are supplemented by proportional flow restrictions on arcs entering or leaving some nodes. This paper describes a new primal partitioning algorithm for solving pure processing networks using a working basis of variable dimension. In testing against MPSX/370 on a class of randomly generated problems, a FORTRAN implementation of this algorithm was found to be an order-of-magnitude faster. Besides indicating the use of our methods in stand-alone fashion, the computational results also demonstrate the desirability of using these methods as a high-level module in a mathematical programming system.
A definition optimization technique used in a code translation algorithm
Authors: DeJean David M. , Zobrist George W.
Published: July 2002

Data flow analysis is used to optimize variable definitions in a program that translates microprocessor object code to a higher order language.