Deciding associativity for partial multiplication tables of order $3$
HTML articles powered by AMS MathViewer
- by Paul W. Bunting, Jan van Leeuwen and Dov Tamari PDF
- Math. Comp. 32 (1978), 593-605 Request permission
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
- H. H. Baker, A. K. Dewdney, and A. L. Szilard, Generating the nine-point graphs, Math. Comp. 28 (1974), 833–838. MR 371134, DOI 10.1090/S0025-5718-1974-0371134-8 J. R. BITNER & E. M. REINGOLD, "Backtrack programming techniques," Comm. ACM, v. 18, 1975, pp. 651-656.
- Richard Hubert Bruck, A survey of binary systems, Reihe: Gruppentheorie, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1958. MR 0093552 A. H. CLIFFORD & G. B. PRESTON, The Algebraic Theory of Semigroups, Math. Surveys, Vol. 7, Part I, Amer. Math. Soc., Providence, R. I., 1964.
- J. B. de Carvalho and Dov Tamari, Sur l’associativité partielle des symétrisations de semigroupes, Portugal. Math. 21 (1962), 157–169 (French). MR 150215
- George E. Forsythe, SWAC computes $126$ distinct semigroups of order $4$, Proc. Amer. Math. Soc. 6 (1955), 443–447. MR 69814, DOI 10.1090/S0002-9939-1955-0069814-7
- H. Jürgensen, Calculation with the elements of a finite group given by generators and defining relations, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 47–57. MR 0258955 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.
- H. Jürgensen and P. Wick, Die Halbgruppen der Ordnungen $\leq 7$, Semigroup Forum 14 (1977), no. 1, 69–79. MR 447452, DOI 10.1007/BF02194655
- E. S. Ljapin, Semigroups, Translations of Mathematical Monographs, Vol. 3, American Mathematical Society, Providence, R.I., 1963. MR 0167545
- M. H. A. Newman, On theories with a combinatorial definition of “equivalence.”, Ann. of Math. (2) 43 (1942), 223–243. MR 7372, DOI 10.2307/1968867
- Rohit J. Parikh, On context-free languages, J. Assoc. Comput. Mach. 13 (1966), 570–581. MR 209093, DOI 10.1145/321356.321364
- Robert J. Plemmons, There are ${\rm 15973}$ semigroups of order ${\rm 6}$, Math. Algorithms 2 (1967), 2–17. MR 235059
- Robert Plemmons, Construction and analysis of non-equivalent finite semigroups, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 223–228. MR 0258994
- Arto Salomaa, Formal languages, ACM Monograph Series, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0438755
- H. R. Strong Jr., A. Maggiolo-Schettini, and B. K. Rosen, Recursion structure simplification, SIAM J. Comput. 4 (1975), no. 3, 307–320. MR 383814, DOI 10.1137/0204025 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. 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. 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.
- Dov Tamari, The associativity problem for monoids and the word problem for semigroups and groups, Word problems: decision problems and the Burnside problem in group theory (Conf., Univ. California, Irvine, Calif., 1969; dedicated to Hanna Neumann), Studies in Logic and the Foundations of Math., Vol. 71, North-Holland, Amsterdam, 1973, pp. 591–607. MR 0393288
- Kazutoshi Tetsuya, Takao Hashimoto, Tadao Akazawa, Ry\B{o}ichi Shibata, Tadashi Inui, and Takayuki Tamura, All semigroups of order at most $5$, J. Gakugei Tokushima Univ. 6 (1955), 19–39. Errata on loose, unpaginated sheet. MR 78377 R. B. WEISS, Finding Isomorph Classes for Combinatorial Structures, MAC Techn. Memo 64, M. I. T., Cambridge, Mass., 1975.
Additional Information
- © Copyright 1978 American Mathematical Society
- 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