Presentation for the Partial Dual Symmetric Inverse Monoid

We give a monoid presentation in terms of generators and define relations for the partial analogue of the finite dual symmetric inverse monoid.     

Constructing finitely presented monoids which have no finite complete presentation

Squier (1987) showed that if a monoid is defined by a finite complete rewriting system, then it satisfies the homological finiteness condition FP₃, and using this fact he gave monoids (groups) which have solvable word problems but cannot be presented by finite complete systems. In the present paper we show that a monoid cannot have a finite complete presentation if it contains certain special elements. This observation enables us to construct monoids without finite complete presentation in a direct and elementary way. We give a finitely presented monoid which has (1) a word problem solvable in linear time and (2) linear growth but (3) no finite complete presentation. We also give a finitely presented monoid which has (1) a word problem solvable in linear time, (2) finite derivation type in the sense of Squier and (3) the property FP_∞, but (4) no finite complete presentation.     

Comparing Semigroup and Monoid Presentations for Finite Monoids

 It is known that for any finite group G given by a finite group presentation there exists a finite semigroup presentation for G of the same deficiency, i.e. satisfying . It is also known that the analogous statement does not hold for all finite monoids. In this paper we give a necessary and sufficient condition for a finite monoid M, given by a finite monoid presentation, to have a finite semigroup presentation of the same deficiency.     

Knuth’s Coherent Presentations of Plactic Monoids of Type A

We construct finite coherent presentations of plactic monoids of type A. Such coherent presentations express a system of generators and relations for the monoid extended in a coherent way to give a family of generators of the relations amongst the relations. Such extended presentations are used for representations of monoids, in particular, it is a way to describe actions of monoids on categories. Moreover, a coherent presentation provides the first step in the computation of a categorical cofibrant replacement of a monoid. Our construction is based on a rewriting method introduced by Squier that computes a coherent presentation from a convergent one. We compute a finite coherent presentation of a plactic monoid from its column presentation and we reduce it to a Tietze equivalent one having Knuth’s generators.     

Comparing Semigroup and Monoid Presentations for Finite Monoids

 It is known that for any finite group G given by a finite group presentation there exists a finite semigroup presentation for G of the same deficiency, i.e. satisfying . It is also known that the analogous statement does not hold for all finite monoids. In this paper we give a necessary and sufficient condition for a finite monoid M, given by a finite monoid presentation, to have a finite semigroup presentation of the same deficiency. (Received 17 April 2001; in revised form 15 September 2001)     

Catalan monoids,monoids of local endomorphisms,and their presentations

The Catalan monoid and partial Catalan monoid of a directed graph are introduced. Also introduced is the notion of a local endomorphism of a tree, and it is shown that the Catalan (resp. partial Catalan) monoid of a tree is simply its monoid of extensive local endomorphisms (resp. partial endomorphisms) of finite shift. The main results of this paper are presentations for the Catalan and partial Catalan monoids of a tree. Our presentation for the Catalan monoid of a tree is used to give an alternative proof for a result of Higgins. We also identify results of Aîzen?tat and Popova which give presentations for the Catalan monoid and partial Catalan monoid of a finite symmetric chain.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

Coxeter groups,Coxeter monoids and the Bruhat order

Associated with any Coxeter group is a Coxeter monoid, which has the same elements, and the same identity, but a different multiplication. (Some authors call these Coxeter monoids 0-Hecke monoids, because of their relation to the 0-Hecke algebras—the q=0 case of the Hecke algebra of a Coxeter group.) A Coxeter group is defined as a group having a particular presentation, but a pair of isomorphic groups could be obtained via non-isomorphic presentations of this form. We show that when we have both the group and the monoid structure, we can reconstruct the presentation uniquely up to isomorphism and present a characterisation of those finite group and monoid structures that occur as a Coxeter group and its corresponding Coxeter monoid. The Coxeter monoid structure is related to this Bruhat order. More precisely, multiplication in the Coxeter monoid corresponds to element-wise multiplication of principal downsets in the Bruhat order. Using this property and our characterisation of Coxeter groups among structures with a group and monoid operation, we derive a classification of Coxeter groups among all groups admitting a partial order.     

Ideal Structure of the Kauffman and Related Monoids

The generators of the Temperley-Lieb algebra generate a monoid with an appealing geometric representation. It has been much studied, notably by Louis Kauffman. Borisavljevi?, Do?en, and Petri? gave a complete proof of its abstract presentation by generators and relations, and suggested the name “Kauffman monoid”. We bring the theory of semigroups to the study of a certain finite homomorphic image of the Kauffman monoid. We show the homomorphic image (the Jones monoid) to be a combinatorial and regular *-semigroup with linearly ordered ideals. The Kauffman monoid is explicitly described in terms of the Jones monoid and a purely combinatorial numerical function. We use this to describe the ideal structure of the Kauffman monoid and two other of its homomorphic images.     

A deterministic algorithm to decide if a finitely presented abelian monoid is cancellative

In this paper we give an algorithm to compute a finite presentation for any finitely generated commutative cancellative monoid, and in particular we apply it to derive an algorithm to decide whether a finitely presented commutative monoid is cancellative or not.     

On Finite Complete Presentations and Exact Decompositions of Semigroups

We prove that given a finite (zero) exact right decomposition (M, T) of a semigroup S, if M is defined by a finite complete presentation, then S is also defined by a finite complete presentation. Exact right decompositions are natural generalizations to semigroups of coset decompositions in groups. As a consequence, we deduce that any Zappa–Szép extension of a monoid defined by a finite complete presentation, by a finite monoid, is also defined by such a presentation.

It is also proved that a semigroup M ⁰[A; I, J; P], where A and P satisfy some very general conditions, is also defined by a finite complete presentation.     

The monoid of ordered partitions of a natural number

The sequences of non-negative integers form a monoid, a natural submonoid of which has elements corresponding to order-preserving transformations of a finite chain. This, in turn, has a submonoid whose elements are ordered partitions of a natural number. A presentation for the last monoid is given, and the inclusion poset of principal right ideals is described. The poset of principal left ideals has a recursive structure that gives rise to an interesting sequence of numbers.     

Idempotent-Conjugate Monoids with Nilpotent Unit Groups

Let M be a finite monoid with unit group G such that J-related idempotents in M are conjugate. If G is nilpotent, we prove that the complex monoid algebra CM of M is semisimple if and only if M is an inverse monoid. Conversely let G be a finite group such that for any finite idempotent-conjugate monoid M with unit group G, CM semisimple implies that M is an inverse monoid. We then show that G is a nilpotent group.     

On the inverse braid and reflection monoids of type <Emphasis Type="Italic">B</Emphasis>

There are well-known relations between braid and symmetric groups as well as Artin-Brieskorn braid groups and Coxeter groups: the latter are the factor-groups of the Artin-Brieskorn braid groups. The inverse braid monoid is related to the inverse symmetric monoid in the same way. We show that similar relations exist between the inverse braid monoid of type B and the inverse reflection monoid of type B. This gives a presentation of the latter monoid.     

On the singular braid monoid of an orientable surface

In this paper we show that the singular braid monoid of an orientable surface can be embedded in a group. The proof is purely topological, making no use of the monoid presentation.

     

Inverse monoids and rational Schreier subsets of the free group

An inverse monoidM is an idempotent-pure image of the free inverse monoid on a setX if and only ifM has a presentation of the formM=Inv<X:e_o=f_i, i∈I>, wheree _i ,f _i are idempotents of the free inverse monoid: every inverse monoid is an idempotent-separating image of one of this type. IfR is anR-class of such an inverse monoid, thenR may be regarded as a Schreier subset of the free group onX. This paper is concerned with an examination of which Schreier subsets arise in this way. In particular, ifI is finite, thenR is a rational Schreier subset of the free group. Not every rational Schreier set arises in this way, but every positively labeled rational Schreier set does. Research supported by National Science Foundation grant #DMS8702019.     

A conjugacy invariant for reducible sofic shifts and its semigroup characterizations

We introduce a notion of magic words and, through them, we present a lattice of sub-synchronizing subshifts which describes the synchronizing parts of a sofic shiftS. We show that topological conjugacy maps subsynchronizing subshifts onto sub-synchronizing subshifts, it preserves their mutual relationship (i.e. the corresponding lattices are isomorphic) and the corresponding covers within the Krieger covers are topologically conjugate. Using the magic words, a full characterization of the syntactic monoid of a shift of finite type is given. We show that a synchronizing deterministic presentation of every sub-synchronizing subshift ofS can be seen within a two-sided ideal of the syntactic monoid ofS.     

Complexity issues of checking identities in finite monoids

We study the computational complexity of checking identities in a fixed finite monoid. We find the smallest monoid for which this problem is coNP-complete and describe a significant class of finite monoids for which the problem is tractable.     

一类模糊逻辑系统幺半群与同态映射

首先利用代数中幺半群的概念给出了模糊逻辑系统专业领域的概念, 建立专业领域概念的目的是为了规范模糊逻辑系统中语言变量的取值范围, 从而将模糊逻辑系统看作是某个笛卡儿乘积幺半群的有限子集. 然后利用这个笛卡儿乘积幺半群的乘积运算构造了模糊逻辑系统幺半群. 最后, 在一定的约定条件下证明了通常使用的一类Mamdani形模糊逻辑系统的输出可以看作是从模糊逻辑系统幺半群到连续函数域的同态映射.     

Double Catalan monoids

In this paper, we define and study what we call the double Catalan monoid. This monoid is the image of a natural map from the 0-Hecke monoid to the monoid of binary relations. We show that the double Catalan monoid provides an algebraization of the (combinatorial) set of 4321-avoiding permutations and relate its combinatorics to various off-shoots of both the combinatorics of Catalan numbers and the combinatorics of permutations. In particular, we give an algebraic interpretation of the first derivative of the Kreweras involution on Dyck paths, of 4321-avoiding involutions and of recent results of Barnabei et al. on admissible pairs of Dyck paths. We compute a presentation and determine the minimal dimension of an effective representation for the double Catalan monoid. We also determine the minimal dimension of an effective representation for the 0-Hecke monoid.