The dual braid monoid

We study a new monoid structure for Artin groups associated with finite Coxeter systems. Like the classical positive braid monoid, the new monoid is a Garside monoid. We give several equivalent constructions: algebraically, the new monoid arises when studying Coxeter systems in a “dual” way, replacing the pair (W,S) by (W,T), with T the set of all reflections; geometrically, it arises when looking at the reflection arrangement from a certain basepoint. In the type A case, we recover the monoid constructed by Birman, Ko and Lee.     

The shifted plactic monoid

We introduce a shifted analog of the plactic monoid of Lascoux and Schützenberger, the shifted plactic monoid. It can be defined in two different ways: via the shifted Knuth relations, or using Haiman’s mixed insertion. Applications include: a new combinatorial derivation (and a new version of) the shifted Littlewood–Richardson Rule; similar results for the coefficients in the Schur expansion of a Schur P-function; a shifted counterpart of the Lascoux–Schützenberger theory of noncommutative Schur functions in plactic variables; a characterization of shifted tableau words; and more.     

The inverse braid monoid

We introduce an inverse monoid which plays a similar role with respect to the symmetric inverse semigroup that the braid group plays with respect to the symmetric group.     

The radical-annihilator monoid of a ring

Kuratowski’s closure-complement problem gives rise to a monoid generated by the closure and complement operations. Consideration of this monoid yielded an interesting classification of topological spaces, and subsequent decades saw further exploration using other set operations. This article is an exploration of a natural analogue in ring theory: a monoid produced by “radical” and “annihilator” maps on the set of ideals of a ring. We succeed in characterizing semiprime rings and commutative dual rings by their radical-annihilator monoids, and we determine the monoids for commutative local zero-dimensional (in the sense of Krull dimension) rings.     

The syntactic monoid of a hypercode

This paper gives a characterization of the syntactic monoid of a hypercode H over a finite alphabet X, a hupercode being a non empty set of non empty words over X, which are pairwise incomparable relatively to the embedding partial order of X. This research has been supported by Grant A7877 of the National Research Council of Canada.     

The geometry monoid of left self-distributivity

We develop a counterpart to Garside's analysis of the braid monoid B_n⁺ relevant for the monoid M_LD that describes the geometry of the left self-distributivity identity. The monoid M_LD extends B_∞⁺, of which it shares many properties, with the exception that it is not a direct limit of finitely generated monoids. By introducing a convenient local version of the fundamental elements Δ, we prove that right least common multiples exist in M_LD, and, more generally, that M_LD resembles a generalized Artin monoid.     

The dimension monoid of a lattice

We introduce the dimension monoid of a lattice L, denoted by Dim L. The monoid Dim L is commutative and conical, the latter meaning that the sum of any two nonzero elements is nonzero. Furthermore, Dim L is given along with the dimension map, D\Delta from L2L to Dim L, which has the intuitive meaning of a distance function. The maximal semilattice quotient of Dim L is isomorphic to the semilattice Con_c L of compact congruences of L; hence Dim L is a precursor of the congruence lattice of L. Here are some additional features of this construction: ¶¶ (1) Our dimension theory provides a generalization to all lattices of the von Neumann dimension theory of continuous geometries. In particular, if L is an irreducible continuous geometry, then Dim L is either isomorphic to \Bbb Z⁺\Bbb Z^+ or to \Bbb R⁺\Bbb R^+.¶ (2) If L has no infinite bounded chains, then Dim L embeds (as an ordered monoid) into a power of \Bbb Z⁺è{￥}.{\Bbb Z}^{+}\cup \{\infty\}.¶ (3) If L is modular or if L has no infinite bounded chains, then Dim L is a refinement monoid.¶ (4) If L is a simple geometric lattice, then Dim L is isomorphic to \Bbb Z⁺\Bbb Z^+, if L is modular, and to the two-element semilattice, otherwise.¶ (5) If L is an à₀\aleph_0-meet-continuous complemented modular lattice, then both Dim L and the dimension function D\Delta satisfy (countable) completeness properties.¶¶ If R is a von Neumann regular ring and if L is the lattice of principal right ideals of the matrix ring M₂ (R), then Dim L is isomorphic to the monoid V (R) of isomorphism classes of finitely generated projective right R-modules. Hence the dimension theory of lattices provides a wide lattice-theoretical generalization of nonstable K-theory of regular rings.     

The rook monoid is lexicographically shellable

We prove that the Bruhat–Chevalley–Renner order on the rook monoid is EL-shellable. We determine the homeomorphism type of the associated order complex.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

The monoid of strong endomorphisms of a graph

We explicitly find all the idempotents in eachL(R)-class and all the inverses of each element of the strong endomorphism monoid of a graph. The number of these idempotents and inverses is also obtained. The author is deeply indebted to Professor Dr. T. E. Hall for his stimulating questions about this theme and much improvement made to an earlier version of this paper. The author would like to thank Professor Dr. U. Knauer and Dr. E. Wilkeit for helpful comments.     

The core congruence on a monoid

The core congruence is defined and its properties studied. It is shown that every fundamental regular monoid can be faithfully represented by its action by translations on its set of left congruences.This research was partially supported by a grant from Tulane University.     

The monoid of orientation-preserving mappings on a chain

We introduce new kinds of regular monoids of transformations consisting of mappings which preserve or reverse the orientation of a finite cycle.     

The acquisition queue

We propose a new queueing model named the acquisition queue. It differs from conventional queueing models in that the server not only serves customers, but also performs acquisition of new customers. The server has to divide its energy between both activities. The number of newly acquired customers is uncertain, and the effect of the server’s acquisition efforts can only be seen after some fixed time period δ (delay). The acquisition queue constitutes a (δ+1)-dimensional Markov chain. The limiting queue length distribution is derived in terms of its probability generating function, and an exact expression for the mean queue length is given. For large values of δ the numerical procedures needed for calculating the mean queue length become computationally cumbersome. We therefore complement the exact expression with a fluid approximation. One of the key features of the acquisition queue is that the server performs more acquisition when the queue is small. Together with the delay, this causes the queue length process to show a strongly cyclic behavior. We propose and investigate several ways of planning the acquisition efforts. In particular, we propose an acquisition scheme that is designed specifically to reduce the cyclic behavior of the queue length process. This research was financially supported by the European Network of Excellence Euro-NGI. The work of the second author was supported in part by a TALENT grant from the Netherlands Organisation for Scientific Research (NWO).