No Access

Evolution of algebraic terms 2: Deep drilling algorithm

David M. Clark

Mathematics Department, SUNY New Paltz, New Paltz, New York 12561, USA

E-mail Address: [email protected]

Search for more papers by this author

Maarten Keijzer

Chordiant, Utrecht, Amsterdam 3524CX, The Netherlands

E-mail Address: [email protected]

Search for more papers by this author

, and

Lee Spector

School of Cognitive Science, Hampshire College, Amherst, MA 01002 USA

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S021819671650048XCited by:1 (Source: Crossref)

Abstract

The Deep Drilling Algorithm (DDA) is an efficient non-evolutionary algorithm, extracted from previous work with evolutionary algorithms, that takes as input a finite groupoid and an operation over its universe, and searches for a term representing that operation. We give theoretical and experimental evidence that this algorithm is successful for all idemprimal term continuous groupoids, which appear to be almost all finite groupoids, and that the DDA is seriously compromised or fails for most finite groupoids not meeting both of these conditions. See our online version of the DDA at http://hampshire.edu/lspector/dda.

Communicated by K. Keames

Keywords:

References

1. J. Berman and S. Burris, A computer study of 3-element groupoids, Logic Algebra (the Proceedings of the Magari conference), Aldo Ursini and Paolo Aglian, eds. (Marcel Dekker Inc., New York, NY, USA, 1996), pp. 379–430. Google Scholar
2. D. Clark, Evolution of algebraic terms 1: Term to term operation continuity, Int. J. Algebra Comput. 23(5) (2013) 1175–1205. Link, Web of Science, Google Scholar
3. D. Clark, B. Davey, J. Pitkethly and D. Rifqui, Flat unars: The primal, the semi-primal and the dualisable, Algebra Universalis 63(4) (2010) 303–329. Crossref, Web of Science, Google Scholar
4. D. Clark, M. Keijzer and L. Spector, Evolution of algebraic terms 3: A co-evolutionary algorithm (in preparation). Google Scholar
5. A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing (Springer-Verlag, New York, NY, USA, 2003). Crossref, Google Scholar
6. R. Freese, E. Kiss and M. Valeriote, UACalc, a Universal Algebra Calculator, Available at: www.uacalc.org (2011). Google Scholar
7. J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, Cambridge, MA, USA, 1992). Google Scholar
8. V. L. Murskıĭ, Konéc̆naá baziruémost' toźdéstv i drugié svojstva “poc̆ti vséh” konéc̆nyh algébr (A finite basis of identities and other properties of “almost all” finite algebras), Problémy Kibérnétiki 30 (1975) 43–56. Google Scholar
9. A. Pixley, Functionally complete algebras generating distributive and permutable classes, Math. Z. 114 (1970) 361–372. Crossref, Web of Science, Google Scholar
10. I. Rosenberg, Über die funktionale Vollständigkeit in den mehrwertigen Logiken (Struktur der Funktionen von mehreren Veränderlichen auf endlichen Mengen), Rozpravy Československé Akad. Věd Řada Mat. Přírod. 80 (1970) 1–93. Google Scholar
11. G. Rousseau, Completeness in finite algebras with a single operation, Proc. Amer. Math. Soc. 18 (1967) 1009–1013. Crossref, Web of Science, Google Scholar
12. C. E. Shannon, A symbolic analysis of relay and switching circuits, Transactions of the American Institute of Electrical Engineers 57(12) (1938) 713–723, doi: 10.1109/T-AIEE.1938.5057767. Crossref, Google Scholar
13. L. Spector, D. Clark, B. Barr, J. Klein and I. Lindsay, Genetic programming for finite algebras Genetic and Evolutionary Computation Conference (GECCO) 2008 Proceedings, Atlanta GA (July 2008), Editor-in-Chief Maarten Keijzer, Association for Computing Machinery (ACM), ISBN: 978-1-60558-130-9, pp. 1291–1298. [Paper won first place in the GECCO 2008 Human Competitive competition.] $〈$ www.genetic-programming.org/hc2011/combined.html $〉$ . Google Scholar
14. H. Werner, Eine Charakterisierung funktional vollständiger Algebren, Arch. Math. (Basel) 21 (1970) 381–385. Crossref, Web of Science, Google Scholar