View in EDS HTML Full Text PDF Full Text

EGG+: A graph grammar formalism with uncertain structure processing mechanism.

Saved in:
Bibliographic Details
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.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 153223857
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: EGG+: A graph grammar formalism with uncertain structure processing mechanism.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Liu%2C+Yufeng%22">Liu, Yufeng</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> yfengliu28@126.com</i><br /><searchLink fieldCode="AR" term="%22Yang%2C+Fan%22">Yang, Fan</searchLink><relatesTo>1</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Logic+%26+Computation%22">Journal of Logic & Computation</searchLink>. Oct2021, Vol. 31 Issue 7, p1800-1819. 20p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Graph+grammars%22">Graph grammars</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Programming+languages%22">Programming languages</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink><br /><searchLink fieldCode="DE" term="%22Search+algorithms%22">Search algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=153223857
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1093/logcom/exab055
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 20
        StartPage: 1800
    Subjects:
      – SubjectFull: Graph grammars
        Type: general
      – SubjectFull: Polynomial time algorithms
        Type: general
      – SubjectFull: Programming languages
        Type: general
      – SubjectFull: Problem solving
        Type: general
      – SubjectFull: Search algorithms
        Type: general
    Titles:
      – TitleFull: EGG+: A graph grammar formalism with uncertain structure processing mechanism.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Liu, Yufeng
      – PersonEntity:
          Name:
            NameFull: Yang, Fan
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2021
              Type: published
              Y: 2021
          Identifiers:
            – Type: issn-print
              Value: 0955792X
          Numbering:
            – Type: volume
              Value: 31
            – Type: issue
              Value: 7
          Titles:
            – TitleFull: Journal of Logic & Computation
              Type: main
ResultId 1