What is a Coalgebra?
The definition of a coalgebra isn’t too involved. First we choose a category \(\mathcal{C}\) and an endofunctor \(\mathcal{F} : \mathcal{C} \rightarrow \mathcal{C}\). Then a coalgebra (more precisely an \(\mathcal{F}\)-coalgebra) is a pair of an object \(X \in \mathcal{C}\) and a morphism \(f : X \rightarrow \mathcal{F}(X)\).
In practice, we are primarily interested in cases where we take the category \(\mathcal{C}\) to be \(\textbf{Set}\). So what we really have is a pair of a set \(X\) and a function from this set to a related set. It might seem a bit of a weird idea, but we will see that it is actaully a very general idea which models a large number of automata and transition systems [Silv10].
Deterministic Finite Automata Coalgebraically
Let’s change tack a bit and recap the basics of transition systems. A DFA over an alphabet \(\Sigma\) is normally given by a finite set of states \(Q\), together with a transition function \(\delta : Q \times \Sigma \rightarrow Q\), a set \(F \in 2^Q\) of accepting states, and a start state \(q_0 \in Q\). Usually we package this together as a tuple.
\[ \langle Q, \delta, q_0, F \rangle \]
In order to get a coalgebra, we need to express this a bit differently. If we ignore the start state \(q_0\) for now, a DFA over an alphabet \(\Sigma\) can also be expressed as a pair.
\[ \langle Q, f \rangle \]
Where \(Q\) is a set \(f : Q \rightarrow 2 \times Q^\Sigma\) is a function that combines the \(\delta\) and \(F\). The function assigns to every state a pair of a boolean indicating if it is an accepting state, and a fuction which gives the state a sucessor state for each element of \(\Sigma\). So our functor \(\mathcal{F}\) is defined as \(\mathcal{F}(X) = 2 \times X^\Sigma\). Now we can see that \(\langle Q, f \rangle\) really is a coalgebra!
This is still a bit abstract, so let’s look at a concrete example in both representations. We will choose a simple alphabet \(\Sigma = \{ a, b\}\). We will work with the transition system which recognizes nonempty strings ending in \(b\).
Using the normal quad representation we can represent this DFA in the standard way.
\[\langle \{ 1, 2, 3 \}, \{ (1, a) \mapsto 2, (1, b) \mapsto 3, ..., (3, b) \mapsto 3\}, 1, \{ 3 \} \rangle \]
However, from the coalgebraic perspective, we have to choose a specific \(\mathcal{F}\)-coalgebra, namely \(\langle\{1,2,3\}, f\rangle\) with \(f\) given by:
\[ f(x) = \begin{cases} 0, \{a \mapsto 2, b \mapsto 3\} & x = 1 \\ 0, \{a \mapsto 2, b \mapsto 3\} & x = 2 \\ 1, \{a \mapsto 2, b \mapsto 3\} & x = 3 \end{cases} \]
Automata Homomorphisms
It is helpful to think of all the possible DFAs over \(\Sigma\) as being objects in the category \(\textbf{CoAlg}(\mathcal{F})\). Then it is very natural to ask, what are the morphims in this category? They turn out to be exactly the DFA homomorphisms. That is to say, they are exactly the functions from the sets of states of one automaton to another which preserve the language recognized by each state.
Final Coalgebras
A final coalgebra is simply a terminal object in \(\textbf{CoAlg}(\mathcal{F})\) so it is a DFA to which we can find a DFA-homomorphism from every other DFA over the same alphabet. Given that homorphisms preserve the language recognised by each state, it must be the case that this terminal DFA has a state for every regular language over \(\Sigma\)! Ok we cheated a bit. It certainly isn’t the case that this is a finite automaton, but it certainly is deterministic.
In fact, the states correspond to regular languages so our set \(Q\) is really \(2^{\Sigma ^ * }\) and the transition function corresponds to string derivatives so \(\delta(a, L) = \{ w \in \Sigma^{ * } \mid aw \in L \}\). The set of accepting states \(F\) is given by the set of languages containing the empty string \(F = \{ L \in 2^{\Sigma^{ * }} \mid \epsilon \in L \}\)
It actually has the nice property of being locally finite, meaning that from any state only a finite number of other states are reachable.