Writing my first textbook was an eye-opening experience. I had to dig deep. I had ideas I was excited about and found others that were excited about them as well. I also found strong opposition to my approach, which was difficult for publishers to evaluate. My experience raised a number of questions that I have outlined below. These questions range from personnel motivation to future trends in computing. I have gathered a panel of respected authors. I have asked each to respond to some of these questions. Time will also be available for the audience to ask questions and share their own experiences.

No abstract available.

The RAM model of Cook and Reckhow ~s extended to allow parallel recursive calls and the elementary theory of such machines is developed The uniform cost criterion is used The results include proofs of (!) the eqmvalence of nondetermmtsUc and determm~sttc polynomml Ume for such parallel machines and (2) the eqmvalence of polynomml tmae on such parallel machines and polynomml space on ordinary nonparallel RAM's Also included are results showing that parallelism appears to be stnctly more powerful than nondetermmlsm rg~,t WOgDS ANt~ Pm~AsEs parallelism, nondetermm~sm, random access machine, tune, storage CR CATEGORIES 5 23, 5.25, 5 26 IntroductionA machine model called a parallel random access machine (PRAM) is introduced.The model is obtained by extending the RAM model of Cook and Reckhow [3] to allow parallel recursive calls.These PRAM's are then used to develop a theory for the time complexity of parallel algorithms.In this paper the uniform cost criterion [3] is used; that is, in computing running times, we charge a constant amount of time for each memory access.The only arithmetic operations allowed m the model are addition and subtraction.This paper is organized as follows.In Sections 2 and 3 the PRAM model is formally defined and a high level programming language for PRAM's is discussed.In Section 4 it is shown that deterministic and nondeterministic polynomial time are equivalent for PRAM's.The proof is based on the well-known observation that nondeterminism can be viewed as a special form of parallehsm, and so nondeterminism can be simulated by parallelism.Since a nondetermlnistic parallel machine may have many processors making simultaneous, independent nondetermimstic moves, the simulation is, however, more complicated than that of simulating a nondeterministic serial machine by a deterministic parallel machine.Section 4 also includes results showing that parallelism appears to be more powerful than nondeterminism.More specifically, it is shown that, provided they are Permission to copy wRhout fee all or part of this material is granted provided that the copies are not made or d,stnbuted for direct commercial advantage, the ACM copyright notice and the title of the pubhcatlon and ~ts date appear, and notice ~s given that copymg ~s by permtss~on of the AssooaUon for Computing Machinery To copy otherwise, or to repubhsh, requires a fee and/or specific permtsslon Most of these results were presented m [12] and [13] This research was supported, m part, by the National Soence Foundation under Grant MCS-74-02338.

Normal form theorems which factor arbitrary phrase-structure grammars into context-free grammars and “a little more” are presented. Every phrase-structure grammar is proven equivalent to one in which each production is either context-free or pure erasing. A pda-like machine is shown to characterize the phrase-structure languages.

In [2], computations of nondeterministic machines are shown to correspond to threadings of certain mazes. We briefly summarize these results and then obtain some new extentions of them. A new device called a maze-recognizing automaton is introduced. This is a type of finite-state device that crawls through mazes. The following statements are proven equivalent.

Computations of non-deterministic Turing machines are shown to correspond to “solving” certain mazes. The storage needed to “solve” mazes is related to the storage needed to deterministically simulate non-deterministic Turing machines. In particular, it is shown that a non-deterministic L(n)-tape bounded Turing machine can be simulated by an (L(n))2-tape bounded Turing machine, provided L(n)≥log2n.