Algebraic structure generated by primitive graph operations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T23:33:16Z http://mathoverflow.net/feeds/question/93634 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93634/algebraic-structure-generated-by-primitive-graph-operations Algebraic structure generated by primitive graph operations Anton Salikhmetov 2012-04-10T08:41:11Z 2013-01-12T16:00:16Z <p>Let <code>\$M\$</code> be a finite set, and</p> <p><code>\$S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}\$</code>.</p> <p>Each element of <code>\$S(M)\$</code> can be considered as a finite directed graph with the set of nodes <code>\$M\$</code>, which has exactly two arrows from each node, the arrows being labeled <code>\$0\$</code> and <code>\$1\$</code>. Let us take a look at the simplest operations on graphs of this type:</p> <p><code>\$e[b_0b_1…b_n := a_1…a_m]: S(M) → S(M)\$</code>, where <code>\$e ∈ M\$</code> and <code>\$∀i: a_i, b_i ∈ {0, 1}\$</code>.</p> <p>We will require <code>\$e[b_0b_1…b_n := a_1…a_m](f_0, f_1) = (g_0, g_1)\$</code> to have certain properties. Namely, if</p> <p><code>\$a = f_{a_1}(…f_{a_m}(e)…)\$</code></p> <p>and</p> <p><code>\$b = f_{b_1}(…f_{b_n}(e)…)\$</code>,</p> <p><code>\$a\$</code> must be equal to <code>\$g_{b_0}(b)\$</code>, and <code>\$b\$</code> must be the only point where <code>\$(g_0, g_1)\$</code> differs from <code>\$(f_0, f_1)\$</code>. That is,</p> <ul> <li><code>\$a = g_{b_0}(b)\$</code>;</li> <li><code>\$i ≠ b_0 ⇒ ∀x ∈ M: g_i(x) = f_i(x)\$</code>;</li> <li><code>\$∀x ∈ M: x ≠ b ⇒ g_{b_0}(x) = f_{b_0}(x)\$</code>.</li> </ul> <p><strong>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.</strong></p> <hr> <p>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 <code>\$S(M)\$</code> and what I am eventually looking for is (preferably, the simplest) particular transition</p> <p><code>\$T = e[b_0b_1…b_n := a_1…a_m] ∘ … ∘ e[y_0y_1…y_q := x_1…x_p]\$</code></p> <p>so that the resulting automata would implement a graph rewriting system or an interaction system for optimal reduction of <code>\$λ\$</code>-expressions.</p> <p>I will take the liberty to illustrate a particular operation of the introduced type by its implementation in the C programming language:</p> <pre><code>struct node { struct node *left, *right; } state[MEMSIZE]; void op(struct node *element) { element-&gt;left-&gt;right = element-&gt;right-&gt;left-&gt;left; } </code></pre> <p>If every structure's fields all point to nodes in the array itself, the state corresponds to an element of <code>\$S(M)\$</code>, <code>\$|M|\$</code> being equal to the array size. Then, calling the function basically maps the array from one state to another, so it directly implements <code>\$e[01 := 100]\$</code>, <code>\$e\$</code> corresponding to the function's argument.</p> http://mathoverflow.net/questions/93634/algebraic-structure-generated-by-primitive-graph-operations/118736#118736 Answer by Bilal Khan for Algebraic structure generated by primitive graph operations Bilal Khan 2013-01-12T16:00:16Z 2013-01-12T16:00:16Z <p>Perhaps this paper might be tangentially related to the ideas you are developing?</p> <p><a href="http://www.integers-ejcnt.org/vol7.html" rel="nofollow">Bilal Khan, Kiran Bhutani, Delaram Kahrobaei. A Graphic Generalization of Arithmetic, Electronic Journal of Combinatorial Number Theory, 2007.</a> </p>