2021/07/07 by Amnon Rosenmann, Rosenmann, Amnon, Enric Ventura Capell +1 · 1 citation
Computer Science · Mathematics · #20F70 #Algebraic Geometry and Number Theory #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2107.03154
openalex publication_date 2021/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a finitely generated subgroup H of a free group F, we present an algorithm which computes g1,…,gm∈ F, such that the set of elements g∈ F, for which there exists a non-trivial H-equation having g as a solution, is, precisely, the disjoint union of the double cosets H\sqcup Hg1H\sqcup ⋯ \sqcup HgmH. Moreover, we present an algorithm which, given a finitely generated subgroup H\leqslant F and an element g∈ F, computes a finite set of elements of H * ⟨ x ⟩ that generate (as a normal subgroup) the ``ideal" IH(g) \unlhd H * ⟨ x ⟩ of all ``polynomials" w(x), such that w(g)=1. The algorithms, as well as the proofs, are based on the graph-theory techniques introduced by Stallings and on the more classical combinatorial techniques of Nielsen transformations. The key notion here is that of dependence of an element g∈ F on a subgroup H. We also study the corresponding notions of dependence sequence and dependence closure of a subgroup.