# Algebraic structure generated by primitive graph operations

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.

• To get an algebraic structure I think you definitely need somewhat a binary operation operation, and for an algebra even a basefield....so far you just have a set with a family of maps (not even bijections?). So far I don't see any, sorry, but maybe if you share, what your intuition behind this problem is, we find any? – Simon Lentner Apr 10 '12 at 10:07
• For instance, but not necessarily, the binary operation could be composition of the introduced primitive graph operations. The 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. What I am eventually looking for is such a composition of the primitive graph operations which could result in universal (Turing-complete) finite-state machine as its transition function for optimal reduction of lambda expressions. – Anton Salikhmetov Apr 10 '12 at 11:00
• I'm having trouble parsing what you want. You have a complete deterministic automaton over a two-letter alphabet. Can you explain graphically this primitive operation? – Benjamin Steinberg Apr 10 '12 at 18:57
• (Actually, I am afraid the details on application of the above construction might not be helpful, but confusing instead.) I have an 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[b0b1…bn := a1…am] ∘ … ∘ e[y0y1…yq := x1…xp] so that the resulting automata would implement a graph rewriting system or an interaction system for optimal reduction of lambda expressions. – Anton Salikhmetov Apr 11 '12 at 5:27
• There might be an operad hanging around... – David Roberts Apr 11 '12 at 6:59