Introduction to Graph Rewriting

50 %
50 %
Information about Introduction to Graph Rewriting
Education

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

Add a comment

Related presentations

Related pages

1 Introduction 1.1 Graph Rewriting Everywhere? -- The ...

1 Introduction 1.1 Graph Rewriting Everywhere? -- The Purpose of Graph Rewriting Systems Many problems in everyday life can be stated in terms ...
Read more

Graph Rewriting - st.inf.tu-dresden.de

Graph Rewriting Applications of Graph Rewriting and the Graph Rewriting Calculus Jan Lehmann University of Technology Dresden Department of Computer Science
Read more

On Graph Rewriting, Reduction and Evaluation

On Graph Rewriting, Reduction and Evaluation Ian Zerny1 ... 1.1 INTRODUCTION Graph reduction [39] has become a key subject in the specification and implemen-
Read more

An Introduction to Graph Rewriting Thomas Huining Feng ...

Presentation on theme: "An Introduction to Graph Rewriting Thomas Huining Feng CHESS, UC Berkeley May."— Presentation transcript: 1 An Introduction to ...
Read more

An introduction to term graph rewriting - dl.acm.org

Publication years: 1982-2014: Publication count: 22: Citation Count: 248: Available for download: 4: Downloads (6 Weeks) 8: Downloads (12 Months) 85 ...
Read more

Term Graph Rewriting - pdfs.semanticscholar.org

Term Graph Rewriting syntax and semantics ... Introduction Graph rewriting is a rather intuitive subject, but unfortunately proofs can become very tedious.
Read more

ALGEBRAIC GRAPH REWRITING USING A SINGLE PUSHOUT ABSTRACT ...

ALGEBRAIC GRAPH REWRITING USING A SINGLE PUSHOUT P.M ... 1 Introduction The conventional algebraic approach of graph rewriting is originally
Read more

Preface Contributors An Introduction to Term Graph ...

Preface Contributors An Introduction to Term Graph Rewriting p. 1 Partial Type Assignment in Left Linear Applicative Term Rewriting Systems p. 15
Read more

Graph Transformation in Software Engineering

Graph Transformation in Software Engineering ... Introduction to graph transformation ... Theory of term graph rewriting
Read more