International Journal of Algebra and Computation

The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However, we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Given a NW-deterministic Wang tile set, we construct a Mealy automaton, such that the plane admits a valid Wang tiling if and only if the Mealy automaton generates a infinite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover, Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroups is undecidable.

A reconstruction problem is formulated for multisets over commutative groupoids. The cards of a multiset are obtained by replacing a pair of its elements by their sum. Necessary and sufficient conditions for the reconstructibility of multisets are determined. These results find an application in a different kind of reconstruction problem for functions of several arguments and identification minors: classes of linear or affine functions over nonassociative semirings are shown to be weakly reconstructible. Moreover, affine functions of sufficiently large arity over finite fields are reconstructible.

We construct an uncountable family of 3-generated residually finite just-infinite groups with isomorphic profinite completions. We also show that word growth rate is not a profinite property.

It has been shown by Lubotzky in [10] that the set of verbal images of a fixed non-abelian finite simple group G is precisely the set of automorphism invariant subsets of G. Here, we use similar methods to those of Lubotzky to determine the verbal images of certain almost simple groups and quasisimple groups.

In this paper, we consider how the O'Nan sporadic simple group acts as the automorphism group of an abstract regular polytope. In particular, we prove that there is no regular polytope of rank at least five with automorphism group isomorphic to O′N. Moreover, we classify all rank four regular polytopes having O′N as their automorphism group.

Normalization is a fundamental ring-theoretic operation; geometrically it resolves singularities in codimension one. Existing algorithmic methods for computing the normalization rely on a common recipe: successively enlarge the given ring in form of an endomorphism ring of a certain (fractional) ideal until the process becomes stationary. While Vasconcelos' method uses the dual Jacobian ideal, Grauert–Remmert-type algorithms rely on so-called test ideals. For algebraic varieties, one can apply such normalization algorithms globally, locally, or formal analytically at all points of the variety. In this paper, we relate the number of iterations for global Grauert–Remmert-type normalization algorithms to that of its local descendants. We complement our results by a study of ADE singularities. All intermediate singularities occurring in the normalization process are determined explicitly. Besides ADE singularities the process yields simple space curve singularities from the list of Frühbis-Krüger.

Dinits–Karzanov–Lomonosov showed that it is possible to encode all minimal edge cuts of a graph by a tree-like structure called a cactus. We show here that minimal edge cuts separating ends of the graph rather than vertices can be "encoded" also by a cactus. As a corollary, we obtain a new proof of Stallings' ends theorem. We apply our methods to finite graphs as well and we show that several types of cuts can be encoded by cacti.