2
$\begingroup$

Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed graph with the set of nodes $M$, which has exactly two arrows from each node, the arrows being labeled $0$ and $1$.

Then, the simplest operations on those graphs are

$e[b_0b_1 \dots b_n := a_1 \dots a_m]: S(M) \rightarrow S(M)$,

where $e \in M$, $\forall i: a_i, b_i \in \{0, 1\}$, and for every mapping

$e[b_0b_1 \dots b_n := a_1 \dots a_m](f_0, f_1) = (g_0, g_1)$

node $b = f_{b_1}(\dots f_{b_n}(e) \dots)$ must be the only point where ${(g_0, g_1)}$ differs from $(f_0, f_1)$, and $a = f_{a_1}(\dots f_{a_m}(e) \dots)$ must be equal to ${g_{b_0}(b)}$, that is

  • $a = g_{b_0}(b)$;
  • $i \not= b_0 \Rightarrow \forall x \in M: g_i(x) = f_i(x)$;
  • $\forall x \in M: x \not= b \Rightarrow g_{b_0}(x) = f_{b_0}(x)$.

Assuming $M$ to be unbounded, is there a composition

$T = e[b_0b_1\dots b_n := a_1\dots a_m] \circ \dots \circ e[y_0y_1\dots y_q := x_1\dots x_p]$

which as the only graph rewriting rule for the set of graphs $S(M)$ results in a universal graph rewriting system (a graph rewriting system able to simulate any other graph rewriting system)?


In somewhat more details, the above constructions are described in arXiv:1204.3372.

$\endgroup$
1
  • $\begingroup$ Please be aware of this research which provides a more general algebraic graph rewriting method using a 3x3 grid of pushouts / pullbacks instead of the 2x1 DPO grid: link.springer.com/chapter/10.1007/978-3-642-15928-2_15 . It seems like "blind graph rewriting" would be most general, but the linked chapter is currently (afaik) the most generalized structured approach so far. $\endgroup$ Sep 22, 2021 at 21:43

1 Answer 1

2
$\begingroup$

The construction is similar to that of Schönhage's Storage Modification Machine (SMM) model.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.