TY - JOUR
T1 - Group extensions over infinite words
AU - Diekert, Volker
AU - Myasnikov, Alexei
PY - 2012/8
Y1 - 2012/8
N2 - 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 interesting algorithmic problems in geometric and algorithmic group theory. There is also a connection to logic and the first-order theory in free groups (Tarski Problems). 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 groupG 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. In order to show that every group G embeds into E(A, G) we combine methods from combinatorics on words, string rewriting and group theory.
AB - 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 interesting algorithmic problems in geometric and algorithmic group theory. There is also a connection to logic and the first-order theory in free groups (Tarski Problems). 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 groupG 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. In order to show that every group G embeds into E(A, G) we combine methods from combinatorics on words, string rewriting and group theory.
KW - Confluent rewriting systems
KW - discrete groups
KW - infinite words
KW - non-Archimedean words
UR - http://www.scopus.com/inward/record.url?scp=84867205238&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867205238&partnerID=8YFLogxK
U2 - 10.1142/S0129054112400424
DO - 10.1142/S0129054112400424
M3 - Article
AN - SCOPUS:84867205238
SN - 0129-0541
VL - 23
SP - 1001
EP - 1019
JO - International Journal of Foundations of Computer Science
JF - International Journal of Foundations of Computer Science
IS - 5
ER -