JOURNAL ARTICLE

A comparison of reserved graph grammar and edge-based graph grammar.

  • Published In: Computer Journal, 2025, v. 68, n. 2. P. 145 1 of 3

  • Database: Academic Search Ultimate 2 of 3

  • Authored By: Zou, Yang 3 of 3

Abstract

This article investigates the expressive power relationship between two prominent context-sensitive graph grammar formalisms: Reserved Graph Grammar (RGG) and Edge-based Graph Grammar (EGG). It introduces a variant of RGG called VRGG to serve as an intermediary, establishing that the class of graph languages generated by EGG is a proper subset of those generated by RGG. The paper provides bidirectional transformations between EGG and VRGG, demonstrating their expressive equivalence, and shows that VRGG is strictly contained within RGG due to an additional embedding constraint on VRGG. These results clarify the hierarchy of expressive power among these formalisms and offer practical means to leverage their respective advantages in applications involving visual programming languages and graph transformations.

Additional Information

  • Source:Computer Journal. 2025/02, Vol. 68, Issue 2, p145
  • Document Type:Article
  • Subject Area:Language and Linguistics
  • Publication Date:2025
  • ISSN:0010-4620
  • DOI:10.1093/comjnl/bxae100
  • Accession Number:183076324
  • Copyright Statement:Copyright of Computer Journal 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.)

Looking to go deeper into this topic? Look for more articles on EBSCOhost.