TY - GEN
T1 - Solving word problems in group extensions over infinite words
AU - Diekert, Volker
AU - Myasnikov, Alexei G.
PY - 2011
Y1 - 2011
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 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 " u ∈ 〈v〉?" is decidable for all v ∈ G. Our methods combine 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 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 " u ∈ 〈v〉?" is decidable for all v ∈ G. Our methods combine combinatorics on words, string rewriting, and group theory.
UR - http://www.scopus.com/inward/record.url?scp=79960726088&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960726088&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22321-1_17
DO - 10.1007/978-3-642-22321-1_17
M3 - Conference contribution
AN - SCOPUS:79960726088
SN - 9783642223204
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 192
EP - 203
BT - Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings
T2 - 15th International Conference on Developments in Language Theory, DLT 2011
Y2 - 19 July 2011 through 22 July 2011
ER -