###
Journal of Software:2012.23(7):1635-1655

上下文相关图文法的表达能力分析
邹阳,吕建,曹春,胡昊,宋巍,杨启亮
(计算机软件新技术国家重点实验室(南京大学),江苏 南京 210093;河海大学 计算机与信息学院,江苏 南京 210098;计算机软件新技术国家重点实验室(南京大学),江苏 南京 210093;解放军理工大学 工程兵工程学院,江苏 南京 210007)
On the Expressiveness of Context-Sensitive Graph Grammars
ZOU Yang,Lü Jian,CAO Chun,HU Hao,SONG Wei,YANG Qi-Liang
(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210093, China;Computer and Information College, Hohai University, Nanjing 210098, China;State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210093, China;Engineering Institute of Corps of Engineers, PLA University of Science and Technology, Nanjing 210007, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3448   Download 3493
Received:June 26, 2010    Revised:March 29, 2011
> 中文摘要: 上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.
Abstract:Context-Sensitive graph grammars are formal tools used for specifying visual languages. In order to intuitively describe and parse visual languages, current research has stressed the formalisms and algorithms of graph grammars, but has neglected the comparison of their expressiveness. Based on the analysis and induction of the key characteristics of context-sensitive graph grammar, the relationships between their expressiveness are uncovered and proved in this paper by constructing formalism-transforming algorithms. Moreover, the proposed algorithms correlate with these formalisms; thus, facilitating the usage of context-sensitive graph grammars, as alternative formalisms rather than merely one can be chosen to separately specify and parse visual objects in applications.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61021062, 61170089, 61003019); 国家重点基础研究发展计划(973)(2009CB320702); 核高基重大专项(2009ZX01043-001-06); 河海大学中央高校基本科研业务费(2009B21914) 国家自然科学基金(61021062, 61170089, 61003019); 国家重点基础研究发展计划(973)(2009CB320702); 核高基重大专项(2009ZX01043-001-06); 河海大学中央高校基本科研业务费(2009B21914)
Foundation items:
Reference text:

邹阳,吕建,曹春,胡昊,宋巍,杨启亮.上下文相关图文法的表达能力分析.软件学报,2012,23(7):1635-1655

ZOU Yang,Lü Jian,CAO Chun,HU Hao,SONG Wei,YANG Qi-Liang.On the Expressiveness of Context-Sensitive Graph Grammars.Journal of Software,2012,23(7):1635-1655