Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra (Q1060232): Difference between revisions

Fast algorithms are presented which find the minimal nontrivial congruences, subalgebras, and ideals of a finite algebra, given by tables of its operations. Our method involves finding objects which are minimal among all nontrivial objects, i.e. objects distinct from the least one. The running times of the presented algorithms are \(O(n^{r+1})\), in case of congruences, and \(O(n^ r)\), in case of subalgebras and ideals where n is the number of elements of the algebra and r is the maximal arity of its operations. For the minimal nontrivial congruences in groups and rings, better algorithms are presented working in \(O(n^ 2)\) time. The algorithm for minimal nontrivial congruences is used for a test whether a given algebra is simple, or subdirectly irreducible. This algorithm is both a generalization and an improvement of that for sequential automata, published earlier by the present authors [RAIRO, Inf. Théor. 15, 23-46 (1981; Zbl 0482.68050)].