Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra (Q1060232): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Jiri Demel / rank | |||
Property / author | |||
Property / author: Marie Demlová / rank | |||
Property / author | |||
Property / author: Václav Koubek / rank | |||
Property / author | |||
Property / author: Jiri Demel / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Marie Demlová / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Václav Koubek / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(85)90042-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1999391918 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the computational power of pushdown automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subdirect unions in universal algebra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3946212 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3940851 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3862398 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3666904 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572358 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Group-theoretic algorithms and graph isomorphism / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Depth-First Search and Linear Graph Algorithms / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 18:09, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra |
scientific article |
Statements
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra (English)
0 references
1985
0 references
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)].
0 references
minimal nontrivial congruences
0 references
subalgebras
0 references
ideals
0 references
finite algebra
0 references
algorithms
0 references
simple
0 references
subdirectly irreducible
0 references