文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Characterizing the Ability of Parallel Array Generators on Reversible Partitioned Cellular
侵权投诉

Characterizing the Ability of Parallel Array Generators on Reversible Partitioned Cellular

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 t

Proc. of The Fifth International Workshop on Parallel Image Analysis (IWPIA'97) Sept. 29{30, 1997, Hiroshima, Japan

Characterizing the Ability of Parallel Array Generators on Reversible Partitioned Cellular Automata Faculty of Engineering, Hiroshima University, Higashi-Hiroshima 739, Japan morita@ke.sys.hiroshima-u.ac.jp Satoshi Ueno Tohoku Seiki Industries, Yamagata 990-22, Japan Katsunobu Imai Faculty of Engineering, Hiroshima University, Higashi-Hiroshima 739, Japan imai@ke.sys.hiroshima-u.ac.jp 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 satis es monotonic constraint. We show that the generating ability of MRPCAAGs is exactly characterized by two-dimensional deterministic linear-bounded automata.

Kenichi Morita

Abstract

1 Introduction A PCA array generator (called PCAAG) introduced by Morita and Ueno 3] is a parallel generating system of symbol arrays using a nondeterministic partitioned cellular automata (PCA), a kind of CA. It has some similarity with a system of array grammars 1, 5, 6, 7], because, in both systems, symbol arrays are generated from a start symbol by applying rewriting (or transition) rules repeatedly. It is a little di cult to introduce parallelism for a grammar formalism. But, a PCAAG is by nature a parallel system, and thus suited for formulating and studying parallel array generation. Another advantage of a PCAAG is that we can de ne a\reversible" version RPCAAG. Roughly speaking, it is a backward deterministic system. Hence, parsing of an array language (i.e., a set of symbol arrays) can be performed without backtracking using an inverse system of the RPCAAG 3]. Therefore, parallel pattern recognition system on a deterministic CA can be immediately obtained, if the pattern set is described by an RPCAAG. In 3] several examples of RPCAAGs that generate sets of geometrical patterns in parallel were given. In this paper, we characterize the abilities of RPCAAGs in terms of two-dimensional deterministic automata. First, it is shown that RPCAAGs are characterized by two-dimensional deterministic Turing machines. Hence, even if the reversibility constraint is added, they are still universal in their generating ability. We then

investigate a monotonic RPCAAG (MRPCAAG) 3], which is an RPCAAG satisfying monotonic constraint. We prove that MRPCAAGs are exactly characterized by deterministic two-dimensional linear-bounded automata. 144

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email