Finite automata for Schreier graphs of virtually free groups

J. Group Theory 19 (2016), 25–54 DOI 10.1515/jgth-2015-0028 © de Gruyter 2016 Finite automata for Schreier graphs of virtually free groups Pedro V. Silva, Xaro Soler-Escrivà and Enric Ventura Communicated by James Howie Abstract. The Stallings construction for f.g. subgroups of free groups is generalized by introducing the concept of Stallings section, which allows efficient computation of the core of a Schreier graph based on edge folding. It is proved that the groups that admit Stallings sections are precisely the f.g. virtually free groups, this is proved through a constructive approach based on Bass–Serre theory. Complexity issues and applications are also discussed. 1 Introduction Finite automata have, over the years, become the standard representation of finitely generated subgroups Hof a free group FA. The Stallings construction constitutes a simple and efficient algorithm for building an automaton S.H/ which can be used for solving the membership problem of Hin FAand many other applications. This automaton S.H/ is nothing more than the core automaton of the Schreier graph (automaton) of Hin FA, whose structure can be described as S.H/ with finitely many infinite trees adjoined. Many features of S.H/ were (re)discovered over the years and were known to Reidemeister, Schreier, and particularly Serre [17]. One of the greatest contributions of Stallings [19] is certainly the algorithm to construct S.H/: taking a finite set of generators h1; : : : ; hmof Hin reduced form, we start with the so-called flower automaton, where petals The first named author was partially supported by CMUP (UID/MAT/00144/2013), which is funded by FCT (Portugal) with national (MEC) and European structural funds through the programs FEDER, under the partnership agreement PT2020. The second named author acknowledges support from Proyecto MTM2010-19938-C03-01 of Ministerio de Ciencia e Innovación of Spain. The third named author acknowledges partial support from the Spanish Government through project number MTM2011-25955. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 26 P. V. Silva, X. Soler-Escrivà and E. Ventura labelled by the words hi(and their inverse edges) are glued to a basepoint q0:  h1 11 h2  hm QQ. Then we proceed by successively folding pairs of edges of the form qa  pa ! r until no more folding is possible (so we get an inverse automaton). And we will have just built S.H /. For details and applications of the Stallings construction, see [1,6, 13]. Since S.H/ turns out to be the core of the Schreier graph of HFA, this construction is independent of the finite set of generators of Hchosen at the beginning, and of the particular sequence of foldings followed. And the membership problem follows from the fact that S.H/ recognizes all the reduced words representing elements of H,: : : and the reduced words constitute a section for any free group. Such an approach naturally invites generalizations for further classes of groups. For instance, an elegant geometric construction of Stallings type automata was achieved for amalgams of finite groups by Markus-Epstein [12]. On the other hand, the most general results were obtained by Kapovich, Weidmann and Miasnikov [7] for finite graphs of groups where each vertex group is either polycyclic-by-finite or word-hyperbolic and locally quasiconvex, and where all edge groups are virtually polycyclic. However, the complex algorithms were designed essentially to solve the generalized word problem, and it seems very hard to extend other features of the free group case, either geometric or algorithmic. Our goal in the present paper is precisely to develop a Stallings type approach with some generality which is robust enough to exhibit several prized algorithmic and geometric features, namely in connection with Schreier graphs. Moreover, we are able to identify those groups Gfor which this can be achieved: (finitely generated) virtually free groups. What ingredients do we need to get a Stallings type algorithm? First of all, we need a section Swith good properties that can emulate the role played by the reduced words in the free group. In particular, we need a rational language (i.e. recognizable by a finite automaton). We may of course need to be more restrictive than taking all reduced words, if we want our finite automaton to recognize all the representatives of Hf:g: Gin S. To get inverse automata, it is also convenient to have SDS1 Secondly, the set Sgof words of Srepresenting a certain g2Gmust be at least rational, so we can get a finite automaton to represent each of the generalized Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 27 petals. Third, the folding process to be performed in the (generalized) flower automaton (complemented possibly by other identification operations) must ensure in the end that all representatives of elements of Hin Sare recognized by the automaton. And folding is the automata-theoretic translation of the reduction process w!wtaking place in the free group. So we need the condition Sg1g2Sg1Sg2, to make sure that the petals (corresponding to the generators of H) carry enough information to produce, after the subsequent folding, all the representatives of elements of H. This is how we were led to our definition of Stallings section. It is somewhat surprising how much we can get from this concept, which turns out to be more robust than one would expect. Among other features, we can mention independence from the generating set (so we can have Stallings automata for free groups when we consider a noncanonical generating set!), or closure of rational sets with respect to computation of normal forms. We present some applications of the whole theory, believing that many others should follow in due time, as happened in the free group case. The paper is structured as follows. In Section 2 we present the necessary basic concepts. The theory of Stallings sections is presented in Section 3. In Section 4, we discuss the complexity of the generalized Stallings construction in its most favourable version. In Section 5 we use Muller–Schupp’s Theorem and Bass–Serre theory to prove that those groups admitting a Stallings section are precisely the finitely generated virtually free groups. In Section 6 we show that we can assume stronger properties for Stallings sections with an eye to applications, namely the characterization of finite index subgroups. 2 Preliminaries Given a finite alphabet A, we denote by Athe free monoid on A, with 1 denoting the empty word. A subset of a free monoid is called a language. We say that AD.Q; q0; T; E/ is a (finite) A-automaton if: Qis a (finite) set, q02Qand TQ, EQAQ. Anontrivial path in Ais a sequence p0 a1 ! p1 a2 !    an ! pn with .pi1; ai; pi/2Efor iD1; : : : ; n. Its label is the word a1   an2ACDAn ¹1º: It is said to be a successful path if p0Dq0and pn2T. We consider also the Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 28 P. V. Silva, X. Soler-Escrivà and E. Ventura trivial path p1 ! pfor p2Q. It is successful if pDq02T. The language L.A/ recognized by Ais the set of all labels of successful paths in A. A path of minimal length between two vertices is called a geodesic, and so is its label by extension. The automaton AD.Q; q0; T; E/ is said to be deterministic if, for all p2Q and a2A, there is at most one edge of the form .p; a; q/. We say that Ais trim if every q2Qlies in some successful path. Given deterministic A-automata AD.Q; q0; T; E/ and A0D.Q0; q0 0; T 0; E0/, a morphism 'WA!A0is a mapping 'WQ!Q0such that q0'Dq0 0and T ' T0, .p'; a; q'/ 2E0for every .p; a; q/ 2E. It follows that L.A/L.A0/if there is a morphism 'WA!A0. The morphism 'WA!A0is: injective if it is injective as a mapping 'WQ!Q0, an isomorphism if it is injective, T0DT ' and every edge of E0is of the form .p'; a; q'/ for some .p; a; q/ 2E. The star operator on A-languages is defined by LD[ n0 Ln; where L0D ¹1º. A language LAis said to be rational (or to admit a rational expression) if Lcan be obtained from finite languages using the operators union, product and star a finite number of times. Alternatively, Lis rational if and only if it is recognized by a finite (deterministic) A-automaton AD.Q; q0; T; E/, see [3, Section III]. The definition generalizes to subsets of an arbitrary monoid Min the obvious way. We denote the set of all rational languages LAby Rat A. Note that Rat A, endowed with the product of languages, constitutes a monoid. In the statement of a result, we shall say that a rational language Lis effectively constructible if there exists an algorithm to produce from the data implicit in the statement a finite A-automaton Arecognizing L. It is convenient to summarize some closure and decidability properties of rational languages in the following proposition (see, e.g., [3]). The prefix set of a language LAis defined as Pref.L/ D ¹u2AjuA\L¤ ;º: Arational substitution is a morphism 'WA!Rat B(where Rat Bis endowed Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 29 with the product of languages). Given LA, we denote by L' the language [ u2L u' B: Since singletons are rational languages, monoid homomorphisms constitute particular cases of rational substitutions. More generally, a mapping WA!2Bis called a transduction. Its graph is defined by D ¹.u; v/ 2ABjv2uº: The transduction is rational if is a rational subset of the monoid AB. Rational substitutions constitute a particular case of rational transductions. Rational transductions are most commonly defined through rational transducers, i.e. finite automata with edges labelled by elements of ARat B. The inverse transduction 1WB!2Ais defined by v1D ¹u2Ajv2uº: It is well known (see [3, Section III.4]) that rational transductions are closed under inversion. Proposition 2.1. Let Abe a finite alphabet and let K; L Abe rational. Then: (i) K[L; K \L; AnL; Pref.L/ are rational, (ii) if WA!2Bis a rational transduction, then L is rational, (iii) if 'WA!Mis a monoid homomorphism and Mis finite, then X'1is rational for every XM. Moreover, all the constructions are effective, and the inclusion KLis decidable. The class of context-free languages (see [3, Chapter II] for details) constitutes the next level in the classical Chomsky hierarchy above rational languages. We have also the following closure property (see [3, Corollary III.4.2]): Proposition 2.2. Let WA!2Bbe a rational transduction and let LAbe context-free. Then L is context-free. Given an A-automaton Aand LA, we denote by AuLthe A-automaton obtained by removing from Aall the vertices and edges which do not lie in some successful path labelled by a word in L. Proposition 2.3. Let Abe a finite A-automaton and let LAbe a rational language. Then AuLis effectively constructible. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 30 P. V. Silva, X. Soler-Escrivà and E. Ventura Proof. Write AD.Q; q0; T; E/ and let A0D.Q0; q0 0; T 0; E0/be a finite A-automaton recognizing L. The direct product A00 D.Q Q0; .q0; q0 0/; T T0; E00/ is defined by E00 D ¹..p; p0/; a; .q; q0// j.p; a; q/ 2E; .p0; a; q0/2E0º: Let Bdenote the trim part of A00 (by removing all vertices/edges which are not part of successful paths in A00; this can be done effectively). Then, AuLcan be obtained by projecting onto the first component the various constituents of B. Given an alphabet A, we denote by A1the set of formal inverses of A, and write e ADA[A1. We say that e Ais an involutive alphabet. We extend 1WA!A1; a 7! a1; to an involution on e Athrough .a1/1Da; .uv/1Dv1u1.a 2A; u; v 2e A/: An automaton Aover an involutive alphabet e Ais said to be involutive if, whenever .p; a; q/ is an edge of A, so is .q; a1; p/. Therefore it suffices to depict just the positively labelled edges (having label in A) in their graphical representation. An involutive automaton is inverse if it is deterministic, trim and has a single final state (note that for involutive automata, being trim is equivalent to being connected). If the latter happens to be the initial state, it is called the basepoint. The next result is folklore. For a proof, see [1, Proposition 2.2]. Proposition 2.4. Given inverse automata Aand A0, then L.A/L.A0/if and only if there exists a morphism 'WA!A0. Moreover, such a morphism is unique. Given an alphabet A, let denote the congruence on e Agenerated by the relation ¹.aa1; 1/ ja2e Aº:(2.1) The quotient FADe A=is the free group on A. We denote by We A!FAthe canonical morphism u7! Œu. Alternatively, we can view (2.1) as a confluent length-reducing rewriting system on e A, where each word w2e Acan be transformed into a unique reduced word wwith no factor of the form aa1. As a consequence, the equivalence uv”uDv .u; v 2e A/ solves the word problem for FA. We shall use the notation RADe A. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 31 We close this section with the following equivalent version of Benois’ Theorem, relating rational languages with free group reduction: Theorem 2.5 (Benois [2]). If Le Ais rational, then Lis an effectively constructible rational language. 3 Stallings sections Let Gbe a (finitely generated) group generated by the finite set A. More precisely, we consider an epimorphism We A!Gsatisfying a1D.a/1(3.1) for every a2A. A homomorphism satisfying condition (3.1) is said to be matched. Note that in this case (3.1) holds for arbitrary words. For short, we shall refer to a matched epimorphism We A!G(with Afinite) as an m-epi. We shall call a language Se Aasection (for ) if S DGand S1DS. For every XG, we write SXDX1\S: We say that an effectively constructible rational section SRAis a Stallings section for if, for all g; h 2G: (S1) Sgis an effectively constructible rational language, (S2) Sgh SgSh. Note that (S2) immediately yields Sg1gnSg1   Sgn(3.2) for all g1; : : : ; gn2G. Moreover, in (S1) it suffices to consider Sa for a2A. Indeed, by (3.2), and since S1DSand SgDgfor every g2G, we may write S.a1an/ DSa1   San\S(3.3) and Sa1 iDS1 ai for all ai2e A. Then, by Proposition 2.1 and Theorem 2.5, Sgis a rational language for every g2G; furthermore, it is effectively constructible from Sa1; : : : ; San. Note that if Sis a Stallings section, then S[ ¹1ºis also a Stallings section. Indeed, it is easy to see that conditions (S1) and (S2) are still verified: namely, if gh D1, then 12SgS1 gDSgShand so Sgh [ ¹1º  SgShas required. The next result shows that the existence of a Stallings section is independent from the finite set Aand the m-epi We A!Gconsidered. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 32 P. V. Silva, X. Soler-Escrivà and E. Ventura Proposition 3.1. Let We A!Gand 0We A0 !Gbe two m-epis. Then, Ghas a Stallings section for if and only if Ghas a Stallings section for 0. Proof. Let SRAbe a Stallings section for . There exists an m-epi 'We A!e A0 such that '0D. Write S0DS'. By Proposition 2.1 (ii) and Theorem 2.5, S0is an effectively constructible rational subset of RA0. We claim that S0 gDSg'(3.4) holds for every g2G. Indeed, let u2S0 g. Then uDv' for some v2Sand v Dv'0Dv'0Du0Dg: Hence v2Sgand so S0 gSg'. Conversely, let v2Sg. Then v' 2S' DS0and v'0Dv'0Dv Dg; hence v' 2S0 gand so (3.4) holds. Since .S0/1D.S'/1D.S'/1DS1'DS' DS0; it follows from (3.4) that S0is a section for 0. Moreover, (S1) is inherited by S0 from Sby Proposition 2.1 (ii) and Theorem 2.5. Finally, for all g; h 2G, we get S0 gh DSgh'.SgSh/' D.SgSh/' D.Sg'/.Sh'/ D.Sg'/.Sh'/ DS0 gS0 h; hence (S2) holds for S0and so S0is a Stallings section for 0. By symmetry, we get the required equivalence. Proposition 3.2. Free groups of finite rank and finite groups have Stallings sections. Proof. Let Abe a finite set and consider the canonical m-epi We A!FA. Let SDRADe A; which is rational by Theorem 2.5. Since SgD ¹gºfor every g2FA, it is immediate that Sis a Stallings section for . Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 33 Assume now that Gis finite and We A!Gis an m-epi. We show that SDRA is a Stallings section for . For every g2G, we have SgDg1\RADg1. Since both g1and RAare effectively constructible rational languages, so is their intersection and so (S1) holds. Finally, let u2Sgh and take v2Sh. Then .uv1/ Dghh1Dg and so uv12g1DSg. Hence uDuv1vDuv1v2SgSh and (S2) holds as well. Therefore RAis a Stallings section for . Given an m-epi We A!Gand H6G, we define the Schreier automaton .G; H; / to be the e A-automaton having: the right cosets Hg (g2G) as vertices, Has the basepoint, edges Hg a ! Hg.a/ for all g2Gand a2e A. It is immediate that .G; H; / is always an inverse e A-automaton, but it is infinite unless Hhas finite index in G. Moreover, L..G; H; // DH1. We will prove that .G; H; / uSis an effectively constructible finite inverse automaton when Sis a Stallings section for . The following lemmas pave the way for the construction of .G; H; / uS: Lemma 3.3. Let We A!Gbe an m-epi. Let Abe a trim e A-automaton and let pa ! q be an edge of Afor some a2e A. Let Bbe obtained by adding the edge qa1 ! p to A. Then .L.B//  h.L.A//i. Proof. Write AD.Q; q0; T; E/. We can factor any u2L.B/as uDu0a1u1   a1un; where a1labels each visit to the new edge. We show that u 2 h.L.A//iby induction on n. The case nD0being trivial, assume that n1and the claim holds for n1. Writing vDu0a1u1   a1un1, we have a path in Bof the form q0 v ! qa1 ! pun ! t2T: Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 40 P. V. Silva, X. Soler-Escrivà and E. Ventura Lemma 4.1. Let SRAbe a Stallings section for the m-epi We A!Gand let g2G. Then there exists a finite trim uniterminal e A-automaton Cgsatisfying SgL.Cg/g1: Proof. Let CD.Q; i; T; E/ be the minimum automaton of Sg(or any other finite trim automaton with a single initial vertex recognizing Sg) and let Cgbe obtained by identifying all the terminal vertices of C. Clearly, Cgis a finite trim uniterminal automaton and SgDL.C/L.Cg/yields SgDSgL.Cg/. It remains to prove that .L.Cg// Dg. Let u2L.Cg/. Then there exists a factorization uDu0u1   uksuch that iu0 ! t0; s1 u1 ! t1; : : : ; sk uk ! tk are paths in Cwith sj; tj2T. Take a path ivj ! sjin C, for jD1; : : : ; k. Then vj; vjuj2L.C/and so vjD.vjuj/ Dg. Hence, ujD.v1 jvjuj/ Dg1gD1 and so u D.u0u1   uk/ Du0Dg since u02L.C/DSg. Thus, .L.Cg// Dgand so L.Cg/g1 as required. Next we introduce a multiplication of (finite trim) uniterminal automata: given (finite trim) uniterminal e A-automata AD.Q; i; t; E/ and A0D.Q0; i0; t0; E0/, let AA0D.Q00; i; t0; E00/be the (finite trim) uniterminal e A-automaton obtained by taking the disjoint union of the underlying graphs of Aand A0and identifying t with i0. Lemma 4.2. Let SRAbe a Stallings section for the m-epi We A!G, and let g; g02G. Let Aand A0be finite trim uniterminal e A-automata satisfying SgL.A/g1; Sg0L.A0/g01: Then Sgg0L.AA0/.gg0/1: Proof. Since L.A/L.A0/L.AA0/, we get in view of (S2) Sgg0SgSg0L.A/L.A0/L.AA0/: Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 41 Now let u2L.AA0/. Then ulabels a path in AA0of the form iu0 ! pu1 ! pu2 !    uk1 ! puk ! t0; where we emphasize all the occurrences of the vertex pobtained through the identification of tand i0. Now it is easy to see that there exist paths iu0 ! tand i0uk ! t0 in Aand A0, respectively. Moreover, for each jD1; : : : ; k 1, there exists either a path tuj ! t in Aor a path i0uj ! i0 in A0. Now, in view of .L.A// Dgand .L.A0// Dg0, we can use the same argument as in the proof of Lemma 4.1 to show that ujD1for jD1; : : : ; k 1. Hence u D.u0u1   uk/ D.u0uk/ Dgg0and so L.AA0/.gg0/1 as required. In view of the preceding two lemmas, we can now set an algorithm to construct the automata Aiin the proof of Theorem 3.9. All we need for a start are the minimum automata of Sa for each a2A(or any other finite trim automaton with a single initial vertex recognizing Sa ; this can be effectively constructed by (S1)). Following the argument in the proof of Lemma 4.1, we may identify all the terminal vertices to get finite trim uniterminal e A-automata Ca satisfying Sa L.Ca /a1: Note that, since S1DS, we get finite trim uniterminal e A-automata Ca1satisfying Sa1L.Ca1/a11 by exchanging the initial and the terminal vertices in Ca and replacing each edge pb ! q by an edge qb1 ! p: Now, given an element hi2G, we may represent it by some reduced word a1   an(ai2e A), and may compute AiD..   .Ca1Ca2/Ca3/    /Can: Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 42 P. V. Silva, X. Soler-Escrivà and E. Ventura By Lemma 4.2, Aiis a finite trim uniterminal e A-automaton satisfying ShiL.Ai/hi1: What is the maximum size of Airelatively to jhij? What is the time complexity of the algorithm for its construction? Note that we start with only finitely many “atomic” automata Ca (a2A). Hence the number of vertices (edges) in Aiis a bounded multiple of jhij, therefore is O.jhij/, and the time complexity of the construction (disjoint union followed by identification of two vertices, jhij  1 times) is also clearly O.jhij/. This is why we gave ourselves (and the reader) the trouble of constructing the Aithis way instead of just taking the minimum automaton of Shi, whatever that may be! But what is the time complexity of the full algorithm leading to the Stallings automaton .G; H; / uS? It is also useful to discuss the complexity of the important intermediate B3in the proof of Theorem 3.9 since B3suffices for such applications as the generalized word problem: indeed, since B3satisfies (3.5), we may replace .G; H; / uSby B3in Corollary 3.10. Let nD jh1jCCjhmj. It follows easily from our previous discussion of the time complexity of the construction of the Aithat B0(and therefore B1and B2) can be constructed in time O.n/. Since we get to B3through complete folding, the complexity of constructing B3is that of the classical Stallings construction in the free group. The Ackermann hierarchy is a sequence .Ak/kof transformations of Ndefined by A1.n/ Dnand Ak.n/ DAn k1.1/ for k > 1 (where An k1denotes the n-fold composition of Ak1). Following Nivatsch [15], we can define the Ackermann function AWN!Nby A.n/ DAn.3/: The inverse Ackermann function ˛WŒ0; C1Œ!Nis then defined by ˛.x/ Dmin¹n2NjA.n/ xº: The inverse Ackermann function grows extremely slowly. Using a famous result of Tarjan on Union-Find [20] (see also [4]) Touikan proved in [21] that such complexity is O.n˛.n//, i.e. very close to linear. Therefore B3can be constructed in time O.n˛.n//. We shall now discuss the complexity of the construction of the Stallings automata: Theorem 4.3. Let SRAbe a Stallings section for the m-epi We A!Gand let HD hh1; : : : ; hmi6 f:g: G. Then .G; H; / uScan be constructed in time O.n3˛.n//, where nD jh1jCCjhmj. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 43 Proof. We go back to the proof of Theorem 3.9, starting at B3. The number of vertices of B3is O.n/ and therefore we have O.n2/candidate pairs to J. For each one of these pairs, we must decide whether or not they belong to J. This involves bounding the complexity of the algorithm described in the proof of Lemma 3.8. Let p; q be distinct vertices of B3and let q0denote its basepoint. Take two geodesics q0 u ! pand q0 v ! q. Clearly, gD.uv1/ can be represented by a word of length O.n/. It follows from the previous discussion on the complexity of the construction of Aithat we may construct a finite trim uniterminal e A-automaton Cg satisfying SgL.Cg/g1 in time O.n/. Performing a complete folding on Cg(in time O.n˛.n//), we get a finite inverse e A-automaton Dgsatisfying SgL.Dg/g1: Since Sis a constant for our problem, we can compute an element s2S\L.Dg/DSg in time O.n/ and check if s2L.B3/in time O.n/. Therefore, by the proof of Lemma 3.8, we can decide whether or not .p; q/ 2Jin time O.n˛.n//. Since we had O.n2/candidates to consider, we may compute Jin time O.n3˛.n//. It is very likely that this upper bound can be improved. Since B4is obtained from B3by identifying the pairs in Jfollowed by complete folding, and B3has O.n/ vertices, it follows that B4can be constructed in time O.n3˛.n// in view of Touikan’s bound. For the last step, we must discuss the time complexity of the algorithm in the proof of Proposition 2.3. Note that B4has O.n/ vertices and therefore (since the alphabet is fixed) O.n/ edges. Since Sis a constant for our problem, we can build the direct product of B4by some deterministic automaton recognizing Sin time O.n/ and compute its trim part in time O.n/ (we have O.n/ vertices and O.n/ edges), and the final projection can also be performed in linear time. Therefore .G; H; / uScan be constructed in time O.n3˛.n//, which means very close to cubic complexity. We should stress that the above discussion of time complexity was performed for a fixed Stallings section of a fixed group. But the computation of a Stallings section for a (virtually free) group can be in itself a costly procedure, particularly if it is supported by Bass–Serre theory as in the present case. This will become more evident throughout the next section. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 44 P. V. Silva, X. Soler-Escrivà and E. Ventura 5 Virtually free groups A group is virtually free if it has a free subgroup of finite index. Some recent papers involving virtually free groups include [5,9, 10,18]. Next we recall the concept of graph of groups, central in Bass–Serre theory [17]. In Serre’s viewpoint, a graph is a structure of the form D.V; E; ; N/, where: Vis a nonempty set (vertices), Eis a set (edges), WE!Vis a mapping (target mapping), NW E!Eis an involution without fixed points. Concepts such as cycle, connectedness, tree or subgraph are defined in the obvious way. If is connected and TEdefines a subtree of connecting all the vertices, we say that Tis a spanning tree of . We write ve ! wif e Dwand Ne Dv. This allows us to view as an E-automaton whenever convenient. Note that ve ! wif and only if wNe ! v. A (finite) graph of groups over a (finite) connected graph is a structure of the form GD..Gv/v2V; .Ge/e2E; .e/e2E/; (5.1) where: Gvis a group for every v2V(vertex groups), Geis a group for every e2Esatisfying GNeDGe(edge groups), eWGe!Ge is a monomorphism for every edge e2E(boundary monomorphisms). Let P.G/denote the quotient of the free product .v2VGv/FEby the normal subgroup generated by the elements of the form e.ge/Ne.gNe/1.e 2E; g 2GeDGNe/: Note that eNearises from the particular case gD1. Serre presents two alternative constructions for the fundamental group of G: The cycle construction. Fix v02V. Let C.G; v0/denote the set of all closed paths of the form vnDv0 e1 //v1 e2 "" vn1 en88 en1 oov2 e3 oo in (including the trivial path). Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 45 The fundamental group 1.G; v0/of the graph of groups (5.1) with respect to v02Vis the subgroup of P.G/consisting of the following elements: for every closed path of the above form, 1.G; v0/contains all the elements of the form g0e1g1: : : engn;with gi2Gvifor iD0; : : : ; n: (5.2) We shall use the notation .g0e1g1   engn/ De1   en. The spanning tree construction. Let Tbe a spanning tree of the graph . The fundamental group 1.G; T / is the quotient of P.G/by the normal subgroup generated by the edges in T. Serre shows that the canonical projection P.G/!1.G; T / induces an isomorphism from 1.G; v0/to 1.G; T /, which implies in particular that both constructions are independent from the choice of v0and T. Therefore, we can benefit from the best of both worlds: 1.G; T / provides a nice canonical generating set, while 1.G; v0/provides the concept of reduced word (S-reduced in this text (S from Serre), to avoid confusion with free group reduced), which makes the cycle construction the preferred option, most of the time. A word of the form (5.2) is said to be S-reduced if the following two conditions hold: If nD0, then g0¤1. If 1i < n and eiC1D Nei, then gi…Geiei. Note that S-reduced words play a major role in the theory of graphs of groups due to the following two well-known properties: every element of 1.G; v0/n ¹1ºcan be represented by some S-reduced word, no S-reduced word represents the identity in P.G/(nor 1.G; v0/). It follows that the group Gv0(and therefore every vertex group) is naturally embedded into 1.G; v0/. HNN extensions and amalgamated free products arise as important particular cases of graphs of groups, by taking graphs with two edges, respectively of the form  e77Ne ww e ++. Ne kk Moreover, whenever is finite, the fundamental group 1.G; v0/can be built from the vertex groups using a finite number of HNN extensions and amalgamated free products, where the associated/amalgamated subgroups are of the form Gee. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 46 P. V. Silva, X. Soler-Escrivà and E. Ventura The nature of 1.G; v0/is conditioned by the nature of the vertex and edge groups. By a well-known theorem of Karrass, Pietrowski and Solitar [8] (see also [16, Theorem 7.3]), a finitely generated group is virtually free if and only if it is the fundamental group of a finite graph of finite groups. This important result provides the key to our main theorem: Theorem 5.1. A finitely generated group admits a Stallings section if and only if it is virtually free. Proof. Let Gbe a finitely generated group. Assume that Sis a Stallings section for the m-epi We A!G. We will show that the word problem submonoid 11 is context-free. By Muller–Schupp’s Theorem [14], this is equivalent to Gbeing virtually free. By the remark following the definition of Stallings section in Section 3, we can assume that 12S1. Let We A!FAdenote the canonical morphism, as usual. We show that a1   an211”Sa1   San\.11/¤ ; (5.3) holds for all a1; : : : ; an2e A. Indeed, since 12Sgif and only if gD1, we have a1   an211if and only if 12S.a1an/ . By equation (3.3), this is equivalent to 12Sa1   San, i.e. Sa1   San\.11/¤ ;: Therefore (5.3) holds. We define now a transduction We A!2e Aby .a1   an/ DSa1   San for a1; : : : ; an2e Aand 1 D1. Since D ¹¹aº  Saja2e Aº is clearly a rational subset of AA, then is a rational transduction, and so must be 1. Let LD11. By Muller–Schupp’s Theorem [14], Lis context-free and so L1is also context-free by Proposition 2.2. By (5.3), we have a1   an211”.a1   an/ \L¤ ; ” a1   an2L1 for all a1; : : : ; an2e A. Since 1211\L1, it follows that 11DL1and is therefore context-free. By Muller–Schupp’s Theorem, Gis virtually free. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 47 Conversely, assume that Gis virtually free. By the theorem ([8]) of Karrass, Pietrowski and Solitar, we may assume that GD1.G; v0/, where GD..Gv/v2V; .Ge/e2E; .e/e2E/ is a graph of groups over a finite connected graph D.V; E; ; N/, with finite vertex and edge groups. For every v2V, consider an alphabet AvDGvn ¹1ºand take Ato be the disjoint union ADE[[ v2V Av: We shall consider the involutive alphabet e A, hence it is convenient to set e1D Ne for every e2E. For every v2V, let 'vWf Av!Gvbe the canonical m-epi. Fix a spanning tree Tof and v02V. We have a canonical m-epi 'We A!1.G; T /. Composing with the canonical isomorphism 1.G; T / !1.G; v0/, we obtain an m-epi e A!1.G; v0/which, by abuse of notation, shall also be denoted by '. We define SRAto be the union of RAv0with the languages of the form .g0'1 v0/e"1 1.g1'1 v1/   e"n n.gn'1 vn/\RA; where "iD ˙1,e"i iDvi,iD1; : : : ; n, and g0e"1 1g1   e"n ngnis an S-reduced word of the form (5.2). We shall prove that Sis a Stallings section for the m-epi 'We A!1.G; v0/. Since every element of 1.G; v0/can be represented by an S-reduced word, it follows easily that S' D1.G; v0/. Since S-reduced words are well known to be closed under inversion, we have S1DS. Thus Sis a section for '. We may view as an E-automaton .V; v0; v0; E0/by taking E0D ¹.Ne; e; e/ je2Eº: The language of this automaton is precisely the set of closed paths with basepoint v0, i.e. C.G; v0/. We define now a rational transducer .V; v0; v0; E00/by replacing each label ein the edges of E0by ¹eº¹e; Ne1ºA e (note that we must admit the double representation of edges when we go from Eto e E). This defines a rational transduction WE!2A. By Proposition 2.1 (ii), .C.G; v0// is a rational language. Now it is easy to check that SD.A v0.C.G; v0// nL/ \RA; where Ldenotes the language of all words in Ahaving some factor of the form eue1or euNe; with u2.Gee/'1 e ; Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM 48 P. V. Silva, X. Soler-Escrivà and E. Ventura for some e2E. Note that the languages .Gee/'1 e are rational by Proposition 2.1 (iii). Since RAis also rational, it follows easily from Proposition 2.1 (i) that Sis a rational section for '. Moreover, the construction of Sis effective. Let g21.G; v0/. We must show that Sgis an effectively constructible rational language. If g¤1, then it is well known that all the S-reduced words representing garise from the same closed path v0 e1 ! v1 e2 !    en ! vnDv0: As vertex groups are finite, it follows that there exist only finitely many S-reduced words representing g. Using the transduction built to prove the rationality of S, adapted in the obvious way, we deduce that Sgis a finite union of rational languages, hence rational. If gD1, we get S1D1'1 v0\RAv0, also rational in view of Proposition 2.1. All the constructions are effective, so Sgis an effectively constructible rational language for every g. Finally, let g; h 21.G; v0/. We must show that Sgh SgSh. Note that the mapping defined above for S-reduced words extends naturally to S, taking values on the free monoid on E(identifying e1with Ne). Fix u2Sgand w2Sh. We can compute some word .uw/ 2Sgh by successively lifting the substitutions e.ge/Ne! gNe.e 2E; g 2GeDGNe/: Note that .uw/ is not unique, so we fix one of the possible choices. We may write u Du0p,w Dp1w0and .uw/  Du0w0for some u0; w0; p. Indeed, we may assume that WSS!Sis a mapping defined in the above terms. Without loss of generality, we shall assume that u0; w0¤1. The remaining cases constitute mere simplifications of this general case. Let z2Sgh. Then z Du0w0. If we compute .zw1/ , this implies that we must remove precisely jw0jedges from each of the words zand w1, hence the prefixes of zand .zw1/ ending at edge number ju0jmust coincide. Denote this prefix by z1and write .zw1/ Dz1s1. Similarly, the suffixes of zand .u1z/ starting at edge number jw0j(counting in reverse order) must also coincide. Denote this by z2and write .u1z/ Ds2z2. Now we have .zw1/  Du0p and .u1z/  Dp1w0, hence on computing xD..zw1/ .u1z/ / 2Sgh we must cancel pedges from each word. It follows that s2D.s1/1and the words xand zdiffer at most in the factor between the occurrence of edge number ju0jand the next edge. Write zDz1qz2. Note that, since every element of a vertex group has finite order and we have at our disposal an involutive alphabet, we can always, if necessary, replace the last vertex component of s1by an equivalent word so that s1 1qis reduced. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM Finite automata for Schreier graphs of virtually free groups 49 Let yDs1 1qz2. We have y' D.s1 1qz2/' D.s1 1z1 1z/' D.wz1z/' Dw' Dh: Since w2Sharises from an S-reduced word, it follows that jwjis minimum possible among ¹jtj j t2h'1ºand so jyjjwjDj.u1z/ jDjs2jCjz2jDjs1 1jCjz2jDjyj; whence jyjDjwj. It follows from minimality that the word ymust arise from an S-reduced word. Since y2RAby our preprocessing of s1(recall also that the first letter of z2is in e E), it follows that y2Sand so y2Sh. Therefore zDz1qz2Dz1s1s1 1qz2D..zw1/ /y 2SgSh and so we have Sgh SgSh. This completes the proof that Sis a Stallings section for '. 6 Sections with good properties Having established that finitely generated virtually free groups are precisely the groups with a Stallings section, we shall now discuss the possibility of imposing stronger conditions on their Stallings sections, with the purpose of allowing further applications of the Stallings automata .G; H; / uS. We start with the concept of extendable Stallings section, which will turn out to be useful to characterize finite index subgroups. Let Sbe a Stallings section for the m-epi We A!G. We say that Sis extendable if, for every u2S, there exists some w2RAsuch that uwSand u2Pref.S.uwnu1/ /(6.1) for almost all n2N. Proposition 6.1. Every finitely generated virtually free group has an extendable Stallings section. Proof. Let Gbe a finitely generated virtually free group. Assume first that Gis finite. Let We A!Gbe an m-epi. By the proof of Proposition 3.2, we may take SDRAand wD1for every u2S. Hence uwS. We have SgDg1for every g2G. Next we show that Pref.Sg/DRA. Let z2RAand take a2e Asuch that za 2RA. Since Gis finite, there exists some m2Nsuch that every element of Gcan be represented by some word of length < m. In particular, there exists some x2RAsuch that ..amz1//g Dx and jxj< m. Hence .zamx/ Dgand so zamx2g1DSg. Since zam2RA and jxj< m, we get z2Pref.Sg/and so Pref.Sg/DRA. Brought to you by | Univ Politecnica Cat Authenticated Download Date | 3/4/16 5:54 PM