EGG+: A graph grammar formalism with uncertain structure processing mechanism
EGG+: A graph grammar formalism with uncertain structure processing mechanism
复制标题
DOI：
10.1093/logcom/exab055
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Fan Yang
中科院分区：
文献类型：
--
作者：
Yufeng Liu;Fan Yang
Abstract. Extended from string grammars, graph grammar is a 2D formal method, which could specify the syntax structures of visual programming languages intuitively yet formally. However, the graph matching conditions in most graph grammars are too strict in specified applications, influencing the flexibility and fault tolerant capability of graph grammar. To solve the problems, this paper introduces an uncertain structure processing mechanism into graph grammar formalism and proposes a new graph grammar named EGG+. Different from traditional graph grammars, EGG+ defines a class of special edges named uncertain edges to specify the uncertain relationships between graphical elements. Each graph with uncertain edge is defined an uncertain graph, as a prototype of a set of graphical structures. By the new terms and definitions, EGG+ productions are divided into two categories: certain productions and uncertain productions, where certain productions specify the structures with strict matching requirements and uncertain productions are used to ignore specified syntactical errors during derivation and reduction, providing fault tolerant capability for the accessible non-isomorphic structures. Moreover, a redex searching algorithm with polynomial time complexity is designed for the convenience of grammatical application in the new formalism.
