图文法综述  

Survey of Graph Grammars

作　　者：韩秀清[1] 曾晓勤[1] 邹阳[1] 张康[2] 

机构地区：[1]河海大学计算机与信息工程学院,南京210098 [2]德克萨斯大学达拉斯分校计算机科学系,德克萨斯750803021

出　　处：《计算机科学》2008年第8期10-16,共7页Computer Science

基　　金：国家自然科学基金(60571048;60673186)的资助

摘　　要：形式语言理论对计算机科学的发展起了重大的作用,作为对传统字符文法扩展的图文法的形式化研究,其重要意义是不言而喻的。本文在概述图文法的产生、发展和现状的基础上,着重介绍了从一维字符文法扩展到二维图文法所出现的新问题,以及在形式化处理上引出的新方法,其中最主要的是嵌入问题的解决、文法类型的划分和成员问题的判定。文中以目前较为流行的图文法为例,特别是一些典型的上下文无关和上下文相关的图文法,对上述的问题进行了深入的讨论,指出了现有方法中的一些不足之处,并展望了图文法今后值得研究的问题和方向。It is well known that formal language theory plays an important role in the aevelopment of computer science,and so will be the research on two dimensional graph grammar formalisms, which is an extension of one dimensional string grammars. Based on a summary of the generation, development and current status of graph grammars, this paper mainly introduces the newly emerging problems caused by the dimension extension and some new approaches, such as the solution to embedding problem, the classification of graph grammars and the decidability of membership problem. By taking some popular graph grammars as examples, especially some typical contex-free and context-sensitive graph grammars, the paper discusses their approaches for solving the above mentioned problems, their shortcomings and unsolved research problems and future directions.

关 键 词：形式语言 图文法 嵌入问题 文法类型 成员问题 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论] TN912.34[自动化与计算机技术—计算机科学与技术]