CHARACTERIZING THE ABILITY OF PARALLEL ARRAY GENERATORS ON REVERSIBLE PARTITIONED CELLULAR AUTOMATA

摘要

A PCAAG introduced by Morita and Ueno is a parallel array generator on a partitioned cellular automaton (PCA)that generates an array language (i.e. a set of symbol arrays). A "reversible" PCAAG (RPCAAG) is a backward deterministic PCAAG, and thus, parsing of two-dimensional patterns can be performed without backtracking by an "inverse" system of the RPCAAG. Hence, a parallel pattern recognition mechanism on a deterministic cellular automaton can be directly obtained from a RPCAAG that generates the pattern set. In this paper, we investigate the generating ability of RPCAAGs and their subclass. It is shown that the ability fo RPCAAGs is characterized by two-dimensioanl deterministic Turing machines, i.e. they are universal in their generating ability. We then investigate a monotonic RPCAAG (MRPCAAG), which is a special type of an RPCAAG that satisfies monotonic constraint. We show that the generating ability of MRPCAAGs is exactly characterized by two-dimensional deterministic linear-bounded automata.