Matrix Graph Grammars as a Model of Computation
classification
💻 cs.DM
cs.CCcs.FL
keywords
graphcomputationgrammarsmatrixmodelambitiousappliedapproach
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.