Effective JSJ Decompositions

By Olga Kharlampovich, Alexei G. Myasnikov. 2004

57 citations recorded by the source corpus.

In this paper we describe an elimination process which is a de- terministic rewriting procedure that on each elementary step transforms one system of equations over free groups into a finitely many new ones. Infinite branches of this process correspond to cyclic splittings of the coordinate group of the initial system of equations. This allows us to construct algorithmically Grushko's decompositions of finitely generated fully residually free groups and cyclic (abelian) JSJ decompositions of freely indecomposable finitely generated fully residually free groups. We apply these results to obtain an effective de- scription of the set of homomorphisms from a given finitely presented group into a free group, or, more generally, into an NTQ group.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/b6fd237210e1c47c572438a86dd5a3182ac48476

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Mathematical Physics

Citations in the corpus

On the finite presentation of subdirect products and the nature of residually free groups (2012, background): “In [28] Kharlampovich and Myasnikov describe an algorithm to find such an embedding, based on the deep work of Makanin [34] and Razborov [36].”
Elementary theory of free non-abelian groups (2006, background): “Some of the results of [14] are improved in [19] and [20].”
The outer space of a free product (2005, background): “Using results of [18] and [5] about the abelian JSJ splitting, one gets:”