{'fraction_non_alphanumeric': 0.030822531509467774, 'fraction_numerical': 0.008541903112119945, 'mean_word_length': 4.232536333802156, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Conjugacy and Dynamics in Thompson's Groups

We give a unified solution to the conjugacy problem for Thompson's groups F, T, and V. The solution uses strand diagrams, which are similar in spirit to braids and generalize tree-pair diagrams for elements of Thompson's groups. Strand diagrams are closely related to piecewise-linear functions for elements of Thompson's groups, and we use this correspondence to investigate the dynamics of elements of F. Though many of the results in this paper are known, our approach is new, and it yields elegant proofs of several old results.

1. Every slope is a power of two, and 2. Every breakpoint has dyadic rational coordinates.
The group F is finitely presented (with two generators and two relations) and torsion-free. In addition to F , Thompson introduced two other finitely-generated groups known as T and V . Briefly, T is the set of piecewise-linear self-homeomorphisms of the circle [0, 1] / {0, 1} satsifying the two conditions above, while V is the set of piecewise-linear bijections of the interval (or self-homeomorphisms of the Cantor set) satisfying the above conditions. The standard introduction to F , T , and V is [8]. We will assume some familiarity with Thompson's groups and, in particular, with tree diagrams.
In this paper we give a unified solution for the conjugacy problem in Thompson's groups F, T and V . We introduce strand diagrams, a modification of tree diagrams for these groups, and show how identifying the roots of the two trees defines a conjugacy invariant in all cases. This reduces the conjugacy problem to the study of the isomorphism problem for certain classes of graphs and gives us elementary proofs of some known results. Strand diagrams were first introduced by Pride in his study of the homotopy of relations using the term pictures in [19], [20] and [3] and are dual to the diagrams introduced by Guba and Sapir in [11].
In 1997 Guba and Sapir showed that F can be viewed as a diagram group for the monoid presentation x | x 2 = x [11]. They give a solution for each diagram group, and in particular for F . Their solution amounted to an algorithm which had the same complexity as the isomorphism problem for planar graphs. This last problem has been solved in linear time in 1974 by Hopcroft and Wong [14], thus proving the Guba and Sapir solution of the conjugacy problem for diagram groups optimal. We mention here relevant related work: in 2001 Brin and Squier in [5] produced a criterion for describing conjugacy classes in PL + (I). In 2006 Kassabov and Matucci in [15] give a solution to the simultaneous conjugacy problem using the piecewise-linear point of view. In 2007 Gill and Short [10] extended Brin and Squier's criterion to work in F , thus finding another way to characterize conjugacy classes from a piecewise linear point of view.
The conjugacy problem in V was previously solved by Higman [13] by combinatorial group theory methods and again by Salazar-Diaz [21] by using the techniques introduced by Brin in his paper [4]. On the other hand, to the best of our knowledge, the solution for T is entirely new. This is the first of two papers on conjugacy in Thompson's groups. In the sequel paper [2], we will show how to interpret strand diagrams for F directly as piecewise-linear homeomorphisms, and we will use this correspondence as well as the solution to the conjugacy problems to analyze the dynamics of elements of F . This paper is organized as follows. In section 1 we give a simplified solution to the conjugacy problem in F . We extend this solution to T in section 2, and to V in section 3, and in section 4 we analyze the running time of the algorithm.
1 Conjugacy in Thompson's group F

Strand Diagrams
In this section, we describe Thompson's group F as a group of strand diagrams. A strand diagram is similar to a braid, except instead of twists, there are splits and merges (see figure 1). To be precise, a strand diagram (or a (1, 1)-strand diagram) is any directed, acyclic graph in the unit square satisfying the following conditions: 1. There exists a unique univalent source along the top of the square, and a unique univalent sink along the bottom of the square.
2. Every other vertex lies in the interior of the square, and is either a split or a merge (see figure 2).
As with braids, isotopic strand diagram are considered equal. A reduction of a strand diagram is either of the moves shown in figure 3.
Two strand diagrams are equivalent if one can be obtained from the other via a sequence of reductions and inverse reductions. A strand diagram is reduced if it is not subject to any reductions. Proof: This result was first proved by Kilibarda [16], and appears as lemma 3.16 in [11]. We repeat the proof here, for we must prove several variations of this result later. Consider the directed graph G whose vertices are strand diagrams, and whose edges represent reductions. We shall use Newman's Diamond Lemma (see [18]) to show that each component of G contains a unique terminal vertex. Clearly G is terminating, since each reduction decreases the number of vertices in a strand diagram. To show that G is locally confluent, suppose that a strand diagram is subject to two different reductions, each of which affects a certain pair of vertices. If these two pairs are disjoint, then the two reductions simply commute. The only other possibility is that the two pairs have a vertex in common, in which case the two reductions have the same effect (figure 4).

Figure 4: Diamond Lemma
The advantage of strand diagrams over tree diagrams is that multiplication is the same as concatenation (see figure 2.4.1). This algorithm is considerably simpler than the standard multiplication algorithm for tree diagrams. The inverse of a strand diagram is obtained by reflection across a horizontal line and by inverting the direction of all the edges. Note that the product of a strand diagram with its inverse is always equivalent to the identity.

Theorem 1.2 Thompson's group F is isomorphic with the group of all equivalence classes of strand diagrams, with product induced by concatenation.
Proof. There is a close relationship between strand diagrams and the well-known tree pair diagrams for elements of F . In particular, a strand diagram for an element f ∈ F can be constructed by gluing the two trees of a tree pair diagram together along corresponding leaves, after turning one tree upside down (see  A more formal proof of the intuition given by the previous two figures can be found in [17]. Note 1. 3 We will sometimes need to consider more general strand diagrams, with more than one source and sink (see figure 5). We call an object like this an (m, n)-strand diagram, where m is the number of sources and n is the number of sinks. This graph is built with the same conditions as (1,1)-strand diagrams, except that it is allowed to have multiple sources and sinks. We observe that, for every positive integer k the equivalence classes of (k, k)-strand diagrams equipped with the product given by concatenation returns a group. It is possible to prove that the group of all (1, 1)-strand diagrams is isomorphic to the group of all (k, k)-strand diagrams, for every positive integer k. In fact, if we denote by v m the right vine with m leaves (figure 6). then any (k, k)-strand diagram can be identified with the corresponding (1, 1)strand diagram given by v −1 k f v k of Thompson's group F .In particular, we can compose two elements of F by concatenating any corresponding pair of strand diagrams. The previous description can be seen more formally from a categorical point of view. We consider a category C, where Obj(C) = N, M or(C) = {morphisms i → j are labeled binary forests with i trees and j total leaves} (notice that the labeling on the trees induces a labeling on the leaves). The composition of two morphisms f : i → j and g : j → k, is the morphism f g : i → k obtained by attaching the roots of the trees of g to the leaves of f by respecting the labeling on the roots of g and the leaves of f . With this definition, the equivalence classes of strand diagrams with any number of sources and sinks is the groupoid of fractions of the category C (more details on this construction can be found in [1]). We call this Thompson's groupoid F . From the categorical point of view, we see that the projection f → v −1 n f v m is an epimorphism from the groupoid F to the group F .

Annular Strand Diagrams
Definition 1.4 An annular strand diagram is a directed graph embedded in the annulus with the following properties: 2. Every directed cycle has positive winding number around the central hole.
Our definition of graph allows the existence of free loops, i.e. directed cycles with no vertices on them. Every element of F gives an annular strand diagram: given a strand diagram in the square, we can identify the top and bottom and delete the resulting vertex to get an annular strand diagram (figure 7). More generally, you can obtain an annular strand diagram from any (k, k)-strand diagram in the square, for any k ≥ 1. We observe that we may obtain free loops with no vertices (figure 8) Figure 8: An example of a free loop in an annular strand diagram Definition 1.5 A cutting path for an annular strand diagram is a continuous path in the annulus that satisfies the following conditions: 1. The path begins on the inner circle of the annulus, and ends on the outer circle.
2. The path does not pass through any vertices of the strand diagram.
3. The path intersects edges of the strand diagram transversely, with the orientation shown in figure 9.
Cutting an annular strand diagram along a cutting path yields a (k, k)-strand diagram embedded in the unit square (thus an element of Thompson's group F , by Note 1.3). Conversely, given an element of F as a (k, k)-strand diagram we can build an associated annular strand diagram by gluing the i-th source and the i-th sink, for i = 1, . . . , k. This gluing also defines a cutting path for the associated annular diagram. On the other hand, it can be shown that every annular strand diagram has at least one cutting path, hence any annular strand diagram is the associated annular strand diagram for some (k, k)-strand diagram (a proof of this fact can be found in [17]).  In the third move, two concentric free loops with nothing in between are combined into one. Note that a reduction of an annular strand diagram yields an annular strand diagram. Note also that any two annular strand diagrams for the same element of F are equivalent.

Proposition 1.7 Every annular strand diagram is equivalent to a unique reduced annular strand diagram.
Proof: We shall use Newman's Diamond Lemma (see [18]). Clearly the process of reduction terminates, since any reduction reduces the number of edges. We must show that reduction is locally confluent. Suppose that a single annular strand diagram is subject to two different reductions. If one of these reductions is of type III, then the two reductions commute: if the other one is of type I or II, then the reductions must act on disjoint connected components of the diagram, while if the other is of type III too, we can collapse all adjacent free loops in any given order. Otherwise, both of the reductions involve the removal of exactly two trivalent vertices. If the reductions remove disjoint sets of vertices, then they commute. If the reductions share a single vertex, then the results of the two reductions are the same (see figure 4). Finally, it is possible for the reductions to involve the same pair of vertices, in which case they can be resolved with a reduction of type III (see figure 11). It is not hard to see that conjugate elements of F yield the same reduced annular strand diagram. The task is to prove that two elements of F with the same reduced annular strand diagram are conjugate. We begin with the following proposition, whose proof closely follows the arguments of Guba and Sapir regarding conjugacy [11]. Proposition 1.9 Any two cutting paths for the same annular strand diagram yield conjugate elements of F .
Proof: Let σ 1 and σ 2 be cutting paths for the same annular strand diagram, and let g 1 , g 2 be the resulting strand diagrams. Consider the universal cover of the annulus, with the iterated preimage of the annular strand diagram drawn upon it. Any path σ in the annulus lifts to a collection σ (i) : i ∈ Z of disjoint paths in the universal cover: Figure 12: Creating a conjugator Then g 1 h = hg 2 , where h is the strand diagram bounded by σ (i) 1 and σ (j) 2 for some j ≫ i, that is we choose j big enough so that the two paths σ (see figure 12). Assume now that g 1 and g 2 are, respectively, (k, k)-strand diagram and an (m, m)-strand diagram. We have proved that they are conjugate in Thompson's groupoid F (see Note 1.3).
To conclude the proof we can rewrite g 1 , g 2 , h as (1, 1)-strand diagrams using the right vine, that is Therefore, any annular strand diagram determines a conjugacy class in F . Proposition 1.10 Equivalent strand diagrams determine the same conjugacy class.
Proof: Recall that a type III reduction is the composition of a type II reduction and an inverse reduction of type I. Therefore, it suffices to show that the conjugacy class is unaffected by reductions of types I and II. Given any reduction of type I or type II, it is possible to find a cutting path that does not pass through the affected area. In particular, any cutting path that passes through the area of reduction can be moved (figure 13). If we cut along this path, then we are performing a reduction of the resulting strand diagram, which does not change the corresponding element of F . This proves Theorem 1.8. The reduced annular strand diagram is a computable invariant, so this gives a solution to the conjugacy problem in F . We will discuss in Section 4 that the complexity of this algorithm can be implemented in linear time. Figure 14 shows an example of a reduced annular strand diagram.

Structure of Annular Strand Diagrams
The main feature of this diagram is the large directed cycles winding counterclockwise around the central hole. We begin by analyzing the structure of these cycles:  Proof: Suppose L has both splits and merges. Then if we trace around L, we must eventually find a merge followed by a split, implying that the annular strand diagram is not reduced.
We shall refer to L as a split loop if its vertices are all splits, and as a merge loop if its vertices are all merges.  (1), observe that intersecting directed cycles would have to merge together and then subsequently split apart, implying that the diagram is not reduced. For (2), recall that the directed cycles are required to wind around at least once, and, since the graph is embedded in the plane, any closed curve that wound around more than once would have a self-intersection.
For (3), observe that any vertex in an annular strand diagram has at least one outgoing edge, and therefore any directed path can be extended indefinitely. If we start a path at a vertex p, then the path must eventually intersect itself as there are only finitely many vertices in the component, which proves the existence of a directed loop in the component containing p.
For (4), suppose that a component of an annular strand diagram has a split loop. Any path that begins at a split can never again intersect the split loop, and must therefore eventually intersect a merge loop, proving that this component has at least two directed cycles. Similarly, any path followed backwards from a merge loop must eventually intersect a split loop.
For (5), observe that two adjacent concentric directed cycles in the same component cannot both be split loops: a path starting in the region between them must eventually cycle, for it cannot end on any of the two split loops. Similarly, it is not possible to have two concentric merge loops. To prove that the order does not depend on the cutting path we start by observing that, by the proof of Proposition 1.9, any two cutting paths bound a conjugator h in Thompson's groupoid. By Proposition 7.2.1 in [1], h must be a product of merges and splits, so to conclude we must observe that if one cutting path can be obtained from another by passing through a merge or a split, the order of directed cycles does not change. This is immediately clear by looking at the moves in figure 13.
In the next section we will define cylindrical strand diagrams for elements of Thompson's group T . With this definition and the previous proposition, we can construct a component of a reduced annular strand diagram by drawing alternating split and merge loops, and then filling the connections between them with unlabeled reduced cylindrical strand diagrams (see figure 15). 2 Conjugacy in Thompson's group T

Strand Diagrams for T
We are now going to generalize to Thompson's group T the diagrams and the characterization of conjugacy that we have found for F . As many parts of this section are similar to the previous one, we are going to omit some details to avoid repetition. A cylindrical strand diagram is a strand diagram drawn on the cylinder  As with strand diagrams on the square, isotopic cylindrical strand diagrams are considered equal. We remark that isotopies of the cylinder include Dehn twists. We recall that a Dehn twist of the cylinder is a homeomorphism obtained by holding the top circle rigid while rotating the bottom circle through an angle of 2π. Hence two diagrams are equal if we can get from one to the other through a Dehn twist on the bottom. A reduction of a cylindrical strand diagram is either of the moves shown in figure 17. For the second move, the two parallel edges are required to span a disc on the cylinder. In particular, the diagram shown in figure 18 cannot be reduced.  Conversely, we can cut any reduced cylindrical strand diagram along all the edges that go from a split to a merge. This cuts the diagram into two trees, each of which is contained in its own cylinder ( figure 20).
The leaves of each tree lie along a circle, and therefore the correspondence between the leaves must be a cyclic permutation.  If we want concatenation of cylindrical (m, n)-strand diagrams to be well-defined, we must insist on a labeling of the sources and sinks (as in the figure above). Assuming this requirement, the set of cylindrical (m, n)-strand diagrams forms a groupoid, with the group based at 1 being Thompson's group T . Using the canonical embedding of the right vine on a cylinder, we can then view any cylindrical (m, n)-strand diagram as representing an element of T .

Characterization of Conjugacy in T
If we glue together the top and bottom of a cylindrical strand diagram, we obtain a strand diagram on the torus. The common image of the top and bottom circles is called a cutting loop. Definition 2.2 A toral strand diagram is a directed graph embedded on the torus S 1 × S 1 with the following properties: 1. Every vertex is either a merge or a split.

Every directed cycle has positive index around the central hole.
To make the second requirement precise, let c be the cohomology class (1, 0) in H 1 (S 1 ×S 1 ) = Z×Z. Then a toral strand diagram is required to satisfy the condition c (ℓ) > 0 for every directed loop ℓ. For a toral strand diagram obtained from a cylinder, c is precisely the cohomology class determined by counting intersection number with the cutting loop. For this reason, we shall refer to c as the cutting class.
The cutting class is related to a slight difficulty in defining the notion of equality for toral strand diagrams. Because a Dehn twist of the cylinder is isotopic to the identity map, two cylindrical strand diagrams that differ by a Dehn twist are isotopic and hence considered equal. However, the resulting toral strand diagrams are not isotopic (for example, see figure 22).   In the second move, the two edges of the bigon are required to span a disc, and in the third move the two loops must be the boundary of an annular region. Two toral strand diagram are equivalent if one can obtained from the other via a sequence of reductions and inverse reductions.

Proposition 2.7 Every toral strand diagram is equivalent to a unique reduced toral strand diagram.
Proof: The argument on reductions used in the proof of Proposition 1.7 can be extended to this case without additional details and so we omit it.
Gluing the top and the bottom circles of a cylindrical strand diagram is not well defined in general. However by Convention 2.3, all resulting toral diagrams are equal.

Theorem 2.8 Two elements of T are conjugate if and only if they have the same reduced toral strand diagram.
Proof: Our convention for equality of strand diagrams guarantees that any two conjugate elements of T yield the same reduced toral strand diagram. We claim that any two cutting loops for the same toral strand diagram yield conjugate elements of T . Suppose we are given cutting loops ℓ 1 and ℓ 2 , and consider the cover of the torus corresponding to the subgroup ker(c) ≤ π 1 (T). This cover is an infinite cylinder, with the deck transformations π 1 (T) /ker(c) ∼ = Z acting as vertical translation. Each of the loops ℓ i lifts to an infinite sequence ℓ for some k ≫ j. Clearly reductions do not change the conjugacy class described by a toral strand diagram, and therefore any two elements of T with the same reduced toral strand diagram are conjugate.

Structure of Toral Strand Diagrams
The following section is an analogue for T of Section 1.4 for F . Given an element f ∈ T , the structure of the toral strand diagram for f is closely related to the dynamics of f as a self-homeomorphism of the circle. In this section we analyze the structure of toral strand diagrams, and in the next we show how this structure is related to the dynamics of an element. We begin by noting some features of annular strand diagrams that remain true in the toral case: Proposition 2.9 For any reduced toral strand diagram. Any directed cycle is either a free loop, a split loop, or a merge loop. 2. Any two directed cycles are disjoint, and no directed cycle can intersect itself.

Every component of the graph has at least one directed cycle, and any component with only one directed cycle is a free loop.
In an annular strand diagram, each directed cycle winds around the central hole exactly once, and the components of the diagram form concentric rings. The structure of a toral strand diagram is more complicated. Proof: By the definition of a toral strand diagram, n > 0 for any directed cycle. Any two disjoint nontrivial loops on a torus are homotopic, and therefore any two directed cycles must have the same (n, k). Furthermore, since a directed cycle cannot intersect itself, n and k must be relatively prime.
Note that the number k is not uniquely determined. Specifically, recall that two strand diagrams that differ by the Dehn twist 0 @ 1 0 1 1 1 A are equal. (This matrix is the transpose of the earlier matrix, since we are now considering the action on homology.) Applying this Dehn twist to a diagram whose directed cycles are (n, k) yields a diagram whose cycles are (n, k + n), so the number k is only well-defined modulo n. We will always assume that 0 ≤ k < n. The reduced fraction k/n ∈ [0, 1) is called the rotation number of a toral strand diagram. It is possible to show that this corresponds to the dynamical rotation number of a homeomorphism f ∈ T (see [12] for the definition). Toral strand diagrams can also be used to recover the following two known results about the dynamics of elements in T . We omit the details of the proofs (that can be found in [17]). Proposition 2.11 (Ghys-Sergiescu, [9]) Every element of T has a periodic point.
We remark that the previous result has been recently proved again by Calegari in [7]. Bleak and Farley (private communication) also have a proof of this result using "revealing tree-pair diagrams" as introduced by Brin [4]. It is not too hard to see that, for any 1 ≤ k < n, the element c k n has rotation number k/n. This proves that, for any rational number k/n (mod 1) there is an element of T with rotation number k/n (another result due to Ghys and Sergiescu in [9]).

Strand Diagrams for V
Definition 3.1 An abstract strand diagram is an acyclic directed graph, together with a cyclic ordering of the edges incident on each vertex, and subject to the following conditions: 1. There exists a unique univalent source and a unique univalent sink.

Every other vertex is either a split or a merge.
The cyclic orderings of the edges allow us to distinguish between the left and right outputs of a split, and between the left and right inputs of a merge. We can draw an abstract strand diagram as a directed graph in the plane with edge crossings (see figure 26).  The first two moves are the same kind of move, drawn differently depending on the embedding in the plane. The cyclic order of the vertices must be exactly as shown above. The move shown in figure 28 is not valid. Every abstract strand diagram is equivalent to a unique reduced abstract strand diagram. Abstract strand diagrams represent elements of Thompson's group V .
Given an element f ∈ V , we can construct an abstract strand diagram for V by attaching the two trees of a tree diagram for f along corresponding leaves (figure 29). Figure 29: From a tree diagram to an abstract strand diagram Conversely, any reduced abstract strand diagram can be cut along all the edges that go from splits to merges to yield a tree diagram. Assuming we label the sources and sinks, the set of abstract (m, n)-strand diagrams forms a groupoid, and elements of this groupoid can viewed as representing elements of Thompson's group V .

Characterization of Conjugacy in V
If we glue together the sources and sinks of an abstract strand diagram, we obtain a directed graph whose vertices are all merges and splits. The images of the original sources and sinks now fall in the interiors of certain edges, and are called the cut points. Note that a single edge may contain more than one cut point. The function that measures the number of cut points in each edge is a 1-cocycle, and therefore yields a cohomology class c, which we call the cutting class. The cohomology class c is called the cutting class. To make our arguments as accessible as possible, we will use a very geometric approach to cohomology. In particular, we will make heavy use of the following well known result: for any CW-complex X, there is a natural one-to-one correspondence between elements of H 1 (X) and homotopy classes of maps from X to the punctured plane. Using the above theorem, we can represent a closed strand diagram as a graph with crossings drawn on the punctured plane (figure 30). The cohomology class c is given by winding number around the puncture. By convention, we always draw closed strand diagrams so that the cyclic order of the edges around each vertex is counterclockwise. The sequence p 1 , . . . , p n of points on the graph cut by the line is called a cutting sequence. Note that we can "cut" along a cutting sequence to obtain an ordered abstract (k, k)-strand diagram. The above definition is very geometric. Here is a combinatorial description of cutting sequences:  In the second move, the loop spanned by the bigon must lie in the kernel of c, i.e. the parallel edges must be homotopic in the punctured plane. In the third move, we require that the difference of the two loops lie in the kernel of c, or equivalently that the two loops have the same winding number around the puncture. In each of the three cases, the reduced graph D ′ inherits a cutting class in the obvious way. For a type I reduction, the new cutting class is ϕ * (c), where ϕ is the obvious map D ′ → D (figure 33).
For a reduction of type II, there are two obvious maps D ′ → D → {punctured plane}: we send the reduced edge to any of the two sides of the bigon. These maps are homotopic, and therefore yield the same homomorphism H 1 (D) → H 1 (D ′ ). The same holds for reductions of type III. Proposition 3.6 Every closed strand diagram is equivalent to a unique reduced closed strand diagram.
Proof: We must show that reduction is locally confluent, keeping careful track of the fate of the cohomology class c. Suppose that a single closed strand diagram is Figure 33: Cutting classes and reductions subject to two different reductions. If one of these reductions is of type III or they remove disjoint sets of vertices, then they commute. If the reductions share a single vertex, then the results of the two reductions are the same, as seen in previous cases (see figure 11 in Proposition 1.7). Note in particular that the map D ′ → D obtained from the type I reduction is homotopic in the punctured plane to the pair of maps D ′ → D obtained from the type II reduction. Finally, it is possible for the reductions to involve the same pair of vertices, in which case they can be resolved with a reduction of type III (figure 34).  Proof. Let f, g ∈ V . Then figure 35 is a closed strand diagram for both f and g −1 f g. Since f and g −1 f g share a closed strand diagram, they must have the same reduced closed strand diagrams.
We remark that Guba and Sapir had already proven that their solution to the conjugacy problem for diagram groups had the same complexity of the isomorphism problem for planar graphs (private communication). Thus their solution along with Theorem 4.2 give again a linear time algorithm.

Proposition 4.3 There exists a linear-time algorithm to determine whether two (reduced) annular strand diagrams are isotopic.
Proof: We must show that isotopy of connected annular strand diagrams reduces to isomorphism of planar graphs in linear time. If the given strand diagrams are disconnected, then we may check isotopy of the components separately. It therefore suffices to prove the proposition in the connected case. Given a strand diagram, subdivide each edge into three parts, and attach new edges around each merge and split as drawn in figure 36. This new graph can be constructed in linear time, and its isomorphism type completely determines the isotopy class of the original reduced annular strand diagram. In particular, the decorations determine both the directions of the original edges and the cyclic order of the original edges around each merge or split.
All that remains is to show that the reduced annular strand diagram for an element of F can be constructed in linear time. This requires two steps: 1. Construct a strand diagram for the element.
2. Reduce the resulting annular strand diagram.
The first step is easy to carry out in linear time: given a word in {x 0 , x 1 }, simply concatenate the corresponding strand diagrams for the generators and their inverses. No reduction is necessary in this phase. For the second step, observe that any reduction of a strand diagram reduces the number of vertices, and therefore only linearly many reductions are required. However, it is not entirely obvious how to search for these reductions efficiently. Proof: We give a linear-time algorithm for performing all the necessary type I and type II reductions. Any required type III reductions can be performed afterwards. We can write G as a set of vertices V = {v 1 , . . . , v k } := V 1 . We build inductively new sets of vertices V i . To build the sequence V i+1 , we read and classify every vertex of V i . We let R i be the set of vertices of V i which are reducible. By definition R i will have an even number of vertices, since a vertex is reducible if there is an adjacent vertex which forms a reduction in the diagram. Then we define V i+1 to be all the vertices of V \ i j=1 R j which are adjacent to a vertex in R i . This algorithm goes to look for vertices which were not reducible at the i-th step, but might have become reducible at the i + 1-th step. We repeat this process until we find an m such that R m = ∅. By construction, |R i+1 | ≤ |V i+1 | ≤ 4|R i | since every point involved in a reduction is adjacent to at most 3 vertices, one of which will be reduced. In other words, for each pair of vertices that we reduce, we might have to reinsert up to 4 vertices which were previously not reducible. On the other hand, it is obvious that The final cost of the computation is thus given by Though it may seem that we are done, we have not yet specified the time needed to perform a reduction. To do this we must choose a specific data structure to represent an annular strand diagram, and this choice is fraught with difficulty. We have worked out the details, and it suffices to keep track of either the dual graph (i.e. the cell structure) or of the sequence of edges crossed by some cutting path. In neither case can reductions actually be performed in constant time, but one can show that the amount of time required for linearly many reductions is indeed linear.
Unfortunately, the algorithm may not be as fast for the groups T and V . Checking whether two closed strand diagrams are the same involves a comparison of the cutting cohomology classes. This requires a Gaussian elimination, for it must be determined whether the difference of the two classes lies in the subspace spanned by the coboundaries of the vertices. Gaussian elimination has cubic running time, thus: Theorem 4.5 Let X be Thompson's group T or V described through their standard generating sets. There exists a cubic time algorithm to determine whether two elements of X are conjugate.