{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T12:37:56Z","timestamp":1648643876060},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[1999,6]]},"abstract":"<jats:p> 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 of RPCAAGs is characterized by two-dimensional 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. <\/jats:p>","DOI":"10.1142\/s0218001499000318","type":"journal-article","created":{"date-parts":[[2003,4,24]],"date-time":"2003-04-24T01:59:35Z","timestamp":1051149575000},"page":"523-538","source":"Crossref","is-referenced-by-count":3,"title":["CHARACTERIZING THE ABILITY OF PARALLEL ARRAY GENERATORS ON REVERSIBLE PARTITIONED CELLULAR AUTOMATA"],"prefix":"10.1142","volume":"13","author":[{"given":"KENICHI","family":"MORITA","sequence":"first","affiliation":[{"name":"Faculty of Engineering, Hiroshima University, Higashi-Hiroshima 739-8527, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SATOSHI","family":"UENO","sequence":"additional","affiliation":[{"name":"Tohoku Seiki Industries, Yamagata 990-2251, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KATSUNOBU","family":"IMAI","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Hiroshima University, Higashi-Hiroshima 739-8527, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(78)80022-7"},{"key":"p_2","first-page":"758","volume":"72","author":"Morita K.","year":"1989","journal-title":"Trans. IEICE"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001494000280"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050091"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001489000243"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(72)80019-4"},{"key":"p_8","author":"Morita Y. Y","journal-title":"Int. J. Pattern Recognition"}],"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001499000318","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:12:24Z","timestamp":1565143944000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001499000318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,6]]},"references-count":7,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1999,6]]}},"alternative-id":["10.1142\/S0218001499000318"],"URL":"https:\/\/doi.org\/10.1142\/s0218001499000318","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,6]]}}}