logging in or signing up Introduction to Graph Rewriting Marco1 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 326 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 10, 2008 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript An Introduction to Graph Rewriting: An Introduction to Graph Rewriting Thomas Huining Feng http://www.eecs.berkeley.edu/~tfeng/ CHESS, UC Berkeley May 1, 2007 Inspired by Tutorial Introduction to Graph Transformation: A Software Engineering Perspective. Luciano Baresi, Reiko Heckel. ICGT 2002PacMan: a Motivating Example: PacMan: a Motivating Example : Field : Field : Field : Field : Field : Field : Field : Field : Field Field 1 1..4 Type : Ghost Ghost 1 0..1 : PacMan PacMan 1 0..1 : Marble Marble 1 0..1 2Our 1st Rule: pmove: Our 1st Rule: pmove b : Field a : Field : PacMan b : Field a : Field : PacMan 3 LHS (Left Hand Side) RHS (Right Hand Side) : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan : Marble Host Graph Redex Redex finding is a sub-graph isomorphism problem). Multiple redexes? Our 2nd Rule: gmove: Our 2nd Rule: gmove b : Field a : Field : Ghost b : Field a : Field : Ghost : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan : MarbleCombining pmove and gmove: Combining pmove and gmove 5 catch Rule: catch Rule 6 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan : MarbleImportant Decision: Which Rule to Choose?: Important Decision: Which Rule to Choose? 7 Attribute Binding: collect Rule: Attribute Binding: collect Rule 8 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan 3 : marble : Marble : PacMan 4 : marbleAttribute Binding: collect Rule: Attribute Binding: collect Rule 9 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan 3 : marble : MarbleCompleting the PacMan Game: Completing the PacMan Game 10 b : Field a : Field : Ghost b : Field a : Field : Ghost : PacMan sub-case interfering sub-case 1 2 3 3 Priority: The Graph Rewriting Problem: Host Graph – Redex The Graph Rewriting Problem 11 m < BAG_SIZE b : Field a : Field : PacMan m : marble b : Field a : Field : PacMan m+1 : marble : Marble The Graph Rewriting Problem: The Graph Rewriting Problem 12More on Application Decision: More on Application Decision 13More on Application Decision: More on Application Decision 14 Field 1 1..4 Entrance 1 0..1 Kid 1 0..1 Exit 1 0..1More on Application Decision: More on Application Decision 15Conclusion: Conclusion 16 You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Introduction to Graph Rewriting Marco1 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 326 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 10, 2008 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript An Introduction to Graph Rewriting: An Introduction to Graph Rewriting Thomas Huining Feng http://www.eecs.berkeley.edu/~tfeng/ CHESS, UC Berkeley May 1, 2007 Inspired by Tutorial Introduction to Graph Transformation: A Software Engineering Perspective. Luciano Baresi, Reiko Heckel. ICGT 2002PacMan: a Motivating Example: PacMan: a Motivating Example : Field : Field : Field : Field : Field : Field : Field : Field : Field Field 1 1..4 Type : Ghost Ghost 1 0..1 : PacMan PacMan 1 0..1 : Marble Marble 1 0..1 2Our 1st Rule: pmove: Our 1st Rule: pmove b : Field a : Field : PacMan b : Field a : Field : PacMan 3 LHS (Left Hand Side) RHS (Right Hand Side) : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan : Marble Host Graph Redex Redex finding is a sub-graph isomorphism problem). Multiple redexes? Our 2nd Rule: gmove: Our 2nd Rule: gmove b : Field a : Field : Ghost b : Field a : Field : Ghost : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan : MarbleCombining pmove and gmove: Combining pmove and gmove 5 catch Rule: catch Rule 6 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan : MarbleImportant Decision: Which Rule to Choose?: Important Decision: Which Rule to Choose? 7 Attribute Binding: collect Rule: Attribute Binding: collect Rule 8 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan 3 : marble : Marble : PacMan 4 : marbleAttribute Binding: collect Rule: Attribute Binding: collect Rule 9 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan 3 : marble : MarbleCompleting the PacMan Game: Completing the PacMan Game 10 b : Field a : Field : Ghost b : Field a : Field : Ghost : PacMan sub-case interfering sub-case 1 2 3 3 Priority: The Graph Rewriting Problem: Host Graph – Redex The Graph Rewriting Problem 11 m < BAG_SIZE b : Field a : Field : PacMan m : marble b : Field a : Field : PacMan m+1 : marble : Marble The Graph Rewriting Problem: The Graph Rewriting Problem 12More on Application Decision: More on Application Decision 13More on Application Decision: More on Application Decision 14 Field 1 1..4 Entrance 1 0..1 Kid 1 0..1 Exit 1 0..1More on Application Decision: More on Application Decision 15Conclusion: Conclusion 16