Factorizable inverse monoids

Factorizable inverse monoids constitute the algebraic theory of those partial symmetries which are restrictions of automorphisms; the formal definition is that each element is the product of an idempotent and an invertible. This class of monoids has theoretical significance, and includes concrete instances which are important in various contexts. This survey is organised around the idea of group acts on semilattices and contains a large range of examples. Topics also include methods for construction of factorizable inverse monoids, and aspects of their inner structure, morphisms, and presentations.     

Partially commutative inverse monoids

Free partially commutative inverse monoids are investigated. As in the case of free partially commutative monoids or groups (trace monoids or graph groups), free partially commutative inverse monoids are defined as quotients of free inverse monoids modulo a partially defined commutation relation on the generators. A quasi linear time algorithm for the word problem is presented. More precisely, we give an algorithm for a RAM. -completeness of the submonoid membership problem (also known as the generalized word problem) and the membership problem for rational sets is shown. Moreover, free partially commutative inverse monoids modulo a finite idempotent presentation are studied. It turns out that the word problem is decidable if and only if the complement of the partial commutation relation is transitive. The work on this paper has been supported by the DFG research project GELO (Graphen mit entscheidbaren Logiken).     

Infinite dual symmetric inverse monoids

Let \({\mathcal {I}}^*_X\) be the dual symmetric inverse monoid on an infinite set X. We show that \({\mathcal {I}}^*_X\) may be generated by the symmetric group \({\mathcal {S}}_X\) together with two (but no fewer) additional block bijections, and we classify the pairs \(\alpha ,\beta \in {\mathcal {I}}^*_X\) for which \({\mathcal {I}}^*_X\) is generated by \({\mathcal {S}}_X\,\cup \,\{\alpha ,\beta \}\). Among other results, we show that any countable subset of \({\mathcal {I}}^*_X\) is contained in a 4-generated subsemigroup of \({\mathcal {I}}^*_X\), and that the length function on \({\mathcal {I}}^*_X\) (and its finitary power semigroup) is bounded with respect to any generating set.     

Invariant means

Let m and M be symmetric means in two and three variables, respectively. We say that M is type 1 invariant with respect to m if M(m(a,c),m(a,b),m(b,c))≡M(a,b,c). If m is strict and isotone, then we show that there exists a unique M which is type 1 invariant with respect to m. In particular, we discuss the invariant logarithmic mean L₃, which is type 1 invariant with respect to L(a,b)=(b−a)/(logb−loga). We say that M is type 2 invariant with respect to m if M(a,b,m(a,b))≡m(a,b). We also prove existence and uniqueness results for type 2 invariance, given the mean M(a,b,c). The arithmetic, geometric, and harmonic means in two and three variables satisfy both type 1 and type 2 invariance. There are means m and M such that M is type 2 invariant with respect to m, but not type 1 invariant with respect to m (for example, the Lehmer means). L₃ is type 1 invariant with respect to L, but not type 2 invariant with respect to L.     

Generation of infinite factorizable inverse monoids

We investigate the generation of factorizable inverse monoids, paying special attention to the factorizable parts of the symmetric and dual symmetric inverse monoids. Key ideas covered include rank, relative rank, Sierpiński rank, and the semigroup Bergman property. The results for finite monoids are well-known or follow quickly from well-known facts, so most of the paper concerns the infinite case.     

Nonlinearity of Some Invariant Boolean Functions

One of the hardest problems in coding theory is to evaluate the covering radius of first order Reed–Muller codes RM(1,m), and more recently the balanced covering radius for crypto graphical purposes. The aim of this paper is to present some new results on this subject. We mainly study boolean functions invariant under the action of some finite groups, following the idea of Patterson and Wiedemann [The covering radius of the (1, 15) Reed-Muller Code is atleast 16276. IEEE Trans Inform Theory. Vol. 29 (1983) 354.]. Our method is Fourier transforms and our results are both theoretical and numerical.     

The word problem for nilpotent inverse monoids

The concept ofk-nilpotency is adapted for inverse semigroups andN _k(X) is defined as the largestk-nilpotent Rees quotient of the free inverse monoid onX. The membership problem is solved for a certain class of ideals of quasifree inverse monoids. As a consequence, the word problem is shown to be decidable for every finite relation onN _k (X), producing an unusual example of total decidability. The author acknowledges support from JNICT-Project SAL (PBIC/C/CEN/1021/92) and ESPRIT-BRA Working Group 6317 “ASMICS”.     

On F-inverse covers of inverse monoids

It is shown that each finite inverse monoid admits a finite F-inverse cover if and only if the same is true for each finite combinatorial strict inverse semigroup with an identity adjoined if and only if the same is true for the Margolis-Meakin expansion M(H) of each finite elementary abelian p-group H for some prime p. Additional equivalent conditions are given in terms of the existence of locally finite varieties of groups having certain properties. Ultimately, the problem of whether each finite inverse monoid admits a finite F-inverse cover, is reduced to a question concerning the Kostrikin-Zelmanov varieties K_n of all locally finite groups of exponent dividing n.     

On clones, transformation monoids, and finite Boolean algebras

We prove that, for a finite Boolean algebra, there exist only finitely many clones which consist of polynomial functions of the algebra and contain the monoid of its unary polynomial functions. Received January 7, 2000; accepted in final form December 13, 2000.     

Invariant means on double coset spaces

In this paper we study invariant means on and amenability of double coset spaces. We prove the amenability of Gelfand pairs. As an application we prove a stability theorem for a functional equation related to spherical functions.     

On the relative solvability of certain inverse monoids

The notion of kernel of a finite monoid relative to a pseudovariety of groups can be used to define relative solvability of monoids in a similar way to the manner in which the notion of derived subgroup can be used to define solvable group. In this paper we study the solvability of certain inverse monoids relative to pseudovarieties of abelian groups.     

The classification of maximal inverse monoids of matrices

Semigroup Forum - Let $${\mathbb {F}}$$ be a field. The set $$M_{n}({\mathbb {F}})$$ of all $$n \times n$$ matrices over $${\mathbb {F}}$$ forms a monoid under usual matrix multiplication. We...     

二元Boolean矩阵的加权Moore-Penrose逆

主要研究了二元Boolean矩阵A的加权Moore-Penrose逆的存在性问题,给出了二元Boolean矩阵A的加权Moore-Penrose逆存在的一些充分必要条件,并讨论了加权Moore-Penrose逆存在时的若干等价刻画及惟一性问题.     

On certain codes admitting inverse semigroups as syntactic monoids

The purpose of this paper is to investigate under what conditions an inverse semigroup M is isomorphic to the syntactic monoid M(A)* of afinite prefix code A over an alphabet X. We find a necessary condition for this to happen. It expresses a precise link between the group of units of M and the maximal subgroups of the 0-minimal ideal of M (Theorem 2.1). The condition is shown to be sufficient in case M is an ideal extension of a Brandt semigroup by a group (Corollary 2.3). We also introduce and study stable codes (products of subsets of the alphabet) and give structural properties of their syntactic monoids (Proposition 3.3 and Theorem 3.5). Most of our results inter-relate structural properties of certain semigroups and divisibility of integers attached to them. The terminology follows [1] and [3].     

AF inverse monoids and the structure of countable MV-algebras

This paper is a further contribution to the developing theory of Boolean inverse monoids. These monoids should be regarded as non-commutative generalizations of Boolean algebras; indeed, classical Stone duality can be generalized to this non-commutative setting to yield a duality between Boolean inverse monoids and a class of étale topological groupoids. MV-algebras are also generalizations of Boolean algebras which arise from many-valued logics. It is the goal of this paper to show how these two generalizations are connected. To do this, we define a special class of Boolean inverse monoids having the property that their lattices of principal ideals naturally form an MV-algebra. We say that an arbitrary MV-algebra can be co-ordinatized if it is isomorphic to an MV-algebra arising in this way. Our main theorem is that every countable MV-algebra can be so co-ordinatized. The particular Boolean inverse monoids needed to establish this result are examples of what we term AF inverse monoids and are the inverse monoid analogues of AF $C^{?}$-algebras. In particular, they are constructed from Bratteli diagrams as direct limits of finite direct products of finite symmetric inverse monoids.