The n-Category Café

Yes, graded monoids have shown up in the theory of automata. See Hines (2003), “A Categorical Framework for Finite Automata”[1]. Basically, he uses graded categories are to model automata that can both read and write. If I understand properly, the idea is that an automata modifies its input as it progresses, and you can use the grading to keep track of the intermediate states of the computation.

It’s a pretty idea, but I’m not sure what it’s for – it seems too intensional to model sequential computation well. Perhaps it has some applications to concurrency.

[1] http://peterhines.net/Site/DOWNLOADS_files/MSCS.pdf

Graded monoids such as free monoids?

Yes, but a bit more general than free monoids. I want the following structure: a collection of sets $\{M_n\}_{n\in \mathbb{N}}$ (or a family of objects in your favourite category with binary products) graded by natural numbers $\mathbb{N}$ together with a family of “compositions”

satisfying an appropriate notion of associativity. I think that amounts to an algebra over the multicategory of natural numbers, no?

Free monoids, I think, would be graded by word length.

These structures come up if one takes modularity seriously, as in this paper (shameless self-promotion), and tries to do it for discrete time systems.

Right, that’s an algebra over the multicategory of natural numbers.

Another way to say the same thing is that it’s a lax monoidal functor from $(\mathbb{N}, +, 0)$ (seen as a discrete monoidal category) to $Set$.

Yet another way is to see it as a one-object category enriched in the discrete monoidal category $(\mathbb{N}, +, 0)$. Such an enriched category is sometimes called an $\mathbb{N}$-graded category (at least by me). They’ve been considered from time to time.

Yet another way is to see it as a monoid over $\mathbb{N}$, i.e. equipped with a monoid homomorphism to $\mathbb{N}$. More generally, an $\mathbb{N}$-graded category is a category over the one-object category $\mathbb{N}$.

The free category on a directed graph has a natural $\mathbb{N}$-grading. For if $G$ is a directed graph then we have the unique map $G \to 1$, where $1$ denotes the terminal graph; then applying the free category functor $F$ gives a functor $F(G) \to F(1) = \mathbb{N}$. In particular, the free monoid on a set has a natural $\mathbb{N}$-grading.

Hi, David, Neel - a more recent view on that paper is some stuff I did on dynamical systems, from a category theory / domain theory point of view.

Machine semantics

I wasn’t entirely sure what it was for at the time either ;) but it ended up being useful in building quantum circuits:

Quantum circuit oracles for Abstract Machine computations

Not sure how relevant this is to the thread, but I’m glad someone’s taking an interest in it.

Tim wrote:

My query would be: would some of the stochastic and information based variants of Petri nets correspond to certain variants of symmetric monoidal categories as yet undefined?

I’m writing a paper on this now — or at least something pretty similar. I’ll be blogging about it over on Azimuth in a while.

I don’t remember us talking here about Petri nets. Nor do I know the article “Petri nets are monoids”. I’ll have to find that!