January 1969 - Vol. 12 No. 1
Features
Computers in group theory: a survey
Computers are being applied to an increasingly diverse range of problems in group theory. The most important areas of application at present are coset enumeration, sub-group lattices, automorphism groups of finite groups, character tables, and commutator calculus. Group theory programs range from simple combinatorial or numerical programs to large symbol manipulation systems. In this survey the more important algorithms in use are described and contrasted, and results which have been obtained using existing programs are indicated. An extensive bibliography is included.
Methods of analyzing the control flow and data flow of programs during compilation are applied to transforming the program to improve object time efficiency. Dominance relationships, indicating which statements are necessarily executed before others, are used to do global common expression elimination and loop identification. Implementation of these and other optimizations in OS/360 FORTRAN H are described.
Computing polynomial resultants: Bezout's determinant vs. Collins' reduced P.R.S. algorithm
Algorithms for computing the resultant of two polynomials in several variables, a key repetitive step of computation in solving systems of polynomial equations by elimination, are studied. Determining the best algorithm for computer implementation depends upon the extent to which extraneous factors are introduced, the extent of propagation of errors caused by truncation of real coeffcients, memory requirements, and computing speed. Preliminary considerations narrow the choice of the best algorithm to Bezout's determinant and Collins' reduced polynomial remainder sequence (p.r.s.) algorithm. Detailed tests performed on sample problems conclusively show that Bezout's determinant is superior in all respects except for univariate polynomials, in which case Collins' reduced p.r.s. algorithm is somewhat faster. In particular Bezout's determinant proves to be strikingly superior in numerical accuracy, displaying excellent stability with regard to round-off errors. Results of tests are reported in detail.
The role of programming in a Ph.D. computer science program
In this general paper the role of programming in advanced graduate training is discussed. Subject matter related to programming as well as programming per se is considered. The importance and application of formalism are considered and also the need for good empirical experimentation. A brief outline for a sequence of courses is included, and subject headings that have been obtained from an extensive bibliography are given. A bibliography of programming references is included.
Directed random generation of sentences
The problem of producing sentences of a transformational grammar by using a random generator to create phrase structure trees for input to the lexical insertion and transformational phases is discussed. A purely random generator will produce base trees which will be blocked by the transformations, and which are frequently too long to be of practical interest. A solution is offered in the form of a computer program which allows the user to constrain and direct the generation by the simple but powerful device of restricted subtrees. The program is a directed random generator which accepts as input a subtree with restrictions and produces around it a tree which satisfies the restrictions and is ready for the next phase of the grammar. The underlying linguistic model is that of Noam Chomsky, as presented in Aspects of the Theory of Syntax. The program is written in FORTRAN IV for the IBM 360/67 and is part of a unified computer system for transformational grammar. It is currently being used with several partial grammars of English.
Some criteria for time-sharing system performance
Time-sharing systems, as defined in this article, are those multiaccess systems which permit a terminal user to utilize essentially the full resources of the system while sharing its time with other terminal users. It is each terminal user's ability to utilize the full resources of the system that makes quantitative evaluation of time-sharing systems particularly difficult. Six criteria are described which have been successfully used to perform first-level quantitative time-sharing system performance evaluation.
