International Journal of Algebra and Computation

Let be the pseudovariety of all finite monoids whose principal right ideals have a unique generator, let be its dual, and let . Using the word problem for free pro- monoids, it is shown that the bilateral semidirect product is local, where denotes the pseudovariety of all finite semilattices. The global of the pseudovariety where is also computed and it is shown that this join is not local.

For a given finite monoid M we explicitly construct a finite group G and a relational morphism τ:M→G such that only elements of the type II construct M_c relate to 1 under τ. This provides an elementary and constructive proof of the type II conjecture of John Rhodes. The underlying idea is also used to modify the proof of Ash's celebrated theorem on inevitable graphs. For any finite monoid M and any finite graph Γ a finite group G is constructed which "spoils" all labelings of Γ over M which are not inevitable.

We prove new results about the remarkable infinite simple groups introduced by Richard Thompson in the 1960s. We give a faithful representation in the Cuntz C^⋆-algebra. For the finitely presented simple group V we show that the word-length and the table size satisfy an n log n relation. We show that the word problem of V belongs to the parallel complexity class AC¹ (a subclass of P), whereas the generalized word problem of V is undecidable.

We study the distortion functions of V and show that V contains all finite direct products of finitely generated free groups as subgroups with linear distortion. As a consequence, up to polynomial equivalence of functions, the following three sets are the same: the set of distortions of V, the set of Dehn functions of finitely presented groups, and the set of time complexity functions of nondeterministic Turing machines.

The notion of κ-tameness of a pseudovariety was introduced by Almeida and Steinberg and is a strong property which implies decidability of pseudovarieties. In this paper we prove that the pseudovariety LSl, of local semilattices, is κ-tame.

We show that if S is a finite semigroup with aperiodic idempotent-generated subsemigroup and H is a pseudovariety of groups, then the sequence of iterated H-kernels of S stops at the idempotent-generated subsemigroup if and only if each subgroup of S belongs to the wreath product closure of H. Applications are given to Mal'cev products.

The automorphism group of a 3-generated 2-group G of intermediate growth is determined and it is shown that the outer group of automorphisms of G is an elementary abelian 2-group of infinite rank.

We study some properties of the Cayley graph of R. Thompson's group F in generators x₀, x₁. We show that the density of this graph, that is, the least upper bound of the average vertex degree of its finite subgraphs is at least 3. It is known that a 2-generated group is not amenable if and only if the density of the corresponding Cayley graph is strictly less than 4. It is well known this is also equivalent to the existence of a doubling function on the Cayley graph. This means there exists a mapping from the set of vertices into itself such that for some constant K>0, each vertex moves by a distance at most K and each vertex has at least two preimages. We show that the density of the Cayley graph of a 2-generated group does not exceed 3 if and only if the group satisfies the above condition with K=1. Besides, we give a very easy formula to find the length (norm) of a given element of F in generators x₀, x₁. This simplifies the algorithm by Fordham. The length formula may be useful for finding the general growth function of F in generators x₀, x₁ and the growth rate of this function. In this paper, we show that the growth rate of F has a lower bound of .

In this paper we answer a question posed by John Rhodes: "What are the aperiodic-idempotent-pointlike subsemigroups of S?" Answer: Precisely those aperiodic-pointlike subsemigroups that are idempotents, i.e. EPl_A(S)={X|X≤E=E²∈Pl_A(S)}. In the proof we define, for a given variety V (closed under n-tuple expansion) and a given relation R:S-V∈V computing the V-pointlike subsets of S, an "improved" relation R_(n):S-V⁽ⁿ⁾ that computes the V-idempotent-pointlike subsemigroups of S. Consequently, for any W with decidable membership problem W ⓜ A is decidable.

We show that any locally finite automata network with global synchronous updates can be emulated by another one , whose structure derives from that of by a simple construction, but whose updates are made asynchronously at its various component automata (e.g. possibly randomly or sequentially, with or without possible simultaneous updates at different nodes). By "emulation", we refer to the existence of a spatial-temporal covering 'local time', allowing one to project the behavior of continuously onto that of . We also show the existence of a spatial-temporal section of the asynchronous automata network's behavior which completely determines the synchronous global state of at every time step.

We give the construction of the asynchronous automata network, establish its freedom from deadlocks, and construct local time functions and spatial-temporal sections relating any posssible behavior of to the single corresponding behavior of on a given input sequence starting from a given initial global state.

This establishes that the behavior of any locally finite synchronous automata network actually can be emulated without the restriction of synchronous update, freeing us from the need of a global clock signal. Local information is sufficient to guarantee that the synchronous behavior of is completely determined by any asynchronous behavior of starting from a corresponding global state and given the same input sequence as . Moreover, the relative passage of corresponding local time at any two nodes in is bounded in a simple way by approximately one-third of the distance between them.

As corollaries, any synchronous generalized cellular automaton or synchronous cellular automaton can be emulated by an asynchronous one of the same type.

Implementation aspects of these asynchronous automata are also discussed, and open problems and research directions are indicated.

An unambiguous construction of an embedding of the free product of n cyclic groups of order p into the the group of finite state infinite unitriangular matrices over the finite field of size p is presented.

Let be a nonempty class of finite groups closed under taking subgroups, quotients and extensions. We consider groups G endowed with their pro- topology, and say that G is 2-subgroup separable if whenever H and K are finitely generated closed subgroups of G, then the subset HK is closed. We prove that if the groups G₁ and G₂ are 2-subgroup separable, then so is their free product G₁*G₂. This extends a result to T. Coulbois. The proof uses actions of groups on abstract and profinite trees.

We prove that in the variety of nilpotent semigroups of class ≤2, which is defined by the Neumann–Taylor identity xyzyx=yxzxy, the sequence of the superdimensions for relatively free semigroups is convergent to 1 and at the same time every element of the sequence is strictly less than 1. This gives the first example of a semigroup variety for which the set of superdimensions for the free objects is infinite.

A variation of first-order logic with variables for exponents is developed to solve some problems in the setting of recognizable languages on the free monoid, accommodating operators such as product, bounded shuffle and reversion. Restricting the operators to powers and product, analogous results are obtained for recognizable languages of an arbitrary finitely generated monoid M, in particular for a free inverse monoid of finite rank. As a consequence, it is shown to be decidable whether or not a recognizable subset of M is pure or p-pure.

This contribution wishes to argue in favor of increased interaction between experts on finite monoids and specialists of theory of computation. Developing the algebraic approach to formal computations as well as the computational point of view on monoids will prove to be beneficial to both communities. We give examples of this two-way relationship coming from temporal logic, communication complexity and Boolean circuits. Although mostly expository in nature, our paper proves some new results along the way.

Straubing deduced from Simon's theorem that monoids of reflexive relations as well as monoids of order preserving extensive transformations generate the pseudovariety of -trivial monoids. We refine these results by showing that each pseudovariety in Simon's hierarchy of -trivial monoids is generated by a single relation/transformation monoid. From this and from some results by Blanchet–Sadri we obtain a complete solution of the finite basis problem for Straubing's monoids.