权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

A Systematic Study on Pattern Generative Grammars and Pattern Recognition Algorithms

模式生成语法和模式识别算法的系统研究

基本信息

批准号：
01470144
负责人：
TANIGUCHI Hiroshi
金额：
$ 2.3万
依托单位：
Tottori University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (B)
财政年份：
1989
资助国家：
日本
起止时间：
1989 至 1990
项目状态：
已结题

项目摘要

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.

在本研究中，我们介绍了几种生成文法，它们都是由A。罗森菲尔德，并调查了他们的模式生成能力。在IAG中，重写规则的左手边和右手边被要求是等距的（即。即，具有相同的形状），以避免在生成的图案中的剪切。引入了一个空符号（#）来保持等距约束。众所周知，单调数组文法（MAG）、上下文无关数组文法（CFAG）和正则数组文法（RAG）构成了IAG中的Chomsky类层次结构。本研究的主要结果如下：（1）RAG是该层次的最低子类，具有非常简单的重写规则。我们发现，RAGs可以感觉到一种上下文，并可以产生一些集的上下文需要模式，通过使用#-感知能力，尽管形式的简单。(2)我们已经提出了几种RAG类文法，作为一类文法增加了感知非#-符号的RAG的能力。我们发现，这些类的生成能力比RAG的生成能力更强大。这一结果向我们表明，非#感测能力是RAG产生复杂图案所必需的。(3)我们提出了MAG的两类三向文法，并证明了它们的模式生成能力是由某种二维三向图灵机精确刻画的. (4)我们提出了一些类型的文法，称为文法，它们由几个IAG组成。例如，我们证明了存在一组模式，该模式是由叠加的语法耦合两个RAG而不是CFAG生成的。