A temporal graph grammar formalism. (August 2018) - Shi, Zhan; Zeng, Xiaoqin; Zou, Yang; Huang, Song; Li, Hui; Hu, Bin; Yao, Yi
Highlights: We propose a new context-sensitive graph grammar formalism called TEGG in short. TEGGs introduce some temporal mechanisms in order to tackle time-related issues. A parsing algorithm for graphs' structure and temporal sequence is presented. The decidability and complexity of the parsing algorithm are proven. A case study on an application with temporal requirements is provided. 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.