%0 Journal Article
%T Grid Automata and Grid Grammars for Picture Languages<br>处理图像语言的格点自动机与格点文法
%A SHEN En-shao
%A <br>沈恩绍
%J 软件学报
%D 2000
%I 
%X 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.
%K Formal language
%K picture language
%K grammar
%K automata
%K restricted second-order logic<br>形式语言，图像语言，自动机，文法，约束型二阶逻辑.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=38DF8B8B03F28752&yid=9806D0D4EAA9BED3&vid=708DD6B15D2464E8&iid=DF92D298D3FF1E6E&sid=1F8584045E0BED57&eid=750AE535ABE3D62A&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=17