Solving word problems in group extensions over infinite words

Volker Diekert and Alexei Myasnikov

Abstract. Non-Archimedean words have been introduced as a new type of infinite words which can be investigated through classical methods in combinatorics on words due to a length function. The length function, however, takes values in the additive group of polynomials ℤ[t] (and not, as traditionally, in ℕ), which yields various new properties. Non-Archimedean words allow to solve a number of algorithmic problems in geometric and algorithmic group theory. There is a connection to the first-order theory in free groups (Tarski Problems), too.

In the present paper we provide a general method to use infinite words over a discretely ordered abelian group as a tool to investigate certain group extensions for an arbitrary group G. The central object is a group E(A, G) which is defined in terms of a non-terminating, but confluent rewriting system. The group G as well as some natural HNN-extensions of G embed into E(A, G) (and still ”behave like” G), which makes it interesting to study its algorithmic properties. The main result characterizes when the Word Problem (WP) is decidable in all finitely generated subgroups of E(A, G). We show that this property holds if and only if the Cyclic Membership Problem “uv ?” is decidable for all vG. Our methods combine combinatorics on words, string rewriting, and group theory.

Comments are closed.