{'fraction_non_alphanumeric': 0.05225118112699853, 'fraction_numerical': 0.010575388755045212, 'mean_word_length': 3.653079050807978, 'pattern_counts': {'":': 0, '<': 0, '<?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': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Balanced strong shift equivalence, balanced in-splits and eventual conjugacy

We introduce the notion of balanced strong shift equivalence between square nonnegative integer matrices, and show that two finite graphs with no sinks are one-sided eventually conjugate if and only if their adjacency matrices are conjugate to balanced strong shift equivalent matrices. Moreover, we show that such graphs are eventually conjugate if and only if one can be reached by the other via a sequence of out-splits and balanced in-splits; the latter move being a variation of the classical in-split move introduced by Williams in his study of shifts of finite type. We also relate one-sided eventual conjugacies to certain block maps on the finite paths of the graphs. These characterizations emphasize that eventual conjugacy is the one-sided analog of two-sided conjugacy.


Introduction
Shifts of finite type are accurately represented as finite essential directed graphs with associated adjacency matrices, and Williams' seminal paper [17] was a deep investigation into two-sided conjugacy of shifts of finite type. He successfully characterized conjugacy in terms of a matrix relation, strong shift equivalence, of the associated matrices and also in terms of certain state splittings of the symbolic dynamical systems. A pair of nonnegative integer matrices A and B are elementary equivalent if there is a pair of rectangular nonnegative matrices (R, S) satisfying A = RS, SR = B, and strong shift equivalence is the transitive closure of elementary equivalence. Two shifts of finite type are two-sided conjugate if and only if their corresponding matrices are strong shift equivalent. This algebraic point of view is intimately related to the notion of shift equivalence (though the two relations are distinct by work of Kim and Roush [9]). While shift equivalence is decidable [10], it is arguably the biggest open problem in symbolic dynamics to determine whether strong shift equivalence is a decidable relation. On the other hand, Williams showed that any conjugacy can be decomposed into a finite sequence of state splittings. At the level of graphs, this amounts to splitting vertices and appropriately distributing the out-going edges (out-splits) or the in-going edges (in-splits).
Motivated by equivalences of graph C * -algebras, Bates and Pask [1] generalized these graphical constructions -which we now call moves -to arbitrary directed graphs and showed that whereas out-splits (Move (O)) produce * -isomorphic graph C * -algebras, the in-split (Move (I)) only preserves the Morita equivalence class of the graph C * -algebras. The coarser relation of flow equivalence of the dynamical systems was shown by Parry and Sullivan [16] to be generated by conjugacies and symbol expansions. This expansion or stretching of time corresponds to a delay move on the graphs which again preserves the Morita equivalence class of the C * -algebra. In fact, it was known since the inception of the graph C * -algebras of finite essential graphs (irreducible and not just a cycle) -the Cuntz-Krieger algebras -that the stabilized graph C * -algebra together with its canonical diagonal subalgebra is invariant under flow equivalence of the underlying dynamical systems [7].
Only much later with a remarkable use of groupoid techniques did Matsumoto and Matui [15] finally prove the converse statement: The stable isomorphism class of simple Cuntz-Krieger algebras together with their diagonal subalgebra (suitably stabilized) completely remembers the flow class of the underlying shift of finite type. It follows that the stable Cuntz-Krieger algebras are diagonally * -isomorphic if and only if the underlying graphs can be connected by a finite sequence of splittings and stretchings. This was later generalized to all finite essential graphs [5].
Moreover, Carlsen and Rout [6] showed that two finite essential graphs E and F are two-sided conjugate if and only if there is a * -isomorphism Ψ : C * (E) ⊗ K −→ C * (F ) ⊗ K which respects the diagonal subalgebras Ψ(D(E) ⊗ c 0 ) = D(F ) ⊗ c 0 and intertwines the gauge actions Ψ • (γ E ⊗ id) = (γ F ⊗ id) • Ψ. Here, K is the C * -algebra of compact operators on separable Hilbert space and c 0 is the C * -subalgebra of diagonal operators. Hence this kind of equivalence of graph C * -algebras is implemented by out-splits and insplits of the underlying graphs by Williams' result. A general program for determining which moves on the graphs captures structure-preserving * -isomorphisms of the graph C * -algebras was recently initiated by Eilers and Ruiz [8].
The present paper addresses one-sided eventual conjugacy as studied by Matsumoto and its relation to two-sided conjugacy. The motivation is three-fold.
Firstly, work of Matsumoto [13] and Carlsen and Rout [6] showed that a pair of graphs E and F are one-sided eventually conjugate if and only if there is a * -isomorphism Ψ : C * (E) −→ C * (F ) which respects the diagonal Ψ(D(E)) = D(F ) and intertwines the gauge actions Ψ • γ E = γ F • Ψ. This leads us to the observation that one-sided eventual conjugacy is structurally related to two-sided conjugacy. We may also say that eventual conjugacy is the one-sided analog of two-sided conjugacy. A fortiori, one-sided conjugacy is not the one-sided analog of two-sided conjugacy in this sense, cf. work of the author and Carlsen [3].
From a dynamical perspective, two-sided conjugacies are sliding block codes with a finite "window" (with memory and anticipation) arising from block maps on finite paths of the graphs. Similarly, one-sided conjugacies are sliding block codes with anticipation but no memory. It is possible to make sense of one-sided sliding block codes with both anticipation and memory and, in fact, such sliding block codes induce all eventual conjugacies.
The connection between two-sided conjugacy and one-sided eventual conjugacy it seems is present before passing to infinite sequences.
The second motivation is connected to Eilers and Ruiz' recent program of understanding the relationship between moves on graphs and structure-preserving * -isomorphisms of graph C * -algebras [8]. We study their variation of Williams' classical in-split called the balanced in-split (Move (I+)) and show that it induces eventually conjugate graphs. This new move introduces sources in the graphs which is why we consider finite graphs with no sinks but potentially with sources. We arrive at the following result.
Theorem (Theorem 4.9). One-sided eventual conjugacy of finite graphs with no sinks is generated by out-splits and balanced in-splits.
The presence of sources is an essential part of the proof even if the graphs we start with do not have sources. It also follows from the proof that one-sided conjugacy is generated by out-splits alone, cf. [17,2,11]. Since work of Carlsen and Rout [6] shows that eventual conjugacy of the graphs is equivalent to diagonal-preserving * -isomorphism of the graph algebras which intertwines the gauge actions -this is a 111-isomorphism in the terminology of [8] -the result characterizes this particular structure-preserving * -isomorphism in terms of Move (O) and Move (I+).
Thirdly, we introduce balanced strong shift equivalence of nonnegative integer matrices which is akin to strong shift equivalence. A pair of matrices A and B are balanced elementary equivalent if there is a triple of rectangular nonnegative integer matrices and balanced strong shift equivalence is the transitive closure of balanced elementary equivalence. It is an interesting question whether balanced strong shift equivalence is a decidable relation. As an analog of Williams' algebraic description of conjugacy, we find the following result.
Theorem (Theorem 5.5). A pair of finite graphs E and F with no sinks are eventually conjugate if and only if they are conjugate to graphs E ′ and F ′ , respectively, whose adjacency matrices are balanced strong shift equivalent.
Even if the present work is in part motivated by operator algebraic questions, the approach is purely dynamical. Hopefully, a thorough investigation of one-sided eventual conjugacy can also shed light on questions concerning two-sided conjugacy as well.
Acknowledgements I would like to thank Søren Eilers and Efren Ruiz for valuable comments on an earlier draft of this paper, and Aidan Sims and the University of Wollongong for their hospitality during my visit.

Preliminaries
We recall the relevant concepts of finite graphs and the dynamics on their path spaces and fix notation. Let Z, N = {0, 1, 2, . . .} and N + = {1, 2, . . .} denote the integers, the nonnegative integers and the positive integers, respectively.
A directed graph (or just a graph) is a quadrupel E = (E 0 , E 1 , r E , s E ) where E 0 is the set of vertices, E 1 is the set of edges and s E , r E : E 1 −→ E 0 are the source and range maps, respectively. We shall omit the subscripts to simplify notation when the graph is Assumption. In this paper we consider only finite graphs with no sinks.
A finite path is a string µ = µ 1 · · · µ n of edges where n ∈ N + and r(µ i ) = s(µ i+1 ) for i = 1, . . . n − 1. The length of µ is |µ| = n. By convention, the length of a vertex is zero. Let E n be all finite paths of length n and let E * = n∈N E n be the collection of all finite paths. The source and range maps naturally extend to E * by s(µ) = s(µ 1 ) and r(µ) = r(µ |µ| ). The path space of E is the set of all infinite paths of edges on the graph. The path space E ∞ is compact and Hausdorff in the subspace topology of the product topology on The cylinder set of a finite path µ is the compact open set and the collection of cylinder sets constitutes a basis for the topology of E ∞ .
Define a shift operation σ E : This is a local homeomorphism, and it is surjective if and only if E contains no sources.
In this case we say the graphs E and F are conjugate and that h is a conjugacy. Edge shifts are examples of shifts of finite type and, in fact, every shift of finite type is (conjugate to) an edge shift of a finite graph [12,Section 2].
Let E be a graph. The N'th higher block graph of E is the graph E [N ] with edge set E N and vertex set E N −1 . The source and range of µ = µ 1 · · · µ N ∈ E N is s N (µ) = µ [1,N ) and r N (µ) = µ (1,N ] . Note that E [1] = E, and that for any N there is a canonical conjugacy ϕ :

Eventual conjugacy and block maps
Let us fix two finite graphs with no sinks E and F and let E ∞ and F ∞ be their infinite path spaces, respectively.
3.1. Eventual conjugacy. A sliding block code ϕ : E ∞ −→ F ∞ is a continuous map which intertwines the shift operations in the sense that ϕ • σ E = σ F • ϕ. A conjugacy is a bijective sliding block code. In order to describe eventual conjugacies on graphs we first modify the notion of sliding block codes slightly. Definition 3.1. Let ℓ ∈ N. An ℓ-sliding block code is a continuous map ϕ : E ∞ −→ F ∞ such that σ ℓ E • ϕ is a sliding block code, that is, σ ℓ+1 F (ϕ(x)) = σ ℓ F (ϕ(σ E (x))), for every x ∈ E ∞ . If ℓ = 0, then ϕ is a sliding block code in the usual sense. An ℓ-conjugacy is a bijective ℓ-sliding block code.
An ℓ-conjugacy is simply one half of an eventual conjugacy.

Definition 3.2 ([13]
). Two finite graphs with no sinks E and F are eventually conjugate if there exist a homeomorphism h : E ∞ −→ F ∞ and ℓ, ℓ ′ ∈ N such that h and h −1 are ℓand ℓ ′ -conjugacies, respectively. That is, , for x ∈ E ∞ and y ∈ F ∞ . We say that h is an eventual conjugacy is an eventual conjugacy, then there is an ℓ ∈ N such that h and h −1 are ℓ-conjugacies.
Let ℓ ∈ N and suppose h : for k ℓ and x ∈ E ∞ . We shall refer to c as a continuity constant for h (relative to ℓ). Note that if c is a continuity constant for h (relative to ℓ), then c + i is a continuity constant for h for any i ∈ N. Moreover, if h and h −1 are ℓ-and ℓ ′ -conjugacies, then we can choose a continuity constant relative to max{ℓ, ℓ ′ }.
The following lemma shows that we can always reduce the continuity complexity of an ℓ-conjugacy, at the expense of increasing the continuity complexity of the inverse.

Block maps.
Definition 3.5. Let E and F be finite graphs with no sinks and let ℓ, c ∈ N.
Let ψ : E 1+ℓ+c −→ F 1+ℓ be an (ℓ, c)-block map. The compatibility condition ensures that there is an extension ψ : E 1+ℓ+c+i −→ F 1+ℓ+i given by We shall use the same symbol ψ for the block map and its extension, this should cause no confusion. Iterating this process ad infinitum, ψ extends to a map on the infinite path spaces h = h ψ : In particular, c is a continuity constant for h relative to ℓ. We would now like to find conditions on the block maps which ensure that the induced map on the path spaces is bijective.
On the other hand, ψ satisfies the injectivity condition if for every k ℓ there is K ∈ N such that for every x, x ′ ∈ E ∞ . We say that ψ satisfies the bijectivity condition if it satisfies both the injectivity and the surjectivity conditions. Remark 3.7. Note that for the case c = 0, the surjectivity condition reduces to surjectivity of the block map while the injectivity condition is, in general, weaker than injectivity of the block map. The term bijectivity condition is only meant to reflect the fact that the induced map on the infinite path spaces is bijective (see the proof below). If ψ : E 1+ℓ −→ F 1+ℓ is in fact a bijective block map, then the inverse homeomorphism h ψ −1 : E ∞ −→ F ∞ is induced by ψ −1 and has vanishing continuity constant.
We now arrive at the main result of this section.
Theorem 3.8. Let E and F be finite graphs with no sinks and let ℓ, c ∈ N. There is a one-to-one correspondence between the collection of (ℓ, c)-block maps ψ : E 1+ℓ+c −→ F 1+ℓ and the collection of (ℓ, c)-sliding block codes h : E ∞ −→ F ∞ . In addition, ψ satisfies the injectivitiy condition or the surjectivity condition if and only if h is injective or surjective, respectively.
the continuous extension to the infinite path spaces given by for x ∈ E ∞ and k ℓ. Note that c is a continuity constant for h relative to ℓ. If ax ∈ E ∞ , then Suppose ψ satisfies the surjectivity condition and let y ∈ F ∞ . For each k ℓ choose . Since E ∞ is compact the sequence (x (k) ) k has a convergent subsequence; let x ∈ E ∞ be its limit. Then h(x) = y and h is surjective.
Next, assume ψ satisfies the injectivity condition and suppose h( As this is the case for every k ℓ, we see that For the other direction, let h : This is well-defined by the choice of c and ψ is compatible with E and F . Hence ψ is an (ℓ, c)-block map. Furthermore, the (ℓ, c)-sliding block code h ψ induced by ψ coincides with h.
Fix β ∈ F 1+k for some k ℓ and let βy ∈ Z F (β). If h is surjective, we may choose Hence ψ satisfies the surjectivity condition.
If h is injective, then it is a homeomorphism onto its image; by the choice of c and by the choice of c φ . Hence ψ satisfies the injectivity condition. Finally, it is straightforward to verify that if ψ : E 1+ℓ+c −→ F 1+ℓ is an (ℓ, c)-block map and h is the (ℓ, c)-sliding block code induced from ψ, then the (ℓ, c)-block map ψ h induced from h coincides with ψ.
Remark 3.10. At the level of block maps, the index (ℓ, c) can be interpreted as memory and anticipation, respectively. For one-sided conjugacies, memory is not allowed (cf. [12,Section 13.8]), however, we have seen that memory of the block map exactly corresponds to eventual conjugacies. At the level of path spaces, the ℓ indicates the lag of the eventual conjugacy while c indicates the continuity complexity of the associated homeomorphism.

Moves on graphs
In this section, we relate eventual conjugacies with moves on the graph. We first recall the definition of the out-split and in-split of [17] modified for graphs (cf. [12,1]). For simplicity, we only define these moves for finite graphs with no sinks. Let v ∈ G 0 be a vertex, let n ∈ N + and partition s −1 G (v) into finitely many nonempty sets The out-split graph E of G at v with respect to the partition (4.1) is given by with source and range maps r E , s E : E 1 −→ E 0 given by A directed graph is conjugate to its out-split graph, see [4, Corollary 6.2]. Next, we introduce a slight modification of the classical in-split graph, cf. [8].  I-)). Let G = (G 0 , G 1 , r G , s G ) be a finite graph with no sinks.
Let v ∈ G 0 be a vertex and partition r −1 G (v) into n ∈ N + possibly empty sets The in-split graph E of G at v with respect to the partition E is given by with source and range maps s E , r E : E 1 −→ E 0 given by Remark 4.3. The above definition is a modification of [1] in that we allow the partition sets to be empty, this is called Move (I-) in [8]. Note that this in-split introduces new sources, one for each empty partition set. The out-split introduces no new sources.
is not a block map since it is not compatible with E and F . We shall identify the vertices and edges of E and F via these bijections.
Given v i E ∈ E 0 we can perform an in-split of E at v i E using n partition elements to obtain a graph E (2) . Similarily, we obtain a graph F (2) as an in-split of F at v i F ∈ F 0 using n partition elements. Again there is a canonical identification of the vertices and edges in the two graphs. Proposition 4.6 below shows that E (2) and F (2) are eventually conjugate and we say that they are a 2-step balanced in-split of G. Iterating this process, we define an ℓ-step balanced in-split recursively.
For ℓ = 2, we depict this as Proposition 4.6. Let G be a finite graph with no sinks and let ℓ ∈ N. If E (ℓ) and F (ℓ) are ℓ-step balanced in-split graphs of G, then E (ℓ) and F (ℓ) are ℓ-conjugate. In particular, if E and F are elementary balanced in-split graphs of G, then E and F are 1-conjugate.
Proof. Suppose E and F are in-split graphs of G at v ∈ G 0 using n sets in the partitions There is a canonical surjection q E : E 2 −→ G 2 given by for e i f j ∈ E 2 . The map simply forgets the indeces of the edges. Similarly, there is a canonical surjection q F : F 2 −→ G 2 . We will construct a map ψ (1) : If ef ∈ G 2 and s(e) = v then there is a unique bijection θ : q −1 E (ef ) −→ q −1 F (ef ) which preserves the label of the first edge, that is, . If instead s(e) = v, then the preimage of ef under q E is a singleton. We may therefore define ψ (1) : for e i f j ∈ E 2 . This is bijective and compatible and satisfies q E = q F • ψ (1) . It therefore induces a 1-conjugacy between E ∞ and F ∞ .
Step 2. Set E (1) = E and F (1) = F and suppose E (2) is an in-split graph of E (1) at w E ∈ E 0 (1) while F (2) is an in-split graph of F (1) at an identified vertex w F ∈ F 0 (1) using m sets in the partitions We will use the block map ψ (1) : E 2 (1) −→ F 2 (1) constructed in Step 1 to define a 2-block map ψ (2) : E 3 (2) −→ F 3 (2) . As before there is a canonical surjection q E (2) : given by q E (2) (e i f j g k ) = ef g for e i f j g k ∈ E (2) . The map simply forgets the indeces of the edges. Similarily, there is a canonical surjection q F (2) : (2) .
Step ℓ: Assume now that E (ℓ) and F (ℓ) are ℓ-step balanced in-split graphs of G. In particular, there is an . This may be extended to a block mapψ (ℓ−1) : E ℓ+1 (ℓ−1) −→ F ℓ+1 (ℓ−1) , and there are canonical surjections Step 2. Using the same strategy as above, we can define a block map ψ (ℓ) : E ℓ+1 (ℓ) −→ F ℓ+1 (ℓ) which is bijective and compatible and satisfiesψ (ℓ−1) • q E (ℓ) = q F (ℓ) • ψ (ℓ) . It therefore induces an ℓ-conjugacy between E ∞ (ℓ) and F ∞ (ℓ) . Next, we prove a converse to Proposition 4.6. The proof uses ideas from [2] (see also [11]). Theorem 4.7. Let E and F be finite directed graphs with no sinks. Then E and F are eventually conjugate if and only if there exists a graph G such that E and F are (conjugate to) the iterated balanced in-split graphs of G.
Proof. If E and F are the iterated balanced in-split graphs of G, then they are eventually conjugate by Proposition 4.6. For the converse implication suppose that E and F are eventually conjugate. We may assume that there is a homeomorphism h : E ∞ −→ F ∞ which is an ℓ-conjugacy and whose inverse h −1 : F ∞ −→ E ∞ is also an ℓ-conjugacy and that c ∈ N is a continuity constant for h and h −1 .
We start by constructing the graph G as follows: The set of vertices is given by h(x) = y} and a transition rule similar to the above. Define also the graph F (j) with vertices h(x) = y} and a similar transition rule. Then E (0) = G = F (0) . We will show that E (ℓ) and F (ℓ) are iterated balanced in-splits of G. Whenever It follows from the choice of c ∈ N that if z, z ′ ∈ A and h(z . By a symmetric argument using h −1 , there is a bijection between the words of length ℓ which can be appended to x [ℓ,ℓ+2c] and the words of length ℓ which can be appended to y [ℓ,ℓ+2c] . In particular, if ℓ = 1 then E (1) and F (1) are balanced in-splits of G.
Assume now that ℓ > 0 and take z, 1,ℓ) . By the choice of c, we see that ℓ) . It follows that there is a bijection between the set of words of length ℓ−1 which can be appended to x [ℓ,ℓ+2c] and the set of words of length ℓ−1 which can be appended to y [ℓ,ℓ+2c] . Continuing this process we see that for each j = 0, . . . , ℓ, the graphs E (ℓ−j) and F (ℓ−j) are iterated balanced in-splits of G. In particular, E (ℓ) and F (ℓ) are ℓ-step balanced in-splits of G.
It remains to verify that E (ℓ) can be reached from E by a finite sequence of out-splits, and that F (ℓ) can be reached from F by a finite sequence of out-splits.
For each i = 0, . . . , 2c, consider the graph E (ℓ+i) with the set of vertices in E (ℓ+1) with identical pasts but distinct futures. A similar argument shows that F (ℓ) can be reached from F via a sequence of out-splits.
Hence E and F are conjugate to graphs which are the iterated balanced in-split of the graph G.
For ℓ = 0, we have an immediate consequence.
Corollary 4.8. One-sided conjugacy among finite graphs with no sinks is generated by out-splits (Move (O)).
Finally, we will show that ℓ-step balanced in-split graphs can be connected by a sequence of elementary balanced in-splits. Theorem 4.9. Eventual conjugacy of finite graphs with no sinks is generated by outsplits (Move (O)) and elementary balanced in-splits (Move (I+)).
Proof. Suppose E and F are eventually conjugate graphs. We know from Theorem 4.7 that E and F are conjugate (via a sequence of out-splits) to graphs which are ℓ-step balanced in-splits of a graph G. We may assume that ℓ 2. If E and F are ℓ-step balanced in-splits of G, we will show that they can be connected by a finite sequence of elementary balanced in-splits.
Remark 4.10. For ℓ = 2, the procedure in the proof above looks like this We illustrate this in Example 6.3.
Remark 4.11. In the proof of Theorem 4.9 it is crucial to make use of graphs with sources in order to connect ℓ-step balanced in-split graphs by elementary balanced insplits. This indicated the usefulness of considering the class of finite graphs with no sources instead or the smaller class of essential finite graphs. We do not know if it possible to prove this result circumventing graphs with sources.

Balanced strong shift equivalence
Williams introduced the notion of strong shift equivalence of nonnegative integer matrices and showed that a pair of shifts of finite type are two-sided conjugate if and only if their defining matrices are strong shift equivalent. In this section, we introduce balanced strong shift equivalence of nonnegative integer matrices and show that a pair of finite graphs with no sinks are eventually conjugate if and only if they are conjugate to graphs whose adjacency matrices are balanced strong shift equivalent.
Definition 5.1. A division matrix is a finite rectangular {0, 1}-matrix in which every column contains exactly one nonzero entry and every row contains at least one nonzero entry. The transpose of a division matrix is called an amalgamation matrix.
Given a graph E, its adjacency matrix is a nonnegative E 0 × E 0 -matrix A E whose (i, j)-entry is the number of edges in E from i to j. The adjacency matrix of a graph is unique up to a permutation of vertices. A classical result relates an out-splitting of a graph to their adjacency matrices. The theorem below is stated in [12,Theorem 2.4.14] for essential graphs but the proof carries through with the existence of sources.
Theorem 5.2. Let E and F be finite graphs with no sinks. Then F is an out-split of E if and only if there exist a division matrix D and a nonnegative rectangular matrix E such that Similarly, F is an in-split of E if and only if there exist a division matrix D and a nonnegative rectangular matrix E such that Here, A E and A F are the adjacency matrices of E and F , respectively.
Let G be a finite graph with no sinks and suppose E is an in-split graph of G. Fix an ordering of E 0 and F 0 , and let |E 0 | and |F 0 | denote the number of vertices in the graphs, respectively. We can construct a division matrix D as the |E 0 | × |F 0 | {0, 1}matrix subject to the condition that D(v, w) = 1 if and only if w ∈ E 0 is one of the split vertices of v ∈ G 0 . The matrix E is the |E 0 | × |F 0 | nonnegative integer matrix (with the same ordering of the vertices in E and F as for D) for which E(v, w) is the number of edges in G which are emitted from i ∈ G 0 and contained in the partition set corresponding to w ∈ E 0 . In [12], the matrix E is called the edge matrix of the split.
The fact that we allow empty partition sets for in-splits, Move (I-), is reflected in E as zero columns, and it has no effect on D. From this description we also see that if F is another in-split graph of G, then E and F are balanced in-splits if and only if the division matrices agree (up to permutation of vertices). Proposition 5.3. Let E and F be finite graphs with no sinks. Then E and F are elementary balanced in-splits of a graph G if and only if there exist an amalgamation matrix S and nonnegative rectangular matrices R E and R F such that where A E and A F are the adjacency matrices of E and F , respectively.
Proof. The graph E is an in-split of G if and only if there exist a division matrix D E and a nonnegative rectangular matrix R E such that Similarly, F is an in-split of G if and only if there exist a division matrix D F and a nonnegative rectangular matrix R F such that A F = D t F R F and A G = R F D t F . By the observation above, the in-splittings are balanced exactly when D E = D F . Putting S := D t E = D t F finishes the proof. The proposition above is a balanced analog of Theorem 5.2 and this motivates the next definition. Let us discuss some immediate consequences of this definition.
• If A and B are balanced elementary equivalent via (R A , S, R B ), then A and B are necessarily square with the same dimensions and this allows us to identify the vertices of the graphs determined by A and B. The matrices R A and R B also have the same dimensions. For this reason, balanced strong shift equivalence is too rigid to capture one-sided conjugacy (out-splits) of the graphs. • A zero row in S produces zero rows in A and B. This corresponds to sinks in the corresponding graphs so we do not allow this in the context of this paper. However, it might be relevant for a similar description encompassing a broader class of graphs. • In spite of its name, elementary equivalence is not an equivalence relation because it fails to be transitive, and strong shift equivalence is exactly its transitive closure. Similarly, balanced elementary equivalence is reflexive and symmetrix but not transitive, see Example 6.2, and we have defined balanced strong shift equivalence to be its transitivification. Moreover, A n+1 = B n A and B n+1 = A n B, for all n ∈ N + . • Given a pair of graphs E and F with adjacency matrices A and B, respectively, we can ask whether they are balanced elementary equivalent via some graph with adjacency matrix C whose dimensions must be bounded by the dimensions of A and B. This puts a natural bound on the dimensions and entries of a balanced elementary equivalence (R A , S, R B ). There are only finitely many choices of such matrices so this relation is decidable. It would be interesting to know whether balanced strong shift equivalence is a decidable relation. We construct a new graph as follows. Start by considering the disjoint union of the graphs E, F and G. The edges in E are called E-edges and, similarly, the edges in F and G are called F -edges and G-edges, respectively. For each vertex k ∈ G 0 and i ∈ E 0 we add R E (k, i) edges from k to i called R E -edges, and for each vertex k ∈ G 0 and j ∈ F 0 we add R F (k, j) edges from k to j called R F -edges. Similarly, for vertices i ∈ E 0 , j ∈ F 0 and k ∈ G 0 , we add S(i, k) edges from i to k and S(j, k) edges from j to k called S-edges. This finishes the construction of the graph. An S,R E -path is an S-edge followed by an R E -edge forming a path in the graph. We define S, R F -paths, R E , S-paths and R F , S-paths analogously.
Observe that we may identify the vertices of E and F , and if i ∈ E 0 is paired with j ∈ F 0 then S(i, k) = S(j, k) for all k ∈ G 0 . Moreover, since A = SR E , there is a bijection between E-edges and S, R E -paths from vertices i to i ′ in E 0 , and since B = SR F there is a bijection between F -edges and S, R E -edges from vertices j to j ′ in F 0 . Similarly, the relation R E S = R F S defines a bijection between edges in G and R E , S-paths, and R E , S-paths, respectively, from vertices k to k ′ in G 0 . Fix such bijections.
A 2-path in E now corresponds to an S, R E -path followed by another S, R E -path, and the middle two edges of these four edges are an R E , S-path which in turn corresponds to a single edge in G. As explained in [12,Section 7.2] this defines a 2-block map from E to G. Similarly, there is a 2-block map from G to F . Extending the first map and composing it with the second, we obtain a map E 3 −→ F 1 which is compatible with E and F . Moreover, if x 0 x 1 x 2 ∈ E 3 is mapped to an edge y ∈ F 1 via this map and i = s(x 0 ), then the S-edge emitted from i ∈ E 0 (with some range k ∈ G 0 ) corresponds to a paired S-edge emitted from the vertex j ∈ F 0 paired with i (also landing in k ∈ G 0 ). Since there is an R F -edge emitted from k ∈ G 0 and landing in s(y) ∈ F 0 , this defines an edge from j to s(y), say y 0 . Therefore, we actually obtain a (1, 1)-block map ψ : E 3 −→ F 2 sending x 0 x 1 x 2 ∈ E 3 to y 0 y ∈ F 2 .
The block map ψ extends to a (1, 1)-sliding block code h : E ∞ −→ F ∞ on the path spaces. An inverse is constructed by applying the same procedure from F to E, so h is a homeomorphism. This shows that E and F are eventually conjugate.

Examples
Example 6.1. This example shows that one-sided conjugacy and eventual conjugacy can be distinguished among graphs with finite path spaces. Consider the graphs E : . . a . F : . .
. α The adjacency matrices of the graphs have different total column amalgamations, so they are not conjugate. However, we can construct E and F as a balanced in-split of the graph .
. v at the vertex v. Hence E and F are 1-conjugate. In fact, any bijection of the path spaces which maps the loop in E to the loop in F is an explicit 1-conjugacy. Then E and F are elementary balanced in-splits, and F and G are elementary balanced in-splits. However, if A and B are the adjacency matrices of E and G, respectively, then A 2 = BA, so E and G are cannot be elementary balanced in-splits. Example 6.3. In this example we generate ℓ-conjugate graphs. Consider the graph G : . w .
. v e where e is a path of length ℓ − 1. If we perform balanced in-splits along the vertices of the path e ending at w we will obtain ℓ-conjugate graphs. The case with ℓ = 1 and v = w appeared in [3]. We illustrate the procedure when ℓ = 2 and e is a path of length one. A balanced in-split at v is given by Next, we perform a balanced in-split at w 1 to get . v .
e Hence E (2) and F (2) are connected by three elementary balanced in-splits.