EGG+: A graph grammar formalism with uncertain structure processing mechanism.
Saved in:
| Title: | EGG+: A graph grammar formalism with uncertain structure processing mechanism. |
|---|---|
| Authors: | Liu, Yufeng1 (AUTHOR) yfengliu28@126.com, Yang, Fan1 (AUTHOR) |
| Source: | Journal of Logic & Computation. Oct2021, Vol. 31 Issue 7, p1800-1819. 20p. |
| Subjects: | Graph grammars, Polynomial time algorithms, Programming languages, Problem solving, Search algorithms |
| 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
Be the first to leave a comment!
