A temporal graph grammar formalism

•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 ar...

Full description

Saved in:
Bibliographic Details
Published in:Journal of visual languages and computing 2018-08, Vol.47, p.62-76
Main Authors: Shi, Zhan, Zeng, Xiaoqin, Zou, Yang, Huang, Song, Li, Hui, Hu, Bin, Yao, Yi
Format: Article
Language:English
Subjects:
Graph grammar
Graphical language
Parsing algorithm
Simulation
Temporal specification
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•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. 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.
ISSN:1045-926X
1095-8533
DOI:10.1016/j.jvlc.2018.06.003