International Journal of Algebra and Computation

We introduce several equivalent notions that generalize ones introduced by Klaus Wagner for finite Muller automata under the name of chains and superchains. We define such objects in relation to ω-rational sets, Muller automata or also ω-semigroups. We prove their equivalence and derive some basic properties of these objects. In a subsequent paper, we show how these concepts allow us to derive a new presentation of the hierarchy due to K. Wagner and W. Wadge.

Grigorchuk and Kurchanov's conjecture states that, up to natural equivalence, there is precisely one splitting epimorphism F_2n→F_n×F_n from a free group F_2n onto F_n×F_n. The -conjecture, while formally similar to the the Poincaré conjecture, implies the well-known Andrews–Curtis conjecture about the balanced presentations of the trivial group. In this paper we undertake the task of fully analyzing the -conjecture modulo the second commutator subgroup F_2n″. We derive some consequences for the general -conjecture.

A ternary algebra is a De Morgan algebra (that is, a distributive lattice with 0 and 1 and a complement operation that satisfies De Morgan's laws) with an additional constant Φ satisfying , , and . We provide a characterization of finite ternary algebras in terms of "subset-pair algebras," whose elements are pairs (X, Y) of subsets of a given base set ℰ, which have the property X ∪ Y = ℰ, and whose operations are based on common set operations.

Finite monogenerated groupoids G satisfying the left distributive law x · (y · z) = (x · y) · (x · z) are completely described.

Let A be an alphabet and u, v two words in A*. We show that the word problem is decidable for the monoid presentation

We obtain a criterion for quasiconvexity of a subgroup of an amalgamated free product of two word hyperbolic groups along a virtually cyclic subgroup. The result provides a method of constructing new word hyperbolic group in class (Q), that is such that all their finitely generated subgroups are quasiconvex. It is known that free groups, hyperbolic surface groups and most 3-dimensional Kleinian groups have property (Q). We also give some applications of our results to one-relator groups and exponential groups.