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.



Algebraic structure generated by primitive graph operations
Perhaps this paper might be tangentially related to the ideas you are developing?


[Bilal Khan, Kiran Bhutani, Delaram Kahrobaei. A Graphic Generalization of Arithmetic, Electronic Journal of Combinatorial Number Theory, 2007.](http://www.integers-ejcnt.org/vol7.html) 


