Computer Science – Discrete Mathematics
Scientific paper
2009-02-05
Computer Science
Discrete Mathematics
30 pages, 12 figures
Scientific paper
Graph transformation is concerned with the manipulation of graphs by means of rules. Graph grammars have been traditionally studied using techniques from category theory. In previous works, we introduced Matrix Graph Grammars (MGGs) as a purely algebraic approach for the study of graph grammars and graph dynamics, based on the representation of graphs by means of their adjacency matrices. MGGs have been succesfully applied to problems such as applicability of rule sequences, sequentialization and reachability, providing new analysis techniques and generalizing and improving previous results. Our next objective is to generalize MGGs in order to approach computational complexity theory and "static" properties of graphs out of the "dynamics" of certain grammars. In the present work, we start building bridges between MGGs and complexity by introducing what we call "Monotone Complex Logic", which allows establishing a (bijective) link between MGGs and complex analysis. We use this logic to recast the formulation and basic building blocks of MGGs as more proper geometric and analytic concepts (scalar products, norms, distances). MGG rules can also be interpreted - via operators - as complex numbers. Interestingly, the subset they define can be characterized as the Sierpinski gasket.
Lara Juan de
Perez Velasco Pedro Pablo
No associations
LandOfFree
Matrix Graph Grammars and Monotone Complex Logics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Matrix Graph Grammars and Monotone Complex Logics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matrix Graph Grammars and Monotone Complex Logics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-25551