Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
type: Item
instance of: scholarly article
title: Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
zbMATH Open document ID: 0568.08002
DOI: 10.1016/0304-3975(85)90042-8
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 08A30
Mathematics Subject Classification ID: 08-04
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3906560
zbMATH Keywords: minimal nontrivial congruences
zbMATH Keywords: subalgebras
zbMATH Keywords: ideals
zbMATH Keywords: finite algebra
zbMATH Keywords: algorithms
zbMATH Keywords: simple
zbMATH Keywords: subdirectly irreducible
author: Jiri Demel
author: Marie Demlová
author: Václav Koubek
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90042-8
OpenAlex ID: W1999391918
cites work: On the computational power of pushdown automata
cites work: Subdirect unions in universal algebra
cites work: Q3946212
cites work: Q3940851
cites work: Q3862398
cites work: Q3666904
cites work: Q5572358
cites work: Group-theoretic algorithms and graph isomorphism
cites work: Depth-First Search and Linear Graph Algorithms
description: scientific article; zbMATH DE number 3906560