Skip to main content

Research Repository

Advanced Search

The lattice and semigroup structure of multipermutations

Carvalho, Catarina; Martin, Barnaby

The lattice and semigroup structure of multipermutations Thumbnail


Authors

Catarina Carvalho



Abstract

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.

Citation

Carvalho, C., & Martin, B. (2022). The lattice and semigroup structure of multipermutations. International Journal of Algebra and Computation, 32(2), 211-235. https://doi.org/10.1142/s0218196722500096

Journal Article Type Article
Acceptance Date Sep 5, 2021
Online Publication Date Nov 10, 2021
Publication Date 2022-03
Deposit Date Feb 8, 2022
Publicly Available Date Mar 29, 2024
Journal International Journal of Algebra and Computation
Print ISSN 0218-1967
Electronic ISSN 1793-6500
Publisher World Scientific Publishing
Peer Reviewed Peer Reviewed
Volume 32
Issue 2
Pages 211-235
DOI https://doi.org/10.1142/s0218196722500096

Files

Accepted Journal Article (555 Kb)
PDF

Copyright Statement
Electronic version of an article published as International Journal of Algebra and Computation, 30:2,, 2022, 211-235 [10.1142/S0218196722500096] © copyright World Scientific Publishing Company





You might also like



Downloadable Citations