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

doi:10.11772/j.issn.1001-9081.2014.11.3180

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (11): 3180-3183.DOI: 10.11772/j.issn.1001-9081.2014.11.3180

Previous Articles Next Articles

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

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

王毅,丁函

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

通讯作者: 王毅
作者简介:王毅(1980-),男,湖北襄阳人,讲师,博士研究生,主要研究方向:软件可视化、图文法;丁函(1980-),女,湖北随州人,讲师,硕士,主要研究方向:图文法、逻辑程序设计。
基金资助:
湖北省教育厅科学研究计划资助项目

Abstract

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.

摘要：

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

CLC Number:

TP391.4

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	. Pavement defect detection algorithm with enhanced morphological perception [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	YANG Jianfeng, CHEN Bin, LI Yuxuan. Self-supervised point cloud anomaly detection method based on point cloud reconstruction [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	. Binocular vision object location algorithm for robot arm grasping [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Multi-attention contrastive learning for infrared small target detection [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	LI Zhonghua, ZHONG Gengxin, FAN Ping, ZHU Hengliang. Camouflaged object detection by boundary mining and background guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	. Multi-view difficult airway recognition based on discriminant region guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	. Privacy preserving localization of surveillance images based on large vision models [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	. Data augmentation method for abnormal passenger behavior in elevators based on dynamic graph convolutional network [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Text-based person retrieval method based on multi-granularity shared semantic center association [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Distribution adaptation and dynamic curriculum pseudo-labeling framework for semi-supervised fire detection [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Image Caption Method Based on Swin-Transformer and Multi-Scale Feature Fusion [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	Wei XIONG, Yibo CHEN, Lizhen ZHANG, Qian YANG, Qin ZOU. Self-supervised monocular depth estimation using multi-frame sequence images [J]. Journal of Computer Applications, 2024, 44(12): 3907-3914.
[13]	Keyi FU, Gaocai WANG, Man WU. Few-shot object detection method based on improved region proposal network and feature aggregation [J]. Journal of Computer Applications, 2024, 44(12): 3790-3797.
[14]	Chenghao YANG, Jie HU, Hongjun WANG, Bo PENG. Incomplete multi-view clustering algorithm based on attention mechanism [J]. Journal of Computer Applications, 2024, 44(12): 3784-3789.
[15]	Peng FANG, Fan ZHAO, Baoquan WANG, Yi WANG, Tonghai JIANG. Development， technologies and applications of blockchain 3.0 [J]. Journal of Computer Applications, 2024, 44(12): 3647-3657.