{'fraction_non_alphanumeric': 0.05603062320916905, 'fraction_numerical': 0.011528474212034383, 'mean_word_length': 3.4388910969793325, 'pattern_counts': {'":': 0, '<': 5, '<?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': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On an algorithm to decide whether a free group is a free factor of another

We revisit the problem of deciding whether a finitely generated subgroup H is a free factor of a given free group F. Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of H and exponential in the rank of F. We show that the latter dependency can be made exponential in the rank difference rank(F) - rank(H), which often makes a significant change.

sometimes play an important role in purely language-and monoid-theoretic questions (e.g. the type II conjecture, see [6] for a survey). Algorithmic questions (the word problem, the conjugacy problem, etc.) have been very influential in group theory throughout the 20th century, starting from the work of Dehn, and specialists of combinatorics on words find a particular interest in the challenges posed by the analogous combinatorics of the free group. Recent work on important non-commutative groups like the Thompson group and the so-called automata groups strongly relies on the formalism of finite state automata (see [3,7,22] for recent examples). It is already a classical result that these automata-theoretic and combinatorial points of view converge in the (admittedly simpler) study of the subgroups of free groups, this is central in the algorithmic problem tackled here and is discussed in detail in the first part of this paper.
Let us also mention another reason for the recent multiplication of research projects on the boundary between computer science and combinatorial group theory. Public-key cryptography relies heavily on group theory: sometimes finite groups such as the groups of units in modular arithmetic, or the groups of rational points on elliptic curves over finite fields, sometimes infinite non-commutative groups like the braid groups (see for instance [2,4,21] and many others). At any rate, the design of more robust cryptographic schemes and the attack of such schemes rely on a deeper understanding of the combinatorial and algorithmic properties of non-commutative groups.
As mentioned above, the combinatorial and algorithmic problems concerning free groups are of special interest. Free groups are archetypal groups, whose structure is far from being totally elucidated, and the efficient solution of standard problems in their context can shed some light on the possible solution of the same problems in more complex groups. Moreover, the solution of algorithmic problems in free groups may be more attainable since we can use the resources of combinatorics on words and automata theory.
We now present the specific algorithmic problem addressed in this paper. For the classical facts about free groups recorded below without a reference, we refer the reader to the book by Lyndon and Schupp [12]. It is well-known that the minimal sets of generators, or bases, of a free group F all have the same cardinality, called the rank of F . Moreover, if F has finite rank r, every r-element generating set of F is a basis, see [12,Prop. I.3.5]. In this paper, we consider only finite rank free groups.
Let H be a subgroup of a free group F , written H ≤ F . Then H itself is a free group whose rank may be greater than the rank of F . We say that H is a free factor of F , written H ≤ ff F , if there exist bases B of H and A of F such that B ⊆ A (free factors can be defined in all groups by a universal property, but the operational definition given here is sufficient for the purpose of this study). It is well known that one can decide whether a given finite rank subgroup H ≤ F is a free factor of F , but the known algorithms have a rather high time complexity. More precisely, the best of these algorithms require time that is polynomial in the size of H and exponential in the rank of F , see Section 1.3 below for the details.
Here, the size of H is taken to be the sum of the lengths of a finite set of generators of H in F .
We propose a new algorithm to decide whether a given finitely generated subgroup H is a free factor of the free group F , which is polynomial in the size of H and exponential in the rank difference between F and H. In many instances, this represents a substantial advantage over exponential dependency in the rank of F .
Our algorithm relies essentially on a careful analysis of the construction of the graph representation of H. More precisely, once a basis A of the ambient free group F is fixed, there is a natural and elegant representation of the finitely generated subgroups of F by A-labeled graphs (or inverse automata). This constructiona graphical representation of ideas that go back to the early part of the twentieth century [19,Chap. 11] -was made explicit by Serre [20] and Stallings [23]. It has been used to great profit by many authors since the late 1970s, see [8,13,14,26] for recent examples. Given a finite set of generators of H (as reduced words over the alphabet A ∪ A −1 ), the graph representation of H can be effectively constructed (see [23], [14], etc). The number of vertices and edges of this graph is bounded above by ℓ, the sum of the lengths of a set of generators of H, and the whole representation can be computed in time at most O(ℓ 2 ) (in fact, in time O(ℓ log * ℓ) according to a recent announcement 1 by Touikan [25]). We discuss this representation in more detail in Section 1.2 below, and we show in Sections 2 and 3 how to use it to decide more efficiently the free factor relation.
It is interesting to note that our algorithm is the first to be expressed entirely in terms of the graph representation of H. Let us also emphasize that we do not claim that our algorithm is optimal. It is an open question whether one can decide the free factor relation H ≤ ff K in time polynomial both in the size of H and in the size, or the rank of K.

Background
If A is a basis of a free group F , we often write F = F (A) and we represent the elements of F as reduced words over the alphabet A. More precisely, we consider the set of all words on the symmetrized alphabetÃ = A ∪ A −1 , where A −1 = {a −1 | a ∈ A} is a set that is disjoint from A, equipped with an explicit bijection with A, namely a → a −1 . It is customary to extend the mapping u → u −1 to all words u ∈Ã * by letting (a −1 ) −1 = a for each a ∈ A, 1 −1 = 1 (where 1 denotes the empty word) and (a 1 a 2 · · · a n ) −1 = a −1 n · · · a −1 2 a −1 1 for all a 1 , . . . , a n ∈Ã. A word inÃ * is reduced if it contains no factor of the form aa −1 or a −1 a with a ∈ A, and it is well known that F can be identified with the set of reduced words over A. We denote by ρ the map that assigns to each word u the corresponding reduced word uρ ∈ F (A), obtained by iteratively deleting all factors of the form aa −1 or a −1 a (a ∈ A).

On inverse automata
We describe the main tool for the representation of subgroups of free groups in terms of automata (see [17]). Readers less familiar with this terminology may think of automata as edge-labeled directed graphs.
An automaton on alphabet A is a triple of the form A = (Q, q 0 , E) where Q is a finite set called the state set, q 0 ∈ Q is the initial state, and E ⊆ Q × A × Q is the set of edges, or transitions. A transition (p, a, q) is said to be from state p, to state q, with label a. The label of a path in A (a finite sequence of consecutive transitions) is the sequence of the labels of its transitions, a word on alphabet A, that is, an element of the free monoid A * . We write p u −→ q if there is a path from state p to state q with label u. The language accepted by A is the set L(A) of all words in A * which label a path in A from q 0 to q 0 .
This definition of automata leads naturally to the definition of a homomorphism ϕ from an automaton A = (Q, q 0 , E) to an automaton A ′ = (Q ′ , q ′ 0 , E ′ ) (over the same alphabet A): ϕ is a mapping from Q to Q ′ such that ϕ(q 0 ) = q ′ 0 , and such that whenever (p, a, q) ∈ E, we also have (ϕ(p), a, ϕ(q)) ∈ E ′ . The homomorphism ϕ is an isomorphism if it is a bijection and if ϕ −1 is also a homomorphism.
The automaton A is called deterministic if no two distinct edges with the same initial state bear the same label, that is, The automaton is called trim if every state q ∈ Q lies in some path from q 0 to q 0 .
In the sequel, we consider automata where the alphabet is symmetrized, that is, the alphabet is of the formÃ = A ∪ A −1 . We say that A is dual if for each a ∈ A, there is an a-labeled edge from state p to state q if and only if there is an a −1 -labeled edge from q to p, Let us immediately record the following fact. Fact 1.1. Let A be a deterministic dual automaton. If a word u labels a path in A from state p to state q, then so does the corresponding reduced word uρ. Moreover L(A) is a submonoid ofÃ * and L(A)ρ is a subgroup of F (A). Now let A = (Q, q 0 , E) be a trim dual automaton and let p, q ∈ Q be states of A. If w = a 1 · · · a n ∈Ã * is a non-empty word, the expansion of A by (p, w, q) is the automaton obtained from A by adding n − 1 vertices q 1 , . . . , q n−1 and 2n edges p Note that this automaton is still trim and dual. Moreover, if p = q = q 0 , then we observe the following. Proposition 1.2. Let A = (Q, q 0 , E) be a trim dual automaton, let H = L(A)ρ and let w be a non-empty word. If B is the expansion of A by (q 0 , w, q 0 ), then L(B)ρ is the subgroup generated by H and wρ, that is, L(B)ρ = H, w .
Proof. Let C be the dual automaton consisting of the state q 0 and the states and edges added to A in the expansion. It is immediate that L(C)ρ is the subgroup of F (A) generated by wρ.
If u ∈ L(B), we can factor a path q 0 u −→ q 0 according to the successive visits of state q 0 . The resulting factorization of u makes it clear that u is a product of elements of L(A) and L(C). Thus, L(B) is the submonoid generated by L(A) ∪ L(C), and L(B)ρ is the subgroup generated by L(A)ρ and wρ. This concludes the proof.

Reduced inverse automata
The automaton A is called inverse if it is deterministic, trim and dual. It is reduced if every state q ∈ Q lies in some path from q 0 to q 0 , labeled by a (possibly empty) reduced word. We note the following result, a cousin of [24,Thm 1.16]. Proof. Let A = (Q, q 0 , E) and B = (P, p 0 , D) be reduced inverse automata such that L(A)ρ = L(B)ρ. We construct an isomorphism ϕ between A and B as follows. We first let ϕ(q 0 ) = p 0 .
Let q ∈ Q. Since A is reduced, there exist reduced words u and v such that the word uv is reduced, q 0 u −→ q and q v −→ q 0 . Then uv ∈ L(A)ρ, so uv ∈ L(B)ρ, and hence uv ∈ L(B) by Fact 1.1. Thus uv labels a path in B from p 0 to p 0 , and we let ϕ(q) be the unique state in P such that p 0 We first verify that ϕ is well defined. Suppose that uv and u ′ v ′ are reduced words such that q 0 We note that u ′ v labels a path from q 0 to q 0 in A. If u ′ v is a reduced word, then by the same reasoning as above, u ′ v labels a path in B from p 0 to p 0 , say, p 0 If u ′ v is not reduced, and a is the first letter of v, then the last letter of u ′ is a −1 while the last letter of u is not a −1 . Therefore u ′ u −1 is reduced, u ′ u −1 ∈ L(A) and again, there is a path in B of the form p 0 This shows that ϕ is well defined. A dual construction yields a well-defined mapping ψ from P to Q such that, whenever p 0 Using the determinism of A and B, it is now immediate that ψ • ϕ is the identity on Q and ϕ • ψ is the identity on P .
There remains to verify that ϕ and ϕ −1 are homomorphisms. The case of ϕ −1 is dual of that of ϕ and we treat only the latter. That is, we want to show that if (q, a, q ′ ) is a transition in A, then (ϕ(q), a, ϕ(q ′ )) is a transition in B. Let uv and If uav ′ is reduced, then in B, there is a path from p 0 to p 0 labeled uav ′ , and by determinism, there is a transition (ϕ(q), a, ϕ(q ′ )). If uav ′ is not reduced, then either ua is not reduced or av ′ is not reduced. If ua is not reduced, then u = u 1 a −1 and by determinism, q 0 u1 −→ q ′ . As in the first part of the proof, it follows that at least one of u 1 v ′ and u 1 u ′ −1 is reduced, so p 0 u1 −→ ϕ(q ′ ) in B and hence there is a transition (ϕ(q), a, ϕ(q ′ )). The case where av ′ is not reduced is handled symmetrically, and this concludes the proof.
Let H be a subgroup of F (A). Say that an automaton A on alphabet A represents H if A is reduced and inverse and if L(A)ρ = H. Proposition 1.3 shows that there exists at most one such automaton, and we denote it by Γ A (H) if it exists. We now discuss the existence and the construction of Γ A (H) when H is finitely generated. (As it turns out, Γ A (H) always exists, but our interest in this paper is restricted to the finite rank case.) Let A be an automaton and let p, q be distinct states of A. The automaton obtained from A by identifying states p and q is constructed as follows: its state set is Q \ {p, q} ∪ {n}, where n is a new state; its initial state is q 0 (or n if p or q is equal to q 0 ); and its set of transitions is obtained from E by replacing everywhere p and q by n. If A is trim or dual, then so is the automaton obtained from A by identifying a pair of states. Now let A be a dual automaton. If A is not deterministic, there exist transitions (r, a, p) and (r, a, q) with p = q and a ∈Ã. Identifying p and q yields a new dual automaton B, and we say that B is obtained from A by an elementary reduction of type 1. Proof. It is easily seen that L(A) ⊆ L(B). For the converse, we use the notation given above: in B, the states p and q of A are replaced with a new state n. Let u ∈ L(B). Then there exists a path labeled u from the initial state of B (say, q 0 ) to itself. If that path does not visit state n, then u also labels a path from q 0 to itself in A and hence u ∈ L(A).
If that path does visit state n, we consider the factorization of u given by the passage of that path through n: we have u = u 0 u 1 · · · u r , r ≥ 1 and It follows that in A, u i -labelled paths exist, with end states p or q (or q 0 ). Then one of u 0 and u 0 a −1 a labels a path in A from q 0 to q. Similarly, one of u r and a −1 au r labels a path from q to q 0 (making due allowance if p or q is equal to q 0 ). And for each 1 ≤ i ≤ r, one of u i , a −1 au i , u i a −1 a and a −1 au i a −1 a labels a path in A from q to q. Therefore, there exists a path in A of the form q 0 v −→ q 0 such that uρ = vρ, which concludes the proof. Now assume that A is a deterministic dual automaton. Fact 1.5. Let A be an inverse automaton. Then A is non-reduced if and only if there exist states q = q 0 and p, and a letter a ∈Ã such that the only transitions of A involving q are (p, a, q) and (q, a −1 , p).
In graph-theoretic terms, this means that A is reduced if and only if no vertex of A has degree one (more precisely: no vertex is adjacent to a single A-labeled edge), except possibly q 0 .
Proof. By definition, A is not reduced if and only if there exists a state q that does not lie on any path from q 0 to itself, labeled by a reduced word. We first observe that the state q cannot be equal to q 0 since the empty word is reduced, and labels a path from q 0 to itself. Suppose now that there exist reduced words u, v with distinct last letters, labeling paths from q 0 to q: then uv −1 is a reduced word, labeling a path from q 0 to itself and visiting q. On the other hand, if every reduced word labeling a path from q 0 to q ends with, say, letter a ∈Ã, then every path from q 0 to itself visiting q has a non-reduced label. Thus A is not reduced if and only if there exists a state q = q 0 and every reduced word labeling a path from q 0 to q ends with the same letter. By determinism, this is equivalent to the existence of another state p such that the transitions involving q are (p, a, q) and (q, a −1 , p).
Let A be inverse and not reduced, and let a, p, q be as in Fact 1.5. If B is obtained from A by omitting state q and the transitions involving it, we observe that B is again an inverse automaton, and we say that B is obtained from A by an elementary reduction of type 2. Proof. Let a be a letter and let p, q be states of A as in Fact 1.5, and let us assume that B is obtained from A by omitting state q and the transitions involving it. It is easily seen that L(B) ⊆ L(A). Conversely, let u ∈ L(A). By Fact 1.1, uρ ∈ L(A). Now Fact 1.5 shows that the path q 0 u −→ ρq 0 in A cannot visit state q, since uρ is a reduced word. It follows that this path is also a path in B, uρ ∈ L(B) and hence uρ ∈ L(B)ρ.
Let A be a trim, dual automaton, and let B be an automaton obtained by iteratively performing elementary reductions, first of type 1 until the automaton is inverse, and then of type 2 until none is possible. Then B is a reduced inverse automaton, we write B = Aρ and we say that B is obtained from A by reduction. Moreover, Facts 1.4 and 1.6 show that L(A)ρ = L(B)ρ.
This leads directly to the well-known algorithm to construct a reduced inverse automaton representing a given finitely generated subgroup H. Let h 1 , . . . , h n be generators of H, and let us consider the automaton obtained from the trivial automaton (one vertex q 0 , no transitions) by performing successively expansions by (q 0 , h i , q 0 ) (1 ≤ i ≤ n) and then reducing the automaton. It follows from Propositions 1.2 and 1.3 that the resulting automaton is Γ A (H). Note that it does not matter which set of generators of H was used, nor in which order the elementary reductions were performed. Remark 1.7. This construction of Γ A (H) is well known, and can be described in many different ways, notably in terms of immersions over the bouquet of circles (Stallings [23]) or of closed inverse submonoids of a free inverse monoid (Margolis and Meakin [13]). Fact 1.8. There is a well-known converse to the above construction: if A is a reduced inverse automaton and H = L(A)ρ, then H has finite rank and a basis for H can be computed as follows (see Stallings [23]). Given a spanning tree T of the (graph underlying the) automaton A, for each state p, let u p be the reduced word labeling a path from q 0 to p inside the tree T . For each transition e = (p, a, q), let b e = u p au −1 q : then a basis of H consists of the elements b e , where e runs over the transitions e = (p, a, q) not in T and such that a ∈ A.
We note that, given a finite set h 1 , . . . , h n of elements of F (A) with total length ℓ = i |h i |, one can construct Γ A (H) in time at most O(ℓ 2 ) and Γ A (H) has v ≤ ℓ − n + 1 states. Moreover, finding a basis of H can be done in time at most O(v 2 ) (O(v log * v) according to Touikan's announcement [25]), and the rank of H is equal to e − v + 1, where e is the number of edges in Γ A (H).

On the complexity of Whitehead and other algorithms
It is well known that one can decide, given a subgroup H of a finite rank free group F , whether H is a free factor of F . We briefly describe here the main known algorithms and discuss their complexity.
Let H be a finitely generated subgroup of a free group F of rank r, with basis A. Let h 1 , . . . , h n be a generating set of H. By the results summarized in Fact 1.8, up to a quadratic time computation, we may assume that h 1 , . . . , h n is a basis of H. Let ℓ = |h 1 | + · · · + |h n | be the total length of the tuple (h i ) i , and let d = r − n be the rank difference between F and H -which we assume to be positive, since H can be a proper free factor of F only if n < r.
Federer and Jónsson (see [12, Prop. I.2.26]) gave the following observation and decision procedure: H is a free factor of F if and only if there exist d words h n+1 , . . . , h r , each of length at most max{|h i | | 1 ≤ i ≤ n}, such that h 1 , . . . , h r generate the whole of F . The resulting algorithm requires testing every suitable d-tuple of reduced words on alphabet A. Each of these tests (does a certain r-tuple of words generate F ?) takes time polynomial in the total length of the r-tuple, and hence in dℓ. However, the number of tests is O(r dℓ ), which is exponential in ℓ and d.
This approach leads to the following.
Proof. To verify that H ≤ ff K, we need to guess d words of length at most ℓ, and verify that together with H, they generate F , which can be done in O((dℓ) 2 ).
Another approach is based on the use of Whitehead automorphisms. We refer the readers to [12,Sec. I.4] for the definition of these automorphisms, it suffices to note here that the set W of Whitehead automorphisms of F which do not preserve length, has exponential cardinality (in terms of r). A result of Whitehead [12,Prop. I.4.24] shows the following: if there exists an automorphism ϕ of F such that the total length of (ϕ(h i )) i is strictly less than ℓ, then there exists such an automorphism in W . In particular, an algorithm to compute the minimum total length of an automorphic image of the tuple (h i ) i consists in repeatedly applying the following step: try every automorphism ψ ∈ W until the total length of (ψ(h i )) i is strictly less than the total length of (h i ) i ; if such a ψ exists, replace (h i ) i by (ψ(h i )) i ; otherwise, stop and output the total length of (h i ) i . This applies to the decision of the free factor relation since H ≤ ff F if and only if there exists an automorphism ϕ mapping a basis of H to a subset of A. Thus an algorithm consists in first computing a basis of H, and assuming that h 1 , . . . , h n is a basis, verifying whether the minimum total length of (ϕ(h i )) i when ϕ runs over the automorphisms of F , is exactly n. This algorithm may require O((ℓ − n)card(W )) steps, each of which consists in computing the image of a tuple of length at most ℓ under an automorphism, and hence has complexity O(ℓ). Thus the time complexity of this algorithm is O(ℓ 2 card(W )), which is quadratic in ℓ and exponential in r.
A variant of this algorithm was established by Gersten [5], who showed that a similar method applies to find the minimum size (number of vertices) of Γ A (ϕ(H)), when ϕ runs over the automorphisms of F (A). It is clear that H is a free factor of F (A) if and only if there exists an automorphism ϕ such that Γ A (ϕ(H)) has a single vertex. The time complexity is computed as above, where the number of vertices of Γ A (H) is substituted for the total length of a basis for H. As noted earlier, this number of vertices is usually substantially smaller than the total length of a basis, but the two values are linearly dependent, so the order of magnitude of the time complexity is not modified, notably the exponential dependence in r.
Remark 1.10. The discussion of Whitehead's algorithm above concerns only the so-called easy part of the algorithm (see for instance Kapovich, Miasnikov and Shpilrain [9]). Results by Miasnikov and Shpilrain [15], Khan [10], and most recently by Donghi Lee [11] on the possible polynomial complexity of the hard part of the algorithm also consider the rank of the ambient free group as a constant, and do not question the actual exponential dependence in that parameter.

A careful look at the expansions and reductions of inverse automata
Let A be a reduced inverse automaton. Let B be obtained from A by performing an expansion, say by (p, w, q), and then reducing the resulting automaton. In this situation, we write A −→ (p,w,q) exp B, or simply A −→ exp B. We distinguish two special cases.
• If the reduction following the expansion does not involve identifying or omitting states of A, or equivalently if A embeds in B, we say that B is obtained from A by a reduced expansion and we write A −→ (p,w,q) re B or A −→ re B.
• If the states p and q are equal to the distinguished state q 0 of A, we say that B is obtained from A by an e-step and we write A −→ w e B, or simply A −→ e B. Finally, let B be obtained from A by identifying two distinct vertices p and q, and then reducing the resulting automaton. Then we say that B is obtained from A by an i-step and we write A −→ p=q We first record a few facts.
Fact 2.1. Let u be a reduced word labeling a path in A from a state p to a state p ′ , and from a state q to a state q ′ , By definition of the reduction of dual automata, the identification of p and q implies that of p ′ and q ′ , and the converse holds as well.
Let us now examine in detail the effect of an operation of the form −→ exp . Fact 2.2. Let p, q be states of A and let w be a non-empty reduced word. Let u be the longest prefix of w that can be read in A from state p, and let v be the longest suffix of w that can be read in A to state q (that is, v −1 is the longest prefix of w −1 that can be read in A from state q). We distinguish two cases: (1) If |u| + |v| < |w|, then w = uw ′ v for some non-empty reduced word w ′ . If we let p ′ (resp. q ′ ) be the end (resp. start) state of the path labeled u (resp. v) and starting in p (resp. ending in q), (2) If |u| + |v| ≥ |w|, then there exist words x, y, z, possibly empty, such that u = xy, v = yz and w = xyz. Let p ′ , p ′′ , q ′ , q ′′ be the states of A defined by the following paths We derive from Fact 2.2 the following statement.

Proposition 2.3. Let A and B be inverse automata. If
B for some states p and q and a reduced word u such that |u| ≤ |w|.
The following converse statements are derived from Facts 2.1 and 2.2. Proof. Let A ′ be the expansion of A by (q 0 , uv, q 0 ). The analysis in Fact 2.2 (2) shows that a step in the reduction of A ′ is provided by the automaton obtained in identifying p and q. By Proposition 1. Proof. Since the expansion of A by (p, w, q) is a reduced expansion, the word uwv is reduced and the expansion by (q 0 , uwv, q 0 ) falls in the situation described in Fact 2.2 (1). Together with Proposition 1.2, it follows that A −→ uwv e B, which concludes the verification that of the first part of the proposition.
The free factor and the rank statements follow from the statement on a basis for L(B)ρ, which is a direct consequence of the definition of a reduced expansion and of the discussion on bases and spanning trees in Fact 1.8.
Finally, we introduce an order relation on the set of finite sequences of non-negative integers. Letk = (k 1 , . . . , k n ) andl = (ℓ 1 , . . . , ℓ m ) be such sequences. We say that k l if either n < m, or n = m and ℓ i andk precedesl in the lexicographic order. It is routine to check that is a well-order on the set of finite sequences of non-negative integers, which is stable under the concatenation of sequences. We writek ≺l ifk l andk =l. Proposition 2.6. Let A, A ′ and B be inverse automata such that A ′ is obtained from A by a reduced expansion σ 1 and B is obtained from A ′ by an i-step σ 2 , Then there exist a sequence of reduced expansions or i-stepsσ ′ of length 1 or 2 such that B is obtained from A by applying the steps inσ ′ and λ(σ ′ ) ≺ λ(σ 1 , σ 2 ). Let Q be the state set of A and let u and v be reduced paths,

Proof. Suppose that A −→
Then uwv is a reduced word and L(A ′ )ρ = L(A)ρ, uwv by Proposition 2.5. We distinguish three cases, depending whether or not r and s lie in Q. Note that the words u and v label paths from and into state q 0 in A ′′ as well. It follows from Proposition 2.3 that, if uwv ∈ L(A ′′ ), then B can be obtained from A ′′ by an i-step or by a reduced expansion of the form −→ (t,z,t ′ ) re with |z| ≤ |w|. Thus B is obtained from A either by a sequence of 1 or 2 transformations, of cost 0 or (0, k) with 0 ≤ k ≤ |w|. This is ≺-less than (|w|, 0), as expected.
Case 2: Exactly one of r and s is in Q. Without loss of generality, we may assume that r ∈ Q and s ∈ Q. Let z be a reduced word labeling a path from q 0 to r in A, and hence also in A ′ . Let g be the unique reduced word labeling a path from p to s in A ′ , using only edges that were not in A. By assumption, g is a proper, non-empty prefix of w. Moreover, by Propositions 1.2 and 2.4, Let h be the longest common suffix of g and z, so that g = g ′ h, z = z ′ h, g ′ z ′ −1 is reduced and we have the following paths in A ′ , , so we may assume that h = 1, g = g ′ and z = z ′ . There is a possibility that the word g is now empty (if h was in fact equal to g), but in that case, we are returned to the situation of Case 1, with s ′ = p. Thus we may still assume that g = 1. In particular, the word ugz −1 is reduced.
Then let A ′′ and B ′ be defined by Proposition 2.3 states that each e-step can be replaced by an i-step or by a reduced expansion of cost bounded above by the cost of the e-step. Going back to Fact 2.2, we see that the e-step A −→ ugz −1 e A ′′ can be replaced by a transformation of cost k ≤ |g| since both u and z can be read from state q 0 in A (in fact, of cost exactly |g| by definition of g). As for the e-step A ′′ −→ uwv e B, it can be replaced by a transformation of cost ℓ ≤ |w| − |g| since ug (a prefix of uw) and v can be read to state q 0 in A ′′ . Now, it suffices to verify that (k, ℓ) ≺ (|w|, 0), which is easily done if we observe that k + ℓ ≤ |w| and k < |w|. Case 3: Neither r nor s is in Q. Without loss of generality, we may assume that r occurs before s along the w-labeled path from p to q. Thus, the word w factors as w = w 1 w 2 w 3 and the path in A ′ made of edges added to A factors as Since r = s and these vertices are not in Q, each of the three factors w 1 , w 2 , w 3 is non-empty. Moreover, Let h be the longest common suffix of w 1 and w −1 is reduced and we have the following paths in A ′ , There is a possibility that the words w 1 or w 3 be now empty (if h was in fact equal to w 1 or w 3 ), but in that case, we are returned to the situation of Cases 1 or 2, with r ′ = p or s ′ = q. Thus we may still assume that w 1 = 1 and w 3 = 1. In particular, the word uw 1 w 3 v is reduced.
As in Case 2, we use Fact 2.2 to verify that the e-step A −→ uw1w3v e A ′′ can be replaced by a reduced expansion of cost k = |w 1 w 3 | since u and v are the maximal prefix and suffix of uw 1 w 3 v that can be read from and to state q 0 in A. As for the e-step A ′′ −→ uwv e B, it can be replaced by a reduced expansion of cost ℓ = |w 2 | since uw 1 and w 3 v are the maximal prefix and suffix of uwv that can be read from and to state q 0 in A ′′ . Now, it suffices to verify that (k, ℓ) ≺ (|w|, 0), which is easily done if we observe that k + ℓ = |w| and k < |w|.

A geometric characterization of free factors
We put together the technical results from Section 2 to prove the following characterization of free factors. Since is a well-order on the set of finite sequences of non-negative integers, we may consider a sequenceσ of d i-steps and reduced expansions leading from Γ A (H) to Γ A (K), which is -minimal. Proposition 2.6, together with the stability of under concatenation, then shows that the i-steps inσ come before the reduced expansions. Thus, H ≤ ff K if and only if Γ A (H) yields Γ A (K) by a sequence of d ′ i-steps followed by d − d ′ reduced expansions.
It follows from the discussion on bases and spanning trees in Fact 1.8 that if Γ A (H) embeds in Γ A (K), then H is a free factor of K. Not every free factor of K occurs that way, and those that do are called the graphical free factors of K (with respect to A). It is easily verified that H is a graphical free factor of K if and only if Γ A (H) yields Γ A (K) by a sequence of reduced expansions.
Corollary 3.2. Let H, K be finitely generated subgroups of F = F (A) and assume that d = rank(K) − rank(H) > 0. Then H is a free factor of K if and only if the inverse automaton Γ A (H) can be transformed by a sequence of d ′ ≤ d i-steps into some Γ A (L) such that rank(L) = rank(H) + d ′ and L is a graphical free factor of K with respect to A.
Proof. Let us first assume that H ≤ ff K. By Theorem 3.1, for some d ′ ≤ d, Γ A (H) can be taken to some Γ A (L) by a sequence of d ′ i-steps, and Γ A (L) can be taken to Γ A (K) by a sequence of d − d ′ re-steps. Since rank(K) = rank(H) + d and an i-step or an re-step can increment the rank by at most one (Propositions 2.4 and 2.5), L must have rank exactly rank(H) + d ′ .
Conversely, suppose that a sequence of d ′ ≤ d i-steps takes Γ A (H) to Γ A (L) in such a way that rank(L) = rank(H) + d ′ and Γ A (L) embeds in Γ A (K). By Propositions 2.4 and 2.5 again, we have H ≤ ff L ≤ ff K, and hence H ≤ ff K. Remark 3.3. We observe the following by-product of the proof of Corollary 3.2: if Γ A (H) can be transformed into Γ A (L) by a sequence of d ′ i-steps such that rank(L) = d ′ + rank(H), then for every i-step A −→ i B occurring in that sequence, we have rank(L(B)ρ) = 1 + rank(L(A)ρ). We say that such an i-step is rankincrementing.
In the special case where K = F , we have the following statement.

Deciding whether H ≤ ff F
We first consider the problem of deciding whether a given finitely generated subgroup H of F = F (A) is a free factor of F . With the notation of Corollary 3.4 and Remark 3.3, the algorithm to decide whether H ≤ ff F consists of the following. We need to explore the sequences of rank-incrementing i-steps, starting from Γ A (H) and of length d = |A 0 | − rank(H). Then H ≤ ff F if and only if one of the automata occurring at the end of one of these sequences has a single vertex. Note that no automaton obtained after less than d i-steps could be a single-vertex automaton.
These automata can be viewed as nodes of a tree, rooted at Γ A (H), in which the children of a node are the automata produced by a rank-incrementing i-step. Let n be the number of states of Γ A (H). Then every automaton occurring along this tree has at most n states.
If A is such an automaton, then A has at most 1 2 (n 2 − n) pairs of distinct vertices, and hence at most 1 2 (n 2 − n) children, each of which has at most n − 1 states. The computation of the children of A is done by computing all the (at most Finally, if H is given by a finite set of generators, of total length ℓ, we recall that computing Γ A (H) takes time O(ℓ 2 ) and that Γ A (H) has at most ℓ states and ℓ edges. This discussion justifies the following statement. Remark 3.6. The tree exploration described above can be speeded up by the following observation. If the automaton A occurs in a sequence of rank-incrementing i-steps from Γ A (H) to the one-vertex automaton Γ A (F (A 0 )) (a winning sequence), then L(A)ρ ≤ ff F (A 0 ), which implies that L(A)ρ is a free factor of every subgroup of F (A 0 ) containing it. It follows that, if some i-step A −→ i B does not increment the rank, then A does not occur in a winning sequence, that is, we may ignore the subtree below A.
There are undoubtedly other implementation tricks and ideas that can reduce the decision process, however without changing the worst-case complexity.
Remark 3.7. In view of Touikan's announcement (see Fact 1.8), the time complexity in the above theorem can be lowered to O(ℓ 2d+1 log * ℓ).
The above discussion of complexity depends on a uniform cost assumption, by which we assume that the elementary operations on A (reading or writing a letter, comparing two letters) require unit time. In other words, we have been assuming that A is fixed, and not part of the input. We will shortly consider the problem of deciding whether H ≤ ff K where both H and K are part of the input, and for the purpose of that discussion, we reconsider the algorithm and the complexity established above under the bit cost assumption: we let r be the cardinality of A, and we consider that each letter is identified by a bit string of length at most log r, so that the elementary operations on A require O(log r) units of time.
Let f (ℓ, r) be the complexity of reducing a dual automaton onÃ with at most ℓ vertices and ℓ edges. The computation of the automaton obtained by an i-step from an ℓ-vertex automaton takes time at most f (ℓ, r). To compute the tree of rank-incrementing i-steps rooted at Γ A (H), we need to compute the at most O(ℓ 2 ) children of at most ℓ 2d−2 nodes, which requires time O(ℓ 2d f (ℓ, r)). Finally, deciding whether an automaton has a single vertex takes constant time, so the total complexity of the algorithm is O (ℓ 2d f (ℓ, r)).
We now give an upper bound of f (ℓ, r). Let A be an A-automaton with at most ℓ states and ℓ edges. The identifiers of states require space O(log ℓ) and the identifiers of letters require space O(log r). Moreover, we assume that the set of states and the setÃ are linearly ordered, and equipped with a constant time next function.
The automaton can be viewed as the lexicographically ordered list of all triples (u, a, v) such that either a ∈ A and there is an a-labeled edge from state u to state v, orā ∈ A and there is aā-labeled edge from state v to state u. Each entry of this list requires space O(log ℓ + log r) = O(log(ℓr)), and the list contains at most ℓ entries. In particular, a complete scan of the list takes time O(ℓ log(ℓr)).
The reduction of A consists in performing elementary reductions of type 1 as long as it is possible, and then elementary reductions of type 2. To find out whether a type 1 reduction is possible, one needs to scan the list to find two (consecutive) cells of the form (u, a, v) and (u, a, v ′ ), requiring O(ℓ log(ℓr)). Performing the identification consists in reading through the list, replacing every occurrence of v ′ by v, and reordering the list: this takes time O(ℓ log(ℓr)). To find out whether an elementary reduction of type 2 is possible, one scans the list to find a vertex u such that there is a unique triple of the form (u, a, v) in the list: again, this takes time O(ℓ log(ℓr)). Finally, performing the reduction consists simply in deleting the entries (u, a, v) and (v,ā, u) in the list.
Summarizing, since we will perform at most ℓ reductions, we can take the function f (ℓ, r) to be equal to ℓ 2 log(ℓr). This yields the following statement.
Theorem 3.8. There is an algorithm which, given an alphabet A of size r and reduced words h 1 , . . . , h n ∈ F (A) with total length ℓ, decides whether the subgroup H generated by the h i is a free factor of F (A) in time O(ℓ 2d+2 log(ℓr)), where d = |A 0 | − rank(H) and A 0 is the set of letters in A that occur in the h i .

Deciding whether H ≤ ff K
We now suppose that H and K are subgroups of F (A), given by sets of generators with total length ℓ, and we consider the problem of deciding whether H ≤ ff K. The algorithm is the following: we first compute Γ A (K) and we verify whether each generator of H can be read as a loop at q 0 , the designated vertex of Γ A (K). If not, then H is not contained in K, and cannot be a free factor.
We now assume that H ≤ K and we compute a spanning tree T of the graph Γ A (K). This spanning tree determines a basis B of K, indexed by the edges of Γ A (K) that are not in T (see Fact 1.8), and we express the given generators of H in terms of this basis: it suffices to read the generators of H as loops at the designated vertex in Γ A (K), and to record the sequence of edges traversed and not in T . In particular, each generator of H is expressed as a reduced word iñ B * , that is no longer than its expression as a reduced word inÃ * . We then use this expression of the generators of H to construct Γ B (H), and the algorithm in Section 3.2 to decide whether H is a free factor of the ambient free group, namely K.
Let us now discuss the complexity of this algorithm, assuming that H and K are given by tuples of generators of total length ℓ and that F has rank r. As discussed in the previous section, computing Γ A (K) takes time O(ℓ 2 log(ℓr)). Running a word w ∈ F (A) in the automaton Γ A (K) requires reading sequentially each letter of w (time O(log r)) and looking for the corresponding transition in the table representing the automaton (time O(ℓ log(ℓr))). If w has length ℓ ′ , this takes time O(ℓ ′ ℓ log(ℓr)). In order to decide whether H is contained in K, this must be done for every generator of H, and since the total length of these generators is at most ℓ, this requires time O(ℓ 2 log(ℓr)).
Assuming that H is indeed contained in K, the next step is to construct a spanning tree T of Γ A (H), for instance by marking certain edges in the list representing Γ A (K). Again, this can be done in time O(ℓ 2 log(ℓr)). The positively labeled edges of Γ A (K) not in T are in bijection with a basis B of K. In particular, the rank of K is at most ℓ, an upper bound of the number of edges in Γ A (K). The elements of B, seen as words in F (A), consist of the label of a path in T , followed by the label of an edge not in T , followed by the label of a path in T . In particular, their length is at most twice the number of vertices of Γ A (K) plus one, that is O(ℓ). But we do not need to compute these words: it suffices to number (from 1 to rank(K) ≤ ℓ) the positively labeled edges not in T . Then, for each generator h of H, reading h in Γ A (K) from state q 0 and keeping track of the (identifier of the) edges traversed that are not in T , provides an expression of h in B. Moreover, the total length of the expression of the generators of H in this basis of K is at most ℓ.
We now simply apply Theorem 3.8 to a length ℓ set of generators of a subgroup of a free group of rank at most ℓ, to justify the following corollary. Corollary 3.9. Given tuples of generators for subgroups H and K of F (A), with total length ℓ, one can decide whether the subgroup H is a free factor of K in time O(ℓ 2d+2 log(ℓr)), where d = rank(K) − rank(H).
Remark 3.10. Corollary 3.2 suggests an alternative algorithm to decide whether H ≤ ff K: one may explore the sequences of rank-incrementing i-steps of length at most d = rank(K) − rank(H), starting from Γ A (H) and producing only representations of subgroups contained in K. Each Γ A (L) occurring in such a sequence must be checked to verify whether it can be embedded in Γ A (K): if it can, then H ≤ ff K, and if it cannot, then the automata produced by a rank-incrementing i-step from it must be computed and checked in their turn.

Complement of a free factor
By definition of a free factor (see the introduction), H ≤ ff K if there exists a basis C of H and a disjoint set D ⊆ K such that C ∪ D is a basis of K. In that case, the subgroup generated by D is called a complement of H in K. It is easy to see that this complement is not uniquely defined.
If H is indeed a free factor of the free group F , the algorithm described in Section 3.2 also provides a sequence of rank-incrementing i-steps taking Γ A (H) to Γ A (F (A 0 )), where A 0 is the set of letters of A that occur in the generators of H. Repeated applications of Proposition 2.4 then yield a basis of F (A 0 ) containing a basis of H, and hence a complement of H in F (A 0 ).
We can be a little more precise. If A is a reduced inverse automaton, let diam q0 (A), the q 0 -diameter of A, be the longest shortest path in A from q 0 to a state, that is diam q0 (A) = max q min{|u| | u is a reduced word and q 0 u −→ q in A} .
Then Proposition 2.4 shows that if A −→ i B and L(A)ρ ≤ ff L(B)ρ, then a complement of L(A)ρ is generated by a word of length at most 2 diam q0 (A).
This justifies the following statement. It is interesting to observe that this is a graphical analogue -and a minor improvement -of Federer and Jónsson's result (see [12, Prop. I.2.26]) mentioned in Section 1.3. Indeed, if h 1 , . . . , h n are a set of generators of H, then every edge of Γ A (H) is on a loop at q 0 labeled by some h i , and hence max i |h i | ≥ 2 diam q0 (Γ A (H)).
Let us now consider the problem of constructing a basis of a complement of H in K, where H and K are given finitely generated subgroups of F (A) and H ≤ ff K. The algorithm described in Remark 3.10 (based on Corollary 3.2) shows that one can construct effectively a graphical free factor L of K such that H ≤ ff L. As above, in view of Proposition 2.4, the same algorithm can produce a basis of a complement of H in L consisting of words of length at most 2 diam q0 (Γ A (H)). There remains to construct a basis for a complement of L in K.
In view of Fact 1.8 (and using the notation therein), one can find a (basis of a) complement of L in K by considering a spanning tree of Γ A (L), extending it to a spanning tree T of Γ A (K), and considering the elements b e associated with edges of Γ A (K) that are neither in Γ A (L) nor in T . In particular, the words b e have length at most 1 + 2 diam q0 (Γ(K)). Thus we have the following statement. Proposition 3.12. Let H, K be finitely generated subgroups of F (A). If H ≤ ff K, then one can construct effectively a basis for a complement of H in K, consisting of words of length at most max(2 diam q0 (Γ A (H)), 1 + 2 diam q0 (Γ A (K))).
The authors wish to thank both anonymous referees for their many helpful comments, which have substantially contributed to the improvement of the paper. All remaining shortcomings are naturally ours.