Let $M$ be a finite set, and

$S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$.

Each element of $S(M)$ can be considered as 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$. Let us take a look at the simplest operations on graphs of this type:

$e[b_0b_1…b_n := a_1…a_m]: S(M) → S(M)$, where $e ∈ M$ and $∀i: a_i, b_i ∈ {0, 1}$.

We will require $e[b_0b_1…b_n := a_1…a_m](f_0, f_1) = (g_0, g_1)$ to have certain properties. Namely, if

$a = f_{a_1}(…f_{a_m}(e)…)$

and

$b = f_{b_1}(…f_{b_n}(e)…)$,

$a$ must be equal to $g_{b_0}(b)$, and $b$ must be the only point where $(g_0, g_1)$ differs from $(f_0, f_1)$. That is,

- $a = g_{b_0}(b)$;
- $i ≠ b_0 ⇒ ∀x ∈ M: g_i(x) = f_i(x)$;
- $∀x ∈ M: x ≠ b ⇒ g_{b_0}(x) = f_{b_0}(x)$.

**Do some of those primitive graph operations with composition as the binary operation generate a well-known algebraic structure? More generally, I am interested in finding any possible mathematical structures compatible with the definitions given above, for which there are known useful results.**

This question occurred within my small research in computer science, and relatively simple form of the above construction made me think I could find useful results about them, once one points the relevant field. More precisely, I have automata with the set of states equal to $S(M)$ and what I am eventually looking for is (preferably, the simplest) particular transition

$T = e[b_0b_1…b_n := a_1…a_m] ∘ … ∘ e[y_0y_1…y_q := x_1…x_p]$

so that the resulting automata would implement a graph rewriting system or an interaction system for optimal reduction of $λ$-expressions.

I will take the liberty to illustrate a particular operation of the introduced type by its implementation in the C programming language:

```
struct node {
struct node *left, *right;
} state[MEMSIZE];
void op(struct node *element)
{
element->left->right = element->right->left->left;
}
```

If every structure's fields all point to nodes in the array itself, the state corresponds to an element of $S(M)$, $|M|$ being equal to the array size. Then, calling the function basically maps the array from one state to another, so it directly implements $e[01 := 100]$, $e$ corresponding to the function's argument.