Search

We give an algorithm which computes the fixed subgroup and the stable image for any endomorphism of the free group of rank two F 2 , answering for F 2 a question posed by Stallings in 1984 and a question of Ventura. [ABSTRACT FROM AUTHOR]

Abstract We derive a generating series for the number of free subgroups of finite index in Δ + = Z p ∗ Z q by using a connection between free subgroups of Δ + and certain hypermaps (also known as ribbon graphs or "fat" graphs), and show that this generating series is transcendental. We provide non-linear recurrence relations for the above numbers based on differential equations that are part of the Riccati hierarchy. We also study the generating series for conjugacy classes of free subgroups of finite index in Δ + , which correspond to isomorphism classes of hypermaps. Asymptotic formulas are provided for the numbers of free subgroups of given finite index, conjugacy classes of such subgroups, or, equivalently, various types of hypermaps and their isomorphism classes. [ABSTRACT FROM AUTHOR]

L systems generalize context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper, we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives and bases in the free group on two generators, the Bridson-Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk's group can be generated by L systems. To complement the result on primitives in rank 2 free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L languages of intermediate growth. [ABSTRACT FROM AUTHOR]

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism ϕ of F sending W to U. This work analyzes an approach due to Edmunds and improved by Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two-generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U. This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side. [ABSTRACT FROM AUTHOR]

Abstract: Let F be a free group, and let H be a subgroup of F. The ‘Galois monoid’ consists of all endomorphisms of F which fix every element of H; the ‘Galois group’ consists of all automorphisms of F which fix every element of H. The -closure and the -closure of H are the fixed subgroups, and , respectively. Martino and Ventura considered examples where We obtain, for two of their examples, explicit descriptions of , , and , and, hence, give much simpler verifications that , in these cases. [Copyright &y& Elsevier]