# Introduction to Graph Rewriting

Information about Introduction to Graph Rewriting

Published on January 10, 2008

Author: Marco1

Source: authorstream.com

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 2002 PacMan: 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 2 Our 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 : Marble Combining pmove and gmove:  Combining pmove and gmove 5 catch Rule:  catch Rule 6 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan : Marble Important 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 : marble Attribute Binding: collect Rule:  Attribute Binding: collect Rule 9 : Field : Field : Field : Field : Field : Field : Field : Field : Field : Ghost : PacMan 3 : marble : Marble Completing 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 12 More on Application Decision:  More on Application Decision 13 More on Application Decision:  More on Application Decision 14 Field 1 1..4 Entrance 1 0..1 Kid 1 0..1 Exit 1 0..1 More on Application Decision:  More on Application Decision 15 Conclusion:  Conclusion 16

08. 01. 2008
0 views

09. 01. 2008
0 views

10. 01. 2008
0 views

11. 01. 2008
0 views

12. 01. 2008
0 views

15. 01. 2008
0 views

15. 01. 2008
0 views

15. 01. 2008
0 views

15. 01. 2008
0 views

16. 01. 2008
0 views

19. 01. 2008
0 views

23. 01. 2008
0 views

05. 02. 2008
0 views

05. 02. 2008
0 views

11. 02. 2008
0 views

17. 01. 2008
0 views

25. 01. 2008
0 views

28. 01. 2008
0 views

30. 01. 2008
0 views

07. 02. 2008
0 views

13. 02. 2008
0 views

15. 02. 2008
0 views

22. 01. 2008
0 views

29. 01. 2008
0 views

20. 02. 2008
0 views

22. 02. 2008
0 views

24. 01. 2008
0 views

12. 02. 2008
0 views

25. 02. 2008
0 views

25. 02. 2008
0 views

27. 02. 2008
0 views

14. 01. 2008
0 views

29. 02. 2008
0 views

11. 02. 2008
0 views

03. 03. 2008
0 views

14. 03. 2008
0 views

20. 03. 2008
0 views

22. 03. 2008
0 views

27. 03. 2008
0 views

22. 01. 2008
0 views

14. 04. 2008
0 views

07. 02. 2008
0 views

18. 04. 2008
0 views

21. 04. 2008
0 views

22. 04. 2008
0 views

24. 04. 2008
0 views

11. 01. 2008
0 views

04. 02. 2008
0 views

07. 05. 2008
0 views

08. 05. 2008
0 views

19. 03. 2008
0 views

30. 04. 2008
0 views

02. 05. 2008
0 views

02. 05. 2008
0 views

19. 01. 2008
0 views

05. 02. 2008
0 views

24. 01. 2008
0 views

10. 03. 2008
0 views

17. 01. 2008
0 views

24. 01. 2008
0 views

10. 01. 2008
0 views

14. 04. 2008
0 views

28. 03. 2008
0 views

05. 03. 2008
0 views

04. 02. 2008
0 views

28. 02. 2008
0 views

02. 04. 2008
0 views

21. 01. 2008
0 views

17. 01. 2008
0 views

16. 04. 2008
0 views

28. 01. 2008
0 views

20. 02. 2008
0 views

17. 01. 2008
0 views