Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/17637
Title: A context-sensitive graph grammar formalism for the specification of visual languages
Authors: Zhang, DQ
Zhang, K
Cao, J 
Issue Date: 2001
Source: Computer journal, 2001, v. 44, no. 3, p. 186-200 How to cite?
Journal: Computer Journal 
Abstract: Graph grammars may be used as natural and powerful syntax-definition formalisms for visual programming languages. Yet most graph-grammar parsing algorithms presented so far are either unable to recognize interesting visual languages or tend to be inefficient (with exponential time complexity) when applied to graphs with a large number of nodes and edges. This paper presents a context-sensitive graph grammar called reserved graph grammar, which can explicitly and completely describe the syntax of a wide range of diagrams using labeled graphs. The parsing algorithm of a reserved graph grammar uses a marking mechanism to avoid ambiguity in parsing and has polynomial time complexity in most cases. The paper defines a constraint condition under which a graph defined in a reserved graph grammar can be parsed in polynomial time. An algorithm for checking the condition is also provided.
URI: http://hdl.handle.net/10397/17637
ISSN: 0010-4620
DOI: 10.1093/comjnl/44.3.186
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

55
Last Week
0
Last month
0
Citations as of Jul 16, 2017

WEB OF SCIENCETM
Citations

40
Last Week
0
Last month
0
Citations as of Jul 19, 2017

Page view(s)

34
Last Week
1
Last month
Checked on Jul 9, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.