International Journal of Algebra and Computation

A pair (G, A) consisting of a group G and a finite generating set A is a Cannon pair if the language of all geodesics in the associated Cayley graph is regular. We prove that the Cannon pair property is preserved by graph products and indicate applications of this result to the geodesic and spherical growth series of graph products.

We show that abstract homotopy theory can be used to define a suitable notion of homotopy equivalence for inverse semigroups. As an application of our theory, we prove a theorem for inverse semigroup homomorphisms which is the exact counterpart of the well-known result in topology which states that every continuous function can be factorized into a homotopy equivalence followed by a fibration. We show that this factorization is isomorphic to the one constructed by Steinberg in his "Fibration Theorem", originally proved using a generalization of Tilson's derived category.

We show how the Rhodes expansion Ŝ of any stable semigroup S embeds into the cascade integral (a natural generalization of the wreath product) of permutation-reset transformation semigroups with zero adjoined. The permutation groups involved are exactly the Schützenberger groups of the -classes of S. Since S ←← Ŝ is an aperiodic map via which all subgroups of S lift to Ŝ, this results in a strong Krohn–Rhodes–Zeiger decomposition for the entire class of stable semigroups. This class includes all semigroups that are finite, torsion, finite -above, compact Hausdorff, or relatively free profinite, as well as many other semigroups. Even if S is not stable, one can expand it using Henckell's expansion and then apply our embedding. This gives a simplified proof of the Holonomy Embedding theorem for all semigroups.

We exhibit finite algebras each generating a variety with NP-complete finite algebra membership problem. The smallest of these algebras is the flat graph algebra belonging to the tetrahedral graph, a graph of 6 vertices obtained by cutting and spreading out the surface of a tetrahedron on the plane. The sequence of graphs we use to build up our flat graph algebras is similar to the sequence exhibited by Wheeler in [36], 1979, to describe the first order theory of k-colorable graphs. Graph algebras were introduced by Shallon in [34], 1979, and investigated, among others, by Baker, McNulty and Werner in [2], 1987. Flat algebras were constructed and used by McKenzie in [27], 1996, to settle some open questions related to decidability, like Tarski's Finite Basis Problem. Flat graph algebras were also discussed by Willard in [37], 1996, and Delić in [8], 1998.

In a previous work, we have investigated an automata-theoretic property of numeration systems associated with quadratic Pisot units that yields, for every such number θ, a certain group G_θ.

In this paper, we characterize a cross-section of a congruence γ_θ of ℤ⁴ that had arisen when constructing G_θ. This allows us to completely describe the quotient H_θ of ℤ⁴ by γ_θ, that becomes then a second group associated with θ. Moreover, the cross-section thus described is very similar to the symbolic dynamical system associated, by a theorem of Parry, with the two numeration systems attached to θ.

The proof is combinatorial, and based upon rewriting techniques.

Résumé: Dans un article précédent, nous avions associé à chaque nombre de Pisot quadratique unitaire θ un certain groupe G_θ par le biais de la construction d'un automate qui réalise le passage entre les représentations des entiers dans deux systèmes de numération naturellement attachés à θ.

Dans cet article, nous donnons une caractérisation d'un ensemble de représentants pour une congruence γ_θ de ℤ⁴ qui avait été utilisée pour la définition de G_θ. Cette caractérisation permet la description complète du quotient H_θ de ℤ⁴ par γ_θ, autre groupe associé à θ. Elle est d'autre part remarquablement similaire à la description, donnée par un théorème de Parry, du système dynamique symbolique associé aux deux systèmes de numération attachés à θ.

La preuve est combinatoire et utilise les techniques des systèmes de réécriture.

Association schemes are combinatorial objects that allow us solve problems in several branches of mathematics. They have been used in the study of permutation groups and graphs and also in the design of experiments, coding theory, partition designs etc. In this paper we show some techniques for computing properties of association schemes. The main framework arises from the fact that we can characterize completely the Bose–Mesner algebra in terms of a zero-dimensional ideal. A Gröbner basis of this ideal can be easily derived without the use of Buchberger algorithm in an efficient way. From this statement, some nice relations arise between the treatment of zero-dimensional ideals by reordering techniques (FGLM techniques) and some properties of the schemes such as P-polynomiality, and minimal generators of the algebra.

Hypersubstitutions map n-ary operation symbols to n-ary terms. Such mappings can be uniquely extended to mappings defined on the set of all terms. It turns out that the kernels of hypersubstitutions are fully invariant congruence relations on the (absolutely free) term algebra of the considered type. For an arbitrary type τ = (n), n ≥ 1, i.e. if one has only one n-ary operation symbol, we will describe all these congruence relations. The results will be applied to solve the hyperunification problem. Further we will give some generalizations to arbitrary types.