微信服务号

微信订阅号

2025-4-24- 9
Home > Archive>Volume 23, Issue 7, 2012 >1635-1655. DOI:10.3724/SP.J.1001.2012.04085
PDF HTML XML Export Cite reminder
On the Expressiveness of Context-Sensitive Graph Grammars
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [26]
    • |
  • Related
    • | | |
  • Comments
    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.

    Reference
    [1] Chang SK. Visual languages: A tutorial and survey. IEEE Software, 1987,4(1):29?39. [doi: 10.1109/MS.1987.229792]
    [2] Crimi C, Guercio A, Nota G, Pacini G, Tortora G, Tucci M. Relation grammars for modelling multi-dimensional structures. In: Proc. of the ’90 IEEE Workshop on Visual Languages. Los Alamitos: IEEE Computer Society Press, 1990. 168?173. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=128400 [doi: 10.1109/WVL.1990.128400]
    [3] Golin EJ, Reiss SP. The specification of visual language syntax. In: Proc. of the ’89 IEEE Workshop on Visual Languages. Washington: IEEE Computer Society Press, 1989. 105?110. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=77050 [doi: 10.1016/S1045-926X(05)80013-8]
    [4] Marriott K. Constraint multiset grammars. In: Proc. of the ’94 IEEE Symp. on Visual Languages. IEEE Computer Society Press, 1994. 118?125. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=363633 [doi: 10.1109/VL.1994.363633]
    [5] Rekers J, Schürr A. A graph based framework for the implementation of visual environments. In: Proc. of the ’96 IEEE Symp. on Visual Languages. Los Alamitos: IEEE Computer Society Press, 1996. 148?155. http://ieeexplore.ieee.org/xpl/articleDetails.jsp? arnumber=545281 [doi: 10.1109/VL.1996.545281]
    [6] Blostein D, Fahmy H, Grbavec A. Practical use of graph rewriting. Technical Report, 1995. 95?373.
    [7] Ehrig H, Engels G, Kreowski HJ, Rozenberg G. Handbook of Graph Grammars and Computing by Graph Transformation, Vol.2: Applications, Languages and Tools. River Edge: World Scientific, 1999.
    [8] Rekers J, Schürr A. Defining and parsing visual languages with layered graph grammars. Journal of Visual Languages and Computing, 1997,8(1):27?55. [doi: 10.1006/jvlc.1996.0027]
    [9] Zhang DQ, Zhang K, Cao JN. A context-sensitive graph grammar formalism for the specification of visual languages. The Computer Journal, 2001,44(3):187?200.
    [10] Zou Y, Zeng XQ, Han XQ, Zhang K. Context-Attributed graph grammar framework for specifying visual languages. Journal of Southeast University (English Edition), 2008,24(4):455?461.
    [11] Zeng XQ, Han XQ, Zou Y. An edge-based context-sensitive graph grammar formalism. Journal of Software, 2008,19(8): 1893?1901 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/1893.htm [doi: 10.3724/SP.J.1001.2008.01893]
    [12] Zhao CY, Kong J, Zhang K. Program behavior discovery and verification: A graph grammar approach. IEEE Trans. on Software Engineering, 2010,36(3):431?448. [doi: 10.1109/TSE.2010.3]
    [13] Kong J, Zhao CY. Visual language techniques for software development. Journal of Software, 2008,19(8):1902?1919 (in English with Chinese abstract). http://www.jos.org.cn/1000-9825/19/1902.htm [doi: 10.3724/SP.J.1001.2008.01902]
    [14] Song GL, Zhang K, Kong J. Model management through graph transformations. In: Bottoni P, Hundhausen C, Levialdi S, Tortora G, eds. Proc. of the 2004 IEEE Int’l Symp. on Visual Languages and Human-Centric Computing. Washington: IEEE Computer Society Press, 2004. 75?82. [doi: 10.1109/VLHCC.2004.37]
    [15] Zhao CY, Kong J, Dong J, Zhang K. Pattern based design evolution using graph transformation. Journal of Visual Languages and Computing, 2007,18(4):378?398. [doi: 10.1016/j.jvlc.2007.07.004]
    [16] Zhang K, Zhang DQ, Deng Y. A visual approach to XML document design and transformation. In: Proc. of the 2001 IEEE Int’l Symp. on Human-Centric Computing Languages and Environments. Washington: IEEE Computer Society Press, 2001. 312?319. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=995279 [doi: 10.1109/HCC.2001.995279]
    [17] Zhang K, Kong J, Qiu MK, Song GL. Multimedia layout adaptation through grammatical specifications. Multimedia Systems, 2005, 10(3):245?260. [doi: 10.1007/s00530-004-0155-2]
    [18] Kong J, Zhang K, Zeng X. Spatial graph grammars for graphical user interfaces. ACM Trans. on Computer-Human Interaction, 2006,13(2):268?307. [doi: 10.1145/1165734.1165739]
    [19] Rekers J, Schürr A. A graph grammar approach to graphical parsing. In: Haarslev V, ed. Proc. of the 11th IEEE Int’l Symp. on Visual Languages. Los Alamitos: IEEE Computer Society Press, 1995. 195?202. [doi: 10.1109/VL.1995.520809]
    [20] Janhunen T. On the intertranslatability of non-monotonic logics. Annals of Mathematics and Artificial Intelligence, 1999,27(1-4): 79?128. [doi: 10.1023/A:1018927416540]
    [21] Gottlob G. Translating default logic into standard autoepistemic logic. Journal of the ACM, 1995,42(4):711?740. [doi: 10.1145/ 210332.210334]
    [22] Imielinski T. Results on translating defaults to circumscription. Artificial Intelligence, 1987,32(1):131?146. [doi: 10.1016/0004- 3702(87)90064-6]
    [23] Bottoni P, Taentzer G, Schürr A. Efficient parsing of visual languages based on critical pair analysis and contextual layered graph transformation. In: Proc. of the 2000 IEEE Int’l Symp. on Visual Languages. Los Alamitos: IEEE Computer Society Press, 2000. 59?60. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=874351 [doi: 10.1109/VL.2000.874351]
    [24] Zou Y, Lü J, Zeng XQ, Ma XX, Yang QL. Constructing confluent context-sensitive graph grammars from non-confluent productions for parsing efficiency. In: Huang ML, Nguyen QV, Zhang K, eds. Proc. of the Visual Information Communication. New York: Springer-Verlag, 2009. 135?147. [doi: 10.1007/978-1-4419-0312-9_8]
    [25] Nagl M. Set theoretic approaches to graph grammars. In: Proc. of the 3rd Int’l Workshop on Graph Grammars and Their Application to Computer Science. LNCS 291, Berlin: Springer-Verlag, 1986. 41?54. http://www.springerlink.com/content/ ph04315m5r25w160/ [doi: 10.1007/3-540-18771-5_43]
    [26] Uesu T. A system of graph grammars which generates all recursively enumerable sets of labelled graphs. Tsukuba Journal of Mathematics, 1978,2(1):11?26.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

邹阳,吕建,曹春,胡昊,宋巍,杨启亮.上下文相关图文法的表达能力分析.软件学报,2012,23(7):1635-1655

Copy
Share
Article Metrics
  • Abstract:4538
  • PDF: 6374
  • HTML: 0
  • Cited by: 0
History
  • Received:June 26,2010
  • Revised:March 29,2011
  • Online: July 03,2012
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2037987Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063