Search

Any finitely generated commutative monoid has a presentation by a finite Noetherian confluent semi-Thue system over a free monoid.

Ehrenfeucht's Conjecture, that each subset S of a finitely generated free monoid has a finite subset T such that if two endomorphisms of the monoid agree on T , then they agree on S , has recently been verified. In this paper we extend this result from endomorphisms to certain types of finite substitutions by applying Konig's Lemma, and embeddings of the monoid into a free algebra.

There exist finitely generated submonoids of a free monoid which are not finitely presented and have even not a finite cancellative presentation. If Σ∗ is the free monoid on the alphabet Σ and if ϱ⊂Σ∗×Σ∗, let m(ϱ) be the smallest congruence of Σ∗ containing ϱ such that the monoid Σ∗⧸m(ϱ) can be embedded in a group. If a monoid M is isomorphic to Σ∗⧸m(ϱ), then (Σ, ϱ) is said to be a Malcev's presentation of M. We shall prove here the following theorem: “Every finitely generated submonoid of a free monoid has a finite Malcev's presentation and such a presentation can be effectively found”. The necessary and sufficient conditions for embedding a semigroup in a group given by A.I. Malcev and a graph for determining the relators are used to prove this theorem.

Homotopy theory for monoid presentations originated by Squier is developed by means of homotopy reduction systems. Two types of asphericity are considered and a relation to the low-dimensional homology is established. If a monoid presentation has a complete homotopy reduction system that is essentially finite, then the monoid has the homology finiteness property FP 4 .

This paper deals with the scattered deletion of a language by another language, i.e. with scattered residuals. We introduce the notion of the scattered syntactical monoid. The main result is a Myhill-Nerode-like theorem for languages L with the property that the commutative closure of L, com ( L ), is a regular language. We investigate some properties of these families of languages related to the cardinality of the scattered syntactical monoid.

Squier (1987) showed that there exist finitely presented monoids with solvable word problem which cannot be presented by finite complete rewriting systems. In the present note we give a finitely presented monoid with solvable word problem which cannot be presented by a regular complete system. We do not use the homological algebra as Squier did. First, we show that if a monoid is presented by a regular complete system and has some property, it has either polynomial or exponential growth. Next, we construct a finitely presented monoid with intermediate growth which satisfies the desired properties.

The purpose of this paper is to introduce the concept of monoid deformations in connection with group representations. The underlying philosophy for finite reductive monoids M is that while M is contained in a modular representation of the unit group G, a deformation M(q) is contained in a complex representation of G. This is worked out in detail in the case of the Steinberg representation.

We present a purely combinatorial approach to the question of whether or not a finitely presented monoid has a finite canonical presentation. Our approach is based on the notion of “finite derivation type” which is a combinatorial condition satisfied by certain rewriting systems. Our main result states that if a monoid M has a finite canonical presentation, then all finite presentations of M have finite derivation type. By proving that a certain monoid S1 does not have finite derivation type we show in addition that the homological finiteness condition FP ∞ is not sufficient to guarantee that a finitely presented monoid with a decidable word problem has a finite canonical presentation.

In this paper we evaluate the complexity of an algorithm for deciding whether a partially commutative free monoid has an infinite number of square-free elements.

The generating set of a semiretract of a free monoid is an infix code and a biprefix code. If a free monoid is generated by n elements then any nest of semiretracts contains at most n + 1 distinct members.

It is shown that for the presentation (a, b; abbaab = λ) of the Jantzen monoid J no finite complete rewriting system exist that is based on a Knuth-Bendix ordering. However, a finite complete rewriting system is given for a different presentation of J that has four generators. Further, a finite complete rewriting system is given for the presentation 〈a, b, c; abc = cba〉 of the Greendlinger group G. This system induces a polynomial-time algorithm for the word problem for G.

This paper introduces what the authors believe to be the correct definition of the kernel of a monoid morphism a, : M+ N. This kernel is a category, constructed directly from the constituents of 9. In the case of a group morphism, our kernel is a groupoid that is divisionally equivalent to the traditional kernel. This article is a continuation of the work in [8]. The thesis of [8] is that categories, as generalized monoids, are essential ingredients in monoid decomposition theory. The principal development in [S] was the introduction of division, a new ordering for categories, which extend the existing notion for monoids. Since its introduction in [3], division has proved to be the ordering of choice for monoids. This extension of division to categories allows for the useful comparison of monoids and categories. A strong candidate for the title ‘kernel’ was introduced in [8]. This candidate is also a category and is called the derived category of 9. The derived category operation and the wreath product of monoids are shown to have an adjoint-like relationship. This relationship is summed up in the Derived Category Theorem [8, Theorem 5.21. The derived category has its origins in [6], where it appears as the derived semigroup. The kernel construction of this paper is an improvement over the derived category for a variety of reasons. First, it is smaller in the divisional sense. Second, it is a reversal invariant construction. Third, it combines more effectively with classical structure theories. For example, when applied to surmorphisms that cannot be further factored, the kernel has a particularly simple form. This leads to important decomposition theorems for finite monoids.

Dominoes over a free monoid and operations on them are introduced. Related algebraic systems and their applications to decidability problems about morphisms on free monoids are studied. A new simple algorithm for testing DOL sequence equivalence is presented.

Let A∗ be the free monoid of base A and n a fixed positive integer. For any word wϵA∗ we consider the set [w]n of all the words which are equivalent to w modulus the congruence θn generated by the relation xn∼xn+1, where x is any word of A∗. The main result of the paper is that if n>4 then for any word wϵA∗ the congruence class [w]n is a regular language. We also prove that the word problem for the quotient monoid Mn=A∗θn is recursively solvable.

A sofic shift S is a symbolic dynamical system that can be viewed as a set of all bi-infinite sequences obtained by reading the labels of all bi-infinite paths in a finite directed labeled graph G . The presentation G is synchronizing if for every vertex v there is a word x v such that every path in G labeled with x v has v as a terminal vertex. We present an example of a subshift of finite type that has no unique minimal deterministic presentation and we show that if a sofic shift has a synchronizing, deterministic presentation (sdp), then it has a unique minimal one. Irreducible sofic shifts, subshifts of finite type and nonwandering systems have synchronizing, deterministic presentations. We give an intrinsic characterization of a sofic shift S that has an sdp in terms of the syntactic monoid M ( S ) of the factor language F ( S ) of S . Another characterization of sofic shifts with sdp's is given in terms of the predecessor sets. We show that a sofic shift can have at most one bi-synchronizing presentation.

Ehrenfeucht's Conjecture states that each subset S of a finitely generated free monoid has a finite subset T such that if two endomorphisms of the monoid agree on T , then they agree on S . It is the purpose of this note to verify the conjecture.