The Deep Drilling Algorithm

The Deep Drilling Algorithm (DDA) is an efficient algorithm which takes as input a finite groupoid G and a k-ary operation g:GkG that is a term operation of G, and outputs a term representing g. It is fully described in Clark, Keijzer and Spector [2] drawing on Clark [1]. These papers give theoretical and empirical evidence that the DDA will be successful with all finite term continuous idemprimal groupoids, and that these constitute almost all finite groupoids.

Program Function

We give here a program that implements the DDA for n-element groupoids G with G = {0, 1,..., n-1} and with k=3. Instead of an operation the DDA uses an array A:G32G. Arrays reduce to operations in the case that \(A(\vec a)\) is always a singleton. A solution to A is a term t such that \(t(\vec a) \in A(\vec a)\) for all \(\vec a \in G^3\). The DDA will seek to find a solution to A.

The rectangular "Parameter Map" field below illustrates the exact form of an input to the program, which must be written in plain text. In this illustration G is the primal groupoid A1 and the array M is denoted by ":constraints". The notation "[1 1 2] #{2}" means that M(1,1,2) = {2}. Notice that a term is a solution to the array M if and only if it is a Mal'cev term for A1. A solution to M is found by pressing the "Run DDA" button. Press it again and you get another solution.

Instructions

In order to find a term for your own groupoid, first determine the size n of that groupoid. If it is 4 or 5, delete the entire contents of the Parameter Map field. Then go to one of the following links, copy the template you find there, and paste it into the emptied Parameter Map field. You can now make changes within that field to conform to your new application. Be careful not to make any changes aside form the six listed below. Other changes will generally lead the program to either report a syntax error or to return a term that is not a solution to the given array.

References

[1] David M. Clark, Evolution of algebraic terms 1: term to term operation continuity, International Journal of Algebra and Computation, 23, No. 5 (2013) 1175-1205.

[2] David M. Clark, Maarten Keijzer and Lee Spector, Evolution of algebraic terms 2: the Deep Drilling Algorithm, International Journal of Algebra and Computation, (in press).

Questions? Contact Lee Spector.

Parameter Map:

Built using re-simple-term.