A Systematic Study on Pattern Generative Grammars and Pattern Recognition Algorithms

点击翻译按钮获取中文摘要

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.