International Journal of Algebra and Computation

In recent work we associated a natural category to a semigroup and developed Morita theory for semigroups. In particular we gave a generalisation of Rees’ Theorem which led us to define what we call a Morita semigroup, this is our analogue of a structure matrix semigroup. In this article we formulate a method for extending Morita semigroups by groups. We say that a semigroup is an iterative Morita semigroup if it is obtained by successive applications of pasting families of Morita semigroups which have been extended by groups. By relying on Morita theory we show that every regular unambiguous semigroup is isomorphic to an iterative Morita semigroup of a special form. Our result can be viewed as a co-ordinate free version of the Synthesis Theorem.

In this paper we investigate the class of all completely 0-simple semigroups of left quotients of a given semigroup S. We show that (if the class is non-empty) it has a ‘greatest’ member ∈S which is in a sense the free completely 0-simple semigroup on S, and describe how the other members can be obtained as homomorphic images of .

Using purely syntactical arguments, it is shown that every nontrivial pseudovariety of monoids contained in DO whose corresponding variety of languages is closed under unambiguous product, for instance DA, is local in the sense of Tilson.

In this paper we prove that the congruence classes of A* associated to the Burnside semigroup with |A| generators defined by the equation xⁿ=x^n+m, for n≥4 and m≥1, are recognizable.

This problem was originally formulated by Brzozowski in 1969 for m=1 and n≥2. De Luca and Varricchio solved the problem for n≥5 in 90. A little later, McCammond extended the problem for m≥1 and solved it independently in the cases n≥6 and m≥1. Our work, which is based on the techniques developed by de Luca and Varricchio, extends both these results.

We effectively construct a minimal generator Σ of our congruence. We introduce an elementary concept, namely the stability of productions, which allows to eliminate all hypothesis related to the values of n and m. A substantial part of our proof consists of showing that all productions in Σ are stable, for n≥4 and m≥1.

We also show that Σ is a Church-Rosser rewriting system, thus solving the word problem, and show that the semigroup is finite -above. We prove that the frame of the ℛ-classes of the semigroup is a tree. We characterize and calculate the ℛ-classes, ℋ-classes and the -classes of the semigroup, regular or not, and prove that its maximal subgroups are cyclic of order m whenever all productions of Σ are stable.

Recently Guba extended the cases in which the conjecture holds to n≥3 and m≥1. Using his work we obtain the stability of the productions of Σ for n=3 and m≥1 too and, hence, all properties about the semigroup structure hold in this case.

This paper introduces a generalized way of defining languages of infinite words by topological means. It focuses on languages generated by iterating morphisms on free semi-groups (also called substitutions or D0L-systems). The main result is an effective construction of the boundary of such languages which leads to a bijective mapping of the boundary onto a regular language. Among the obtained properties are the uncountability of the boundary and the strict quasiperiodicity of its words. We also investigate the decidability of the boundary equality problem and the dynamical system induced by the inversed morphism.

Mazoyer has constructed a family of systems of two interacting finite automata which synchronize in time about [2/log(m)] Δ log(∆) where Δ is the delay of communication. Here we prove that solutions “à la Mazoyer” are optimal in the following senses: 1°) any synchronizing system operates in time at least [1/ log (N)]Δ log(∆/2), N being the number of states, so that the order Δ log(∆) is optimal 2°) Mazoyer-like systems have about a m³ states so that [2/log(m)] is about 6 times the above lower bound, which is thus nearly optimal.