Emmanuel Jeandel
email: emmanuel.jeandel@loria.fr.

STRONG SHIFT EQUIVALENCE AS A CATEGORY NOTION

come

Strong shift equivalence as a category notion

Introduction

Possibly the most important question in symbolic dynamics [START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF] is the decidability of the conjugacy problem: decide if two symbolic dynamic systems (more precisely subshifts of finite type) are isomorphic [START_REF] Boyle | Open Problems in Symbolic Dynamics[END_REF]. Subshifts of finite type can be interpreted as biinfinite walks in a finite graph, or equivalently as biinfinite words over a finite alphabet forbidding a given finite set of words. In this article, we will be interested in the matrix representation, where a subshift of finite type is just a matrix of nonnegative integers (but the graph representation will be central to understand the results and the intuition). In this context, two matrices M, N are strong shift equivalent (represent isomorphic subshifts) if and only if M ≡ N where ≡ is the smallest equivalence relation s.t. RS ≡ SR for all nonnegative, possibly nonsquare, matrices R, S.

The goal of this article is to investigate strong shift equivalence from the categorical point of view, using the concept of props. Props is a relatively old concept from MacLane's articles on categorical algebra, and is a natural formalism in which one can express easily circuits, i.e. diagrams made of boxes linked by wires. It has proven quite successful recently in categorical quantum mechanics, in particular with the introduction of the ZX-calculus [START_REF] Coecke | Interacting quantum observables: categorical algebra and diagrammatics[END_REF], a graphical language for quantum circuits (and more), and in linear algebra, by providing a new graphical way to reason about matrices [START_REF] Bonchi | Interacting Hopf algebras[END_REF][START_REF] Zanasi | Interacting hopf algebras[END_REF]. Similarities between these two languages are given in [START_REF] Carette | A recipe for quantum graphical languages[END_REF].

On the center of the representation of linear algebra by diagrams is the basic idea that the bialgebra prop is exactly the prop of nonnegative integer matrices, probably observed first in [START_REF] Pirashvili | On the prop corresponding to bialgebras[END_REF]. As symbolic dynamics is interested in a particular equivalence relation on nonnegative integer matrices, this is a good start to think about them categorically. As the equation RS ≡ SR reminds of the trace, it is therefore not surprising that there is a strong link between the traced bialgebra prop (matrices with a notion of traces) and strong shift equivalence.

The link is not completely immediate due to the fact that the classical notion of trace in a category is a notion of a partial trace. We will prove in this article that actually the traced bialgebra prop does not technically correspond to strong shift equivalence, but to another well studied notion of equivalence of matrices, flow equivalence [START_REF] Parry | A topological invariant of flows on 1-dimensional spaces[END_REF]. To obtain a full categorical formulation of strong shift equivalence, we will need to consider bialgebras with a distinguished morphism.

It is important to note that the link between flow equivalence and bicommutative bialgebras is not new, and has been investigated previously by David Hillman [START_REF] Hillman | Combinatorial spacetimes[END_REF], but for some reasons has not been investigated thoroughly since. This categorical manipulation of the concepts of symbolic dynamics is not just an intellectual game but serves some purpose, as it has actually the following consequence: Suppose one knows a category which contains a traced bialgebra (billions examples abound in the literature, the most prominent examples being finite dimensional Hopf algebras). Then one can interpret matrices in this category in such a way that two matrices that are strongly shift equivalent will have the same interpretation. This gives a new way to obtain invariants for strong shift equivalence (i.e. functions from matrices to some set S s.t. two matrices that are strong shift equivalents are equal by the function), with the added property that our approach is complete: there exist at least one category for which having the same interpretation is a necessary and sufficient condition for strong shift equivalence.

The article is organized as follows. In the first section, we recall the classical definitions of a prop, and gives in particular the graphical interpretation of the prop of matrices. In the second section, we introduce traced props, and show the main theorem: the traced completion of matrices with noninteger coefficients corresponds to matrices quotiented by flow equivalence, and the traced completion of matrices with coefficients in Z + [t] corresponds to matrices quotiented by strong shift equivalence.

In the last section, we explain how we can recover classical and new invariants for symbolic dynamics by exploiting the idea of interpreting matrices in traced bialgebra props. This section is developed from the point of view of someone who knowns no invariant of strong shift equivalence: we look at existing and well known bialgebras and see which invariant we get from them. The fact one obtains this way fairly well known invariants from symbolic dynamics acts as a proof that the whole approach is successful.

The perfect reader for this article is someone familiar both with category theory (esp. the categorical approach to universal algebra developed by Lawvere) and symbolic dynamics. It should be accessible however to a reader with only a passing familiarity in at least one of the two domains.

prop and finitely presented props

1.1. props. A prop 1 is one of the categorical ways to represent circuits. Morphisms in a prop (may) represent circuits: we have two composition laws on circuits: parallel (⊗) and sequential (•) compositions that should satisfy some obvious properties.

Definition 1 (prop).

A prop P is the data, for each pair (n, m) ∈ N 2 of a set 2 P[n, m], called the set of morphisms. An element f ∈ P[n, m] is usually written f : n → m. These sets are linked by the following operators:

• A composition • : P[b, c] × P[a, b] → P[a, c] satisfying: (f • g) • h = f • (g • h). • A tensor product ⊗ : P[a, b]×P[c, d] → P[a+c, b+d], satisfying: (f ⊗g)⊗h = f ⊗(g ⊗h) and (f • g) ⊗ (h • k) = (f ⊗ h) • (g ⊗ k). • An empty morphism 1 : 0 → 0 such that f ⊗ 1 = 1 ⊗ f = f for all f : a → b. • An identity id : 1 → 1 such that f • id ⊗a = id ⊗b • f = f for all f : a → b. With the convention id ⊗0 = 1.
• A symmetry σ : 2 → 2 satisfying: σ 2 = id ⊗2 and such that,

σ a • (f ⊗ id) = (id ⊗ f ) • σ b , for all f : a → b, where σ n+1 = (1 ⊗n ⊗ σ) • (1 ⊗ σ n ), with σ 0 = id. A prop functor F (i.e. a morphism of props) from P to Q is a set of maps, again denoted F , from P [n, m] to Q[n, m] such that F (f • g) = F (f ) • F (g), F (f ⊗ g) = F (f ) ⊗ F (g), and F (id P ) = id Q , F (0 P ) = 0 Q , F (σ P ) = σ Q .
1 prop was originally an acronym from PROducts and Permutations 2 Technically we only consider locally small props, i.e. props where morphisms form a set, but the distinction is irrelevant for most of the paper.

In the language of categories [START_REF] Mac | Categories for the working mathematician[END_REF], a prop is a small strict symmetric monoidal category whose monoid of object is spanned by a unique object.

Props admit a nice diagrammatical representation that gives a topological interpretation to the axioms [START_REF] Selinger | A survey of graphical languages for monoidal categories[END_REF]. A morphism f : n → m is represented as a box with n inputs and m outputs, with inputs on the left and outputs on the right. Composition is represented by plugging the boxes, and the tensor product by drawing the boxes side by side. The identity is represented by a single wire, the empty morphism by an empty diagram and the symmetry by wire crossing:

. . . f . . . . . . f . . . g . . . . . . f . . . . . . g . . . f : n → m id : 1 → 1 f • g f ⊗ g σ : 2 → 2
These notations are well chosen, as the equations defining a prop correspond to equalities of diagrams that are obvious to the eye [START_REF] Selinger | A survey of graphical languages for monoidal categories[END_REF][START_REF] Joyal | The geometry of tensor calculus, I[END_REF], so we can equivalently work with equations or with diagrams. To give one example, the symmetry axioms express that the boxes can move through wires:

= . . . . . . f . . . = . . . f . . . . . .

Here are a few examples:

Example 1. Let X be a set. F un X is the prop where the morphisms n → m are exactly the functions from X n to X m . The composition • is the classical composition of functions, the tensor product ⊗ is the cartesian product.

Example 2. Let R be a semiring and d an integer. M at d R is the prop where the morphisms n → m are the matrices with coefficients in R of size d m × d n . The composition • is the product of matrices, the tensor product ⊗ is the Kronecker product of matrices.

1.2.

Presentations. An interesting way to give props is with generators and relations. In a similar way to universal algebra, a formal definition can be obtained by first considering the free prop given by the generators (consider all circuits obtained from the generators using the compositions •, ⊗), and by then quotienting the category by the equations. See [START_REF] Baez | Props in network theory[END_REF] for the formal definition. We only only give the universal property of such a prop: Definition 2. Let G be a set of generators and E be a set of equations. The prop P presented by (G, E) is (one of ) the prop satisfying the following properties:

• P contains the generators G and the generators satisfy the equations of E • For any other prop Q that has this property, there is a unique prop functor from P to Q that sends the generators to the generators. The existence of such a prop is given in [START_REF] Baez | Props in network theory[END_REF]. The uniqueness (upto prop isomorphism) is implied by the universal property.

We will only give here a few examples that we hope are illuminating.

Example 3. In the prop with no generators and no equations, the only thing we can do is use the identity morphism id and the symmetry σ to obtain diagrams.

• (η ⊗ id) = µ • (id ⊗ η) = id , µ • (µ ⊗ id) = µ • (id ⊗ µ) and µ • σ = µ.
If we depict the generators as and , the equations become:

= = = =
Using the first equation, one can "define" a generalized version of the diamond of type k → 1 inputs by composing k -1 diamonds 2 → 1. The first equation essentially states that the order of composition is irrelevant. Now it can be proven easily that every morphism can be represented by a diagram of the following form:

It is then easy to see that what we obtain is the prop F un where F un[n, m] is the set of all functions from [1, . . . , n] to [1, . . . , m], with • as function composition and ⊗ is disjoint union. The picture above represents in particular the function from [START_REF] Baez | Props in network theory[END_REF][START_REF] Michael | Thompson's group F[END_REF][START_REF] Bonchi | Interacting Hopf algebras[END_REF][START_REF] Bowen | Homology for zero-dimensional nonwandering sets[END_REF][START_REF] Bowen | Zeta functions of restrictions of the shift transformation[END_REF][START_REF] Boyle | Open Problems in Symbolic Dynamics[END_REF] to [START_REF] Baez | Props in network theory[END_REF][START_REF] Michael | Thompson's group F[END_REF][START_REF] Bonchi | Interacting Hopf algebras[END_REF][START_REF] Bowen | Homology for zero-dimensional nonwandering sets[END_REF][START_REF] Bowen | Zeta functions of restrictions of the shift transformation[END_REF] given by 1 → 2 2 → 5 3 → 5 4 → 2 5 → 2 6 → 3. Now, to prefigure what we will be doing later on, remark that the equations satisfied by µ and η are exactly the equations of a commutative monoid. This means that the diagrams of the prop F un can be interpreted (i.e., there is a functor) in any prop that contains two morphisms satisfying the monoid equations (this is of course by the universal property of a prop given by generators and relations).

As an example, remember the prop F un X , the prop where the morphisms n → m are exactly the functions from X n to X m , in the particular case X = R. This prop contains a morphism µ : R 2 → R defined by µ(x, y) = x + y and a morphism η : R 0 → R (a constant) define by η = 0 and these two morphism satisfy the monoid equations. This means every diagram in the prop F un can be interpreted in the prop F un X . The previous diagram will correspond to the map from R 6 → R 5 defined by (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) → (0, x 1 + x 4 + x 5 , x 6 , 0, x 2 + x 3 )

In the case where we start from a prop with a complicated set of generators of equations, we can use this method to transform diagrams in a prop we do not understand into diagrams in a prop we do understand. This might be used for example to prove that two different diagrams are nonequal (interpret the diagrams in another prop in which it is clear that they are nonequal) and will be the focus of the last section.

The most important example of a finitely presented prop is the following one, on which we will base all works in this paper: Definition 3. The prop MAT is the prop with the following presentation:

• 4 generators µ : 2 → 1, η : 0 → 1, ∆ : 1 → 2, ǫ : 1 → 0 and • 10 equations: µ • (η ⊗ id) = µ • (id ⊗ η) = id µ • (µ ⊗ id) = µ • (id ⊗ µ) µ • σ = µ (ǫ ⊗ id) • ∆ = (id ⊗ ǫ) • ∆ = id (∆ ⊗ id) • ∆ = (id ⊗ ∆) • ∆ σ • ∆ = ∆ ∆ • η = η ⊗ η ǫ • µ = ǫ ⊗ ǫ ǫ • η = 1 (µ ⊗ µ) • (id ⊗ σ ⊗ id) • (∆ ⊗ ∆) = ∆ • µ
In pictures:

= = = = = = = = = = = =
The first three equations are the monoid equations we saw before, the next three equations are comonoid equations (dual of monoid equations). The last four equations are called the bigebra/bialgebra/bimonoid equations.

With the first equations, we may define as previously white diamonds of type k → 1 and black diamonds of type 1 → k. The last four equations are essentially commuting equations, saying that when we want to do a black and a white operation, the order of the operation doesn't matter.

With these ten equations, it is easy to see that any diagram can be put in the following form: first white diamonds, then a permutation, then black diamonds, as in the following example: One can then prove, using the bialgebra rules, the following result: Proposition 1. The prop MAT is (isomorphic to) the prop M ⋆,⋆ (Z + ), the prop of matrices with nonnegative coefficients. Specifically M AT [n, m] = M m,n (Z + ) is the set of matrices over Z + of size m × n, with • the product of matrices and ⊗ the direct sum :

A ⊗ B = A 0 0 B
This proposition was probably proven first in [START_REF] Pirashvili | On the prop corresponding to bialgebras[END_REF], but is somewhat considered folklore. The preceding example corresponds to the matrix

    0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 2 1 0 0     .
This correspondence makes it easy to represent linear algebra equations by diagrams. The interested reader is urged to read the thesis by Zanasi [START_REF] Zanasi | Interacting hopf algebras[END_REF], and the blog of Pawel Sobocinski on this particular subject.

There is another way to see this prop: morphisms are bipartite graphs (with inputs on the left, and outputs on the right), composition plugs the inputs of the first graph into the outputs of the second graph, deleting the internal vertices by bursting them into edges.

This structure of monoid/comonoid with a bigebra law can be found in many domains of mathematics. One particularly important example is in F un X : one can take for µ and η a monoid on X, and for ∆/ǫ the copy comonoid : ∆(x) = (x, x) (so the black diamond copies its input) and ǫ is the only function with codomain 1 (ǫ forgets its input). The bigebra law then states the following: Supposons you want to do the product (for the monoid) of two inputs x, y then duplicate the result. Then you can alternatively duplicate the outputs (to obtain two copies of x, and two copies of y), then do the initial product twice.

The reader fluent in prop and category theory will probably expect the article to proceed to Hopf algebras, the canonical way to be able to matrices in Z. This article goes however in a different direction. First, we will deal with matrices in Z + [t]. For this we need to add a generator to code our new coefficient t. This can be done in the following way: Proposition 2. Consider the prop that contains the same generators and equations as before, with an additional generator h : 1 → 1 that satifies the following equations:

h • µ = µ • (h ⊗ h) h • η = η (h ⊗ h) • ∆ = ∆ • h ǫ • h = ǫ
In pictures:

= = = = This prop is exactly the prop M ⋆,⋆ (Z + [t]
), the prop of matrices with coefficients in Z + [t]

As an example, the following diagram: correspond to the matrix

    0 1 0 0 t 0 0 0 0 0 0 0 0 0 1 0 t 2 + t 1 0 0     .
We do not prove this result, as the proof is essentially similar to the previous proposition.

We finish this section by a few examples and questions that are actually not used in the following, but might interest the reader coming from symbolic dynamics and/or computability theory Example 5. Consider the prop with two generators linked by the following equations:

= =
Then one can prove easily that the morphisms 1 → 1 of this prop corresponds exactly to Thompson's group V [START_REF] Cannon | Introductory Notes on Richard Thompson's Groups[END_REF]. This will be immediate for the reader familiar with this family of groups as the pictures we obtained here are very similar to the diagrams used to express elements of the group, see [START_REF] Michael | Thompson's group F[END_REF].

There is also a notion of a pro, which is a prop without the symmetry σ. If we delete the symmetry σ from the definition, then one can see that the morphisms 1 → 1 of this pro now corresponds exactly to Thompson's group F . Example 6. Consider the prop with two generators linked by the following equations:

= = = = =
Then one can prove that the morphisms 1 → 1 of this prop corresponds exactly to the invertible generalized shift maps of Moore [START_REF] Moore | Generalized shifts: unpredictability and undecidability in dynamical systems[END_REF] over an alphabet of size 2 (or of Thompson's group 2V ). Equivalently, one can think of morphism n → m as an atomic movement of a reversible one-tape Turing machine on an alphabet of size 2. The n different inputs correspond to the n possible initial state of the Turing machine, and the m output of the state at the next step (usually we take m = n).

The idea is to consider the generators as acting on two binfinite stacks of symbols 0 and 1. The white symbols correspond respectively to the push and pop operations on the first stack. The pop operation splits the input into two different futures: the future where the symbol that was popped is a 0 (say, taking the wire on top), and the future where the symbol that was popped is a 1 (taking the wire on the bottom).

Using two stacks, one can simulate a Turing machine. It is then an exercise to code the "shift" operation by using one pop on one stack and one push on the other stack.

Remark 1. Let M be a finitely presented monoid. Then is it easy to find a prop s.t. the morphisms 1 → 1 of the prop corresponds with the monoid M : just put one generator of the prop per generator of the monoid, and one equation in the prop per equation of the monoid.

Conversely, is it always true that the 1 → 1 morphisms of a finitely presented prop form a finitely presented monoid ? It is obvious that they form a recursively presented monoid.

More generally, consider a prop with a finite number of generators, and a recursive set of equations. Can we always reduce the set of equations to a finite one, at the price of adding some generators and only considering the "subprop" generated by the original generators ? This is the equivalent of the Higman embedding theorems for groups, and an open question asked by Lawvere.

Traced props

2.1. Introduction and statements of the theorems. From the time they were given birth, every computer scientist that sees circuits has only one natural urge: to plug some output back to an input, which would lead to a feedback loop, or to fixed point, depending on the context. From the point of view of category theory, this action is called tracing.

We will now consider traced props, which are props with an additional operator(s): the trace. Intuitively, the operator tr k (trace k) is plugging the k first outputs into the k first inputs. This operator will be represented graphically as follows:

f The dashed rectangle represents on which morphism the trace is applied. Once the equations of a traced prop are given, it will no longer be essential to represent this dashed rectangle, as all ways of understanding the diagram will give the same morphism: Definition 4 (traced prop). A traced prop is a prop that contains an operator tr that transforms a morphism m + 1 → n + 1 into a morphism m → n and that satifies the following five equations, where tr p represents the p-th iterate of the operator (with tr 0 (f ) = f ).

• Tightening: tr ((id ⊗ g) • f • (id ⊗ h)) = g • tr (f ) • h • Yanking:tr (σ) = id • Sliding:tr m (f • (g ⊗ id ⊗p )) = tr n ((g ⊗ id ⊗q ) • f ) for f : p + m → q + n and g : n → m • Strength:tr (f ⊗ g) = tr (f ) ⊗ g
In pictures:

g f h = g f h = g f = f g f g = f g A traced prop functor F is a prop functor that preserves the trace: trF (f ) = F (trf )
We now will be interested in presentations of traced props. The definition of a traced prop given by generators and equations is similar to Definition 2, by replacing props and prop functors by traced prop and prop functors.

Another way of defining it is by first looking at the prop given by generators and equations, and then adding the trace: Definition 5. Let P be a prop. The traced completion P of P is a prop s.t.

• P is traced.

• There is a prop functor ι : P → P .

• For any other prop (Q, η) with the same properties, there is a unique traced prop functor

G from P to Q s.t. Gι = η
By the universal property of the definition, it is easy to see that the traced completion is unique up to isomorphism. It is less clear that it exists, and we will construct explicitely the traced completion of a prop in the next section.

It is important to note that ι is in general not an embedding of P into P , i.e., it is not always injective.

Our goal now is to add traces to matrices. Consider the prop M ⋆,⋆ (Z + ) of definition 3, i.e. the prop of matrices with noninteger coefficients. As explained, the morphisms of this prop can also be seen as bipartite graphs. Now consider the traced prop given by the same axioms, and in particular the morphisms 0 → 0 of this prop, i.e. morphisms with no input and no output. They are clearly obtained by plugging the outputs of some bipartite graph back into its inputs, so that all vertices are not "internal vertices" and there are no inputs/output vertices.

An example is illustrated in Figure 1. We start from a matrix M (1.

(a) (b) (c) (d) M =   0 2 1 0 1 1 0 0 1   Figure 1.
From a matrix to a graph, using diagrams.

However our new prop has relations, which means that some of these square matrices actually represent the same morphism in this prop. When are two matrices/graphs equal exactly? Theorem 1. Let M ⋆,⋆ (Z) be a traced completion of the prop M ⋆,⋆ (Z) of Definition 3.

To any square matrix M of M ⋆,⋆ (Z) of size n, we associate a 0 → 0 morphism M of M ⋆,⋆ (Z) by tracing everything, i.e. M = tr n (ι(M )).

Let M, N two square matrices, possibly of different size. Then M and Ñ represent the same morphism exactly when M and N are flow-equivalent.

Flow equivalence [START_REF] Parry | A topological invariant of flows on 1-dimensional spaces[END_REF] is a relation on graphs (equivalently on square matrices of nonnegative integers) used in symbolic dynamics. The definition will be given later on.

This theorem is already present in the work of Hillman [START_REF] Hillman | Combinatorial spacetimes[END_REF], although its use has never been investigated thoroughly. Here we make it more precise.

Before proving the theorem and giving applications, we will do the same work with the prop of Proposition 2. Here we are able to represent matrices in Z + [t]. There are harder to represents as graphs, unless one starts labelling the edges with elements of Z + [t]. However, if all coefficients of the matrix are integer multiples of t, then we can also see them as graphs.

Theorem 2. Let M ⋆,⋆ (Z + [t]) be a traced completion of the prop M ⋆,⋆ (Z + [t]) of Proposition 2. We use the same notation as the previous theorem.

Let M and N two square matrices with nonnegative integral coefficients. Then tM and tN represent the same morphism exactly when M and N are strong-shift equivalent.

Two matrices are strong-shift equivalent exactly when the graphs represents isomorphic subshifts [START_REF] Williams | Errata to "classification of subshifts of finite type[END_REF]. As a consequence, this theorem essentially states that (a) deciding the theory of strong-shift equivalence, equivalently deciding whether two graphs represents isomorphic subshifts of finite type is exactly the same as (b) deciding which equalities are true in all models of traced bialgebras.

The remainder of this section is devoted to the proof of the two statements, and of the definitions of flow equivalence and strong-shift equivalence.

2.2. Understanding traced props. Suppose we already know quite well a prop given by generators and relations. How do we obtain the traced prop given by the same relations (i.e. the traced completion of the original prop) ? This is what we will do below.

We denote σ a,b : a + b → b + a the symmetry that on diagrams exchanges the first a wires and the last b wires. -((g ⊗ id ⊗m ) • M, q) ∼ (M • (g ⊗ id ⊗n ), p) where M : n + q → m + p and g :

p → q -(M, k) ∼ ((id ⊗ M ) • (σ n,1 ⊗ id ⊗m ), k + 1)
To preverse ink, we will use [M, k] to denote the equivalence class that contains (M, k).

• The composition of [M, p] and [N, q], where M : p + m → p + n and N :

p + r → p + m is [(N ⊗ M ) • (id ⊗q ⊗ σ m+q,r ), p + q + m] • The tensor product of [M, p] and [N, q], where M : m + p → n + p and N : m ′ + q → n ′ + q is (id ⊗p ⊗ σ n,q ⊗ id ⊗n ′ ) • (N ⊗ M ) • (id ⊗p ⊗ σ m,q ⊗ id ⊗m ′ ), p + q • The trace of [M, k] is [M, k + 1]
The definition is a bit hard to digest, and will be easier to see graphically. We will picture pairs [M, k] as the diagram M with the first k wires dashed: M

For simplicity, wires in the following diagrams may represent an arbitrary (possibly zero) number of wires

• The equivalence class on pairs is defined by the following rules (the second equation gives two different diagrammatic interpretations, depending on whether the wire to be permuted with the first wire is dashed or nondashed):

M g ∼ g M M ∼ M M ∼ M • The composition of [M, p] and [N, q] is: N M • The tensor product of [M, p] and [N, q] is N M • The trace of M is M
Proof. The main idea is that:

• Q is indeed a traced prop. In particular the two compositions are well defined. The proof is not interesting and given in appendix A • The equations we took for defining the equivalence class, and the two products are the good one, as illustrated by the diagrammatic equations below.

Let P be the traced completion of P . First, consider the subcategory R of P consisting of all morphisms of the form T r k ι(M ) for M a morphism of P . It is easy to see that R is actually a traced prop. By the universal property, R = P , therefore all morphisms of P can be written in the form T r k ι(M ) for M a morphism of P . Let M be any morphism in a traced prop. All the following equations are true in any traced prop This implies that F G is the identity on ι(M ) and therefore that F G is the identity functor by the universal property of P . F is therefore surjective and injective, and therefore an isomorphism.

2.3.

Flow equivalence and strong shift equivalence. Definition 6. Let R be a semiring. We say that M and N are Parry-Sullivan-equivalent, for short PS-equivalent, in R if M ≃ N where ≃ is the smallest equivalence relation s.t.:

• RS ≃ RS for all (nonnecessarily square) matrices R, S.

• a A ≃   0 1 A 0 a 0 
 for all row vectors a.

In the special case where R = Z + we will say that M and N are flow-equivalent This relation on matrices has only been formulated for the special case of R = Z + by Parry and Sullivan [START_REF] Parry | A topological invariant of flows on 1-dimensional spaces[END_REF].

Corollary 1 (formal statement of Theorem 1). Suppose that P = M ⋆,⋆ (R) is the prop of matrices with coefficients in a semiring R.

Let M, N be two matrices of size n × n and m × m respectively. Then [M, n] = [N, m] in the traced completion of P iff M and N are PS-equivalent It suffices to remark that the equation of ∼ in Proposition 3 coincides with the equations of ≃ given above in the case where there are no inputs and outputs.

For the next theorem, we need : Therefore PS-equivalence implies positive equivalence 4 .

Definition 7. Let R
. . . M n ∈ Z + [t] s.t • M 1 = M • M n = N • for all i ≤ n, either I -M i is obtained from I -M i-
Corollary 2 (formal statement of Theorem 2). Suppose that P = M ⋆,⋆ (Z + [t]) is the prop of matrices with coefficients in a semiring Z + [t]. 3 We include in row/column operations the ability to add one dimension to the matrix. The original article [START_REF] Boyle | Positive algebraic k-theory and shifts of finite type, Modern Dynamical Systems and Applications[END_REF] does not use this property, as it deals with infinite matrices with finitely many nonzero coefficients. This is of course equivalent. 4 There is a generalization of positive-equivalence to any semiring included in some ring, and one can see easily that PS-equivalence always imply positive equivalence. In fact, these notions coincide for rings, but in a general semiring, positive equivalence do not imply PS-equivalence.

Consequences and applications

Deciding strong shift equivalent is the main open problem of symbolic dynamics, and it is not clear that the new reformulation of the problem in terms of category theory would imply decidability or undecidability of the problem. However it can be used to obtain new invariants, or to recover in a natural way existing invariants. An invariant of strong shift equivalence is a quantity (a real number, a group...) associated to a matrix M two matrices that are strong shift equivalent have the same invariant. An invariant is never enough to prove that two matrices are strong shift equivalent, but a well chosen invariant might be used to prove that two matrices are not strong shift equivalent.

Here is our method to obtain new invariants. Consider a category C in the wild, which contains some mathematical items which satisfy the equations of Definition 3 and Proposition 2, and suppose the category is traced. For the ease of the reader, we have recapitulated the most important equations in Fig 2 .  Then, in this case, given a square matrix M with nonnegative integer coefficients, one can associate to the matrix M a morphism ψ(M ) : 0 → 0 in this category C. The correspondance is given in Figure 3, where black diamonds with n outputs corresponds to a cascade of n -1 black diamonds with 2 outputs (same for white diamonds):

• Let M = (a ij ) 1≤i,j≤n
• The diagram has exactly n black diamonds and n white diamonds, numbered from 1 to n • There are a ij wires from the i-th black diamond to the j-th black diamond, each of them support a white rectangle. • The output of the i-th white diamond is linked back to the input of the i-th black diamond.

• The new diagram is a diagram with no inputs and outputs that we call ψ(M ).

This can be done purely categorically without resorting to diagrams: As C is traced, and contain generators that satisfy all the equations of M ⋆,⋆ (Z + [t]), by the universal property of M ⋆,⋆ (Z

+ [t])
there is a functor F from M ⋆,⋆ (Z + [t]) to C. Then the 0 → 0 morphism we are looking at is just

ψ(M ) = F (tr n (ι(tM ))).
From Theorem 2 we obtain that if M and N are strong shift equivalent, then ψ(M ) = ψ(N ). In other words, we have developed a systematic way for obtaining invariants of strong shift equivalence. As Theorem 2 is an equivalence, we also have the guarantee that our approach is complete in the sense that in one specific category (namely M ⋆,⋆ (Z + [t]) itself), M and N are strong shift equivalent iff ψ(M ) = ψ(N ). Now, categories which contains (bicommutative) bialgebras do exist in the wild, and they are actually very well studied. The purpose of this section is now clear: we will look at well known examples of bialgebras, and see to which invariant ψ they correspond.

There are however two caveats: most of the known bialgebras are actually Hopf algebras. The additional structure of Hopf algebras intuitively gives the existence of a "negative wire" (the antipode) that can cancel a wire. This is bad in our case, as, when we interpret matrices in these categories, one would obtain invariants for strong shift equivalence in Z, i.e. a weaker and more well known notion of equivalence. The second caveat is that most examples of bialgebras are actually not in traced categories.

It turns out that in many examples, one can transform the bialgebra to solve the second problem, with the added benefit that the bialgebra will not be a Hopf algebra.

We will give three examples. The first two examples are possibly the most well known examples of bialgebras. We will explain how these bialgebras give rise to some well known invariants of symbolic dynamics. The third one is not that well known, and was actually conceived with foresight.

3.1. Monoids. The first example starts from one of the easiest possible bialgebra.

Let (M, ×) be a commutative monoid, with unit element 1. Consider the prop where arrows n → m corresponds to arbitrary functions from M n → M m , and consider inside this category the following functions:

x y x × y 1 x x x x
It is easy to see that these functions satisfy the defining equations of 3, and in particular the fundamental bigebra equation: = However, there is no easy notion of a trace (of a feedback loop, of fixed points) in this category. One can solve the problem in two different ways. The first way is to consider the prop of multivalued partial functions (i.e. relations) instead of functions. This would work in theory but would not be very interesting: Remember that we will trace all inputs/ouputs of the diagrams, so we are only interested in morphisms 0 → 0 of your category. This particular category has only 2 such morphisms, so this would partition the whole set of matrices into only two sets, which does not give a good invariant.

The "good" way is to go to a weighted setting. In this setting, one has to consider inputs of size n to be elements of M n with multiplicities [START_REF] Eilenberg | Automata, languages and machines[END_REF]. In other words, let S n be the set of functions from M n to N ∞ , the set of nonnegative (possibly infinite) integers. For a function f in S k and x ∈ M k , f (x) has to be interpreted as the multiplicity of x. By identifying x ∈ M n with the function that is zero everywhere except on x, we get an embedding of M n into S n .

Then the arrows n → m of our category correspond to linear (in N ∞ ) functions from S n to S m . Now this category is traced: Let f be a function from S n to S m . T r(f ) is obtained in the following way. Let y be an input of T r(f ), and z ∈ M m . The coefficient of z in the output of T r(f ) is obtained by taking all possibles values of x ∈ M, computing f (x, y), looking at the coefficient of (x, z) in f (x, y), and adding up all these coefficients, possibly obtaining ∞ as a result.

Example 7. Suppose that our monoid M is the monoid R with multiplication and consider the following diagram:

To better understand the diagram, we will look at inputs in R 2 , but inputs are really in R 2 → N ∞ but they can be extended by linearity.

Without the trace part, we are looking at the function (x, y) → (x × y, x × y) Using the trace, we force the first output (x × y) to be actually equal to x. Now, for y ∈ M there are two cases:

• If y = 1, then x × y is actually equal to x, and we actually obtain an output on the other wire of value x, and this for all x. As a consequence, the traced function, on input 1, gives as input all possible values in M, each with coefficient 1.

• If y = 1, then x × y = x only if x = 0.
As a consequence, the traced function, on input y = 1, gives as output the value 0, with coefficient 1

Example 8. Suppose now that our M is the monoid R >0 with multiplication (or equivalently R with addition)

The only difference in this case is that on inputs y = 1 the function does not give an output (technically the output is the function identically equal to 0) Example 9. Suppose now that our M is the monoid of subsets of {0, 1} with union.

• On input y = ∅, the result is all 4 values ∅, {0}, {1}, {0, 1}, each with coefficient 1

• On input y = {1}, the result is {1} with coefficient 1 and {0, 1} with coefficient 1

• On input y = {0, 1}, the result is {0, 1} with coefficient 1 Now, we use our protocol, and start from a matrix M , see it as a diagram in this category using Figure3. What is the result we obtain ? It is easy to see that we obtain exactly the number of solutions of the equation M x = x. Proposition 4. Let M be a commutative monoid written additively. The number of solutions to the equation M x = x is an invariant of flow equivalence. More precisely, if M and N are two matrices that are flow equivalent, then the equation M x = x has the same number of solutions as the equation N x = x.

For strong shift equivalence, we also have to explain what the square will stand for. It is easy to see that we need it to be an homomorphism of M, and we get immediately the following: Proposition 5. Let M be a commutative monoid written additively and h be an homomorphism The number of solutions to the equation h(M x) = x is an invariant of strong shift equivalence. More precisely, if M and N are two matrices that are strong shift equivalent, then the equation h(M x) = x has the same number of solutions as the equation h(N x) = x.

Of course the fact that this is an invariant is quite immediate: the important thing is that we obtained it entirely algebraically.

By taking M = C and h the multiplication by λ, we get that if M and N are strong shift equivalent, then 1/λ is an eigenvalue of M iff 1/λ is an eigenvalue of N , i.e. M and N have the same eigenvalues, except possibly the value 0. This is a well known invariant, called the "spectrum away from zero".

By working in finite fields (so that we can count something: with M = C the number of solutions is either 0 or ∞), we can prove easily that the eigenvalues should also have the same multiplicities.

3.2. Algebras and tensors. In general algebra [START_REF] Robert | Fundamentals of hopf algebras[END_REF][START_REF] Sweedler | Hopf algebras[END_REF], a bialgebra in some vector space V over some field K is something that satifies all axioms of Definition 3 when arrows from n → m are linear maps from V ⊗n to V ⊗m .

The most well known bialgebras are the monoid algebra, and the binomial algebra, as any good book about bialgebras and Hopf algebras will prove 5 .

In the case of the monoid algebra K[M ] of a monoid M , V is the vector space of basis M , the multiplication is the multiplication on M extended linearly, and the comultiplication map ∆ : V → V ⊗2 is the copy map ∆(x) = x ⊗ x.

In the case of the binomial algebra, we take V = R[X], the polynomials with real coefficients in one variable. There is a obvious algebra structure on V , the multiplication:

• µ(P ⊗ Q) = P Q • η = 1
And there is a compatible comultiplication, which gives a bialgebra

• ∆(X) = 1 ⊗ X + X ⊗ 1. More generally ∆(X n ) = k n k X k ⊗ X n-k • ǫ(X n ) = δ 0,n
We can try to exploit these well known (bicommutative) bialgebras in our case. There is however a fundamental problem: When V is infinite, there is in general no notion of a trace.

The first example for a finite, commutative M , essentially amounts to the work that has been done in the previous section.

To fit the second example in our framework, we need to put it somehow in a category where a trace is defined. If we think of these examples as matrices with coefficients in K, then the problem of the trace is that we need to do an infinite sum, which is usually impossible. However, if we think of matrices with coefficients in a complete semiring R instead of a field K, then everything works.

Let R be a commutative complete semiring. This is a semiring where all sums, even possibly infinite, are defined 6 . Let I be a set.

Then we can look at the prop where the morphisms n × m are matrices with coefficients in R of size I n by I m with the usual product and tensor product. More exactly:

• Arrows n × m are functions from I n × I m to R • The composition f g of f : n×m and g : m×p is defined by (f g)(x, y) = z∈I m f (x, z)g(z, y). This is well defined as R is complete. • The tensor product f ⊗ g of f and g is defined by

(f ⊗ g)((a, b), (c, d)) = f (a, c)g(b, d) • The trace of f is (trf )(y, z) = x f ((x, y), (x, z))
If we think in terms of matrices, the full trace (i.e. where all outputs are branched into inputs) of a matrix is exactly what we usually call its trace, i.e. the sum of all diagonal elements (which is always well defined).

The reader should realize that the previous example of section 3.1 corresponds to matrices with coefficients in the complete semiring N ∞ . Now we can try to find the analogue of the binomial bialgebra. In this bialgebra, we were interested in V = R[X]. We will now use the complete semigroup R ∞ , the semigroup which contains nonnegative numbers and ∞, instead of R. The fact we restrict ourself to nonnegative numbers should not be a problem as the equations that define the multiplication and the comultiplication do not involve any negative number 7 . As general sums are now authorized, we will not obtain the polynomials in R

∞ , but formal series in R ∞ , that is R ∞ [[X]].
Let's take time to define things correctly :

• We define V ⊗n = R ∞ [[X 1 . . . X n ]]
, formal power series in n variables. Elements of V ⊗n will be written P (X 1 . . . X n ) • Arrows from n to m are linear maps from V ⊗n to V ⊗m • For two maps f, g the composition f • g is the usual composition of power series.

• If P (X 1 . . . X n ) ∈ V ⊗n and Q(X 1 . . . X m ) ∈ V ⊗m , then the tensor product of P and Q is (P ⊗ Q)(X 1 . . . X n+m ) = P (X 1 . . . X n )Q(X n+1 . . . X n+m ). We will identify X with X 1 , so X n ⊗ X p is a notation for X n 1 X p 2 . We can now look at the previous example in this setting. First, one can see easily that it is still a bialgebra in this setting. We will look at invariants for strong shift equivalence, so we need to interpret the square symbols in the diagrams. We will take the function X n → (λX) n for some λ ∈ R ∞ which is easily seen to be indeed a homomorphism for both the multiplication and comultiplication.

Before explaining which invariant we obtain, we will do a computation in one example.

Let's start with the matrix 1 1 1 0

We therefore want to know to which real number corresponds the diagram:

Let's start with the nontraced version 8 , and an input of the form X n ⊗ X m . After applying the black diamond, we obtain k n k X k ⊗ X n-k ⊗ X m . After applying the symmetry, we obtain k n k X k ⊗ X m ⊗ X n-k . After applying the squares, we obtain k n k (λX) k ⊗ (λX) m ⊗ (λX) n-k . Finally, after applying the white diamond, we obtain

k n k (λX) m+k ⊗ (λX) n-k = λ n+m k n k X m+k ⊗ X n-k
. Now, we are interested in the traced version of this diagram, and therefore, in the diagonal of the map. Now the coefficient of X n ⊗ X m is precisely obtained when m + k = n, and is therefore equal to n n-m λ n+m The trace of the diagram is therefore, for small values of λ:

n,m n n -m λ n+m = n,k n k λ 2n-k = 1 1 -λ 2 -λ
The reader familiar with invariants with symbolic dynamics has recognized this expression and know what our next theorem will be: Theorem 4. Let M be a nonnegative matrix. If we interpret M in the previous bialgebra, with X n → (λX) n as the homomorphism, the result we obtain is exactly ζ M (λ) the value of the Zeta function [START_REF] Bowen | Zeta functions of restrictions of the shift transformation[END_REF] of the shift computed at t = λ, with ζ M (t) = 1 det(I-tM) . In particular the Zeta function is an invariant of strong shift equivalence.

This theorem is a direct consequence of MacMahon's Master Theorem, see [START_REF] Alexander | Combinatory analysis[END_REF].

3.3. Groups and Cospans. In our first example, we proved that, for all monoid M, the number of solutions in M of the equation M x = x is an invariant of flow equivalence.

One can do a bit better, and actually associate a commutative monoid itself to a matrix M . We will explain how this can be explained categorically. Technically, what we will be looking at 7 However, the binomial bialgebra has the additional property of a Hopf algebra that we will lose, as this property involves negative coefficients. This is actually a good thing as we do not want an Hopf algebra. 8 In this particular example, one can use the equations of the traced prop to remove one trace, obtaining a simpler diagram. This is left as an exercise.

is a subcategory of CoSpan(AbGrp) where AbGrp is the category of abelian groups. However we will explain which prop we will look at in layman terms. We assume familiarity with classical notations for finitely presented groups. By X|R ab , we denote the commutative group with generators X and presentation R. It is important to note that all our groups are commutative. One can relax this condition at some point (even to obtain a bicommutative bialgebra at the end), but this will be easier to understand.

Morphisms n → m in our categories are triples (G, n, m) where G is a group with at least n + m generators, G = x 1 . . . x n , y 1 . . . y m , z 1 . . . z p |R ab . x 1 . . . x n and y 1 . . . y m are to be understood as "input" and "output" generators respectively, and z 1 . . . z p as "inside" generators of the group. We will usually write the morphism (G, n, m) = x 1 . . . x n |y 1 . . . y m |z 1 . . . z p |R ab to further separate the three kind of generators.

We will consider two such groups to be equal if there is an isomorphism that can only change the "inner" part of the group, i.e. (G, n, m) =

x 1 . . . x n |y 1 . . . y m |z 1 . . . z p |R ab and (G ′ , n, m) = x 1 . . . x n |y 1 . . . y m |z 1 . . . z q |R ′ ab are equal if there is an isomorphism φ from G to G ′ s.t. φ(x i ) = x i , φ(y j ) = y j .
There are two way to compose these morphisms:

• The composition of the morphism (G, n, m) = x 1 . . .

(H, n, k) = x 1 . . . x n |s 1 . . . s k |r 1 . . . r m , y 1 . . . y m , z 1 . . . z p , t 1 . . . t q |R, R ′ , r i = y i ab • The tensor product of the morphism (G 1 , n 1 , m 1 ) = x 1 1 . . . x 1 n 1 y 1 1 . . . y 1 m 1 z 1 1 . . . z 1 p 1 R 1 ab and the morphism (G 2 , n 2 , m 2 ) = x 2 1 . . . x 2 n 2 y 2 1 . . . y 2 m 2 z 2 1 . . . z 2 p 2 R 2 ab
consists in putting them side by side, i.e. it is the group:

(H, n 1 + n 2 , m 1 + m 2 ) = x 1 1 . . . x 1 n 1 , x 2 1 . . . x 2 n 2 y 1 1 . . . y 1 m 1 , y 2 1 . . . y 2 m 2 z 1 1 . . . z 1 p 1 , z 2 1 . . . z 2 p 2 R 1 , R 2 ab
As our groups are abelian, H is just the direct sum of G 1 and G 2 (or cartesian product if the reader prefer, but categorically it is clearly more like a direct sum). This category is traced (it is even compact closed): the trace of the morphism (G, n, m) = x 1 . . . x n |y 1 . . . y m |z 1 . . . z p |R ab consists in equating the first input and the first output and internalizing them, to obtain (H, n -1, m -1) = x 2 . . . x n |y 2 . . . y m |x 1 , y 1 , z 1 . . . z p |R, x 1 = y 1 ab .

The 0, identity, and symmetry morphisms in this prop have the following definitions (the definitions are kind of obvious as we choose as relations exactly what we want to happen)

• 0 = ||| ab (the trivial group with no generators) • id = x|y||x = y ab (this is the group Z presented with two generators)

• σ = x 1 , x 2 |y 1 , y 2 ||x 1 = y 2 , x 2 = y 1 ab
Now we need to find a bialgebra in this category. Again, the natural definition is quite obvious: These are the same diagrams as in subsection 3.1, except now their meaning are different: every wire now bears a generator. The first diagrammatic expression means that we have three generators, and there is an equation stating that the output generator is the sum of the input generators.

• µ = x 1 , x 2 |y||x 1 + x 2 = y ab (
We can now look at flow equivalence using this bialgebra. Morphisms 0 → 0 are groups with no input/output generators and only internal generators, so they are just plain groups, upto isomorphism. We obtain immediately: Proposition 6. Let M be a n × n matrix. The group x 1 . . . x n |M x = x ab (upto isomorphism) is an invariant of flow equivalence. In other words, the group Z n /(M -I)Z n is an invariant of flow equivalence. This is the celebrated Bowen-Franks group [START_REF] Bowen | Homology for zero-dimensional nonwandering sets[END_REF]. Now there is no reason to do this construction starting with a group, we can do the same with commutative monoids with no change, to obtain: Proposition 7. Let M be a n × n matrix. The commutative monoid x 1 . . . x n |M x = x ab is an invariant of flow equivalence.

Everything we did in this subsection was done informally by Hillman [START_REF] Hillman | Combinatorial spacetimes[END_REF], who also showed that the monoid typically does not contain more information than the group in relevant cases (Theorem 29 in [START_REF] Hillman | Combinatorial spacetimes[END_REF]). For irreducible matrices, the commutative semigroup x 1 . . . x n |M x = x ab is actually a group, and therefore equal to the Bowen-Franks group. The commutative monoid is therefore just a group with an extraneous unit element. Now the Bowen-Franks group is an invariant of flow equivalence, but if we want to find a finer invariant for strong shift equivalence, we need to find a nontrivial representation of the rectangle of Proposition 2, i.e. a nontrivial morphism for µ (adding two generators) and ∆ (duplicating a generator)

If we stay in the realm of groups and monoids, we probably won't obtain anything stronger than the previous group/monoid. One way to go is using Z + [t]-semimodules [12, chapter 14]. In this new setting, morphisms will not be monoids, but semimodules over Z + [t]. This is just a standard commutative monoid M , equipped with an action of Z + [t], denoted multiplicatively, which satifies the obvious axioms: a(m + n) = am + an, (a + b)m = am + bm, (ab)m = a(bm), a0 = 0, 0m = m, 1m = m for a, b ∈ Z + [t] and m ∈ M .

We can do the same theory as before for presentations of Z + [t]-semimodules. Now X|R will represent the Z + [t]-semimodule with generators X and equations R. Such a semimodule is for example x, y|t 2 x = 2ty + (t 2 + 3t)x, x + y = t .

Everything works exactly the same before, with the added benefit that we know have a nontrivial morphism for our bialgebra, as in In the specific case of M = 2 , this semimodule is t, x|2tx = x , which is the monoid Z + [1/2] where t "acts" by multiplication by 1/2.

we can use the same construction with Z[t]-modules instead of Z + [t]-semimodules. In that case, what we obtain is the cokernel of I -tM , which is well known to be equal to the dimension group [START_REF] Krieger | On topological markov chains[END_REF]. It suggests that the Z + [t]-semimodule is related to the positive part of the dimension group (seen as the ordered group), this should be examined more closely.

Conclusion

Using category theory, we have found a way to redescribe the strong shift equivalence problem in a purely categorical way: find identities satisfied in all traced bialgebras with a distinguished morphism.

As a consequence of this approach, we obtain a systematic way of obtaining new invariants for strong shift equivalence, and the hope to actually decide strong shift equivalence using these new invariants.

Here are a few natural questions:

• Is is sufficient to consider bialgebras (in the sense of linear algebra) of finite dimension to decide strong shift equivalence ? Or at the very least bialgebras that are finitely generated as bialgebras ? This might open a way to actually prove decidability of strong shift equivalence • In practice, one observe that many traced props are actually already compact closed. If we restrict ourselves to compact closed categories, do we obtain the same theory and identities ? • Is it possible to define a similar theory for subshifts of finite type in 2D?

  (a)), and represent it in the prop using a diagram (1.(b)). Now we trace the diagram by plugging inputs into outputs (1.(c)). By identifying both extremities that are joined together, one can see we just obtained a fancy way of representing the multigraph (1.(d)),i.e. the graph whose adjacency matrix is exactly M . Therefore, to each matrix M of nonnegative integers, one can associate a morphism (called M in the next definition) with no inputs and outputs in M ⋆,⋆ (Z), which looks visually like the graph whose adjacency matrix is M .

Proposition 3 .

 3 Let P be a prop. The traced completion P of P is isomorphic to the following prop Q:• Morphisms n → m are equivalence classes for ∼ of pairs (M, k) whereM ∈ P [k + n, k + m]and k is an integer, where ∼ is the smallest equivalence relation s.t.

M

  This implies that the map F : [M, k] → T r k ι(M ) from Q to P is well defined, and surjective. Now the following equations are true in any traced prop:This implies (a) that the map M → [M, 0] is a prop functor from P and Q and (b) that F (AB) = F (A)F (B) and F (A ⊗ B) = F (A) ⊗ F (B). Along with F (0) = 0, F (id) = id, F (σ) = σ and trF (f ) = F (trf ), we obtain that F is actually a (surjective) traced prop functor from our prop Q to P . Now by the universal property, we have another functor G from P to Q, satisfying Gι(M ) = [M, 0] for all morphisms M in P .

1 

 1 by a row/column operation 3 with coefficients in Z + [t], or I -M i-1 is obtained from I -M i by a row/column operation with coefficients in Z + [t]. (Notice that I -M i lives in Z[t], not in Z + [t]). By [7], M and N are strong shift equivalent in Z + iff I -tM and I -tN are positive equivalent. Therefore it suffices to prove that if M and N are PS-equivalent in Z + [t], then I -M and I -N are positive equivalent. Using the equations (4.5) to (4.8) of [7] for R, S ∈ Z + [t] and the parameter t (in their paper) equal to 1 , we obtain easily that I -RS and I 0 0 I -SR are positive equivalent, from which it follows easily that I -RS and I -SR are positive equivalent. Second, let M = a A . With a suitable choice of R and S, one can see that I -M is positiveequivalent to I -M ′ with M ′ = and therefore positive-equivalent to I -N where I -M ′ is obtained from I -N by adding the last row to the first row.

Figure 2 .Figure 3 .

 23 Figure2. Some of the equations that should satisfy the black, white diamonds and the rectangle square in the category so that we can apply the whole procedure. Equations involving the morphisms 0 → 1 and 1 → 0 are not shown for simplicity. The full list is presented earlier in Definition 3 and Proposition 2 .

  the group is Z 2 ) • η = |y||y = 0 ab (the trivial group) • ∆ = x|y 1 , y 2 ||x = y 1 = y 2 ab (the group is Z) • ǫ = x||| ab (the group is Z)One could represent them diagrammatically like this:

  Proposition 2: multiplication by t: x|y||y = tx Doing this we obtain immediately: Proposition 8. Let M be a n × n matrix. The Z + [t]-semimodule x 1 . . . x n |tM x = x is an invariant of strong shift equivalence.

  Thus every diagram looks like the following one: and it is easy to see that this prop is (isomorphic to) the prop Sym of invertible maps, i.e. Sym[n, m] is empty if n = m and Sym[n, n] is the set of all invertible functions from [1, . . . , n] to itself, with • as function composition and ⊗ is disjoint union.Example 4. Consider the prop with two generators µ : 2 → 1 and η : 0 → 1 that satisfy the equations: µ

  be a semiring. We say that M and N are strong shift equivalent in R if M ≡ N where ≡ is the smallest equivalence relation on matrices with coefficients in R s.t. RS ≡ SR for all (nonnecessarily square) matrices R, S with coefficients in R . Theorem 3. Let M, N be two matrices with nonnegative integer coefficients. Then tM and tN are PS-equivalent in the semiring R = Z + [t] iff M and N are strong shift equivalent in Z + . Proof. First, it is clear that if M, N are strong shift equivalent in Z + , then tM and tN are strong shift equivalent, and therefore PS-equivalent, in Z + [t].

For two matrices M, N ∈ Z + [t], say that I -M and I -N are positive equivalent if there is a finite sequence of matrices M 1

  x n |y 1 . . . y m |z 1 . . . z p |R ab and the morphism(G ′ , m, k) = r 1 . . . r m |s 1 . . . s k |t 1 . . . t q |R ′ab consists in putting the two groups together and identifying the outputs of the first one with the inputs of the second one. It is therefore the group:

These are the first examples in[START_REF] Robert | Fundamentals of hopf algebras[END_REF] and the first commutative examples in[START_REF] Sweedler | Hopf algebras[END_REF]. In[START_REF] Sweedler | Hopf algebras[END_REF] the binomial algebra is seen as a bialgebra over the symmetric algebra.

We will actually need only countable sums for the applications, so ω-complete semirings are sufficient

Acknowledgements E.J. wants to thank Mike Boyle for discussions about flow equivalence and positive equivalence.

Appendix A. Proof of Proposition 3 In this section, we prove that Q is indeed a traced prop. We will look at all axioms of Definition 1 and Definition 4.

A.1. Preliminary remarks. Before doing the proofs, we recall the equations of the equivalence relations, and give them names:

(A) (B) (C)

First remark by equation (A), when g as a permutation, that we can always permute the dashed wires in a diagram.

Second, let (D) be the equation:

Now, the advantage of using equations (A) + (B) + (D) instead of (A) + (B) + (C) is that we can apply equation (A) to (B) and (D) which shows immediately that the mirror equations of (B) and (D), i.e. when we apply the construction on the input rather than on the output, is still valid. The same is therefore also true of equation (C). We will call (B ′ ), (C ′ ), (D ′ ) the mirror equations of (B) and (C). Equation (C ′ ) for instance is:

The composition is well defined. For this , it is enough to prove the following equalities about the relation ∼, corresponding to equations (A), (B) and (D)

The first two are true by a trivial use of (A). The third one is true by an application of (B) then (A) to permute the wires. The fourth one is true by an application of (B).

The fifth equation is true by an application of (D) and then (A) to permute the wires. The last equation is true by an application of (B) A.3. The tensor product is well defined. Proofs about the tensor product are essentially easy and left to the reader: The definition we take of the tensor product in the category Q only consists in placing the two morphisms side by side, and exchanging the order of the input/outputs so that the dashed wires are on top, which is an operation as innocuous as possible, as equation (A) makes us able to permute the dashed wires.

A.4. The composition is associative. This amount to show the following equation, which is obvious (the two terms are not only equivalent, but equal):

A.5. The tensor product is associative, and has a neutral element. This is again trivial.

A.6. Link between the tensor product and the composition. We need to prove (

This is true by first applying naturality of the symmetry to exchange the positions of the boxes representing M 2 and M 3 , and then using equation (A) to permute the wires. A.7. Alternate form for the composition. Before doing the rest of the proofs, we will give an alternate form for the composition:

Indeed, let's start with the definition of the composition and apply equation (A) with g = N , then permute the first three wires:

By naturality of the symmetry, this is equal to:

M N

We may then apply equation (D ′ ).

A.8. The composition has an neutral element. This is obvious from the previous form.

A.9. The symmetry. . The symmetry is the morphism (σ, 0), where σ is the symmetry in the original category. It is easy to see that it satisfies the axioms necessary for a prop using the previous form for the composition. A.10. The trace axioms (tightening, yanking, sliding, strength. All axioms are easy to prove, using the alternate definition of the composition from above. Yanking in particular is equation (D) in the particular case where M is id. Sliding is essentially equation (A). Strength and Tightening are essentially reordering of the wires using equation (A).