{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,11]],"date-time":"2025-05-11T18:40:06Z","timestamp":1746988806691,"version":"3.37.3"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T00:00:00Z","timestamp":1630627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62002155"],"award-info":[{"award-number":["62002155"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,10,22]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1093\/logcom\/exab055","type":"journal-article","created":{"date-parts":[[2021,8,9]],"date-time":"2021-08-09T19:46:43Z","timestamp":1628538403000},"page":"1800-1819","source":"Crossref","is-referenced-by-count":2,"title":["EGG+: A graph grammar formalism with uncertain structure processing mechanism"],"prefix":"10.1093","volume":"31","author":[{"given":"Yufeng","family":"Liu","sequence":"first","affiliation":[{"name":"College of Information Engineering, Nanjing University of Finance and Economics, Nanjing 210046, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fan","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Information Engineering, Nanjing University of Finance and Economics, Nanjing 210046, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,9,3]]},"reference":[{"key":"2021102214134909300_ref1","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/j.compeleceng.2015.12.027","article-title":"Bidirectional transformation between BPMN and BPEL with graph grammar","volume":"51","author":"Shi","year":"2016","journal-title":"Computers and Electrical Engineering"},{"key":"2021102214134909300_ref2","first-page":"372","volume-title":"International Conference on Big Data","author":"Hibshman","year":"2019"},{"key":"2021102214134909300_ref3","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1002\/spe.2271","article-title":"Breeze graph grammar: A graph grammar approach for modeling the software architecture of big data-oriented software systems","volume":"45","author":"Li","year":"2015","journal-title":"Software Practice & Experience"},{"key":"2021102214134909300_ref4","first-page":"52","volume-title":"Brazilian Symposium on Formal Methods","author":"Duarte","year":"2017"},{"key":"2021102214134909300_ref5","first-page":"235","volume-title":"International Conference on Digital Information Management","author":"Miyadera","year":"2016"},{"key":"2021102214134909300_ref6","first-page":"424","volume-title":"International Conference on Information Science & Technology","author":"Chen","year":"2015"},{"key":"2021102214134909300_ref7","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1109\/TPAMI.2017.2731842","article-title":"Attribute and-or grammar for joint parsing of human pose, parts and attributes","volume":"40","author":"Park","year":"2017","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2021102214134909300_ref8","first-page":"444","article-title":"Top-down online handwritten mathematical expression parsing with graph grammar","volume":"9423","author":"Julcaaguilar","year":"2015","journal-title":"BeroAmerican Congress on Pattern Recognition"},{"key":"2021102214134909300_ref9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.18293\/VLSS2018-028","article-title":"Edge-based graph grammar: Theory and support system","volume":"4","author":"Zeng","year":"2018","journal-title":"Journal of Visual Languages and Sentient Systems"},{"key":"2021102214134909300_ref10","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1109\/NAFIPS.1996.534770","volume-title":"North American Fuzzy Information Processing Society","author":"Watkins","year":"1996"},{"key":"2021102214134909300_ref11","first-page":"445","volume-title":"International Conference on VLSI Design","author":"Das","year":"2009"},{"key":"2021102214134909300_ref12","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/s10559-006-0094-3","article-title":"Categorical approach to the construction of fuzzy graph grammars","volume":"42","author":"Parasyuk","year":"2006","journal-title":"Cybernetics and Systems Analysis"},{"key":"2021102214134909300_ref13","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0165-0114(98)00292-9","article-title":"An inference method for fuzzy tree grammars","volume":"112","author":"Shu","year":"2000","journal-title":"Fuzzy Sets and Systems"},{"key":"2021102214134909300_ref14","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1007\/11556121_92","volume-title":"Computer Analysis of Images and Patterns","author":"Arrivault","year":"2005"},{"key":"2021102214134909300_ref15","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(82)90088-3","article-title":"Graph grammars with neighbourhood-controlled embedding","volume":"1982","author":"Janssens","year":"1982","journal-title":"Theoretical Computer Science"},{"key":"2021102214134909300_ref16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1142\/9789812384720_0002","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformation","author":"Drewes","year":"1997"},{"key":"2021102214134909300_ref17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1006\/jvlc.1996.0027","article-title":"Defining and parsing visual languages with layered graph grammars","volume":"1997","author":"Rekers","year":"1997","journal-title":"Journal of Visual Languages and Computing"},{"key":"2021102214134909300_ref18","first-page":"3187","article-title":"A context-sensitive graph grammar formalism for the specification of visual languages","volume":"2001","author":"Zhang","year":"2001","journal-title":"The Computer Journal"},{"key":"2021102214134909300_ref19","first-page":"167","volume-title":"IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory","author":"Ehrig","year":"1973"},{"key":"2021102214134909300_ref20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/3-540-18771-5","volume-title":"International Workshop on Graph Grammars and their Application to Computer Science","author":"Ehrig","year":"1987"},{"key":"2021102214134909300_ref21","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/BFb0017375","volume-title":"International Workshop on Graph Grammars and their Application to Computer Science","author":"Ehrig","year":"1991"},{"key":"2021102214134909300_ref22","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(93)90068-5","article-title":"Algebraic approach to single-pushout graph transformation","volume":"109","author":"L\u00f6we","year":"1993","journal-title":"Theoretical Computer Science"},{"key":"2021102214134909300_ref23","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1109\/32.917521","article-title":"Design, construction, and application of a generic visual language generation environment","volume":"27","author":"Zhang","year":"2001","journal-title":"IEEE Transactions on Software Engineering"},{"key":"2021102214134909300_ref24","first-page":"137","article-title":"A graph grammar approach to the design and validation of floor plans","volume":"63","author":"Wang","year":"2020","journal-title":"The Computer Journal"},{"key":"2021102214134909300_ref25","first-page":"1460","volume-title":"Proceedings of the Workshop on Generalisation & Multiple Representation Leicester","author":"Stiny","year":"1971"},{"key":"2021102214134909300_ref26","first-page":"1383","article-title":"Pictorial and formal aspects of shape and shape grammars","volume":"31","author":"Guruvaiah","year":"1975","journal-title":"Interdisciplinary Systems Research"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/7\/1800\/40820390\/exab055.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/7\/1800\/40820390\/exab055.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T14:31:37Z","timestamp":1634913097000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/31\/7\/1800\/6363664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,3]]},"references-count":26,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2021,9,3]]},"published-print":{"date-parts":[[2021,10,22]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exab055","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2021,10]]},"published":{"date-parts":[[2021,9,3]]}}}