Computing congruences efficiently (Q1001460)

From MaRDI portal
Revision as of 18:51, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Computing congruences efficiently
scientific article

    Statements

    Computing congruences efficiently (English)
    0 references
    0 references
    17 February 2009
    0 references
    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.
    0 references
    principal congruence
    0 references
    data structure
    0 references
    find-union problem
    0 references

    Identifiers