Decision-algorithms for the associativity of latin squares

Abstract

There are constructed two decision-algorithms for the associativity of latin squares. The first is defined on arbitrary latin squares and has the complexity 0(n ² log n) (for squares of the size n × n). For each symbol-table the decision whether it is a latin square is possible in 0(n ²); therefore we obtain a decision-algorithm for the group-property in 0(n ² log n). For commutative latin squares, the method applied previously can be improved, so that an 0(n ²) decision-algorithm for associativity can be constructed; thus the group-property of commutative symbol—tables is decidable in 0(n ²) (proportional to the size of the table). Finally, the real efficiency of the algorithms is shown for some examples (run-times are given for a PASCAL-program).

Keywords:

• latin square
• decision-algorithms
• associativity

C.R. Categories::

• 5.39