2009/05/08 by Velasco, Pedro Pablo Perez
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.0905.1202
Matrix Graph Grammars (MGG) is a novel approach to the study of graph dynamics ([15]). In the present contribution we look at MGG as a formal grammar and as a model of computation, which is a necessary step in the more ambitious program of tackling complexity theory through MGG. We also study its relation with other well-known models such as Turing machines (TM) and Boolean circuits (BC) as well as non-determinism. As a side effect, all techniques available for MGG can be applied to TMs and BCs.