A Systematic Study on Pattern Generative Grammars and Pattern Recognition Algorithms

在这项研究中，我们介绍了几种生成文法，它们都是A.Rosenfeld提出的等距数组文法(简称IAG)的子类，并考察了它们的模式生成能力。在IAG中，重写规则的左侧和右侧被要求等距(即具有相同的形状)，以避免在生成的图案中发生剪切。引入空白符号(#)以保持等轴测的限制。众所周知，单调数组语法(MAG)、上下文无关数组语法(CFAG)和规则数组语法(RAG)在IAG中形成了类似乔姆斯基的层次结构。本研究的主要结果如下：(1)RAG是该体系中最低的子类，具有非常简单的重写规则。我们证明了RAGS可以感知一种语境，并且可以利用#-感知能力生成一些上下文需要的模式集，尽管形式很简单。(2)我们提出了几种RAG-like文法，作为一类增加了对RAGS的非#-符号感知能力的文法。我们证明了这些类的生成能力比碎布类的生成能力更强大。(3)提出了MAG的子类--两种三向文法，并证明了它们的模式生成能力可以用几种二维三向图灵机来精确刻画。(4)我们提出了几种由IAG对组成的文法，称为UP文法。例如，我们证明了存在一组模式，它是由结合了两个RAG而不是CFAG的堆积语法生成的。

In this study, we have introduced some kinds of generative grammars, all of which are subclasses of isometric array grammar (IAG, for short) introduced by A. Rosenfeld, and investigated their generating powers of patterns. In IAG, left-hand and right-hand sides of rewriting rules are required to be isometric (i. e, having the same shape) to avoid the shearing in a generated pattern. A blank symbol (#) is introduced to keep the restriction of isometric. It is well known that a monotonic array grammar (MAG), a context-free array grammar (CFAG) and a regular array grammar (RAG) form a Chomsky-like hierarchy in IAG. Main results of this study are as follows ;(1) RAGs, which are the lowest subclass of that hierarchy, have rewriting rules of a very simple form. We showed that RAGs can sense a kind of context, and can generate some sets of context-needing patterns by using #-sensing ability, in spite of the simplicity of the form.(2) We have proposed some kinds of RAG-like grammars, as classes of grammars adding a ability of sensing non #-symbols to RAGs. We showed that the generating powers of these classes are properly more powerful than ones of RAGs. This results shows us that a non #-sensing ability is necessary for RAGs to generate complex patterns.(3) We have proposed two-kinds of three-way grammars which are subclasses of MAG, and showed that their generating powers of patterns are precisely characterized by some kinds of two-dimensional three-way Turing machines.(4) We have proposed some kinds of grammars, called up grammars, which consist of couples of IAGs. We showed, for example, that there exists a set of patterns which is generated by a piled up grammar coupled two RAGs but not a CFAG.