Algebraic structure generated by primitive graph operations

2012-04-10T08:41:11Z

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.

Answer by Bilal Khan for Algebraic structure generated by primitive graph operations

2013-01-12T16:00:16Z

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.

Algebraic structure generated by primitive graph operations - MathOverflow

Algebraic structure generated by primitive graph operations

Answer by Bilal Khan for Algebraic structure generated by primitive graph operations