{'fraction_non_alphanumeric': 0.05782553860506902, 'fraction_numerical': 0.013303156476218448, 'mean_word_length': 3.6346384818640405, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 87, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stallings automata for free-times-abelian groups: intersections and index

We extend the classical Stallings theory (describing subgroups of free groups as automata) to direct products of free and abelian groups: after introducing enriched automata (i.e., automata with extra abelian labels), we obtain an explicit bijection between subgroups and a certain type of such enriched automata, which - as it happens in the free group - is computable in the finitely generated case. This approach provides a neat geometric description of (even non finitely generated) intersections of finitely generated subgroups within this non-Howson family. In particular, we give a geometric solution to the subgroup intersection problem and the finite index problem, providing recursive bases and transversals respectively.


Introduction
Stallings automata constitute the main modern tool to understand and work with the lattice of subgroups of a free group F X (usually assumed to have finite rank n = # X, denoted by F n ). In the seminal paper [36], J. R. Stallings used a topological approach to construct a natural and algorithmic-friendly bijection H ↔ St(H, X) between subgroups of F X and certain kind of X-automata; see [1,10,22] for a more combinatorial approach closer to ours. This bijection has proved to be very useful to obtain modern solutions to both classical and new problems regarding subgroups of the free group. First easy applications are computability of bases of finitely generated subgroups, the solution to the membership problem in F n , and description of finite index subgroups. Specially relevant to us is the product (or pull-back) technique, which makes it possible to construct St(H ∩ K, X) from St(H, X) and St(K, X); this immediately implies that F n is Howson, and allows to describe (compute a basis of) H ∩ K in terms of (bases of) H and K. More recent applications of this fruitful theory are included in [8,25,26,29,30,35,37]. See [10] for a recent survey on applications of Stallings automata.
This geometric approach constituted the seed for many successful attempts at generalization; see for example [13,19,20,23,24,34]. In this paper, we present a generalization into another direction, namely to direct products of finitely generated free and abelian groups, i.e., groups of the form G = F n × Z m . This is part of a more ambitious project started in [5,Chapter 5], continued in [11], and aiming at the much more general class of semidirect extensions of free groups, i.e., groups of the form F n A G. We restrict ourselves to freetimes-abelian groups (i.e., G finitely generated abelian and A trivial). The more involved theory for the general semidirect scenario is in progress and will appear published in the near future; see [12]. The theory of intersections of free-times-abelian groups, in turn, have a natural continuation in [6] (where the possible configurations of multiple intersections are studied) and [7] (where the results in [6] are used to obtain groups which, in some sense, admit a structure of quotients as complicated as possible).
So, we revisit the family of free-times-abelian groups (already considered by the same authors in [9]) now from a geometric point of view. This approach provides new insight into the properties and behavior of subgroups that refines and clarifies some known results in the finitely generated realm, and extends into the non finitely generated one. The main idea is to suitably enrich classical Stallings automata with abelian labels to make them expressive enough to represent every subgroup of G, and flexible enough to make this representation unique (and algorithmic when restricted to finitely generated subgroups). With this bijection at hand, we interpret the notion of basis (for subgroups of G), and geometrically rephrase the solution to the membership problem MP(G) given in [9]. Then, we go on to analyze intersections; note that this must be more complicated than just computing products (of the corresponding enriched automata) since G is not a Howson group in general, whereas products of finite objects are again finite. Our approach makes it possible to geometrically understand arbitrary intersections of subgroups of G as (a certain technical variation of) Cayley digraphs of abelian groups. Moreover, when the intersecting subgroups are finitely generated, the obtained description is fully algorithmic and leads to a clean alternative proof for the solvability of the subgroup intersection problem SIP(G); see Definition 4.1.
In Section 2 we introduce the family of free-times-abelian groups (G = F n × Z m ) together with some related terminology and notation. It turns out that this naive-looking family hides interesting features that translate into non-trivial problems; see [4,6,9,14,31,32].
In Section 3 we start by briefly surveying the classical Stallings theory for subgroups of the free group, to then introduce and study enriched automata (restricted to the free-times-abelian case). This leads to the classification Theorem 3.7, which we use to derive first applications, such as the solvability of the membership problem and the computability of bases.
In Section 4 we consider intersections of subgroups. After reviewing the classical pullback technique for the free group, we develop the theory of enriched products to study intersections of subgroups in G. The first important result is Theorem 4.14 where we establish the relation between subgroup intersections and Cayley digraphs of abelian groups. Then, we focus on the algorithmic description of the intersection, which is summarized in Theorem 4.20 and has two notable consequences: a geometric proof of the solvability of the intersection problem SIP(G), and the denial of any possible extension of the celebrated Hanna Neumann conjecture to any group containing F 2 × Z. Finally, we use a topological argument to extend the above ideas to non finitely generated intersections; this leads to Theorem 4.26 providing a geometric description of arbitrary intersections within G.
In Section 5 we use these results to deduce a neat description of the cosets and index of a given finitely generated subgroup H G, which turns out to be transparently encoded in the enriched Stallings automata for H; see Proposition 5.1. A geometric solution for the finite index problem FIP(G) and a description of a recursive transversal set easily follow.
Finally, in Section 6, we provide some examples highlighting the most relevant aspects of our geometric construction.
We use lowercase boldface Latin font to denote abelian elements (a, b, c, . . .), and uppercase boldface Latin font to denote matrices with integer entries (A, B, C, . . .). Capitalized calligraphic font is used to denote subgroups (H, K, L, . . .) and subsets (S, R, T, . . .) of G, in contrast with the corresponding objects in the factors, denoted by H, K, L, . . . and R, S, T , . . . respectively. Furthermore, homomorphisms and matrices are assumed to act on the right; that is, we denote by (x)ϕ (or simply xϕ) the image of the element x by the homomorphism ϕ, and we denote by ϕψ the composition A ϕ B ψ C. Accordingly, the image of the homomorphism associated to a matrix A is the row space of A, denoted by A . Finally, we shall use the symbol ∞ to denote the countable infinity.

Free-times-abelian groups
According to a very well-known classification theorem, any finitely generated abelian group is isomorphic to where m , m , d 1 , . . . , d m are non-negative integers satisfying 2 d 1 | d 2 | · · · | d m . We can think the elements of such a group as integral vectors of length m = m + m whose (m + i)-th coordinate works modulo d i , for i = 1, . . . , m . For this reason, and assuming the list d 1 , . . . , d m of torsion orders fixed all along the paper, we shall denote this abelian group simply as Z m . We shall slightly abuse language and call an abelian basis of Z m any set of generators of the smallest possible cardinal, namely m.
We shall be interested in direct products of finitely generated free and abelian groups, namely groups of the form G = F n × Z m . The group G being non-abelian, it will be convenient to admit both additive and multiplicative notation for the elements in Z m G; to this end, consider the standard presentation , and let us abbreviate their element normal forms w(x)t a 1 1 t a 2 2 · · · t a m m just as wt a , where a = (a 1 , . . . , a m ) ∈ Z m , and t is a formal symbol serving only as a pillar to hold the vector a up in the exponent. This way, the operation in G is given by (ut a )(vt b ) = uvt a+b in multiplicative notation, while the abelian part works additively, as usual, up in the exponent. In particular, the trivial element is t (0,...,0) = t 0 , and t i = t e i , where e i = (0, . . . , 1, . . . , 0), i = 1, . . . , m, are the vectors in the canonical basis of Z m . We extend this notation to subsets S ⊆ Z m G, which are denoted by t S . For an element in normal form wt a , w ∈ F n is called its free part, and the vector a ∈ Z m its abelian part.
Note that the group G fits in the middle of the natural splitting short exact sequence where ι is the inclusion map, and π is the projection to the free part wt a → w. The groups of this form are called free-times-abelian and are the main object of study in the present paper. It is straightforward to see that any subgroup H G is again free-times-abelian; concretely, the restriction of (1) to H again gives a splitting (since Hπ F n is free) short exact sequence and it easily follows that where σ is a (any) splitting of π |H . Therefore, any subgroup H G is isomorphic to F n × A, where n ∈ N ∪ {∞} and A is a subgroup of Z m (and so again finitely generated abelian, with a possibly different sequence of torsion orders). The claim below follows immediately and will become important in Section 4.

Corollary 2.1.
A subgroup H F n × Z m is finitely generated if and only if its projection Hπ to the free part is finitely generated; otherwise, it is countably generated.
It is also obvious from (2) that Taking respective basis for each factor we reach our notion of basis for a subgroup of G.
where A is the p × m matrix having a i as i-th row, L H = b 1 , . . . , b q Z m , and ω = wφρ is the abelianization of the expression of w in base {u 1 , . . . , u p }; that is, φ is the change of basis Hπ w → ω, where w = ω(u 1 , . . . , u p ), and ρ is the abelianization F {u 1 ,...,u p } F p Z p ; see Figure 1.
An immediate consequence of the above discussion is the following useful equivalence.
Remark 2.5. Let wt a ∈ G and H G with basis {u 1 t a 1 , . . . , u p t a p ; t b 1 , . . . , t b q }, then wt a ∈ H ⇔ w ∈ Hπ and a ∈ wφρA + L H Remark 2.6. The natural extension of Lemma 2.4 works as well for non finitely generated subgroups H F n × Z m . In this case, p = ∞, a basis for H looks like {u 1 t a 1 , . . . ; t b 1 , . . . , t b q }, and Eq. (3) is true as written, understanding that A is an integral matrix with countably many rows and m columns, and that Z ∞ means ∞ i=1 Z. Note that, then, ω is a row vector with countably many coordinates, all but finitely many of them being 0; so, the product ωA still makes sense with the usual meaning.

Enriched automata
In this section we briefly survey the basics on the classical Stallings automata, to then develop our enriched theory (restricted to free-times-abelian groups F n × Z m , see [5,12] for a more general and detailed account, including the case of semidirect products).
This geometric approach dates back to the 1980's, with the ideas of Serre, Stallings and others (see [33,36]) interpreting the subgroups of the free group F n = X | − as covering spaces of the bouquet of n circles. This topological viewpoint was later reformulated in a more combinatorial way in terms of pointed X-automata -that is, digraphs labeled by letters in X with a distinguished (initial and terminal) vertex -and can be summarized in Theorem 3.4; see [1,22] for details and proofs. The precise notion of automaton used in this context is stated below.
The involutive closure of a set X (usually understood as an alphabet) is the disjoint union X ± := X X −1 , where X −1 := {x −1 : x ∈ X} is the set of formal inverses of X.
Definition 3.1. Let X be a set. By an (involutive and pointed) X-automaton Γ we mean a X ± -labeled digraph such that for every arc e ≡ p x q (reading x ∈ X ± ) there exists a unique (inverse) arc e −1 ≡ p x −1 q (reading x −1 ), with a distinguished vertex called the basepoint of Γ (which acts as the unique initial and accepting vertex for Γ).
If e ≡ p x q is an arc in Γ, then we say that p and q are respectively the initial vertex or origin of e (denoted by ιe), and the terminal vertex or end of e (denoted by τe); and that x is the label of e, denoted by X (e). We also say that the vertices p, q are adjacent, and that the arc e is incident to both p and q. The sets of vertices and arcs of Γ are denoted by VΓ and EΓ respectively. An involutive X-automaton is said to be saturated (or complete) if every vertex is the origin of an x-arc, for every x ∈ X ± .
A walk in an automaton Γ is a finite alternating sequence γ = p 0 e 1 p 1 · · · e n p n such that ιe i = p i−1 and τe i = p i , for i ∈ [1, n]. If p 0 = p n we say that γ is a (closed) p 0 -walk. The length of a walk is the number of arcs in the sequence. Walks of length 0 correspond precisely to the vertices in Γ. A walk is said to exhibit backtracking if it has two consecutive arcs which are inverses of each other, and is called reduced otherwise.
The label (resp., free label) of a walk γ is the element in (X ± ) * (resp., in F X ) given (resp., represented) by the sequence of labels in the arcs of γ, assumed to be the empty string 1 (resp., the trivial element 1) if the walk consists of just a vertex. It is easy to see that the set of free labels of -walks in an involutive X-automaton Γ is a subgroup of F X . It is called the subgroup recognized by Γ, denoted by Γ .
We denote by E + (Γ) the subset of arcs in Γ labeled by elements in X (which we call the positive arcs of Γ). Note that we can represent involutive automata using only the positive arcs of Γ (this is called the positive part of Γ), with the convention that every x-arc e can also be crossed backwards, reading x −1 (corresponding to the hidden inverse arc e −1 ). Unless stated otherwise, the automata appearing throughout the paper will be assumed to be pointed and involutive. We will refer to them simply as automata. Note that if, in an involutive automaton Γ, we identify mutually inverse arcs and ignore the labeling and basepoint, then we obtain an undirected multigraph, which we call the underlying (undirected) graph of Γ.
If a graph Γ can be obtained by identifying a vertex of some graph ∆ with a vertex of some disjoint non-trivial tree T, then we say that T is a hanging tree of Γ . A hanging tree is maximal if it is not contained in any other hanging tree. Both notions extend naturally to involutive automata via the corresponding underlying graphs.

Definition 3.2.
An X-automaton is said to be deterministic if no two arcs with the same label depart from (or arrive at) the same vertex; and core if every vertex appears in some reduced -walk. Note that being core is equivalent to being connected and having no hanging trees not containing the basepoint. The core of an automaton Γ, denoted by core(Γ), is the maximum core subautomaton of Γ, i.e., the automaton obtained after taking the basepoint component of Γ and removing from it all the hanging trees not containing the basepoint. Note that core(Γ) = Γ . Finally, an X-automaton is said to be reduced if it is both deterministic and core.
Important examples of pointed involutive automata are Schreier and Stallings automata, which we define below.  (H, B), is the automaton with set of vertices H\F (the set of right cosets of H); an arc Hu v Huv (from Hu to Huv labeled by v) for every coset Hu ∈ H\F and every element v ∈ B; and the coset H as basepoint.
Note that Schreier automata are always connected, deterministic, and saturated, but not necessarily core. The core of Sch(H, B) is a reduced (involutive and pointed) B-automaton, called the Stallings automaton of H (w.r.t. B) and denoted by St (H, B); that is, St(H, B) = core (Sch(H, B)). Clearly, Sch(H, B) = St (H, B) = H. Note that both Schreier and Stallings automata depend on the free basis chosen for the ambient group, and hence on the ambient group itself. (We alert the reader that, throughout the paper, Stallings automata relative to different ambient groups and bases shall be considered for the same subgroup.) Theorem 3.4 (J. R. Stallings [36]). Let F X be a free group with basis X. Then, the map is a bijection. Furthermore, finitely generated subgroups correspond precisely to finite automata and, in this case, the bijection is algorithmic.
To compute St(H, X) (given a finite set of generators S for H) we start by building the so-called flower automaton Fl(S) of S, which is obtained after identifying the basepoints of the (involutive) petals spelling the generators in S, which we can assume to be reduced words. Note that, by construction, Fl(S) is core and recognizes H, but may fail to be deterministic at the basepoint. To fix this, one can successively identify the possible arcs breaking determinism. It is clear that these identifications, called foldings, do not change the recognized subgroup. Of course, a folding can produce new nondeterministic situations to be fixed, but since the number of arcs in the graph is finite, and decreases with each folding, the process finishes after a finite number of steps, producing as a result a deterministic X-automaton recognizing H. Moreover, since the folding process can only produce hanging trees containing the basepoint, the final object is still core, and hence a reduced X-automaton recognizing H. Theorem 3.4 states that this resulting automaton must be precisely St (H, X). Furthermore, the bijectivity of (4) implies that the result of the folding process depends neither on the order in which the foldings are performed, nor on the starting (finite) generating set taken for H, but only on the subgroup H F X itself.
For the opposite direction, suppose we are given a finite reduced X-automaton Γ. Consider a spanning tree T of Γ and denote by p T q the unique reduced walk from a vertex p to a vertex q using only arcs in T; and by γ T e the -walk , where e ∈ EΓ ET. It is not difficult to see that the set B T := { X (γ T e ) : e ∈ E + Γ ET } constitutes a free basis of the subgroup Γ F X . We say that B T is the (positive) T-basis of Γ , that the γ T e 's are the (positive) T-petals, and that the e's are the (positive cyclomatic) T-arcs of Γ.
Since the Stallings automaton of any finitely generated subgroup H F n is computable, we can immediately compute a basis for H as described above, and decide membership for H simply by checking whether the candidate reduced word w ∈ F n labels a -walk in St (H, X). Other well-known algorithmic applications of Theorem 3.4 include the study of intersections (see Section 4), and the description of finite index subgroups (see Section 5). Also, the classical Nielsen-Schreier Theorem follows immediately: any subgroup H F n is the fundamental group of the underlying graph of St(H, X) and hence it is free.
In [5] we developed a broader generalization of Stallings' techniques oriented towards extensions of the form F n Z m , not yet available in published form. Below, we present this theory restricted to the case of free-times-abelian groups. Our fundamental object is an extension of the X-automata used in the free case: we shall also admit abelian labels at the end and origin of every arc, and a subgroup of Z m labeling the basepoint of the automata. The precise definition follows. In more detail, an enriched automaton Γ consists of: The body of an enriched automaton Γ, denoted by Γ * , is the result of removing from Γ the basepoint subgroup; whereas the skeleton of Γ, denoted by sk(Γ), is the result of removing all the abelian information (i.e., the basepoint subgroup and all the abelian labels) from Γ. Note that sk(Γ) = sk(Γ * ) is a standard X-automaton. An enriched X-automaton Γ is said to be deterministic (resp., connected, core, reduced) if its skeleton sk(Γ) is so, and we define the core of an enriched automaton accordingly.
If an arc e ≡ p q is labeled by (a, x, b) then we write p q e ≡ (with the first and second abelian labels at the beginning and end of the enriched arc, and the free label in the middle). As in the free case, the idea is that the labeling (of the arcs) in an enriched automaton Γ extends to a G-labeling on the walks (sequences of successively adjacent arcs) in Γ. For enriched automata the rules are the following: 2. Successive arcs in a walk read the product (in G) of the labels of the arcs.
3. Elements from L Γ are thought of as labeling "infinitesimal" commuting loops at , that is, when at one can freely pick an element from L Γ Z m G as a label.
More precisely, the enriched label of a non-trivial walk γ = e 1 1 · · · e k k in Γ, k 1, is X (e i ) t 2 (e i ) ∈ G; note that the label of γ as a walk in the skeleton is just X (γ) = X (e 1 ) 1 · · · X (e k ) k ∈ F n . As a convention, we admit any element in L Γ as a possible label of the trivial -walk.
Recall that a walk beginning and ending at the basepoint is called a -walk. An element (in G) labeling a -walk in an enriched automaton Γ is said to be recognized by Γ; for example, every l ∈ L Γ is so. It is straightforward to check that the set of all the elements recognized by an enriched automaton Γ is a subgroup of G: it is called the subgroup recognized by Γ, and denoted by Γ . Note that sk(Γ) = ( Γ )π, and Γ = core(Γ) .
It is clear that every subgroup in G is recognized by some enriched automata. This is obvious for subgroups inside Z m G (which can be set as basepoint subgroups); on the other hand, given any element ut a ∈ G with u = 1, we can always consider the petal automaton Fl(ut a ); that is, the following directed -walk: Note that the label of this cycle is ut a and hence Fl(ut a ) = ut a . Then, given a finite Of course, a given subgroup H G can be recognized by (infinitely) many enriched automata. Namely, (i) the skeleton of the flower automaton defined above depends on (the free parts of) the chosen set of generators S for H; and there is also a lot of freedom in the distribution of the abelian labeling since: (ii) for any petal, we could alternatively have put the a label at the end of any of the other arcs in the walk (among infinitely many other possible configurations reading the same element ut a ); and (iii) every abelian label in Γ works modulo the basepoint subgroup L Γ . So, the map Γ → Γ from the set of enriched automata to the set of subgroups of G is onto but very far from injective. To make it bijective we have to distinguish one and only one geometric object recognizing each subgroup. Definition 3.6. Let Γ be an enriched X-automaton, and let T be a spanning tree of Γ. We say that Γ is T-normalized if it is reduced, and the abelian labels of Γ are concentrated at the ends of the arcs outside T (i.e., 1 (e) = 0 for every e ∈ EΓ, and 2 (e) = 0 for every e ∈ ET). It is easy to see that, if Γ is a T-normalized automaton recognizing H, then sk(Γ) = St(Hπ, X), and L Γ = H ∩ Z m ; see Proposition 3.9.
It is not difficult to see that, after taking the quotient modulo the basepoint subgroup L Γ (denoted by "mod "), we finally reach the desired unicity: for any given subgroup H G, and any given spanning tree T of St (Hπ, X), every two T-normalized enriched automata recognizing H are equal modulo L Γ . This uniquely determined object is called the T-Stallings automaton for H, denoted by St T (H, X). When the spanning tree T is clear from the context we will usually omit any reference to it and write St(H, X). Also, since unicity is usually not necessary for computational purposes, we will often abuse terminology and call any normalized automaton recognizing H a "Stallings automaton for H".
Finally, in order to obtain the desired bijection, we need a uniform way of distinguishing spanning trees in all the enriched automata. This can be done by fixing a total order in the set X ∪ X −1 : for any given Γ, declare that is in T and then, recursively, add to T the edge (together with its other incident vertex) with smallest possible label incident to the oldest vertex present in T at that moment and not closing a path. This determines (even in the infinite case) a spanning tree in Γ denoted by T (Γ); see [5,11,12] for details. We say that Γ is -normalized if it is T (Γ)-normalized, and we write The main result in this section is the following bijection between subgroups of G and (uniformly chosen) enriched Stallings automata, which are furthermore computable in the finitely generated case. Theorem 3.7. Let F X be a free group with finite basis X, let Z m be a finitely generated abelian group, and let be a total order on X ± . Then, the map is a bijection. Furthermore, finitely generated subgroups correspond precisely to finite automata and, in this case, the bijection is algorithmic.
Let us focus on the algorithmic behavior of bijection (5). Given a finite family of generators for a subgroup H G, we can algorithmically obtain a Stallings automaton recognizing H by constructing the corresponding (enriched) flower automaton and appropriately adapting the folding process to the enriched scenario. To this end, we introduce two new "abelian transformations" intended to move the abelian mass around the automaton without changing the recognized subgroup. Definition 3.8. A vertex transformation consists in adding a vector c ∈ Z m to every abelian label in the neighborhood of a vertex p: It is obvious that these two abelian transformations do not affect the skeleton of the automaton, and it is straightforward to check that they do not affect the recognized subgroup either. Note that a vertex transformation at the basepoint (say by a vector c) corresponds to a conjugation by t c , which in our case belongs to the center of F n × Z m .
We claim that these two abelian transformations suffice to convert any folding situation in sk(Γ) into a folding situation in Γ: suppose that e and f are two arcs in Γ with the same free label X (e) = X (f) departing from the same vertex, say p = ιe = ιf. Distinguish two cases: the open case, when they are non-parallel (i.e., τe = τf), and the closed case when they are parallel (i.e., τe = τf).
In the open case, in order to fold e and f, we have to make sure that both arcs have the same abelian labels: performing an appropriate arc transformation to f we can get Note that the above procedure does not work in the closed situation because the vertex transformation at τf also affects the label 2 (e) we want to match. In this case, instead, we just fully remove f and update the basepoint subgroup from L Γ to L Γ + − 2 (e) + 1 (e) − 1 (f) + 2 (f) in order to take into account the purely abelian contribution of the closed walk around the folded cycle.
x i a b Figure 6: Closed enriched folding It is straightforward to see that these two types of enriched foldings do not change the recognized subgroup. Hence, interspersing the appropriate abelian transformations, we can mimic the (any) folding procedure for the skeleton to obtain a reduced enriched automaton recognizing H which, after normalizing w.r.t. a chosen spanning tree T, will become a Stallings automaton Γ for H.
Note that then the basepoint subgroup of Γ is the original basepoint subgroup for Fl(H) possibly enlarged by the contributions of the eventual closed foldings in the reduction process, whereas sk(Γ) = sk(Γ * ) = St(Hπ, X). Therefore, calling B T = { (γ T e ) : e ∈ E + Γ ET } (the set of enriched labels of the positive T-petals in Γ), we have (B T )π = B T (the positive T-basis of Hπ). Indeed, besides providing the desired bijection (5), enriched Stallings automata encode the internal structure (and, in particular, a basis) of the subgroups of G in a very transparent way.
is a free basis for Γ * (called the (positive) T-basis of Γ * ) which, joined to an abelian basis for L Γ , constitutes a basis for H.
Proof. The inclusion L Γ Γ ∩ Z m is obvious by construction. For the opposite inclusion, and w(u i t a i ) denotes a reduced word on the u i t a i 's. Since the free part of this element is trivial, and {u i } i is freely independent, then w must be the trivial word and thus t a = t l ∈ L Γ , as we wanted to see. For the second claim, it is enough to consider the homomorphism Hπ → H given by X (γ T e ) → (γ T e ), for each arc e ∈ EΓ T, and recall the decomposition (2). Definition 3.10. If Γ is a T-normalized automaton recognizing H G, then any B T defined as above is called an enriched T-basis of Γ * . So, the union of an abelian basis of L Γ , and an enriched T-basis of Γ * is a basis for Γ .
The above considerations, together with the algorithmic nature of bijection (5), allow us to easily compute bases of finitely generated subgroups, and solve the subgroup membership problem within free-times-abelian groups. Corollary 3.11. There exists an algorithm which given a finite family of elements S ⊆ G outputs a basis for the subgroup S G.
Proof. It is enough to construct a Stallings automaton Γ for S (normalized w.r.t. some spanning tree T). Then, an abelian basis for S ∩ Z m = Γ ∩ Z m = L Γ can be computed from the generating set at hand, using linear algebra, whereas an enriched T-basis of Γ * is obtained after reading the enriched labels of the T-petals in Γ.

Intersection of subgroups
Intersections of subgroups is a research topic with a long and interesting history. For an arbitrary group G, we can consider the following concept and problem as natural starting points.

Definition 4.1.
A group G is said to satisfy the Howson property (or to be Howson for short) if the intersection of any pair of finitely generated subgroups of G is again finitely generated.
Subgroup intersection problem, SIP(G). Given two finite sets of words R, S in the generators of G, decide whether the intersection R ∩ S is finitely generated; and, in the affirmative case, compute a generating set for the intersection.
It is well known that subgroups of (non-cyclic) finitely generated free groups are again free, but can have any (finite or countably infinite) rank. However, in 1954 A. G. Howson proved that the intersection of two finitely generated subgroups of the free group is always finitely generated; see [18]. The classical Stallings automata machinery provides a neat and algorithmic-friendly proof for this remarkable fact, and furthermore makes it possible to compute a basis for the intersection. The key concept needed for the geometric proof of this fact is that of product of automata.
The following easily checkable facts complete the link between intersections of subgroups of the free group and products of Stallings automata.

Lemma 4.4.
If Γ 1 and Γ 2 are deterministic X-automata, then the product Γ 1 × Γ 2 is again deterministic, and recognizes the intersection of the corresponding subgroups; that is, However, in general, the product of two core automata is not necessarily core (not even connected); so we need to take the core to reach the Stallings automaton of the intersection.  for any pair of finitely generated subgroups 1 = H 1 , H 2 F X , and conjectured that the factor '2' can be removed; see [28]. After many unsuccessful attempts and partial results, two correct (and unrelated) proofs appeared almost simultaneously more than fifty years later (see [16,27] and the remarkable unpublished simplification in [15]), and a third one shortly after (see [21]).
In [2], B. Baumslag extended Howson's result by showing that the free product of Howson groups is again Howson. However, the same is not true for direct products: Moldavanski (see [3]) already showed that, in F {x,y} × Z, the intersection of the easy looking subgroups xt, y and x, y is the normal closure of y in F {x,y} , which is not finitely generated; see Section 6.1 below for our geometric interpretation of this interesting example. Therefore, in this context the Subgroup Intersection Problem SIP(G) emerges as a natural and interesting question, specially the decision part (which trivializes in the free case).
The purpose of the present section is to solve SIP(G) using our enriched version of Stallings automata (Theorem 3.7). We approach the problem from a similar perspective to that used in the solution to SIP(F n ): in particular, we shall adapt the definition of product of two finite automata to the enriched setting, and obtain an enriched version for Lemma 4.4. However, crucial differences must appear with respect to the free case because the situation is intrinsically different, now with G not being Howson.
Observe also that, if H 1 , H 2 are finitely generated, then H 1 π and H 2 π (and hence H 1 π ∩ H 2 π) are so; but (H 1 ∩ H 2 )π is a (possibly strict) subgroup of the latter, and may very well not be finitely generated. See the characterization in Proposition 4.18, and Examples 6.1 and 6.2 (Case 2).
As in the free case, the (core of the) product of enriched automata encodes all the information about the intersection. However, in this case, the resulting doubly-enriched automaton is not a genuine Stallings automaton. Below, we state the enriched version of Lemma 4.4, which is clear again by inspection. We say that Γ is equalizable if the label wt (a,b) of any -walk in Γ satisfies (a + L 1 ) ∩ (b + L 2 ) = ∅. Note that, when Γ is finite, this can be algorithmically tested by normalizing w.r.t. some previously chosen spanning tree T and, for every arc e with terminal abelian label (a, b) = (0, 0), checking whether (a + L 1 ) ∩ (b + L 2 ) = ∅ (this is enough since, after normalization, (a, b) is also the abelian label of the petal γ T e ). If Γ is equalizable, after normalizing w.r.t. some spanning tree T, we can compute a witness c ∈ (a + L 1 ) ∩ (b + L 2 ) for each arc outside T, and replace the double labeling (a, b) with c; finally replace the pair of basepoint subgroups (L 1 , L 2 ) with its intersection L 1 ∩ L 2 . The resulting enriched automaton is called the equalization of Γ w.r.t. T (or the T-equalization of Γ). G is equalizable if and only if every word in H 1 π ∩ H 2 π admits compatible completions in H 1 and H 2 ; i.e., if for every w ∈ H 1 π ∩ H 2 π, C H 1 (w) ∩ C H 2 (w) = ∅. That is, if and only if (H 1 ∩ H 2 )π = H 1 π ∩ H 2 π, which, as explained in Remark 4.7, is not always the case.
Let {u 1 t a 1,1 , . . . , u p 1 t a 1,p 1 ; t b 1,1 , . . . , t b 1,q 1 } and {v 1 t a 2,1 , . . . , v p 2 t a 2,p 2 ; t b 2,1 , . . . , t b 2,q 2 } be finite bases for H 1 and H 2 , respectively, and let B = {w 1 , . . . , w r } be a free basis for H 1 π ∩ H 2 π (all written in terms of the original generators X, T for G). This means that, for i = 1, 2, ..,v p 2 } , and H 1 π ∩ H 2 π F r = F {w 1 ,...,w r } (note that since both p 1 and p 2 are finite, r is also finite). Now, consider the following homomorphisms and matrices which compose the diagram in Figure 8: • φ (resp., φ 1 , φ 2 ) is the isomorphism sending each word in H 1 π ∩ H 2 π (resp., H 1 π, H 2 π) in the original basis {x 1 , . . . , x n } to its expression in the basis {w 1 , . . . , w r } (resp., {u 1 , . . . , u p 1 }, {v 1 , . . . , v p 2 }); • ρ (resp., ρ 1 , ρ 2 ) is the abelianization map of F r (resp., F p 1 , F p 2 ), not to be confused with the corresponding restrictions of the global abelianization map F n Z n ; • B i is the abelianization of the inclusion map H 1 π ∩ H 2 π → H i π (after the change of bases φ and φ i ), i = 1, 2; note that, although these inclusions are injective maps, the B i 's need not be so; • A i is the p i × m integer matrix having as j-th row the vector a i,j ∈ Z m , i = 1, 2; • C i := B i A i , i = 1, 2 (where every column of the result must be interpreted modulo the corresponding torsion), and D := C 1 − C 2 is the so-called difference matrix. Proposition 4.12. Let H 1 , H 2 be finitely generated subgroups of F n × Z m . With the above notation, where D = B 1 A 1 − B 2 A 2 , and ρ : F r Z r is the abelianization map; see Figures 8 and 9.
Proof. By definition, (H 1 ∩ H 2 )π consists exactly of the elements w ∈ H 1 π ∩ H 2 π admitting compatible abelian completions in H 1 and H 2 , i.e., such that On the other side, from Lemma 2.4 and the commutativities in Figure 8 it is clear that the abelian completion of an element w ∈ H Finally, the normality of (L 1 + L 2 )D −1 ρ −1 in F r follows immediately from the abelianity of (L 1 + L 2 )D −1 and the surjectivity of the abelianization ρ.
The key point in Equation (6) is that it allows to express (H 1 ∩ H 2 )π (and so, its finitely generated character) in abelian terms. Now, we are ready to establish the claimed link between Stallings automata and Cayley digraphs of abelian groups. Recall that the vertical inclusions between the two rows in Figure 9 are all normal (since Z m and Z r are abelian, and ρ is onto).
We call M the s × r integer matrix having as rows the elements of some abelian basis for M (note that s r). Then, the Smith normal form of M is an integral s × r matrix S = diag(δ 1 , . . . , δ s ), where δ 1 , . . . , δ s ∈ Z \ {0}, δ 1 | · · · |δ s , and P and Q are invertible matrices (P ∈ GL s (Z), Q ∈ GL r (Z)) such that PMQ = S. If we finally define δ i := 0 for each i = s + 1, . . . , r (in case they exist), then This allows us to interpret the Stallings automaton of (H 1 ∩ H 2 )π as the Cayley multidigraph (a generalization of the classical Cayley digraph allowing repeated generators; see the precise definition below) of the finitely generated abelian group in Eq. (7); and ultimately, relate the rank of the intersection H 1 ∩ H 2 to the index of M in Z r .

Definition 4.13.
Let G be a group and let {{h i }} i∈I be a multiset of generators for G (i.e., a set of generators with possible repetitions). Then, the Cayley multidigraph of G w.r.t. {{h i }} i∈I , denoted by Cay(G, {{h i }} i∈I ), is the multidigraph with vertex set G, and an h i -arc g h i gh i for every g ∈ G, and every i ∈ I. It is allowed that, for some i ∈ I, h i is the trivial element, hence producing loops labeled by h i in every vertex. Of course, if {{h i }} i∈I is a set, then Cay(G, {{h i }} i∈I ) is the standard Cayley digraph of G.
Theorem 4.14. Let H 1 , H 2 be two finitely generated subgroups of F n × Z m . Then, either (H 1 ∩ H 2 )π is trivial, or (with the above notation) where B = {w 1 , . . . , w r } is a (finite) free basis for H 1 π ∩ H 2 π, {e 1 , . . . , e r } is the canonical basis of Z r , and {{e i Q}} i=1,...,r is the multiset consisting of the rows of Q (recall that S = PMQ) interpreted as elements of r i=1 Z/δ i Z.
Remark 4.15. Note that the generators e i Q in (10) must be interpreted as elements in an ordered multiset (in order to keep track of the link between generators in the corresponding automata).
Remark 4.16. Most of (the non-algorithmic part of) the analysis started in Figure 8 is still valid for arbitrary (maybe non finitely generated) subgroups H 1 , H 2 G. Then p 1 , p 2 and r may be infinite, but Equations (6) and (7) are still valid (with the natural definition of D as an ∞ × m integer matrix), and we can rephrase Theorem 4.14 saying that St((H 1 ∩ H 2 )π, {w 1 , . . . , w r }) is isomorphic to the corresponding Cayley multidigraph of a countably generated abelian group.
Of course, the situation is special in the degenerate case (H 1 ∩ H 2 )π = {1}. The following lemma clarifies the distinction between the two cases.
, which is non-trivial when r 2. Then, (18) follows easily from Equation (9): if the index |H 1 π ∩ H 2 π : (H 1 ∩ H 2 )π| is finite, then (18) corresponds precisely to the well-known Schreier index formula. Otherwise, (H 1 ∩ H 2 )π is a non-trivial normal subgroup of infinite index in H 1 π ∩ H 2 π and hence has infinite rank; and, on the other hand, s < r and the right hand side of (18) is infinite as well. The last claim is obvious from the above discussion.
A neat characterization of when the intersection of two finitely generated subgroups of G is again finitely generated follows easily from Theorem 4.14 and the previous considerations. Note that, since the parameters r and s in Proposition 4.18(c) are clearly computable, this immediately solves the decision part of SIP(G). (a) the intersection H 1 ∩ H 2 is finitely generated; (b) the projection (H 1 ∩ H 2 )π is finitely generated; (c) either r = 0, r = 1, or 2 r = s; (d) the (normal) subgroup (H 1 ∩ H 2 )π is either trivial, or has finite index in H 1 π ∩ H 2 π.
Finally, we can combine the developed machinery to compute an enriched Stallings automaton for H 1 ∩ H 2 .
(2) Replace each w i -arc in ∆ by a directed X-path spelling w i = w i (X) = 1, doubly-enriched with a pair of vectors (a i , b i ) ∈ Z m × Z m (attached, say, to the end of the last arc) such that w i t a i ∈ H 1 and w i t b i ∈ H 2 ; and attach the pair of subgroups (L 1 , L 2 ) to the basepoint.
(3) Reduce the resulting automaton until a reduced doubly-enriched automaton is obtained.
Proof. We start by computing the Stallings automata Γ 1 = St(H 1 , X) and Γ 2 = St(H 2 , X) (see Theorem 3.7). In particular, we can use linear algebra to obtain abelian-bases for the subgroups L 1 = H 1 ∩ Z m , L 2 = H 2 ∩ Z m , and hence an abelian basis for the subgroup Otherwise, 1 s = r (since we are assuming (H 1 ∩ H 2 )π is finitely generated) and we can apply Theorem 4.14: compute the Smith normal form for M, say S = diag(δ 1 , . . . , δ r ), where δ 1 , . . . , δ r ∈ Z \ {0}, δ 1 | · · · |δ r , together with invertible matrices P, Q ∈ GL r (Z) such that PMQ = S, and draw the Cayley multidigraph indicated in Eq. (10), corresponding to the finite abelian group r i=1 Z/δ i Z. After reinterpreting the labels accordingly, this is nothing else but the Stallings automaton ∆ of (H 1 ∩ H 2 )π as a subgroup of H 1 π ∩ H 2 π and w.r.t. the ambient free basis {w 1 , . . . , w r }. This is the content of step (1).
Note that each generator w i corresponds to an edge e i in Γ 1 × Γ 2 outside T with a double label 2 (e i ) = (a i , b i ) and closing a ( 1 , 2 )-walk γ T e i with label w i t (a i ,b i ) , such that w i t a i ∈ H 1 and w i t b i ∈ H 2 . After replacing every w i -arc in ∆ with the doubly enriched X-path γ T e i , successively folding the resulting automaton, and finally taking the core, we obtain a reduced doubly-enriched X-automaton ∆ such that its free part recognizes sk(∆ ) = (H 1 ∩ H 2 )π, and when read w.r.t. the first (resp., second) abelian components recognizes a subgroup of H 1 (resp., H 2 ). Note that no closed foldings are involved, since rk(∆) = rk(H 1 ∩ H 2 )π = rk(∆ ), so no vector gets added to the basepoint subgroups, which remain equal to L 1 and L 2 . This is the content of steps (2) and (3).
According to Definition 4.9, step (4) consists of three parts. Firstly, normalize ∆ w.r.t. some chosen spanning tree T (that is, use abelian transformations to concentrate the double abelian mass of ∆ into the heads of the edges outside T). Secondly, for every edge outside T, read the corresponding label wt (a,b) . By construction, wt a ∈ H 1 and wt b ∈ H 2 , but also w ∈ (H 1 ∩ H 2 )π and so, the coset intersection (a + L 1 ) ∩ (b + L 2 ) is non-empty; this means that ∆ is equalizable. Compute c ∈ (a + L 1 ) ∩ (b + L 2 ) and replace in ∆ the double labeling (a, b) with the genuine one c ∈ Z m . Finally, replace (L 1 , L 2 ) by L 1 ∩ L 2 as basepoint subgroup, and call Γ the final obtained automaton. This is the equalization process mentioned in step (4).
Since finite Stallings automata provide computable bases for the subgroups they recognize, the above results immediately solve the SIP for free-times-abelian groups. The computability part of the SIP problem refers to the case where the intersection H 1 ∩ H 2 is finitely generated. We claim that, even when it is not, we can also "compute" a basis for H 1 ∩ H 2 . It is not clear whether the above proof given for the finitely generated case generalizes to a recursive construction since one would have to do a similar procedure with increasing finite pieces of the (now infinite) Cayley graph from Theorem 4.14, and then somehow control or bound the effect of the foldings coming from new additions onto the previously computed part. Instead, we present an alternative approach covering both the finite and the infinite cases, and providing the desired result. The new key concept needed is that of vertex expansion, which we present below.

Definition 4.22.
Let Ω be a reduced doubly-enriched automaton normalized w.r.t. a spanning tree T, and let B be the corresponding basis for sk(Ω) . Then, given a B-automaton ∆, we define the vertex expansion of ∆ by Ω w.r.t. T as the doubly-enriched automaton ∆[Ω,T] obtained in the following way: 1. Replace every vertex p in ∆ by a copy T (p) of the X-labeled tree T (and denote by v (p) the copy of the vertex v ∈ VT in T (p) ).
2. For w ∈ B, replace every w-arc e ≡ p w q in ∆ by an arc ι (p) 3. Label each new edge ι (p) τ (q) by the full labeling (ι τ) from Ω.
4. Declare ( ) as basepoint, with attached basepoint subgroups (L 1 , L 2 ) as in Ω. Proof. It is enough to see that ∆[Ω,T] is deterministic, core, equalizable, and, furthermore, after equalization, it recognizes the intersection H 1 ∩ H 2 . The determinism of ∆[Ω,T] is clear from the determinism of ∆ and Ω (and hence of T). Second, it is easy to see that, since Ω is core and ∆ is core and saturated, ∆[Ω,T] is also core.
Now, let us see that ∆[Ω,T] is equalizable. Let γ be an arbitrary -walk in ∆[Ω,T] and consider its label (γ) = wt (a,b) . Note that, by construction, the projection of γ to ∆ is a -walk reading the same w ∈ F n ; therefore w ∈ ∆ = (H 1 ∩ H 2 )π, and hence there exist c ∈ Z m such that wt c ∈ H 1 ∩ H 2 . On the other hand, γ is verbatim a -walk in Ω with exactly the same doubly-enriched label wt (a,b) ; hence, wt a ∈ H 1 and wt b ∈ H 2 . Therefore, c ∈ (a + L 1 ) ∩ (b + L 2 ) = ∅, and ∆[Ω,T] is equalizable as claimed.
Finally, choose a spanning tree T, and (T-normalize and) equalize ∆[Ω,T] w.r.t. it; denote Γ the resulting enriched Stallings automaton (with basepoint subgroup L Γ = L 1 ∩ L 2 ). If wt c ∈ Γ , then wt (c,c) ∈ ∆[Ω,T] and, from the paragraph above, wt c ∈ H 1 ∩ H 2 ; hence, Γ H 1 ∩ H 2 . Conversely, if wt d ∈ H 1 ∩ H 2 then w ∈ (H 1 ∩ H 2 )π and so it is the free label of some -walk γ in Ω; then, the label of γ viewed as a -walk in Γ is wt c , for some c ∈ Z m , that is, wt c ∈ Γ H 1 ∩ H 2 . Therefore d − c ∈ L 1 ∩ L 2 and so wt d ∈ Γ . This shows that Γ = H 1 ∩ H 2 and completes the proof. Proposition 4.24 extends Theorem 4.20 by describing Stallings automata of general (not necessarily finitely generated) intersections. Below, we prove that this new approach can also be made algorithmic, even when the intersection is not finitely generated.  To recursively construct the body of Γ, start computing the core Ω of the (finite, doublyenriched) product Γ 1 × Γ 2 normalized w.r.t. a chosen spanning tree T, and the corresponding free basis B T = {w 1 , . . . , w r } for sk(Γ 1 ) × sk(Γ 2 ) = H 1 π ∩ H 2 π.
Once we have a free basis for H 1 π ∩ H 2 π we can compute the parameters δ 1 , . . . , δ r and the multiset {{e i Q}} i from Theorem 4.14. Let ∆ = Cay ( r i=1 Z/δ i Z , {{e i Q}} i ), which may be infinite (if and only if δ r = 0) but is always recursively constructible. Indeed, (for n = 0) let ∆ 0 be the subautomaton induced by the basepoint of ∆ (which may include loops), and for n = 1, 2, . . . construct the n-th ball ∆ n by adding to ∆ n−1 the (finitely many) vertices at distance n from , and (by inspection) all the arcs in ∆ within ∆ n . (For later use, note that all the arcs added in this step have one end at distance n and the other at distance either n or n − 1 from ; so any -walk created during this step must have length at least 2n.) Hereinafter, we reinterpret ∆ = St((H 1 ∩ H 2 )π, B T ) using the explicit bijection between the multiset {{e i Q}} i and the free basis B T given in the proof of Theorem 4.14.
From Remark 4.25, ∆[Ω, T] is also recursively constructible. In fact, since ∆ n−1 is a full subautomaton of ∆ n , then ∆ n−1 [Ω, T] is also a full subautomaton of ∆ n [Ω, T], which is computable by just exploding to T the new vertices, and adding arcs accordingly. Note that every ∆ n [Ω, T] is a full subautomaton of the equalizable automaton ∆[Ω, T], and therefore it is equalizable as well.
Finally, we extend the procedure to output a sequence Γ 0 , Γ 1 , Γ 2 , . . . recursively constructing a Stallings automaton Γ for the intersection H 1 ∩ H 2 ; namely, ∆[Ω, T] equalized w.r.t. to some (possibly infinite) spanning tree T: at step n = 0 declare T 0 := T to be the spanning tree for ∆ 0 [Ω, T], and equalize w.r.t. to it (see Proposition 4.24) to obtain Γ 0 ; at step n construct ∆ n [Ω, T] from ∆ n−1 [Ω, T], enlarge T n−1 to a spanning tree T n of ∆ n [Ω, T], and equalize the new arcs to obtain Γ n . If we call T the direct limit of { T n : n ∈ N }, then it is straightforward to see that T is a spanning tree for Γ, and that Γ 0 , Γ 1 , Γ 2 , . . . is a strictly increasing sequence of full subautomata of Γ whose direct limit is Γ. The claimed result follows.
Note that this last result immediately provides a recursive enumeration of a basis for the intersection H 1 ∩ H 2 . Furthermore, since the enumeration can be made in increasing order (e.g. w.r.t. the word length of the free parts), it turns out that we can obtain a recursive basis. Proof. Let Γ be the Stallings automaton for H 1 ∩ H 2 recursively described in the proof of Theorem 4.26. Since the basis for the abelian part is always finite, it is enough to see that a recursive basis B T (of the free part of the intersection described by the body of Γ) can be obtained. Following the notation in the previous proof, let B n denote the enriched T n -basis of Γ n (which is obviously computable since Γ n is finite). Then, it is clear that the increasing sequence B 0 , B 1 , B 2 , . . . entails a recursive enumeration of the T-basis B T = n∈N B n . Finally, note that every -walk in ∆ passing trough an arc outside ∆ n−1 has length at least 2n. Since vertex expansions do not decrease the length of petals, the same is true (after expanding) for the T-petals of Γ not included in Γ n−1 . Therefore, the free parts of the elements in B T B n−1 are all of length at least 2n. Now the decision of membership for B T is straightforward: given a candidate element ut a ∈ G with λ = |u|, it is enough to check whether it belongs to the finite portion B (λ−1)/2 of B T ; if so, answer yes, and otherwise answer no (since the rest of elements in B T have length at least 2( (λ − 1)/2 + 1) > λ). Hence, B T is recursive, and the proof is complete.

Applications to the index of subgroups
For a general group G and a subgroup H G = X , the Schreier graph Sch(H, X) has as vertices the set of (right) cosets of G modulo H; so, knowing Sch(H, X) we can determine a set of coset representatives for H G, and decide if the subgroup has finite or infinite index. This is the case in the free group: for a finitely generated subgroup H F X , one can compute St(H, X) = core(Sch(H, X)) and decide whether H is of finite index by checking whether St(H, X) is saturated (i.e., every vertex is the origin of an x-arc, for every x ∈ X ± ); in this case H is of finite index and the labels of selected paths from the basepoint to each vertex p in St(H, X) (for example, through a chosen spanning tree T) form a finite transversal; otherwise, H is of infinite index and we can recursively enumerate a transversal by constructing and reading bigger and bigger portions of all the hanging trees in Sch(H, X) going out of St(H, X). Furthermore, since this enumeration can be made in increasing order of the length of the elements, the obtained transversal is a recursive subset of F X = F n .
We aim to use our enriched Stallings machinery to understand the index of a subgroup H G given by a basis {u 1 t a 1 , . . . , u p t a p , t b 1 Applying well-known general properties of the index of intersections and direct products we have: Since claim that i∈I j∈J Hv i t c j = F n × Z m . In fact, for an arbitrary element wt a ∈ F n × Z m , we have w = uv i for some i ∈ I and u ∈ Hπ; choose b ∈ Z m so that ut b ∈ H and write a − b = l + c j for some j ∈ J and l ∈ L H ; then, wt a = uv i t a = (ut b · t l ) · v i t c j ∈ Hv i t c j . This completes the proof. Furthermore, when the index is infinite (and H is finitely generated), a transversal for L H in Z m is recursively enumerable using basic linear algebra techniques, and a transversal for Hπ in F n is also recursively enumerable (by reading first the finite core sk(Γ) and then bigger and bigger portions of all the hanging trees in the Schreier graph Sch(Hπ, X) going out of sk(Γ)). According to Proposition 5.1, combining these two recursive enumerations we can recursively enumerate a transversal for H. Moreover, since these two recursive enumerations can be done in increasing order (say, of the sum of absolute values of the coordinates, and of the word length, respectively) the obtained transversal is indeed recursive. The last claims are summarized below.

Proposition 5.2.
Let H G be a finitely generated subgroup given by a finite set of generators. Then, (i) there is an algorithm to decide whether H is of finite index and, in the affirmative case, compute the index and a transversal for H (i.e., FIP(G) is solvable); and (ii) H has a recursive transversal, which can be effectively computed.
Remark 5.3. Note that our geometric argument improves the proof for FIP(G) given in [9] by removing all the possible redundancy in the coset description, making unnecessary the (computationally expensive) cleaning procedure used there.
One last straightforward application of Proposition 5.1 is the extension of M. Hall's Theorem (see [17]) to the free-times-abelian context. A subgroup H of a free-timesabelian group G is called a factor (of G) if some (and hence, every) basis of H can be extended to a basis of G (which is equivalent to saying that Hπ is a free factor of the free part of G, and L H is a direct summand of the abelian part of G); see [32].
Proposition 5.4. Every finitely generated subgroup H F n × Z m is a factor of a finite index Proof. Let Γ be a Stallings graph for H. Add the necessary x-arcs, x ∈ X (with zero abelian labels) in order to obtain a saturated automaton, and complement the basepoint subgroup L H to a finite index subgroup L of Z m , i.e., L H ⊕ L fi Z m . By Proposition 5.1, the enriched automaton Γ obtained in this way corresponds to a subgroup K = Γ of finite index in F n × Z m and, by construction, H is a factor of K.

Examples
In this section we use enriched automata to study a couple of examples showing relevant situations that can occur when intersecting two finitely generated subgroups of F n × Z m .
Recall that in the graphical representation we shall omit all the trivial abelian labels, including the basepoint subgroup.

Moldavanski's example
Let H 1 = xt, y and H 2 = x, y be subgroups of the group Note that the basis {w 1 , w 2 } obtained for H 1 π ∩ H 2 π is exactly the same as the original basis for H 1 π and for H 2 π, namely w 1 = x and w 2 = y. According to our scheme, 1 0 . Therefore, δ 1 = 1, δ 2 = 0, and applying Theorem 4.14 we have that Since the obtained abelian group Z is infinite, the intersection H 1 ∩ H 2 is not finitely generated. Now, replace the arcs labeled by w 1 , w 2 by the corresponding enriched paths reading xt and y and note that there are no foldings available. Finally, (normalize and) equalize w.r.t. the only possible spanning tree T (consisting of the x-labeled (red) arcs in Figure 10) to obtain a Stallings automaton for H 1 ∩ H 2 .
· · · ; · · · y x Figure 10: Stallings automaton for xt, y ∩ x, y Therefore H 1 ∩ H 2 is not finitely generated, and B T = { x i yx −i : i ∈ Z } is a basis for H 1 ∩ H 2 = y .

Parameterized example
Consider the subgroups H 1 = x 3 t a , yxt b , y 3 xy −2 t c , t L 1 , and H 2 = x 2 t d , yxy −1 , t L 2 of the direct product F 2 × Z 2 , where a, b, c, d ∈ Z 2 , and L 1 , L 2 are subgroups of Z 2 .
According to our previous discussion, in order to compute (a Stallings automaton for) the intersection H 1 ∩ H 2 we first compute respective Stallings automata Γ 1 , Γ 2 for H 1 and H 2 , and then build its product Γ 1 × Γ 2 ; see Figure 11. Note that the product Γ 1 × Γ 2 is disconnected and has a hanging tree not containing the basepoint. After removal, we obtain the core of the doubly-enriched product which can be normalized as follows (the arcs outside the chosen spanning tree are drawn with thicker lines): Remark 6.1. The basis element y 3 xy −2 t c ∈ H 1 does not contribute to the core of the product Γ 1 × Γ 2 . In a similar vein, the abelian labels b, c no longer appear in the normalized product core ( Figure 12) and will not play any role in the intersection H 1 ∩ H 2 .
Note that this is the minimum possible sum of ranks for such an example: if one of the intersecting subgroups has rank 1, then the intersection must be cyclic; if one of the intersecting subgroups is abelian then the intersection has rank at most 2. It only remains to consider the case of two subgroups of rank 2 with trivial abelian part. But then, by Remark 4.19, H 1 ∩ H 2 is either non finitely generated or (H 1 ∩ H 2 )π = H 1 π ∩ H 2 π, and hence has rank bounded by 1(2 − 1)(2 − 1) + 1 = 2. So, the minimum possible ranks of subgroups H 1 , H 2 F 2 × Z with intersection of arbitrarily large finite rank are 3 and 2, as claimed.