Narrow Results

Let $1\le k\le n$. We denote by ${{𝒪}{ℰ}}_{n,k}$ the monoid of all order-preserving k-extensive full transformations on $\{1,\dots ,n\}$ ordered in the standard way. In this paper, it is shown that ${{𝒪}{ℰ}}_{n,k}$ is not a regular semigroup in general, but it is an abundant semigroup. Moreover, we prove that ${{𝒪}{ℰ}}_{n,k}$ is idempotent-generated and compute the idempotent rank and rank of the monoid ${{𝒪}{ℰ}}_{n,k}$. Moreover, we determine the maximal idempotent generated subsemigroups of the monoid ${{𝒪}{ℰ}}_{n,k}$.

Ordered trees are generally drawn using order-preserving planar straight-line grid drawings. We investigate the area-requirements of such drawings and present several results. Let T be an ordered tree with n nodes. We show that:

• T admits an order-preserving planar straight-line grid drawing with O(n log n) area.

• If T is a binary tree, then T admits an order-preserving planar straight-line grid drawing with O(n loglog n) area.

• If T is a binary tree, then T admits an order-preserving upward planar straight-line grid drawing with optimalO(n log n) area.

We also study the problem of drawing binary trees with user-specified aspect ratios. We show that an ordered binary tree T with n nodes admits an order-preserving planar straight-line grid drawing with area O(n log n), and any user-specified aspect ratio in the range [1,n/log n]. All the drawings mentioned above can be constructed in O(n) time.

Let ${{𝒪}}_n$ be the semigroup of all singular order-preserving mappings on the finite set $X_n=\{1,2,\dots ,n\}$. It is known that ${{𝒪}}_n$ is generated by its set of idempotents of rank $n-1$, and its rank and idempotent rank are $n$ and $2n-2$, respectively. In this paper, we study the structure of the semigroup generated by any nonempty subset of idempotents of rank $n-1$ in ${{𝒪}}_n$. We also calculate its rank and idempotent rank.

The purpose of this paper is the study of congruences on semigroups of transformations on a countably infinite fence. We consider the monoid $O_{\mathbb{N}}$ of all full transformations on the set $\mathbb{N}$ of all natural numbers preserving the zig-zag order on $\mathbb{N}$, as well as the monoid $E(O_{\mathbb{N}}^{\ast })$ of all idempotent transformations in $O_{\mathbb{N}}$ additionally preserving the usual linear order on $\mathbb{N}.$ We show that there are uncountably many congruences on $O_{\mathbb{N}}$ and determine seven maximal congruences on $O_{\mathbb{N}},$ which are all the maximal congruences containing a particular congruence on $O_{\mathbb{N}}.$ Moreover, we characterize all congruences on the monoid of all transformations in $E(O_{\mathbb{N}}^{\ast })$ with infinite rank. For the semigroup of all transformations in $E(O_{\mathbb{N}}^{\ast })$ with finite rank, we determine the Rees congruences.

Let $X=\{1,\dots ,n\}$ be a finite chain and let ${𝒫}{𝒪}{ℐ}(X)$ be the semigroup of all injective order-preserving partial transformations on $X$. For any nonempty subset $Y$ of $X$, let ${𝒫}{𝒪}{ℐ}(X,Y)$ be the subsemigroup of ${𝒫}{𝒪}{ℐ}(X)$ of all transformations with range contained in $Y$. In this paper, we characterize Green’s relations on ${𝒫}{𝒪}{ℐ}(X,Y)$, and show that the semigroup ${𝒫}{𝒪}{ℐ}(X,Y)$ is left abundant but not right abundant when $Y$ is a proper subset of $X$. Moreover, the cardinality and the rank of the semigroup ${𝒫}{𝒪}{ℐ}(X,Y)$ is determined.

In this paper, we characterize the monoid of endomorphisms of the semigroup of all monotone full transformations of a finite chain, as well as the monoids of endomorphisms of the semigroup of all monotone partial transformations and of the semigroup of all monotone partial permutations of a finite chain.

In this paper we present a division theorem for the pseudovariety of semigroups 𝖮𝖣 (𝖮𝖱) generated by all semigroups of order-preserving or order-reversing (orientation-preserving or orientation-reversing) full transformations on a finite chain.

In this paper we describe locally maximal idempotent-generated subsemigroups of finite orientation-preserving singular partial transformation semigroups SPOP_n and obtain a complete classification. We also obtain a classification of locally maximal idempotent-generated subsemigroups of finite order-preserving singular partial transformation semigroups with respect to ≤_k.

For n ∈ ℕ, let O_n be the semigroup of all singular order-preserving mappings on [n]= {1,2,…,n}. For each nonempty subset A of [n], let O_n(A) = {α ∈ O_n: (∀ k ∈A) kα ≤ k} be the semigroup of all order-preserving and A-decreasing mappings on [n]. In this paper it is shown that O_n(A) is an abundant semigroup with n-1𝒟*-classes. Moreover, O_n(A) is idempotent-generated and its idempotent rank is 2n-2- |A\ {n}|. Further, it is shown that the rank of O_n(A) is equal to n-1 if 1 ∈ A, and it is equal to n otherwise.

It is well-known that the transformation semigroup $T(X)$ is regular, but their subsemigroups need not be. A fence is an ordered set that the order forms a path with alternating orientation. Consider $X$ as the base set of a fence $X=(X;\le )$. Two subsemigroups of $T(X)$ are studied. Namely, the semigroup $DT(X)$ of all order-decreasing self-mappings of $X$ and the semigroup $OT(X)$ of all order-preserving self-mappings of $X$. In this paper, we obtain that $DT(X)$ is a coregular subsemigroup of $T(X)$. A characterization of regular subsemigroups $OT(X)$ of $T(X)$ is given, that is, $OT(X)$ is regular if and only if $\left|X\right|\le 4$. Finally, we discuss the regularity of elements in $OT(X)$.

The monoid of all partial injections on a finite set (the symmetric inverse semigroup) is of particular interest because of the well-known Wagner–Preston Theorem. Let $n$ be a positive natural number and ${\mathrm{\text{PFI}}}_n$ be the semigroup of all fence-preserving partial one-to-one maps of $\{1,\dots ,n\}$ into itself with respect to composition of maps and the fence $1\prec 2\succ 3\prec \cdots n$. There is considered the inverse semigroup ${\mathrm{\text{IOF}}}_n^{\mathrm{\text{par}}}$ of all $\alpha \in {\mathrm{\text{PFI}}}_n$ such that $\alpha$ is regular in ${\mathrm{\text{PFI}}}_n$, order-preserving with respect to the order $1<2<\cdots <n$ and parity-preserving. According to the main result of the paper, it is $3n-6$ the least of the cardinalities of the generating sets of ${\mathrm{\text{IOF}}}_n^{\mathrm{\text{par}}}$ for $4\le n$. There is determined a concrete representation of a generating set of minimal size.

In this paper, we study the cyclic inverse monoid ${{𝒞}{ℐ}}_n$ on a set ${\mathrm{\Omega }}_n$ with $n$ elements, i.e. the inverse submonoid of the symmetric inverse monoid on ${\mathrm{\Omega }}_n$ consisting of all restrictions of the elements of a cyclic subgroup of order $n$ acting cyclically on ${\mathrm{\Omega }}_n$. We show that ${{𝒞}{ℐ}}_n$ has rank $2$ (for $n\ge 2$) and $n{2}^n-n+1$ elements. Moreover, we give presentations of ${{𝒞}{ℐ}}_n$ on $n+1$ generators and $\frac{1}{2}(n^2+3n+4)$ relations and on $2$ generators and $\frac{1}{2}(n^2-n+6)$ relations. We also consider the remarkable inverse submonoid ${{𝒪}{𝒞}{ℐ}}_n$ of ${{𝒞}{ℐ}}_n$ constituted by all its order-preserving transformations. We show that ${{𝒪}{𝒞}{ℐ}}_n$ has rank $n$ and $3\cdot 2^n-2n-1$ elements. Furthermore, we exhibit presentations of ${{𝒪}{𝒞}{ℐ}}_n$ on $n+2$ generators and $\frac{1}{2}(n^2+3n+8)$ relations and on $n$ generators and $\frac{1}{2}(n^2+3n)$ relations.