A temporal graph grammar formalism. (August 2018)

• Record Type: Journal Article
• Authors: Shi, Zhan; Zeng, Xiaoqin; Zou, Yang; Huang, Song; Li, Hui; Hu, Bin; Yao, Yi
• Is Part Of: Journal of visual languages & computing. Volume 47(2018)
• Page Start: 62
• Page End: 76
• Publication Date: 2018-08
• Subjects: Graphical language -- Graph grammar -- Temporal specification -- Parsing algorithm -- Simulation; Visual programming languages (Computer science) -- Periodicals; Visual programming (Computer science) -- Periodicals; Programming languages (Electronic computers) -- Semantics -- Periodicals; Langages de programmation visuelle -- Périodiques; Programmation visuelle -- Périodiques; Langages de programmation -- Sémantique -- Périodiques; Programming languages (Electronic computers) -- Semantics; Visual programming (Computer science); Visual programming languages (Computer science); Periodicals; Electronic journals; 005
• DOI: 10.1016/j.jvlc.2018.06.003
• Languages: English
• ISSNs: 1045-926X

Abstract

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.