上下文相关图文法的表达能力分析  

On the Expressiveness of Context-Sensitive Graph Grammars

作　　者：邹阳[1,2] 吕建[1] 曹春[1] 胡昊[1] 宋巍[1] 杨启亮[1,3] 

机构地区：[1]计算机软件新技术国家重点实验室(南京大学),江苏南京210093 [2]河海大学计算机与信息学院,江苏南京210098 [3]解放军理工大学工程兵工程学院,江苏南京210007

出　　处：《软件学报》2012年第7期1635-1655,共21页Journal of Software

基　　金：国家自然科学基金(61021062;61170089;61003019);国家重点基础研究发展计划(973)(2009CB320702);核高基重大专项(2009ZX01043-001-06);河海大学中央高校基本科研业务费(2009B21914)

摘　　要：上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.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.

关 键 词：可视化语言 上下文相关 图文法 表达能力 转换算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]