Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6934503 | Journal of Visual Languages & Computing | 2018 | 15 Pages |
Abstract
As a useful formalism tool, graph grammars provide a rigorous but intuitive way to specify visual languages. This paper, based on the existing Edge-based Graph Grammar (EGG), proposes a new context-sensitive graph grammar formalism called the Temporal Edge-based Graph Grammar, or TEGG. TEGG introduces some temporal mechanisms to grammatical specifications, productions, operations and so on in order to tackle time-related issues. In the paper, formal definitions of TEGG are provided first. Then, a new parsing algorithm with a decidability proof is proposed to check the correctness of a given graph's structure, to analyze operations' timing when needed, and to make the computer simulation of the temporal sequence in the graph available. Next, the complexity of the parsing algorithm is analyzed. Finally, a case study on an application with temporal requirements is provided to show how the parsing algorithm of TEGG works.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science Applications
Authors
Shi Zhan, Zeng Xiaoqin, Zou Yang, Huang Song, Li Hui, Hu Bin, Yao Yi,