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

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