| 本文已被：浏览 5235次 下载 7459次 |
码上扫一扫！ |
|
|
| 上下文相关图文法的表达能力分析 |
|
邹阳1,2, 吕建1, 曹春1, 胡昊1, 宋巍1, 杨启亮1,3
|
|
1.计算机软件新技术国家重点实验室(南京大学),江苏 南京 210093;2.河海大学 计算机与信息学院,江苏 南京 210098;3.解放军理工大学 工程兵工程学院,江苏 南京 210007
|
|
| 摘要: |
| 上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性. |
| 关键词: 可视化语言 上下文相关 图文法 表达能力 转换算法 |
| DOI：10.3724/SP.J.1001.2012.04085 |
| 分类号: |
| 基金项目:国家自然科学基金(61021062, 61170089, 61003019); 国家重点基础研究发展计划(973)(2009CB320702); 核高基重大专项(2009ZX01043-001-06); 河海大学中央高校基本科研业务费(2009B21914) |
|
| On the Expressiveness of Context-Sensitive Graph Grammars |
|
ZOU Yang1,2, Lü Jian1, CAO Chun1, HU Hao1, SONG Wei1, YANG Qi-Liang1,3
|
|
1.State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210093, China;2.Computer and Information College, Hohai University, Nanjing 210098, China;3.Engineering Institute of Corps of Engineers, PLA University of Science and Technology, Nanjing 210007, China
|
| 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. |
| Key words: visual language context-sensitive graph grammar expressiveness transforming algorithm |
