处理图像语言的格点自动机与格点文法

• 作者: 沈恩绍
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 形式语言 图像语言 自动机 文法 约束型二阶逻辑
• 年，卷（期）: 2000,（7）
• 页码范围: 871-880
• 页数: 10页
• 分类号: TP301
• 字数: 3520字
• 语种: 中文

摘要

Giammarresi与Restivo在一篇综述中总结出一个关于可识别的图像语言(即2维矩形语言)REC的等价性定理.对比1维字语言的相应结果,其中还缺少关于生成文法的相应一环.提出了一种(矩形的)格点文法,正好弥补了这一缺环.而取代2维on-line tesselation自动机,引入了格点自动机的概念.一方面,它与经典的2元树型自动机更相似,另一方面,它也是格点文法与等价性定理中关于REC的其他描述方式之间的一座桥梁.同时,标准的existential monadic二阶逻辑也被一种更弱的规范框架--positive monadic分划逻辑所取代.由此导出一个新的更完整的关于REC的等价性定理.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈恩绍	上海交通大学计算机科学与工程系	2	15	1.0	2.0