Computing congruences efficiently (Q1001460): Difference between revisions

Let \(A\) be a finite algebra on an \(n\)-element set. Assume that a computation of every based operation requires \(O(1)\) time. By the classical data structure for the union-find problem, an algorithm computing a principal congruence of \(A\) determined by two given elements of \(A\) is suggested. This algorithm runs in \(O(kn)\) time if \(A\) is a unary algebra with \(k\) unary operations and in \(O(n\log n)\) time if \(A\) has at least a binary operation. A generalization for a construction of congruences given by a partition is presented.