###
DOI:
Journal of Software:2000.11(7):871-880

处理图像语言的格点自动机与格点文法
沈恩绍
(上海交通大学计算机科学与工程系,上海,200030)
Grid Automata and Grid Grammars for Picture Languages
SHEN En-shao
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2631   Download 2950
Received:September 17, 1998    Revised:June 22, 1999
> 中文摘要: Giammarresi与Restivo在一篇综述中总结出一个关于可识别的图像语言(即2维矩形语言)REC的等价性定理.对比1维字语言的相应结果,其中还缺少关于生成文法的相应一环.提出了一种(矩形的)格点文法,正好弥补了这一缺环.而取代2维on-line tesselation自动机,引入了格点自动机的概念.一方面,它与经典的2元树型自动机更相似,另一方面,它也是格点文法与等价性定理中关于REC的其他描述方式之间的一座桥梁.同时,标准的existential monadic二阶逻辑也被一种更弱的规范框架——positive monadic分划逻辑所取代.由此导出一个新的更完整的关于REC的等价性定理.
Abstract:A two-dimensional grid grammar was designed to fill up the missing ring in the Equivalence Theorem for recognizable picture languages (REC), summarized in a survey paper by Giammarresi and Restivo. Instead of 2-dimensional on-line tessellation automata, grid automata were introduced, which were closer to the traditional binary tree automata, to bridge the grid grammar and other approaches of describing the class of REC. Meanwhile the standard (existential) monadic second order logic was substituted by a weaker logic framework: positive monadic partition logic. A new and complete version of Equivalence Theorem for REC is presented.
文章编号:     中图分类号:    文献标志码:
基金项目:This research is supported by the National Natural Science Foundation of China(国家自然科学基金,No.69673009) This research is supported by the National Natural Science Foundation of China(国家自然科学基金,No.69673009)
Foundation items:
Reference text:

沈恩绍.处理图像语言的格点自动机与格点文法.软件学报,2000,11(7):871-880

SHEN En-shao.Grid Automata and Grid Grammars for Picture Languages.Journal of Software,2000,11(7):871-880