TY - JOUR

T1 - The lattice and semigroup structure of multipermutations

AU - Carvalho, Catarina

AU - Martin, Barnaby

N1 - Publisher Copyright:
© 2021 World Scientific Publishing Company.

PY - 2021/11/10

Y1 - 2021/11/10

N2 - We study the algebraic properties of binary relations whose underlying digraph is smooth, that is, has no source or sink. Such objects have been studied as surjective hyper-operations (shops) on the corresponding vertex set, and as binary relations that are defined everywhere and whose inverse is also defined everywhere. In the latter formulation, they have been called multipermutations. We study the lattice structure of sets (monoids) of multipermutations over an n-element domain. Through a Galois connection, these monoids form the algebraic counterparts to sets of relations closed under definability in positive first-order logic without equality. We show one side of this Galois connection, and give a simple dichotomy theorem for the evaluation problem of positive first-order logic without equality on the class of structures whose preserving multipermutations form a monoid closed under inverse. These problems turn out either to be in Logspaceor to be Pspace-complete. We go on to study the monoid of all multipermutations on an n-element domain, under usual composition of relations. We characterize its Green relations, regular elements and show that it does not admit a generating set that is polynomial on n.

AB - We study the algebraic properties of binary relations whose underlying digraph is smooth, that is, has no source or sink. Such objects have been studied as surjective hyper-operations (shops) on the corresponding vertex set, and as binary relations that are defined everywhere and whose inverse is also defined everywhere. In the latter formulation, they have been called multipermutations. We study the lattice structure of sets (monoids) of multipermutations over an n-element domain. Through a Galois connection, these monoids form the algebraic counterparts to sets of relations closed under definability in positive first-order logic without equality. We show one side of this Galois connection, and give a simple dichotomy theorem for the evaluation problem of positive first-order logic without equality on the class of structures whose preserving multipermutations form a monoid closed under inverse. These problems turn out either to be in Logspaceor to be Pspace-complete. We go on to study the monoid of all multipermutations on an n-element domain, under usual composition of relations. We characterize its Green relations, regular elements and show that it does not admit a generating set that is polynomial on n.

KW - Galois connection

KW - binary relation

KW - model-checking problem

UR - http://www.scopus.com/inward/record.url?scp=85114929122&partnerID=8YFLogxK

U2 - 10.1142/S0218196722500096

DO - 10.1142/S0218196722500096

M3 - Article

VL - 32

JO - International Journal of Algebra and Computation

JF - International Journal of Algebra and Computation

SN - 0218-1967

IS - 2

ER -