Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Deciding associativity for partial multiplication tables of order $ 3$


Authors: Paul W. Bunting, Jan van Leeuwen and Dov Tamari
Journal: Math. Comp. 32 (1978), 593-605
MSC: Primary 20L05; Secondary 02G05
DOI: https://doi.org/10.1090/S0025-5718-1978-0498906-7
MathSciNet review: 0498906
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The associativity problem for the class of finite multiplication tables is known to be undecidable, even for quite narrow infinite subclasses of tables. We present criteria which can be used to decide associativity in many cases, although any effective method based on such criteria must eventually fail on a table of some size (as otherwise decidability for the general class would follow). By means of an extensive computer search we have been able to use the criteria successfully to solve the associativity problem for all tables of order up to 3. We find 24,733 associative tables and 237,411 nonassociative tables, and present some further statistics about how "deep" we had to search to establish the nonassociativity of a table. We also prove that there are tables of order 3 for which no "one-mountain" theorem holds (which was known previously only for order 6 examples). Our methods make use of efficient data-representations and techniques of heuristic and adaptive programming.


References [Enhancements On Off] (What's this?)

  • [1] H. H. BAKER, A. K. DEWDNEY & A. L. SZILARD, "Generating the nine-point graphs," Math. Comp., v. 28, 1974, pp. 833-838. MR 0371134 (51:7355)
  • [2] J. R. BITNER & E. M. REINGOLD, "Backtrack programming techniques," Comm. ACM, v. 18, 1975, pp. 651-656.
  • [3] R. H. BRUCK, A Survey of Binary Systems, Springer-Verlag, New York, 1966. MR 0093552 (20:76)
  • [4] A. H. CLIFFORD & G. B. PRESTON, The Algebraic Theory of Semigroups, Math. Surveys, Vol. 7, Part I, Amer. Math. Soc., Providence, R. I., 1964.
  • [5] J. B. DE CARVALHO & D. TAMARI, "Sur l'associativité partielle des symétrisations de semi-groupes," Portugal. Math., v. 21, 1962, pp. 157-169. MR 0150215 (27:217)
  • [6] G. E. FORSYTHE, "SWAC computes 126 distinct semigroups of order 4," Proc. Amer. Math. Soc., v. 6, 1955, pp. 443-447. MR 0069814 (16:1085d)
  • [7] H. JÜRGENSEN, "Calculation with the elements of a finite group given by generators and defining relations," in Computational Problems in Abstract Algebra (J. Leech, Editor), Pergamon Press, Oxford, 1970. MR 0258955 (41:3600)
  • [8] H. JÜRGENSEN, Ueber das Rechnen mit den Elementen abstrakt präsentierter Halbgruppen, Bericht 76/06, Inst. f. Informatik u. Praktische Math., Christian-Albrechts-Universität, Kiel, 1976.
  • [9] H. JÜRGENSEN & P. WICK, "Die Halbgruppen der Ordnungen $ \leqslant 7$," Semigroup Forum, v. 14, 1977, pp. 69-79. MR 0447452 (56:5764)
  • [10] E. S. LJAPIN, Semigroups, Transl. Math. Monographs, vol. 3, Amer. Math. Soc., Providence, R. I., 1963. MR 0167545 (29:4817)
  • [11] M. H. A. NEWMAN, "On theories with a combinatorial definition of equivalence," Ann. of Math., v. 43, 1942, pp. 223-243. MR 0007372 (4:126c)
  • [12] R. J. PARIKH, "On contextfree languages," J. Assoc. Comput. Mach., v. 13, 1966, pp. 570-581. MR 0209093 (34:8901)
  • [13] R. J. PLEMMONS, "There are 15973 semigroups of order 6," Math. Algorithms, v. 2, 1967, pp. 2-3. MR 0235059 (38:3371)
  • [14] R. J. PLEMMONS, "Construction and analysis of non-equivalent finite semigroups," in Computational Problems in Abstract Algebra (J. Leech, Editor), Pergamon Press, Oxford, 1970. MR 0258994 (41:3639)
  • [15] A. SALOMAA, Formal Languages, Academic Press, New York, 1973. MR 0438755 (55:11661)
  • [16] H. R. STRONG, A. MAGGIOLO-SCHETTINI & B. K. ROSEN, "Recursion structure simplification," SIAM J. Comput., v.4, 1975, pp. 307-320. MR 0383814 (52:4694)
  • [17] D. TAMARI, "Imbeddings of partial (incomplete) multiplicative systems (monoids), associativity and word problem," Notices Amer. Math. Soc., v. 7, 1960, p. 760; Abstract #575-30.
  • [18] D. TAMARI, Problèmes d'Associativité des Monoides et Problèmes des Mots pour les Groupes, Séminaire Dubreil-Pisot, Vol. 16, 1962/1963, pp. 7.01-7.30.
  • [19] D. TAMARI, Le Problème d'Associativité des Monoides et le Problème des Mots pour les Demi-Groupes, Séminaire Dubreil-Pisot, vol. 24, 1970/1971, pp. 8.01-8.15.
  • [20] D. TAMARI, "The associativity problem for monoids and the word problem for semigorups and groups," in Word Problems (W. W. Boone, Editor), North-Holland, Amsterdam, 1973. MR 0393288 (52:14098)
  • [21] K. T. TETSUYA, T. HASHIMOTO, T. AKASAWA, R. SHIBOTA, T. INUI & T. TAMURA, "All semigroups of order at most 5," J. Gakugei Tokushima Univ., v. 6, 1955, pp. 19-39. MR 0078377 (17:1184c)
  • [22] R. B. WEISS, Finding Isomorph Classes for Combinatorial Structures, MAC Techn. Memo 64, M. I. T., Cambridge, Mass., 1975.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 20L05, 02G05

Retrieve articles in all journals with MSC: 20L05, 02G05


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1978-0498906-7
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society