Parallel Sequential Array Acceptors with Restricted Neighborhood

近傍制限直並列アレイアクセプタ

Parallel Sequential Array Acceptors with Restricted Neighborhood

Creators Saitoh Osamu

Creators Taniguchi Hiroshi

Creators Inoue Katsushi

Creators Takanami Itsuo

This paper investigates some properties of Parallel Sequential Array Acceptors with Restricted Neighborhood (RPSA's). An RPSA is a Parallel Sequential Array Acceptor (PSA) with the restriction that the neighborhood template of each cell except the first cell is {0,1}. This paper first investigates the relationships of accepting powers between RPSA's and PSA's, and also investigates the difference between the accepting powers of one-way and two-way RPSA's, and the difference between the accepting powers of deterministic and nondeterministic RPSA's. This paper then investigates closure properties of the classes of sets accepted by one-way RPSA's under several operations.

[ISSN]0372-7661

[NCID]AN00244228