Ordering \(D\)-classes and computing Schein rank is hard

DOI10.1007/BF02574357zbMath0760.20018MaRDI QIDQ1186845

George Markowsky

Publication date: 28 June 1992

Published in: Semigroup Forum (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/135161

zbMATH Keywords

NP-completeprincipal idealbinary matrixSchein ranksemigroup of binary relationsrectangular binary relationBoolean sum

Mathematics Subject Classification ID

Ideal theory for semigroups (20M12) Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Algebraic systems of matrices (15A30) Other classical set theory (including functions, relations, and set algebra) (03E20)

Related Items

Rank functions of tropical matrices ⋮ The complexity of Boolean matrix root computation ⋮ Unnamed Item ⋮ Mitsch's order and inclusion for binary relations and partitions. ⋮ Ranks of fuzzy matrices. Applications in state reduction of fuzzy automata ⋮ On the potential divisibility of matrices over distributive lattices ⋮ Covering in the set of principal ideals in the semigroup of binary relations

Cites Work

• A maximal chain of principal ideals in the semigroup of binary relations on a finite set
• Unnamed Item