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

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

Grid Automata and Grid Grammars for Picture Languages

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.