4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Apr 10, 2012 at 10:07
  • $\begingroup$ 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. $\endgroup$ Apr 10, 2012 at 11:00
  • $\begingroup$ 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? $\endgroup$ Apr 10, 2012 at 18:57
  • $\begingroup$ (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. $\endgroup$ Apr 11, 2012 at 5:27
  • 1
    $\begingroup$ There might be an operad hanging around... $\endgroup$
    – David Roberts
    Apr 11, 2012 at 6:59

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The mentioned paper is very interesting and close to what I am looking for. Thank you very much. $\endgroup$ Jan 13, 2013 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.