Coordinate Graph Grammar for the Specification of Spatial Graphs. (15th April 2020)

• Record Type: Journal Article
• Authors: Liu, Yufeng; Zeng, Xiaoqin; Zhang, Kang; Zou, Yang
• Is Part Of: Computer journal. Volume 64:Number 5(2021)
• Page Start: 749
• Page End: 761
• Publication Date: 2020-04-15
• Subjects: graph grammar -- quantitative spatial semantics -- qualitative spatial semantics -- spatial specification; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa019
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: 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.