**Contemporary Mathematics**

Volume: 378;
2005;
348 pp;
Softcover

MSC: Primary 20; 81;
Secondary 68

**Print ISBN: 978-0-8218-3618-7
Product Code: CONM/378**

List Price: $110.00

AMS Member Price: $88.00

MAA Member Price: $99.00

**Electronic ISBN: 978-0-8218-7968-9
Product Code: CONM/378.E**

List Price: $103.00

AMS Member Price: $82.40

MAA Member Price: $92.70

# Groups, Languages, Algorithms

Share this page *Edited by *
*Alexandre V. Borovik*

Since the pioneering works of Novikov and Maltsev, group theory has been a
testing ground for mathematical logic in its many manifestations, from the
theory of algorithms to model theory. The interaction between logic and group
theory led to many prominent results which enriched both disciplines.

This volume reflects the major themes of the American Mathematical
Society/Association for Symbolic Logic Joint Special Session (Baltimore, MD),
Interactions between Logic, Group Theory and Computer Science. Included are
papers devoted to the development of techniques used for the interaction of
group theory and logic. It is suitable for graduate students and researchers
interested in algorithmic and combinatorial group theory.

A complement to this work is Volume 349 in the AMS series, Contemporary
Mathematics,
Computational and Experimental Group Theory , which arose
from the same meeting and concentrates on the interaction of group theory and
computer science.

#### Readership

Graduate students and research mathematicians interested in algorithmic and combinatorial group theory.

# Table of Contents

## Groups, Languages, Algorithms

- Contents v6 free
- Preface vii8 free
- Formal languages and their application to combinatorial group theory 110 free
- Regular free length functions on Lyndon's free Z[t]-group FZ[t] 3746
- A-free groups and tree-free groups 7988
- Effective JSJ decompositions 8796
- Introduction 8897
- 1. Preliminaries 95104
- 2. Splittings 101110
- 3. Algorithms over fully residually free groups 120129
- 4. Generalized equations over free groups 125134
- 5. Elimination process: construction of T(Ω) 134143
- 6. Elimination process: periodic structures 151160
- 7. Elimination process: splittings of coordinate groups 165174
- 8. Structure of solutions, the solution tree Tsol(Ω, A) 176185
- 9. Maximal standard quotients and canonical embeddings of F-groups 179188
- 10. Effective free decompositions 186195
- 11. Homomorphisms of finitely generated groups into fully residually free groups 191200
- 12. Free Lyndon length functions on NTQ groups. 194203
- 13. Effective construction of JSJ decompositions of groups from F. 199208
- 14. Homomorphisms into NTQ groups 207216
- 15. Some applications to equations in F-groups 207216
- References 210219

- Algebraic geometry over free groups: Lifting solutions into generic points 213222
- Introduction 214223
- 1. Scheme of the proof 219228
- 2. Elementary properties of liftings 222231
- 3. Cut equations 227236
- 4. Basic automorphisms of orientable quadratic equations 230239
- 5. Generic solutions of orientable quadratic equations 264273
- 6. Small cancellation solutions of standard orientable equations 272281
- 7. Implicit function theorem for quadratic equations 277286
- 8. Implicit function theorem for NTQ systems 306315
- 9. Groups that are elementary equivalent to a free group 311320
- References 317326

- Divisibility theory and complexity of algorithms for free partially commutative groups 319328