Matrix Graph Grammars : An Algebraic Approach to Graph Dynamics

ISBN-13: 9783639212556 / Angielski / Miękka / 2009 / 284 str.

Pedro Pablo Pérez Velasco

Opis

The aim of this book is the study of graph dynamics, also known as graph rewriting. Matrix Graph Grammars proposes a new approach to the many open problems that exist in the subject. From the point of view of a computer scientist, graph grammars are a natural generalization of Chomsky grammars, for which a purely algebraic approach does not exist up to now. A Chomsky (or string) grammar is, roughly speaking, a precise description of a formal language (which in essence is a set of strings). On a more discrete mathematical style, it can be said that graph grammars -- Matrix Graph Grammars in particular -- study the dynamics of graphs in contrast to the more common static approach, which mainly deals with properties such as coloring. Ideally, this algebraization would enforce our understanding of grammars in general, providing new analysis techniques and generalizations of concepts, problems and results known so far. This book may be of interest to any researcher or practitioner of graph theory, or scientific or engineer that uses graph theory as a handy tool.

O autorze

owns a Ph.D. in Computer Science and a M.Sc. in Mathematics, both from Universidad Autónoma de Madrid. He is the father of the MGG approach, with several papers published on the topic. Currently, his main mathematical interests are MGGs as a model of computation and the relationship with Complexity theory, the PvsNP conjecture in particular.