June 1970 - Vol. 13 No. 6

Features

Research and Advances Jun 1 1970

On the feasibility of voice input to an on-line computer processing system

An on-line digital computer processing system is considered in which an ordinary telephone is the complete terminal device, input to the computer being provided as a sequence of spoken words, and output to the user being audio responses from the machine. The feasibility of implementing such a system with a FORTRAN-like algebraic compiler as the object processor is considered. Details of a specific word recognition program are given. This technique depends on three simplifying restrictions, namely, a “small” vocabulary set, “known” speakers, and a “moment of silence” between each input word. Experimental results are presented giving error rates for different experimental conditions as well as the machine resources required to accommodate several users at a time. The results show that at this time it is both economically and logically feasible to handle at least 40 users at a time with an IBM 360/65 computer.

Howard A. Elder

Research and Advances Jun 1 1970

On the conversion of decision tables to computer programs

The use of execution time diagnostics in pinpointing ambiguities in decision tables is discussed. It is pointed out that any attempt at resolving ambiguities at compile time will, in general, be impossible. It is shown that, as a consequence, tree methods of converting decision tables to programs are inadequate in regard to ambiguity detection. Two algorithms for programming decision tables whose merits are simplicity of implementation and detection of ambiguities at execution time are presented. The first algorithm is for limited entry decision tables and clarifies the importance of proper coding of the information in the decision table. The second algorithm programs a mixed entry decision table directly without going through the intermediate step of conversion to a limited entry form, thereby resulting in storage economy. A comparison of the algorithms and others proposed in the literature is made. Some features of a decision table to FORTRAN IV translator for the IBM 7044 developed by the authors are given.

C. R. Muthukrishnan and V. Rajaraman

Research and Advances Jun 1 1970

Scheduling to reduce conflict in meetings

Conflicts in scheduling can be treated as defining an undirected linear graph independently of the relation of the activities in conflict to additional constraints of time and space. Each connected component of such a graph, which can be found by an algorithm described by Gotlieb and Corneil, corresponds to a set of events that must be scheduled at different times.

Joseph E. Grimes

Research and Advances Jun 1 1970

A PL/1 program to assist the comparative linguist

A practical PL/1 program is described which can assist comparative linguists to determine the regular sound correspondences between genetically related languages. The investigator must arrange data for input by aligning pairs of suspected cognates. The program tabulates the correspondences, and uses list processing techniques to sort and count them. Each pair of words is then assigned a relative value that is a function of the total frequency in the data of each correspondence found in that pair of words. The output is a list of all correspondence types with their frequency of occurrence in the data, and a separate listing of each correspondence with all wordpairs showing that correspondence (unless their relative value is below an arbitrarily chosen cutoff point). The article explains the usefulness, as well as the limitations, of the program, and illustrates its use with a small portion of hypothetical data.

Donald G. Frantz

Research and Advances Jun 1 1970

Automatic parsing for content analysis

Although automatic syntactic and semantic analysis is not yet possible for all of an unrestricted natural language text, some applications, of which content analysis is one, do not have such a stringent coverage requirement. Preliminary studies show that the Harvard Syntactic Analyzer can produce correct and unambiguous identification of the subject and object of certain verbs for approximately half of the relevant occurences. This provides a degree of coverage for content analysis variables which compares favorably to manual methods, in which only a sample of the total available text is normally processed.

Frederick J. Damerau

Research and Advances Jun 1 1970

Accurate floating-point summation

This paper describes an alternate method for summing a set of floating-point numbers. Comparison of the error bound for this method with that of the standard summation method shows that it is considerably less sensitive to propagation of round-off error.

Peter Linz

Research and Advances Jun 1 1970

Comparison of several adaptive Newton-Cotes quadrature routines in evaluating definite integrals with peaked integrands

This report compares the performance of five different adaptive quadrature schemes, based on Newton-Cotes (2N + 1) point rules (N = 1, 2, 3, 4, 5), in approximating the set of definite integrals ∫1-1 (x2 + p2)-1 dx with relative accuracy &egr;.

K. E. Hillstrom

Research and Advances Jun 1 1970

Incorporating origin shifts into the QR algorithm for symmetric tridiagonal matrices

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.

G. W. Stewart

Research and Advances Jun 1 1970

Algorithm 383: permutations of a set with repetitions [G6]

Phillip J. Chase

Research and Advances Jun 1 1970

Algorithm 382: combinations of M out of N objects [G6]

Phillip J. Chase

Research and Advances Jun 1 1970

Algorithm 384: eigenvalues and eigenvectors of a real symmetric matrix

G. W. Stewart

Research and Advances Jun 1 1970

Certification of algorithm 245 [M1]:treesort 3:proof of algorithms—a new kind of certification

Ralph L. London

Research and Advances Jun 1 1970

Remark on algorithm 201 [M1]: shellsort

J. P. Chandler and W. C. Harrison

Research and Advances Jun 1 1970

Remark on algorithm 351 [D1]: modified Romberg quadrature

George C. Wallick

Research and Advances Jun 1 1970

Remark on algorithm 361 [G6]: permanent function of a square matrix I and II

Bruce Shriver, P. J. Eberlein, and R. D. Dixon

Research and Advances Jun 1 1970

A relational model of data for large shared data banks

Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation). A prompting service which supplies such information is not a satisfactory solution. Activities of users at terminals and most application programs should remain unaffected when the internal representation of data is changed and even when some aspects of the external representation are changed. Changes in data representation will often be needed as a result of changes in query, update, and report traffic and natural growth in the types of stored information. Existing noninferential, formatted data systems provide users with tree-structured files or slightly more general network models of the data. In Section 1, inadequacies of these models are discussed. A model based on n-ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced. In Section 2, certain operations on relations (other than logical inference) are discussed and applied to the problems of redundancy and consistency in the user's model.

E. F. Codd

Recent Issues

Explore the Issue Archive