On the syntactic algorithm for the word problem of left distributivity

Here we investigate the ‘natural’ syntactic algorithm for the word problem of left distributivity, and we establish a sufficient condition which explains the convergence for all terms of a reasonable size. An algorithm for left division is also constructed. Received February 8, 1996; accepted in final form October 3, 1996     

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”.     

The word problem for one-relation monoids: a survey

This survey is intended to provide an overview of one of the oldest and most celebrated open problems in combinatorial algebra: the word problem for one-relation monoids. We provide a history of the problem starting in 1914, and give a detailed overview of the proofs of central results, especially those due to Adian and his student Oganesian. After showing how to reduce the problem to the left cancellative case, the second half of the survey focuses on various methods for solving partial cases in this family. We finish with some modern and very recent results pertaining to this problem, including a link to the Collatz conjecture. Along the way, we emphasise and address a number of incorrect and inaccurate statements that have appeared in the literature over the years. We also fill a gap in the proof of a theorem linking special inverse monoids to one-relation monoids, and slightly strengthen the statement of this theorem.

     

The next step of the word problem over monoids

It is known that a group presentation P can be regarded as a 2-complex with a single 0-cell. Thus we can consider a 3-complex with a single 0-cell which is known as a 3-presentation. Similarly, we can also consider 3-presentations for monoids. In this paper, by using spherical monoid pictures, we show that there exists a finite 3-monoid-presentation which has unsolvable “generalized identity problem” that can be thought as the next step (or one-dimension higher) of the word problem for monoids. We note that the method used in this paper has chemical and physical applications.     

Small overlap monoids I: The word problem

We develop a combinatorial approach to the study of semigroups and monoids with finite presentations satisfying small overlap conditions. In contrast to existing geometric methods, our approach facilitates a sequential left–right analysis of words which lends itself to the development of practical, efficient computational algorithms. In particular, we obtain a highly practical linear time solution to the word problem for monoids and semigroups with finite presentations satisfying the condition $C(4)$, and a polynomial time solution to the uniform word problem for presentations satisfying the same condition.     

On the divisibility problem for one-relator monoids

This work was supported by the Russian Foundation for Fundamental Research (Under Grant No. 93-011-16015).     

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].     

On the finite basis problem for the monoids of partial extensive injective transformations

Let \(PEI_n (POEI_n)\) be the monoid of all partial (order-preserving) extensive and injective transformations over a chain of order n. We give a sufficient condition under which a semigroup is nonfinitely based and apply this condition to show that the monoid \(PEI_3 (POEI_3)\) is nonfinitely based. This together with the results of Edmunds and Goldberg gives a complete answer to the finite basis problem for the monoid \(PEI_n (POEI_n)\): the monoid \(PEI_n (POEI_n)\) is nonfinitely based if and only if \(n\geqslant 3\). Furthermore, it is shown that the monoid \(PEI_n (POEI_n)\) is hereditarily finitely based if and only if \(n\leqslant 2\).     

On a transport problem and monoids of non-negative integers

A problem about how to transport profitably a group of cars leads us to studying the set T formed by the integers n such that the system of inequalities, with non-negative integer coefficients,

$$\begin{aligned} a_1x_1 +\cdots + a_px_p + \alpha \le n \le b_1x_1 +\cdots + b_px_p - \beta \end{aligned}$$

has at least one solution in \({\mathbb N}^p\). We prove that \(T\cup \{0\}\) is a submonoid of \(({\mathbb N},+)\) and, moreover, we give algorithmic processes to compute T.

     

On the Dulac's problem for piecewise analytic vector fields

This paper presents a version of Dulac's Problem for piecewise analytic vector fields that states conditions for the number of limit cycles around certain minimal sets. A suitable model-theoretic structure is introduced under which a qualitative investigation of the problem is settled.     

Finite basis problem for 2-testable monoids

A monoid S ¹ obtained by adjoining a unit element to a 2-testable semigroup S is said to be 2-testable. It is shown that a 2-testable monoid S ¹ is either inherently non-finitely based or hereditarily finitely based, depending on whether or not the variety generated by the semigroup S contains the Brandt semigroup of order five. Consequently, it is decidable in quadratic time if a finite 2-testable monoid is finitely based.     

The varieties of languages corresponding to the varieties of finite band monoids

We describe the varieties of languages corresponding to the varieties of finite band monoids.     

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.