Research is in progress along two lines. The first line of research concerns a two-person pebble game model of synchronous parallel computation and some of its applications. This game extends the two- person pebble game defined previously by Dymond and Tompa, and provides a combinatorial framework for the study of issues in parallel computation. The extensions are being used to abstract the control structure of parallel algorithms. This game has motivated the discovery of a key property, semi unboundedness of computations in the parallel complexity class LOGCFL. The second line of research deals with some interesting theoretical questions raised by this property. One of these questions involves a study of Boolean circuit models in which fan-in is considered as a resource in addition to the traditional resources such as size and depth. Among other applications, these models are providing a framework in which to address the question of closure under complementation of complexity classes such as LOGCFL. The P.I. is a 1986 Ph.D whose proposal contains fresh ideas for approaching important questions in the complexity of parallel computation. The proposal and the P.I.'s initial research demonstrate that he knows the appropriate background material and has the capability of successfully attacking the problems proposed.
