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:Gk → G 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:G3 → 2G.
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.
- Change the parameter map name to any string of letters, numbers, spaces and punctuation aside from quotation marks. The enclosing quotation marks must be retained.
- Change the n2 values within the *-table to define the new groupoid operation.
- Change the time limit giving the number of milliseconds the program can run to any positive integer (without commas).
- Change the n3 values between "#{" and "}" to define the new target array.
- As an alternative to defining the target array in n3 cases, you can replace the definition of the array, beginning with the outermost "[" and ending with the outermost "]", with any one of the following:
:malcev :discriminator :majority :pixley
to find a:
Mal'cev Term: m(a,b,b) = a = m(b,b,a),
Discriminator Term: d(a,b,c) = a if a≠b; else c,
Majority Term: m(a,b,b) = m(b,a,b) = m(b,b,a) = b, or a
Pixley Term: p(a,b,b) = p(a,b,a) = p(b,b,a) = a.
- Change the size n of the groupoid to any integer other than 3, 4 or 5 by following the pattern of the given templates.
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.