主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
沈恩绍.处理图像语言的格点自动机与格点文法.软件学报,2000,11(7):871-880
处理图像语言的格点自动机与格点文法
Grid Automata and Grid Grammars for Picture Languages
投稿时间:1998-09-17  修订日期:1999-06-22
DOI:
中文关键词:  形式语言,图像语言,自动机,文法,约束型二阶逻辑.
英文关键词:Formal language, picture language, grammar, automata, restricted second-order logic.
基金项目:This research is supported by the National Natural Science Foundation of China(国家自然科学基金,No.69673009)
作者单位
沈恩绍 上海交通大学计算机科学与工程系,上海,200030 
摘要点击次数: 2654
全文下载次数: 2964
中文摘要:
      Giammarresi与Restivo在一篇综述中总结出一个关于可识别的图像语言(即2维矩形语言)REC的等价性定理.对比1维字语言的相应结果,其中还缺少关于生成文法的相应一环.提出了一种(矩形的)格点文法,正好弥补了这一缺环.而取代2维on-line tesselation自动机,引入了格点自动机的概念.一方面,它与经典的2元树型自动机更相似,另一方面,它也是格点文法与等价性定理中关于REC的其他描述方式之间的一座桥梁.同时,标准的existential monadic二阶逻辑也被一种更弱的规范框架——positive monadic分划逻辑所取代.由此导出一个新的更完整的关于REC的等价性定理.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利