Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras. (English) Zbl 0486.08003


08A30 Subalgebras, congruence relations
08-04 Software, source code, etc. for problems pertaining to general algebraic systems
68Q25 Analysis of algorithms and problem complexity
Full Text: EuDML


[1] A. V. Aho J. E. Hopcroft J. D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts 1974. · Zbl 0326.68005
[2] G. Birkhoff: Subdirect unions in universal algebra. Bull. Amer. Math. Soc. 50 (1944), 764-768. · Zbl 0060.05809
[3] M. Demlová J. Demel V. Koubek: On subdirectly irreducible automata. RAIRO Inform. Theor. 15 (1981), 23-46. · Zbl 0482.68050
[4] M. Demlová J. Demel V. Koubek: Several algorithms for finite algebras. Fundamentals of Computation Theory 1979 (L. Budach, Akademie-Verlag, Berlin 1979, 99-104.
[5] M. Demlová J. Demel V. Koubek: Algorithms constructing minimal objects in algebras. · Zbl 0568.08002
[6] G. Grätzer: Universal Algebra. D. Van Nostrand Company, Princeton, N.J. 1968. · Zbl 0182.34201
[7] J. Hartmanis R. E. Stearns: Algebraic Structure Theory of Sequential Machines. Prentice-Hall Inc., Englewood Cliffs, N.J. 1966. · Zbl 0154.41701
[8] J. E. Hopcroft: An n log n algorithm for minimizing states in a finite automaton. Theory of Machines and Computations (Z. Kohavi, A. Paz, Academic Press, New York 1971, 189-196.
[9] J. E. Hopcroft R. M. Karp: An Algorithm for Testing the Equivalence of Finite Automata. TR-71-114. Dept. of Computer Science, Cornell University, Ithaca, N.Y. 1971.
[10] R. E. Tarjan: Efficiency of a good but not linear disjoint set union algorithm. J. Assoc. Comput. Mach. 22 (1975), 215-225. · Zbl 0307.68029
[11] R. E. Tarjan: Reference machines require non-linear time to maintain disjoint sets. Proc. 9th Annual ACM Symposium on Theory of Computing, Boulder, Colorado 1977, 18-29.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.