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

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-11-01 发布日期:2014-12-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-11-01 Published:2014-12-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]	罗圣钦陈金怡李洪均. 基于注意力机制的多尺度残差UNet实现乳腺癌灶分割[J]. 计算机应用, 0, (): 0-0.
[2]	杨鼎康黄帅王顺利翟鹏李一丹张立华. 基于对抗生成网络和网络集成的面部表情识别方法EE-GAN[J]. 计算机应用, 0, (): 0-0.
[3]	秦庭威赵鹏程秦品乐曾建朝柴锐黄永琦. 基于残差注意力机制的点云配准算法[J]. 计算机应用, 0, (): 0-0.
[4]	鲁永帅唐英杰马鑫然. 基于深度特征融合的无纺布低对比度浆丝缺陷检测方法[J]. 计算机应用, 0, (): 0-0.
[5]	裴仪瑶, 郭会明, 张丹普, 陈文博. 基于定位不确定性的鲁棒3D目标检测方法[J]. 计算机应用, 2021, 41(10): 2979-2984.
[6]	许学斌, 张佳达, 刘伟, 路龙宾, 赵雨晴. 融合空间和通道特征的高精度乳腺癌分类方法[J]. 计算机应用, 2021, 41(10): 3025-3032.
[7]	汪虹余, 张彧, 杨恒, 穆楠. 基于蚁群优化算法的弱光图像显著性目标检测[J]. 计算机应用, 2021, 41(10): 2970-2978.
[8]	魏淳武, 赵涓涓, 唐笑先, 强彦. 基于多时期蒸馏网络的随访数据知识提取方法[J]. 计算机应用, 2021, 41(10): 2871-2878.
[9]	韩建栋, 李晓宇. 基于多尺度特征融合的行人重识别方法[J]. 计算机应用, 2021, 41(10): 2991-2996.
[10]	张凯悦, 张鸿. 基于注意力机制网络的航运监控图像识别模型[J]. 计算机应用, 2021, 41(10): 3010-3016.
[11]	李自强, 王正勇, 陈洪刚, 李林怡, 何小海. 基于外观和动作特征双预测模型的视频异常行为检测[J]. 计算机应用, 2021, 41(10): 2997-3003.
[12]	高世伟, 张长柱, 王祝萍. 基于可分离金字塔的轻量级实时语义分割算法[J]. 计算机应用, 2021, 41(10): 2937-2944.
[13]	卓禹心, 韩素雅, 张榆锋, 李支尧, 董毅峰. 基于超声谐波包络Nakagami参数图像的微波消融区域自动分割方法[J]. 计算机应用, 2021, 41(10): 3089-3096.
[14]	李敬虎邢前国郑向阳李琳王丽丽. 基于深度学习的无人机影像夜光藻赤潮提取方法[J]. 计算机应用, 0, (): 0-0.
[15]	任炜白鹤翔. 基于全局与局部的多标签图像分类方法[J]. 计算机应用, 0, (): 0-0.