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 *node {
    struct node *left, *right;
}

struct node 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.

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.