基于边的图文法产生式选择无关条件的判断

doi:10.11772/j.issn.1001-9081.2014.11.3180

计算机应用 ›› 2014, Vol. 34 ›› Issue (11): 3180-3183.DOI: 10.11772/j.issn.1001-9081.2014.11.3180

• 2014年全国开放式分布与并行计算学术年会(DPCS 2014)论文 • 上一篇下一篇

基于边的图文法产生式选择无关条件的判断

王毅,丁函

湖北文理学院数学与计算机科学学院,湖北襄阳 441053

收稿日期:2014-07-25 修回日期:2014-08-08 发布日期:2014-12-01 出版日期:2014-11-01
通讯作者: 王毅
作者简介:王毅(1980-),男,湖北襄阳人,讲师,博士研究生,主要研究方向:软件可视化、图文法;丁函(1980-),女,湖北随州人,讲师,硕士,主要研究方向:图文法、逻辑程序设计。
基金资助:
湖北省教育厅科学研究计划资助项目

Selection-free judgment for productions based on edge-based context-sensitive graph grammar

WANG Yi,DING Han

School of Mathematical and Computer Science, Hubei University of Arts and Science, Xiangyang Hubei 441053, China

Received:2014-07-25 Revised:2014-08-08 Online:2014-12-01 Published:2014-11-01
Contact: WANG Yi

摘要/Abstract

摘要：

为了降低归约算法的时间复杂度,在基于边的上下文相关图文法(EGG)形式化的基础上,通过对产生式形式的适当约束,提出了EGG的产生式选择无关条件的判断方法。通过此方法可有效判断EGG产生式的选择无关性。对于选择无关的产生式,由于归约过程中产生式的使用顺序不会影响归约的结果,从而避免了回溯,能够有效地降低归约算法的时间复杂度。

Abstract:

In order to reduce the time complexity of parsing algorithm, based on the Edge-based context-sensitive Graph Grammar (EGG), a selection-free judgment method was proposed for the productions of EGG with appropriate constraints. This method can effectively judge the selection independence of the productions of EGG. For the selection-free productions, using the order of the productions will not affect the result of the parsing, thus the parsing process can avoid backtracking and the time complexity of the parsing algorithm can be effectively reduced.

中图分类号:

TP391.4

王毅丁函. 基于边的图文法产生式选择无关条件的判断[J]. 计算机应用, 2014, 34(11): 3180-3183.

WANG Yi DING Han. Selection-free judgment for productions based on edge-based context-sensitive graph grammar[J]. Journal of Computer Applications, 2014, 34(11): 3180-3183.

参考文献

[1]PFALTZ J, ROSENFELD A. Web grammars[EB/OL]. [2010-10-10]. http://ijcai.org/Past%20Proceedings/IJCAI-69/PDF/054.pdf.
[2]ECONOMAKOS G, PAPAKONSTANTINOU G, TSANAKAS P. An attribute grammar approach to high-level automated hardware synthesis[J]. Information and Software Technology, 1995, 37(9): 493-502.
[3]COURCELLE B. An axiomatic definition of context-free rewriting and its application to NLC graph grammars[J]. Theoretical Computer Science, 1987, 55(2/3): 141-181.
[4]ADACHI Y, KOBAYASHI S, TSUCHIDA K, et al. An NCE context-sensitive graph grammar for visual design languages[C]// Proceedings of the 1999 IEEE Symposium on Visual Languages. Piscataway: IEEE Press, 1999: 228-235.
[5]JANSSENS D, ROZENBERG G. Graph grammars with neighbourhood-controlled embedding[J]. Theoretical Computer Science, 1982, 21(1): 55-74.
[6]Le METAYER D Describing software architecture styles using graph grammars[J]. IEEE Transactions on Software Engineering, 1997, 24(7): 521-533.
[7]ZHAO C, KONG J, DONG J, et al. Pattern based design evolution using graph transformation[J]. Journal of Visual Languages and Computing, 2007, 18(4): 378-398.
[8]DONG J, YANG S, ZHANG K. Visualizing design patterns in their applications and compositions[J]. IEEE Transactions on Software Engineering, 2007, 33(7):433-453.
[9]FLASINSKI M. Power properties of NLC graph grammars with a polynomial membership problem[J]. Theoretical Computer Science, 1998, 201(1/2): 189-231.
[10]MARRIOTT K. Constraint multiset grammar[C]// Proceedings of the 1994 IEEE Symposium on Visual Languages. Piscataway: IEEE Press, 1994: 118-125.
[11]GOLIN E J. A method for the specification and parsing of visual language [D]. Providence: Brown University, 1991.〖HJ1.73mm〗
[12]REKERS J, SCHRR A. Defining and parsing visual languages with layered graph grammars[J]. Journal of Visual Languages and Computing, 1997, 8(1): 27-55.
[13]ZHANG D, ZHANG K, CAO J. A context-sensitive graph grammar formalism for the specification of visual languages[J]. The Computer Journal, 2001, 44(3): 186-200.
[14]KONG J, ZHANG K, ZENG X. Spatial graph grammars for graphical user interfaces[J]. ACM Transactions on Computer-Human Interaction, 2006, 13(2):268-307.
[15]ZENG X, HAN X, ZOU Y. An edge-based context-sensitive graph grammar formalism[J]. Journal of Software, 2008,19(8):1893-1901.(曾晓勤,韩秀清,邹阳.一种基于边的上下文相关图文法形式化框架[J]. 软件学报, 2008,19(8): 1893-1901.)

基于边的图文法产生式选择无关条件的判断

Selection-free judgment for productions based on edge-based context-sensitive graph grammar

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张佳慧李晓明张嘉祥. 强化形态感知的路面缺陷检测算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	杨建锋陈斌李雨轩. 基于点云重构的自监督点云异常检测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	蒋畅江向杰何旭颖. 面向机械臂抓取的双目视觉目标定位算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	边小勇胡其仁袁培洋. 多注意力对比学习的红外小目标检测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	李钟华钟庚辛范萍朱恒亮. 通过边界挖掘和背景引导的伪装目标检测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[6]	吴松霖张广朝姚远彭博. 基于判别区域引导的多视图困难气道识别[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	李强白少雄熊源袁薇. 基于视觉大模型隐私保护的监控图像定位[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	况世雄姚俊波陆佳炜王琪冰肖刚. 基于动态图卷积网络的电梯乘客异常行为数据增强方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	康斌陈斌王俊杰李昱林赵军智咸伟志. 基于多粒度共享语义中心关联的文本到人物检索方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	王磊胡节彭博. 用于半监督火灾检测的分布自适应和动态课程伪标签框架[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	王子怡李卫军刘雪洋丁建平刘世侠苏易礌. 基于Swin Transformer与多尺度特征融合的图像描述方法#br# [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	熊炜, 陈奕博, 张丽真, 杨茜, 邹勤. 利用多帧序列影像的自监督单目深度估计[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3907-3914.
[13]	付可意, 王高才, 邬满. 基于改进区域提议网络和特征聚合小样本目标检测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3790-3797.
[14]	杨成昊, 胡节, 王红军, 彭博. 基于注意力机制的不完备多视图聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3784-3789.
[15]	方鹏, 赵凡, 王保全, 王轶, 蒋同海. 区块链3.0的发展、技术与应用[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3647-3657.