{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T12:38:19Z","timestamp":1700829499606},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T00:00:00Z","timestamp":1586908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>As a two-dimensional formal method, graph grammar is widely used in defining various visual programming languages. This paper presents a new graph grammar formalism called coordinate graph grammar (CGG). CGG is extended from the edge-based graph grammar (EGG) by introducing the spatial mechanism into the theoretical framework, which consists of continuous coordinate graph grammar (cCGG) and discrete coordinate graph grammar (dCGG). By combining quantitative and qualitative spatial semantics in one framework, CGG provides strong expressiveness and flexibility for specifying various spatial graphs. This paper focuses on several important issues on the new formalism. First, the theoretical framework of CGG is given. Second, two matching algorithms for cCGG and dCGG are proposed, which use the spatial relationships between nodes to narrow down the search space during parsing. Finally, an application of CGG is demonstrated, which generates parsable flowcharts in a uniform layout.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa019","type":"journal-article","created":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T12:10:35Z","timestamp":1581509435000},"page":"749-761","source":"Crossref","is-referenced-by-count":3,"title":["Coordinate Graph Grammar for the Specification of Spatial Graphs"],"prefix":"10.1093","volume":"64","author":[{"given":"Yufeng","family":"Liu","sequence":"first","affiliation":[{"name":"Institute of Intelligence Science and Technology, Hohai University, 8# West Focheng Road, Nanjing 211100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoqin","family":"Zeng","sequence":"additional","affiliation":[{"name":"Institute of Intelligence Science and Technology, Hohai University, 8# West Focheng Road, Nanjing 211100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kang","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, 800 W. Campbell Rd., Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Zou","sequence":"additional","affiliation":[{"name":"Institute of Intelligence Science and Technology, Hohai University, 8# West Focheng Road, Nanjing 211100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,4,15]]},"reference":[{"key":"2021052810194765200_ref1","first-page":"272","article-title":"Research on parsing algorithm of EGG graph grammar","volume":"39","author":"Zhu","year":"2012","journal-title":"Comp. Sci."},{"key":"2021052810194765200_ref2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1676-6","volume-title":"Visual Language Theory","author":"Marriott","year":"1998"},{"key":"2021052810194765200_ref3","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1016\/j.ins.2015.08.052","article-title":"Specification and discovery of web patterns: A graph grammar approach","volume":"328","author":"Roudaki","year":"2016","journal-title":"Inf. Sci."},{"key":"2021052810194765200_ref4","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.jvlc.2016.03.001","article-title":"Multi-amalgamated triple graph grammars: Formal foundation and application to visual language translation","volume":"42","author":"Leblebici","year":"2016","journal-title":"J. Visual Lang. Comput."},{"key":"2021052810194765200_ref5","first-page":"99","volume-title":"Vienna, Austria, 4\u20135 July","author":"Trollmann","year":"2016"},{"key":"2021052810194765200_ref6","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1016\/j.procs.2016.05.314","article-title":"Hypergraph grammars in non-stationary hp- adaptive finite element method","volume":"80","author":"Paszynska","year":"2016","journal-title":"Procedia Comp. Sci."},{"key":"2021052810194765200_ref7","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/j.cag.2016.05.014","article-title":"Procedural mesh features applied to subdivision surfaces using graph grammars","volume":"58","author":"Thaller","year":"2016","journal-title":"Comp. Graphics"},{"key":"2021052810194765200_ref8","first-page":"5242","volume-title":"Proceedings of ICRA, Stockholm, Sweden, 16\u201321 May","author":"Guo","year":"2016"},{"key":"2021052810194765200_ref9","first-page":"153","article-title":"Graph-grammar greedy algorithm for reutilization of partial LU factorization over 3D tetrahedral grids","volume":"18","author":"Paszy\u0144ska","year":"2016","journal-title":"J. Comp. Sci."},{"key":"2021052810194765200_ref10","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/j.compeleceng.2015.12.027","article-title":"Bidirectional transformation between BPMN and BPEL with graph grammar","volume":"51","author":"Shi","year":"2016","journal-title":"Comp. Electr. Eng."},{"key":"2021052810194765200_ref11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(82)90088-3","article-title":"Graph grammars with neighbourhood-controlled embedding","volume":"21","author":"Janssens","year":"1982","journal-title":"Theor. Comp. Sci."},{"key":"2021052810194765200_ref12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1142\/9789812384720_0002","article-title":"Hyperedge Replacement Graph Grammars. Hyperedge Replacement Graph Grammars","volume":"1","author":"Drewes","year":"1997","journal-title":"In Handbook Of Graph Grammars And Computing By Graph Transformation"},{"key":"2021052810194765200_ref13","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1006\/jvlc.1996.0027","article-title":"Defining and parsing visual languages with layered graph grammars","volume":"8","author":"Rekers","year":"1997","journal-title":"J. Visual Lang. Comp."},{"key":"2021052810194765200_ref14","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1093\/comjnl\/44.3.186","article-title":"A context-sensitive graph grammar formalism for the specification of visual languages","volume":"44","author":"Zhang","year":"2001","journal-title":"Comp. J."},{"key":"2021052810194765200_ref15","first-page":"268","article-title":"Spatial graph grammars for graphical user interfaces","volume":"13","author":"Kong","year":"2006","journal-title":"ACM T. Comput.-Hum. Int."},{"key":"2021052810194765200_ref16","doi-asserted-by":"crossref","first-page":"11","DOI":"10.18293\/VLSS2018-028","article-title":"Edge-based graph grammar: Theory and support system","volume":"4","author":"Zeng","year":"2018","journal-title":"J. Visual Lang. and Sent. Syst."},{"key":"2021052810194765200_ref17","volume-title":"World Scientific","author":"Rozenberg","year":"1997"},{"key":"2021052810194765200_ref18","first-page":"118","article-title":"Constraint multiset grammars","author":"Marriott","year":"1994","journal-title":"Proc. IEEE Symp. Visual Lang"},{"key":"2021052810194765200_ref19","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1006\/jvlc.1997.0053","article-title":"On the classification of visual languages by grammar hierarchies","volume":"8","author":"Marriott","year":"1997","journal-title":"J. Visual Lang. Comp."},{"key":"2021052810194765200_ref20","volume-title":"Relational Grammars: Theory and Practice in a Visual Language Interface for Process Modeling","author":"Wittenburg","year":"1996"},{"key":"2021052810194765200_ref21","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S1045-926X(05)80013-8","article-title":"The specification of visual language syntax","volume":"1","author":"Golin","year":"1990","journal-title":"J. Visual Lang. Comp."},{"key":"2021052810194765200_ref22","first-page":"151","volume-title":"Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science, Germany, 16\u201318 June","author":"Sch\u00fcrr","year":"1994"},{"key":"2021052810194765200_ref23","first-page":"148","article-title":"A graph based framework for the implementation of visual environments","author":"Rekers","year":"1996","journal-title":"IEEE Symp. Visual Lang."},{"key":"2021052810194765200_ref24","first-page":"16","volume-title":"Proceedings of GD 94, New Jersey, USA, 10\u201312 Oct","author":"Brandenburg","year":"1994"},{"key":"2021052810194765200_ref25","volume-title":"Quantitative Spatial Semantics in a Graph Grammar Formalism. Proceedings of International Workshop on Interactive and Spatial Computing, Dallas, USA, 12\u201312 April, pp. 1\u20137","author":"Liu","year":"2018"},{"key":"2021052810194765200_ref26","first-page":"125","article-title":"Shape grammars and the generative specification of painting and sculpture","volume":"2","author":"Stiny","year":"1971","journal-title":"Proc. IFIP Congress"},{"key":"2021052810194765200_ref27","first-page":"1383","article-title":"Pictorial and formal aspects of shape and shape grammars","volume":"31","author":"Guruvaiah","year":"1975","journal-title":"Interdiscip. Syst. Res."},{"key":"2021052810194765200_ref28","doi-asserted-by":"crossref","first-page":"1744","DOI":"10.1109\/TPAMI.2012.252","article-title":"Parsing facades with shape grammars and reinforcement learning","volume":"35","author":"Teboul","year":"2013","journal-title":"IEEE T. Pattern Anal. Mach. Intell."},{"key":"2021052810194765200_ref29","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1145\/1141911.1141931","article-title":"Procedural modeling of buildings","volume":"25","author":"M\u00fcller","year":"2006","journal-title":"Acm T. Graphics"},{"key":"2021052810194765200_ref30","first-page":"439","volume-title":"Proceedings of Ninth International Conference on Information Visualisation, London, UK, 6\u20138 July","author":"Huang","year":"2005"},{"key":"2021052810194765200_ref31","first-page":"133","volume-title":"Adaptive Mobile Interfaces through Grammar Induction. Proceedings of 20th IEEE International Conference on Tools with Artificial Intelligence, Dayton, USA, 3\u20135 Nov","author":"Kong","year":"2008"},{"key":"2021052810194765200_ref32","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1109\/TSMCC.2011.2171335","article-title":"Web Interface interpretation using graph grammars","volume":"42","author":"Kong","year":"2012","journal-title":"IEEE T. Syst. Man Cybernet."},{"key":"2021052810194765200_ref33","first-page":"1","article-title":"Spatial specification and reasoning using grammars: From theory to application","author":"Liu","year":"2018","journal-title":"Spat. Cogn. Comput."},{"key":"2021052810194765200_ref34","first-page":"284","volume-title":"Proceeding of IEEE Symposium on Visual Languages, Isle of Capri, Italy, 23\u201326 Sep","author":"Zhang","year":"1997"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/749\/38335194\/bxaa019.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/749\/38335194\/bxaa019.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T11:57:11Z","timestamp":1622203031000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/5\/749\/5819257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,15]]},"references-count":34,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,4,15]]},"published-print":{"date-parts":[[2021,5,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa019","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,5]]},"published":{"date-parts":[[2020,4,15]]}}}