No abstract available.

Over the past several years a great deal has been written, and even more said, regarding the crisis in employment of faculty in computer science departments (1,2,3,4,5). In order to obtain data regarding the magnitude of the problem, and reasons for it, the National Science Foundation, in the 1980-81 academic year conducted a survey of Ph.D. granting departments of computer science in the United States. This paper will present a summary of the results of the survey. Data obtained regarding the departments were consistent with that reported earlier by Hamblen (6,7), and Taulbee and Conte (8). Results of the survey regarding motivation for professional mobility were consistent with those reported by Eisenberg and Galanti (9) regarding the engineering disciplines.

Abstract A graph is quasiprime with respect to a boolean product of graphs if whenever it is a subgraph of the product of two graphs, it must necessarily be isomorphic to a subgraph of one of its factors. This paper provides a characterization of graphs quasi‐prime with respect to cartesian product, as well as graphs quasiprime with respect to other products.

Abstract This work extends the results of M. Rosenfeld [6] on universal graphs with respect to the strong graph product. By using a generalized measure of independence, one can get improved bounds on the growth of the maximum independent set size under this graph product. Furthermore, a necessary and sufficient condition is derived for when the maximum independent set of the product graph is strictly greater than the product of the maximum independent sets.

This panel will discuss the various programs of the National Science Foundation dealing with Computer Science Education and Research. These include programs on basic research in computer science, research in computer science education and various programs designed to increase the quality of science education, especially where computers can plan a significant role in the educational process.

In this paper we discuss a survey recently completed of graduates of Penn State who earned the M.S. in Computer Science degree. The purpose of this survey was to permit an evaluation of the effectiveness of the curriculum in preparing students to meet the job requirements of their employers. Of equal importance was the former student's evaluation of the program after having had a period in which to reflect. In this paper we report some of the more important findings of the survey.

In this paper by tracing the history of the programs and outlining the programs themselves, a comparison will be made of the factors that lead to the creation and development of a computer science program in a large state university and in a small liberal arts college. In the first case the program leads to a baccalaureate degree in computer science. In the second it is a branch of the mathematics curriculum.

This correspondence presents an example of a two-way automaton which has significantly fewer states than any one-way automaton accepting the same set of tapes. Thus, in this particular case, memory space can be saved by using a two-way automaton. This savings in space, however, is accompanied by an increase in recognition time.

If, in a sequential machine, the output upon application of an input character depends only upon the current state of the machine and not upon the input character, the machine is called input-independent. Two states, p and q, of an input-independent machine are compatible if and only if the output strings from the machine starting in initial state, p , are the same as the output strings from the machine with initial state, q , for all input strings to the machine in both states. The minimal length of tape which tests compatibility of states in an input-independent sequential machine with n states is ( n 2 - 2 n )/4 + 1 if n is even, and ( n 2 - 2 n + 1)/4 if n is odd. There are machines with incompatible states such that no tapes of length less than the given bounds will detect the incompatibility.

An investigation is presented which continues the work of Fleck and Weeg concerning the relationships between the equivalence classes of inputs and the group of automorphisms of a finite automaton.The principal result is that if for each state of a strongly connected automaton there exists a subset of the set of equiwfience classes of the input semigroup which constitute t~ group, then this group is isomorphic to a group of automorphisms of the automaton.The relationship between subautomata and subgroups of the group of autoraorphisms is also studied.