Affiliations: School of Computer Science, Universidad
Autónoma de Madrid, Ciudad Universitaria de Cantoblanco, 28049 -
Madrid, Spain. E-mails: [email protected]; [email protected]
Abstract: In the Matrix approach to graph transformation we represent simple
digraphs and rules with Boolean matrices and vectors, and the rewriting is
expressed using Boolean operators only. In previous works, we developed
analysis techniques enabling the study of the applicability of rule sequences,
their independence, state reachability and the minimal graph able to fire a
sequence. In the present paper we improve our framework in two ways. First, we
make explicit (in the form of a Boolean matrix) some negative implicit
information in rules. This matrix (called nihilation matrix) contains the
elements that, if present, forbid the application of the rule (i.e. potential
dangling edges, or newly added edges, which cannot be already present in the
simple digraph). Second, we introduce a novel notion of application condition,
which combines graph diagrams together with monadic second order logic. This
allows for more flexibility and expressivity than previous approaches, as well
as more concise conditions in certain cases. We demonstrate that these
application conditions can be embedded into rules (i.e. in the left hand side
and the nihilation matrix), and show that the applicability of a rule with
arbitrary application conditions is equivalent to the applicability of a
sequence of plain rules without application conditions. Therefore, the analysis
of the former is equivalent to the analysis of the latter, showing that in our
framework no additional results are needed for the study of application
conditions. Moreover, all analysis techniques of [21,22] for the study of
sequences can be applied to application conditions.
Keywords: Graph Transformation, Matrix Graph Grammars, Application Conditions, Monadic Second Order Logic, Graph Dynamics
