A solvable conjugacy problem for finitely presented C(3) semigroups

In his thesis, Remmers (Thesis, Univ. of Mich., 1971), introduced semigroup derivation diagrams and used them to prove that the word problem for finitely presented C(3) semigroups was solvable. In this article we introduce the annular analog of semigroup derivation diagrams and use them to demonstrate the solution to a conjugacy problem for finitely presented C(3) semigroups.     

Free products and the word problem

An example is given to show that even in a variety whose free word problem (identity problem) is solvable, the free product of two recursive presentations with solvable word problems may have unsolvable word problem. Under some extra conditions on the syntax of the identities defining the variety however, the free product is shown to preserve solvability of the word problem for recursive presentations. The conditions can be checked mechanically, and common varieties such as semigroups and groups satisfy them, as well as many less familiar varieties. The results are obtained by using rewrite-completion techniques.Presented by Ralph Freese.     

On some presentations of completely regular semigroups

In this paper we consider three types of presentations of completely regular semigroups. In each of the considered cases the solution of the word problem can be reduced to the solution of the word problem for a corresponding group presentation. As a consequence, in each of these cases the one relator presentation has a solvable word problem.     

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.     

Efficient solution of the word problem in slim varieties

Certain varieties similar to commutative semigroups are shown to have uniformly solvable word problem for all finite presentations by a confluence-completion method.Presented by H. P. Gumm.     

Regular principal factors in free objects in Rees-Sushkevich varieties

In a previous paper, the author showed how to associate a completely 0-simple semigroup with a connected bipartite graph containing labelled edges. In the main theorem, it is shown how these fundamental semigroups can be used to describe the regular principal factors of the free objects in certain Rees-Sushkevich varieties, namely, the varieties of semigroups that are generated by all completely 0-simple semigroups over groups in a variety of finite exponent. This approach is then used to solve the word problem for each of these varieties for which the corresponding group variety has solvable word problem.     

Generalized small cancellation theory and applications I. The word problem

In this paper we develop a generalization of the small cancellation theory. The usual small cancellation hypotheses are replaced by some condition that, roughly speaking, says that if a common part of two relations is a big piece of one relation then it must be a very small piece of another. In particular, we show that a finitely presented generalized small cancellation group has a solvable word problem. The machinery developed in the paper is to be used in the following papers of this series for constructing some group-theoretic examples.     

Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets

In this paper, a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from a Euclidean space is considered. Minimization of the sum over all required subsets of the sum of the squared distances from the elements of these subsets to their geometric centers is used as the search criterion. It is proved that if the coordinates of the input points are integer and the space dimension and the number of required subsets are fixed (i.e., bounded by some constants), the problem is a pseudopolynomial time solvable one.     

Fixed Point Methods for the Complementarity Problem

This paper is concerned with iterative procedures for the monotone complementarity problem. Our iterative methods consist of finding fixed points of appropriate continuous maps. In the case of the linear complementarity problem, it is shown that the problem is solvable if and only if the sequence of iterates is bounded in which case summability methods are used to find a solution of the problem. This procedure is then used to find a solution of the nonlinear complementarity problem satisfying certain regularity conditions for which the problem has a nonempty bounded solution set.     

On the invariance of small overlap hypotheses

Suppose thtS is a semigroup with a finite presentation (X; R). John Remmers has proved that the word problem for the presentation (X; R) is solvable if the presentation satisfies a certain small overlap hypothesis,C(n), forn≥3. Here we prove that, with trivial but numerous exceptions, if (X ₁;R ₁) and (X ₂;R ₂) are both finite presentations forS which satisfyC(2), then forn≥2, (X ₁;R ₁) satisfiesC(n) if and only if (X ₂;R ₂) satisfiesC(n).     

Completely Simple Semigroups,Lie Algebras,and the Road Coloring Problem

Consider a semigroup generated by matrices associated with an edge-coloring of a strongly connected, aperiodic digraph. We call the semigroup Lie-solvable if the Lie algebra generated by its elements is solvable. We show that if the semigroup is Lie-solvable then its kernel is a right group. Next, we study the Lie algebra generated by the kernel. Lie algebras generated by two idempotents are analyzed in detail. We find that these have homomorphic images that are generalized quaternion algebras. We show that if the kernel is not a direct product, then the Lie algebra generated by the kernel is not solvable by describing the structure of these algebras. Finally, we discuss an infinite class of examples that are shown to always produce strongly connected aperiodic digraphs having kernels that are not right groups.     

J rgens结果的一个新证明

文章研究有界线性算子半群的扰动问题 .在一定条件下 ,我们表明 :设算子 B生成最终依范连续半群 S(t) (t τ) ,K是有界线性算子 .如果‖ K R(σ+iτ,B) K‖→ 0 ,τ→∞ ,那么算子 A =B +K生成的半群 T(t) ,t>2τ是依范连续的 .我们将此结果应用于迁移算子 ,给出 J rgens结果的一个新证明 .     

Presentations for subsemigroups of finitely generated commutative semigroups

We introduce the concept of presentation for subsemigroups of finitely generated commutative semigroups, which extends the concept of presentation for finitely generated commutative semigroups. We show that for every subsemigroup of a finitely generated commutative semigroup there are special presentations which solve the word problem in the given subsemigroup. Some properties like being cancellative, reduced and/or torsion free are studied under this new point of view. This paper was supported by the project DGES PB96-1424.     

Normal forms for semigroup amalgams

We define a class of inverse semigroup amalgams and derive normal forms for the amalgamated free products in the variety of semigroups. The class includes all amalgams of finite inverse semigroups, recently studied by Cherubini, Jajcayova, Meakin, Nuccio, Piochi and Rodaro (2005–2014), and lower bounded amalgams, that were introduced by the author (1997). We provide sufficient conditions for decidable word problem. We show that the word problem is decidable for an amalgamated free product of finite inverse semigroups. The normal forms can be used to study amalgams in subvarieties of inverse semigroups. In a forthcoming paper by the author, the results are used for varieties of semilattices of groups.     

On finiteness conditions for Rees matrix semigroups

Let T=[S; I; J; P] be a Rees matrix semigroup where S is a semigroup, I and J are index sets, and P is a J × I matrix with entries from S, and let U be the ideal generated by all the entries of P. If U has finite index in S, then we prove that T is periodic (locally finite) if and only if S is periodic (locally finite). Moreover, residual finiteness and having solvable word problem are investigated.     

Module derivation problem for inverse semigroups

The derivation problem for a locally compact group G asserts that each bounded derivation from L ¹(G) to L ¹(G) is implemented by an element of M(G). Recently a simple proof of this result was announced. We show that basically the same argument with some extra manipulations with idempotents solves the module derivation problem for inverse semigroups, asserting that for an inverse semigroup S with set of idempotents E and maximal group homomorphic image G _S , if E acts on S trivially from the left and by multiplication from the right, any bounded module derivation from ? ¹(S) to ? ¹(G _S ) is inner.     

Semigroups of Herz–Schur multipliers

In order to investigate the relationship between weak amenability and the Haagerup property for groups, we introduce the weak Haagerup property, and we prove that having this approximation property is equivalent to the existence of a semigroup of Herz–Schur multipliers generated by a proper function (see Theorem 1.2). It is then shown that a (not necessarily proper) generator of a semigroup of Herz–Schur multipliers splits into a positive definite kernel and a conditionally negative definite kernel. We also show that the generator has a particularly pleasant form if and only if the group is amenable. In the second half of the paper we study semigroups of radial Herz–Schur multipliers on free groups. We prove that a generator of such a semigroup is linearly bounded by the word length function (see Theorem 1.6).     

The word problem for some classes of Adian inverse semigroups

We show that all of the Schützenberger complexes of an Adian inverse semigroup are finite if the Schützenberger complex of every positive word is finite. This enables us to solve the word problem for certain classes of Adian inverse semigroups (and hence for the corresponding Adian semigroups and Adian groups).     

Positive reynolds operators and generating derivations

It is shown that the spectrum of a positive Reynolds operator on C₀(X) is contained in the disc centered at 1/2 with radius 1/2. Moreover, every positive Reynolds operator T with dense range is injective. In this case, the operator D = 1 — T^?1 is a densely defined derivation, which generates a one — parameter semigroup of algebra homomorphisms. This semigroup yields an integral representation of T. Along the way, it is proved that a densely defined closed derivation D generates a semigroup if, and only if, R(1, D) exists and is a positive operator.     

On the complexity of the word problem for automaton semigroups and automaton groups

In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.A detailed listing of the contributions of this paper can be found at the end of this paper.