The lattice and semigroup structure of multipermutations

DOI10.1142/S0218196722500096MaRDI QIDQ5063206zbMATH OpenOpenAlexFDO

Authors

Publication date 17 March 2022

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.06012

zbMATH Keywords

binary relationGalois connectionmodel-checking problem

Mathematics Subject Classification ID

Equational classes, universal algebra in model theory (03C05) Structure theory of lattices (06B05) General structure theory for semigroups (20M10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Binary Relations and Permutation Groups
• Multigroups
• scientific article; zbMATH DE number 1057702
• scientific article; zbMATH DE number 900393
• Every semigroup is isomorphic to a transitive semigroup of binary relations

Cites work

• A proof of Devadze's theorem on generators of the semigroup of Boolean matrices.
• A proof of the CSP dichotomy conjecture
• Algebraic approach to promise constraint satisfaction
• An algebraic theory of complexity for discrete optimization.
• Basics of Galois Connections
• Closed systems of functions and predicates
• Every semigroup is isomorphic to a transitive semigroup of binary relations
• Factor-powers of finite symmetric groups
• Galois theory for minors of finite functions
• GREEN'S RELATIONS ON THE SEMIGROUP OF BINARY RELATIONS
• How can representation theories of inverse semigroups and lattices be united?
• scientific article; zbMATH DE number 1057702 (Why is no real title available?)
• scientific article; zbMATH DE number 1992703 (Why is no real title available?)
• scientific article; zbMATH DE number 3203829 (Why is no real title available?)
• scientific article; zbMATH DE number 3353590 (Why is no real title available?)
• scientific article; zbMATH DE number 3184994 (Why is no real title available?)
• Inverses of Boolean matrices
• Log Space Recognition and Translation of Parenthesis Languages
• Multigroups
• On the complexity of the model checking problem
• ON THE PARTITION MONOID AND SOME RELATED SEMIGROUPS
• On the semigroup of binary relations
• Primes in the semigroup of Boolean matrices
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• QCSP monsters and the demise of the chen conjecture
• Regular elements of the semigroup of all binary relations
• Relations binaires, fermetures, correspondances de Galois
• Representation of inverse semigroups by local automorphisms and multi- automorphisms of groups and rings
• Semigroups admitting relative inverses
• The complexity of constraint satisfaction games and QCSP
• The complexity of general-valued CSPs
• The complexity of positive first-order logic without equality
• The semigroup of Hall relations
• Total multifunctions and relations

Cited in

(3)

• scientific article; zbMATH DE number 1254499 (Why is no real title available?)
• SIMULTANEOUS REPRESENTATIONS OF SEMILATTICES BY LATTICES WITH PERMUTABLE CONGRUENCES
• Minimal generating sets for matrix monoids

Describes a project that uses

Uses Software

• Semigroups
• GAP

This page was built for publication: The lattice and semigroup structure of multipermutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5063206)