Canonical Nondeterministic Automata

Robert R. Myers, Jiří Adámek, Stefan Milius, Henning Urbat

► To cite this version:

Robert R. Myers, Jiří Adámek, Stefan Milius, Henning Urbat. Canonical Nondeterministic Automata. 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2014, Grenoble, France. pp.189-210, 10.1007/978-3-662-44124-4_11. hal-01408760

HAL Id: hal-01408760

https://inria.hal.science/hal-01408760

Submitted on 5 Dec 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Canonical Nondeterministic Automata

Robert S. R. Myers<fnref n="1" />, Jiří Adámek<fnref n="1" />, Stefan Milius<fnref n="2" /> and Henning Urbat<fnref n="1" />

**Abstract.** For each regular language $L$ we describe a family of canonical non-deterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for $L$ in a locally finite variety $V$, and apply an equivalence between the finite $V$-algebras and a category of finite structured sets and relations. By instantiating this to different varieties we recover three well-studied canonical nfas (the átomaton, the jiromaton and the minimal xor automaton) and obtain a new canonical nfa called the distromaton. We prove that each of these nfas is minimal relative to a suitable measure, and give conditions for state-minimality. Our approach is coalgebraic, exhibiting additional structure and universal properties.

## 1 Introduction

One of the core topics in classical automata theory is the construction of state-minimal acceptors for a given regular language. It is well-known that the difficulty of this task depends on whether one has deterministic or nondeterministic acceptors in mind. First, every regular language $L \subseteq \Sigma^*$ is accepted by a unique minimal deterministic finite automaton (dfa): its states $Q_L$ are the derivatives of $L$, i.e.,

$$Q_L = \{w^{-1}L : w \in \Sigma^*\} \quad \text{where} \quad w^{-1}L = \{v \in \Sigma^* : wv \in L\},$$

the transitions are $K \stackrel{a}{\rightarrow} a^{-1}K$ for $K \in Q_L$ and $a \in \Sigma$, the initial state is $L$, and a state is final iff it contains the empty word. This construction is due to Brzozowski [9], and is the basis for efficient dfa minimization algorithms. For nondeterministic finite automata (nfas) the situation is significantly more complex: a regular language may have many non-isomorphic state-minimal nfas, and generally there is no way to identify a “canonical” one among them. However, several authors have recently proposed nondeterministic acceptors that are in some sense canonical (though not necessarily state-minimal), e.g. the átomaton of Brzozowski and Tamm [8], the jiromaton<fnref n="1" /> of Denis, Lemay and Terlutte [10], and the minimal xor automaton of Vuillemin and Gama [17]. In each case, the respective nfa is formed by closing the set $Q_L$ of derivatives under certain algebraic operations and taking a minimal set of generators as states. Specifically,

1. the states of the átomaton are the atoms of the boolean algebra generated by $Q_L$, obtained by closing $Q_L$ under finite union, finite intersection and complement;

<footnote n="1">¹ Institut für Theoretische Informatik</footnote>

<footnote>Technische Universität Braunschweig, Germany</footnote>

<footnote n="2">² Lehrstuhl für Theoretische Informatik</footnote>

<footnote>Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany</footnote>

<footnote n="1">¹ In [10] the authors called their acceptor “canonical residual finite state automaton”. We propose the shorter “jiromaton” because this is analogous to the átomaton terminology.</footnote>
2. the states of the jiromaton are the join-irreducibles of the join-semilattice generated by $Q_L$, obtained by closing $Q_L$ under finite union;

3. the states of the minimal xor automaton form a basis for the $\mathbb{Z}_2$-vector space generated by $Q_L$, obtained by closing $Q_L$ under symmetric difference.

In this paper we demonstrate that all these canonical nfas arise from a coalgebraic construction. For this purpose we first consider deterministic automata interpreted in a locally finite variety $\mathcal{V}$, where locally finite means that finitely generated algebras are finite. A deterministic automaton is a coalgebra for the functor $T_\Sigma = 2 \times \text{Id}^\Sigma$ on $\mathcal{V}$, for a fixed two-element algebra $\mathbb{2}$. In Section 2 we describe a Brzozowski-like construction that yields, for every regular language, the minimal deterministic finite $\mathcal{V}$-automaton accepting it. Next, for certain varieties $\mathcal{V}$ of interest, we derive an equivalence between the full subcategory $\mathcal{V}_f$ of finite algebras and a suitable category $\bar{\mathcal{V}}$ of finite structured sets, whose morphisms are relations preserving the structure. In each case, the objects of $\bar{\mathcal{V}}$ are “small” representations of their counterparts in $\mathcal{V}_f$, based on specific generators of algebras in $\mathcal{V}_f$. The equivalence $\mathcal{V}_f \cong \bar{\mathcal{V}}$ then induces an equivalence between deterministic finite $\mathcal{V}$-automata and coalgebras in $\bar{\mathcal{V}}$ which are nondeterministic automata.

This suggests a two-step procedure for constructing a canonical nfa for a given regular language $L$: (i) form $L$'s minimal deterministic $\mathcal{V}$-automaton, and (ii) use the equivalence of $\mathcal{V}_f$ and $\bar{\mathcal{V}}$ to obtain an equivalent nfa. Applying this to different varieties $\mathcal{V}$ yields the three canonical nfas mentioned above. For the átomaton one takes $\mathcal{V} = \text{BA}$ (boolean algebras). Then the minimal deterministic BA-automaton for $L$ arises from the minimal dfa by closing its states $Q_L$ under boolean operations. The category $\bar{\mathcal{V}} = \bar{\text{BA}}$ is based on Stone duality: $\bar{\text{BA}}$ is the dual of the category of finite sets, so it has objects all finite sets, as morphisms all converse-functional relations, and the equivalence functor $\text{BA}_f \to \bar{\text{BA}}$ maps each finite boolean algebra to the set of its atoms. This equivalence applied to the minimal deterministic BA-automaton for $L$ gives precisely $L$'s átomaton. Similarly, by taking $\mathcal{V} = \text{join-semilattices}$ and $\mathcal{V} = \text{vector spaces over } \mathbb{Z}_2$ and describing a suitable equivalence $\mathcal{V}_f \cong \bar{\mathcal{V}}$, we recover the jiromaton and the minimal xor automaton, respectively. Finally, for $\mathcal{V}$ = distributive lattices we get a new canonical nfa called the *distromaton*, which bears a close resemblance to the universal automaton [14].

**Example 1.1.** Consider the language $L = (a+b)^*b(a+b)^n$ where $n \in \omega$. Its minimal dfa has $\ge 2^n$ states and its (A) átomaton, (X) minimal xor automaton, (J) jiromaton and (D) distromaton are the nfas with $\le n+3$ states depicted below (see Section 3.3).

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>
The minimal xor automaton accepts *L* by Z₂-weighted acceptance, which is the usual acceptance in this case. It is a state-minimal nfa, as is the jiromaton. The state-minimality of the latter follows from a general result (Theorem 4.4).

Generally, the sizes of the four canonical nfas and the minimal dfa are related as follows:

(a) all the four canonical nfas can have exponentially fewer states than the minimal dfa;

(b) the minimal xor automaton and jiromaton have no more states than the minimal dfa;

(c) the átomaton and distromaton have the same number of states, although their structure can be very different.

In Section 4 we characterize the átomaton, jiromaton, minimal xor automaton and distromaton by a minimality property. This provides an explanation of the canonicity of these acceptors that is missing in the original papers. We then use this additional structure to identify conditions on regular languages that guarantee the *state-minimality* of the canonical nfas. That is, there exists a natural class of languages where *canonical* state-minimal nfas exist and can be computed relatively easily.

*Related work.* Our paper unifies the constructions of canonical nfas given in [8, 10, 17] from a coalgebraic perspective. Previously, several authors have studied coalgebraic methods for constructing minimal and canonical representatives of machines, including Adámek, Bonchi, Hülsbusch, König, Milius and Silva [1], Adámek, Milius, Moss and Sousa [2] and Bezhanishvili, Kupke and Panangaden [4]. Only the first of these three papers, however, treats the case of nondeterministic automata explicitly – in particular, there the átomaton is recovered as an instance of projecting coalgebras in a Kleisli category into a reflective subcategory. This approach is methodologically rather different from the present paper where a categorical equivalence (rather than a reflection) is the basis for the construction of nfas.

In [8] the authors propose a surprisingly simple algorithm for constructing the átomaton of a language *L*: take the minimal dfa for *L*'s reversed language, and reverse this dfa. These steps form a fragment of a classical dfa minimization algorithm due to Brzozowski. Recently Bonchi, Bonsangue, Rutten and Silva [6] gave a (co-)algebraic explanation of this procedure, based on the classical duality between observability and reachability of dfas. We provide another explanation in Section 3.3.

A coalgebraic treatment of linear weighted automata (of which xor automata considered here are a special case) appears in [5]; this paper also provides a procedures for computing the minimal linear weighted automaton.

Finally, our work is somewhat related to work on coalgebraic trace semantics [11]. However, while that work considers coalgebras whose carrier is a free algebra of a variety we consider coalgebras whose carriers are arbitrary algebras from the given variety; this means we consider coalgebras over an Eilenberg-Moore category (cf. [7, 12]).

## 2 Deterministic Automata

We start with recalling the concept of a finite automaton. Throughout this paper let us fix a finite input alphabet $\Sigma$.
**Definition 2.1.** (a) A nondeterministic finite automaton (nfa) is a triple $N = (Z, R_a, F)$ consisting of a finite set $Z$ of states, transition relations $R_a \subseteq Z \times Z$ for each $a \in \Sigma$ and final states $F \subseteq Z$. Morphisms of nfas are the usual bisimulations, i.e., relations that preserve and reflect transitions and final states. If $N$ is equipped with initial states $I \subseteq Z$ we write $N = (Z, R_a, F, I)$. In this case, $N$ accepts a language $L_N(I) \subseteq \Sigma^*$ in the usual way.

(b) A deterministic finite automaton (dfa) is an nfa with a single initial state whose transition relations are functions.

Although the goal of our paper is constructing canonical nondeterministic automata, we first consider deterministic ones from a coalgebraic perspective. Given an endofunctor $T: \mathcal{V} \to \mathcal{V}$ of a category $\mathcal{V}$, a T-coalgebra $(Q, \gamma)$ consists of a $\mathcal{V}$-object $Q$ and a $\mathcal{V}$-morphism $\gamma: Q \to TQ$. A coalgebra homomorphism into another coalgebra $\gamma': Q' \to TQ'$ is a $\mathcal{V}$-morphism $h: Q \to Q'$ such that $Th \circ \gamma = \gamma' \circ h$. This defines a category Coalg($T$). If it exists, its terminal object $\nu T$ is called the final T-coalgebra.

**Assumption 2.2.** From now on $\mathcal{V}$ is a locally finite variety with a specified two-element algebra $\mathbb{2} = \{0, 1\}$. That is, $\mathcal{V}$ is the category of algebras for some finitary signature and equations, its morphisms being the usual algebra homomorphisms. That $\mathcal{V}$ is locally finite means its finitely generated algebras are finite, equivalently its finitely generated free algebras are finite.

**Example 2.3.** (a) The category Set\_ of pointed sets is a locally finite variety, given by the signature with a constant 0 and no equations. Let $\mathbb{2} \in \text{Set\_}$ have point 0.

(b) The category BA of boolean algebras is a locally finite variety: a boolean algebra on $n$ generators has at most $2^{2^n}$ elements. $\mathbb{2}$ is the 2-chain $0 < 1$.

(c) The category Vect($\mathbb{Z}_2$) of vector spaces over the binary field $\mathbb{Z}_2$ is a locally finite variety. Here $\mathbb{2} = \mathbb{Z}_2$ as a one-dimensional vector space.

(d) The category JSL of (join-)semilattices with a least element 0 is locally finite: the finite powerset $P_f X$ is the free semilattice on $X$, so a semilattice on $n$ generators has at most $2^n$ elements. $\mathbb{2}$ is the 2-chain $0 < 1$.

(e) The category DL of distributive lattices with a least and largest element $\perp$ and $\uparrow$ is locally finite. Again, $\mathbb{2}$ is the 2-chain $0 < 1$.

**Definition 2.4.** If $Q$ is a join-semilattice then $q \in Q$ is join-irreducible if $(i) \ q \neq 0$ and $(ii) \ q = r \lor r'$ implies $q = r$ or $q = r'$. The set of join-irreducibles is written $J(Q) \subseteq Q$.

**Definition 2.5.** A T-coalgebra $(Q', \gamma')$ is a subcoalgebra of $(Q, \gamma)$ if there exists an injective coalgebra homomorphism $m: (Q', \gamma') \to (Q, \gamma)$, and a quotient coalgebra of $(Q, \gamma)$ if there exists a surjective coalgebra homomorphism $e: (Q, \gamma) \to (Q', \gamma')$.

**Definition 2.6.** A deterministic $\mathcal{V}$-automaton is a coalgebra for the functor

$$T_{\Sigma}: \mathcal{V} \to \mathcal{V}, \quad T_{\Sigma} = \mathbb{2} \times \text{Id}^{\Sigma} = \mathbb{2} \times \text{Id} \times \dots \times \text{Id}.$$

**Remark 2.7.** Hence, by the universal property of the product, a deterministic $\mathcal{V}$-automaton $Q \to \mathbb{2} \times Q^\Sigma$ is given by an algebra $Q$ of states, a $\mathcal{V}$-morphism $\gamma_e: Q \to \mathbb{2}$ defining final states via $\gamma_e^{-1}(\{1\})$ and, for each $a \in \Sigma$, a $\mathcal{V}$-morphism $\gamma_a: Q \to Q$ representing the $a$-transitions. In particular, deterministic Set-automata are precisely the classical (possibly infinite) deterministic automata without initial states, shortly da's.
*Example 2.8.* (a) A deterministic Set$_*$-automaton is a da whose carrier is a pointed set and whose point is a non-final sink state; these are the partial automata of [16].

(b) A deterministic BA-automaton is a da with a boolean algebra structure on the states $Q$ such that (i) the final states form an ultrafilter, (ii) $q \stackrel{a}{\rightarrow} q'$ and $r \stackrel{a}{\rightarrow} r'$ implies $q \vee r \stackrel{a}{\rightarrow} q' \vee r'$ and $\neg q \stackrel{a}{\rightarrow} \neg q'$, and (iii) $\perp$ is a non-final sink state.

(c) A deterministic Vect($\mathbb{Z}_2$)-automaton is a da with a $\mathbb{Z}_2$-vector space structure on the states $Q$ such that (i) the final states $F \subseteq Q$ satisfy $0 \notin F$ and also $q+r \in F$ iff either $q \in F$ or $r \in F$ but not both, (ii) $q \stackrel{a}{\rightarrow} q'$ and $r \stackrel{a}{\rightarrow} r'$ implies $q+q \stackrel{a}{\rightarrow} r+r'$, and (iii) $0$ is a non-final sink state.

(d) A deterministic JSL-automaton is a da with a join-semilattice structure on the states $Q$ such that (i) the final states form a prime filter, (ii) $q \stackrel{a}{\rightarrow} q'$ and $r \stackrel{a}{\rightarrow} r'$ implies $q+r \stackrel{a}{\rightarrow} q'+r'$, and (iii) $0$ is a non-final sink state. Recall that a *prime filter* is an upwards closed $F \subseteq Q$ where $0 \notin F$ and $q+q' \in F$ iff $q \in F$ or $q' \in F$.

(e) A deterministic DL-automaton is a da with a distributive lattice structure on the states $Q$ such that (i) the final states form an prime filter, (ii) $q \stackrel{a}{\rightarrow} q'$ and $r \stackrel{a}{\rightarrow} r'$ implies $q \vee r \stackrel{a}{\rightarrow} q' \vee r'$ and $q \wedge r \stackrel{a}{\rightarrow} q' \wedge r'$, and (iii) $\perp$ is a non-final sink state and $\top$ is a final one.

**Remark 2.9.** For finitary endofunctors $T$, Milius [15] introduced the concept of a locally finitely presentable coalgebra: it is a filtered colimit of coalgebras carried by finitely presentable objects. In the present context the finitely presentable objects are precisely the finite algebras in $\mathcal{V}$, so we speak about locally finite coalgebras. A $T_{\Sigma}$-coalgebra is locally finite iff from each state only finitely many states are reachable by transitions.

*Remark 2.10.* 1. The final $T_{\Sigma}$-coalgebra in Set is $\nu T_{\Sigma} = \mathcal{P}\Sigma^*$, the set of formal languages over $\Sigma$, with transitions $L \stackrel{a}{\rightarrow} a^{-1}L$ for $a \in \Sigma$ and final states precisely those languages containing $\varepsilon$. Importantly, $\nu T_{\Sigma}$ arises as the $\omega^{op}$-limit of $T_{\Sigma}$'s terminal sequence $(T_{\Sigma}^{n_1})_{n<\omega}$, see [3]. Since for any variety $\mathcal{V}$ the forgetful functor from $\mathcal{V}$ to Set creates limits, the final $T_{\Sigma}$-coalgebra $\nu T_{\Sigma}$ in $\mathcal{V}$ exists and lifts the one in Set, so $\nu T_{\Sigma}$ has underlying set $\mathcal{P}\Sigma^*$ and the transitions and final states are as above.

2. The final locally finite $T_{\Sigma}$-coalgebra is denoted by $\rho T_{\Sigma}$. In $\mathcal{V}$ = Set this is the subda of $\nu T_{\Sigma} = \mathcal{P}\Sigma^*$ given by the set of all regular languages over $\Sigma$. This generalizes to any locally finite variety $\mathcal{V}$: $\rho T_{\Sigma}$ is a subcoalgebra of $\nu T_{\Sigma}$ and its underlying set is the set of regular languages.

*Example 2.11.* (a) In Set$_*$ the carrier of the final coalgebra $\nu T_{\Sigma}$ has the constant $\emptyset$, which $\rho T_{\Sigma}$ inherits.

(b) In BA, $\nu T_{\Sigma}$ has the usual set-theoretic boolean algebra structure. The principal filter $\uparrow\varepsilon$ is an ultrafilter and the transition maps $L \mapsto a^{-1}L$ are boolean morphisms.

(c) In Vect($\mathbb{Z}_2$) the vector space structure on $\nu T_{\Sigma}$ and $\rho T_{\Sigma}$ is given by symmetric difference and $\emptyset$ is the zero vector.

(d) In JSL the join-semilattice structure on $\nu T_{\Sigma}$ is union and $\emptyset$. The final states form a one-generated upset $\uparrow\varepsilon$ which is a prime filter because the language $\{\varepsilon\}$ is join-irreducible in $\nu T_{\Sigma}$. The transitions maps are join-semilattice morphisms.

(e) In DL we have the usual set-theoretic lattice structure on $\nu T_{\Sigma}$. The final states form a prime filter and the transition maps are lattice morphisms.
**Notation 2.12.** Let $(Q, \gamma)$ be a locally finite $T_{\Sigma}$-coalgebra. The unique coalgebra homomorphism into $\rho T_{\Sigma}$ is written:

$$ \mathcal{L}_{\gamma}: Q \to \rho T_{\Sigma}. $$

The function $\mathcal{L}_{\gamma}$ sends $q \in Q$ to the regular language $\mathcal{L}_{\gamma}(q) \subseteq \Sigma^*$ the state $q$ accepts.

**Definition 2.13.** Let $V \in \mathcal{V}$ denote the free algebra on one generator $g$. Then a pointed $T_{\Sigma}$-coalgebra $(Q, \gamma, q_0)$ is a $T_{\Sigma}$-coalgebra $(Q, \gamma)$ with a morphism $q_0: V \to Q$. The latter may be viewed as the initial state $q_0(g) \in Q$. The language accepted by $(Q, \gamma, q_0)$ is $\mathcal{L}_{\gamma}(q_0)$. We say that $(Q, \gamma, q_0)$ is

1. reachable if it is generated by $q_0$, i.e., no proper subcoalgebra contains $q_0$;

2. simple if it has no proper quotients, i.e., for every quotient coalgebra $e: (Q, \gamma) \twoheadrightarrow (Q', \gamma')$ the map $e$ is bijective;

3. minimal if it is reachable and simple.

**Lemma 2.14.** $(Q, \gamma, q_0)$ is reachable iff the algebra $Q$ is generated by those $q \in Q$ reachable from $q_0$ by transitions. It is simple iff $\mathcal{L}_{\gamma}$ is injective.

Broozowski's construction of the minimal dfa for a regular language (see Introduction) generalizes to deterministic $\mathcal{V}$-automata as follows:

**Construction 2.15.** For any regular language $L \subseteq \Sigma^*$ let $A_{\mathcal{V}}^L$ be the pointed $T_{\Sigma}$-coalgebra $(Q_L, \gamma, L)$ where:

1. $Q_L$ is the subalgebra of $\nu T_{\Sigma} = \mathcal{P}\Sigma^*$ generated by all derivatives $w^{-1}L$ ($w \in \Sigma^*$).

2. The transitions are $K \xrightarrow{a} a^{-1}K$ for $a \in \Sigma$ and $K \in Q_L$.

3. $K \in Q_L$ is final iff $\varepsilon \in K$.

**Lemma 2.16.** For every regular language $L \subseteq \Sigma^*$, $A_{\mathcal{V}}^L$ is a well-defined finite pointed $T_{\Sigma}$-coalgebra.

*Proof.* $L$ is regular so it has only finitely many distinct derivatives $w^{-1}L$. Hence $Q_L$ is a finite algebra because $\mathcal{V}$ is a locally finite variety. It remains to show that $\gamma_a: Q_L \to Q_L$ and $\gamma_{\varepsilon}: Q_L \to \mathcal{D}$ as specified in points 2. and 3. are well-defined $\mathcal{V}$-morphisms. Recall the final locally finite $T_{\Sigma}$-coalgebra $(\rho T_{\Sigma}, \gamma_{\rho})$. Then

$$ \gamma_{\varepsilon} = Q_L \hookrightarrow \rho T_{\Sigma} \xrightarrow{(\gamma_{\rho})_{\varepsilon}} \mathcal{D} $$

is a $\mathcal{V}$-morphism since $\rho T_{\Sigma}$ is a lifting of the da of regular languages, see Remark 2.10. Furthermore $(\gamma_{\rho})_a: \rho T_{\Sigma} \to \rho T_{\Sigma}$ is defined $(\gamma_{\rho})_a(K) = a^{-1}K$ i.e. the derivative $a^{-1}(-)$ preserves the algebraic operations. Thus $Q_L$ is closed under derivatives, so $\gamma_a$ is a well-defined algebra morphism. $\square$

*Example 2.17.* (a) In $\text{Set}_*$, we have $Q_L = \{\emptyset\} \cup \{w^{-1}L : w \in \Sigma^*\}$.

(b) In BA, $Q_L$ is the closure of $\{\emptyset\} \cup \{w^{-1}L : w \in \Sigma^*\}$ under union and complement.

(c) In $\text{Vect}(\mathbb{Z}_2)$, $Q_L$ is the closure of $\{w^{-1}L : w \in \Sigma^*\}$ under symmetric difference.

(d) In JSL, $Q_L$ is the closure of $\{\emptyset\} \cup \{w^{-1}L : w \in \Sigma^*\}$ under union.
(e) In DL, $Q_L$ is the closure of $\{\emptyset, \Sigma^*\} \cup \{w^{-1}L : w \in \Sigma^*\}$ under union and intersection.

**Remark 2.18.** The category Coalg($T_\Sigma$) of $T_\Sigma$-coalgebras has a factorization system (surjective homomorphism, injective homomorphism) lifting the usual factorization system (surjective, injective) = (regular epi, mono) in $\mathcal{V}$.

**Construction 2.19 (see [2]).** These factorizations give a two-step minimization of any finite pointed $T_\Sigma$-coalgebra $(Q, \gamma, q_0)$:

1. Construct the reachable subcoalgebra $(R, \delta) \hookrightarrow (Q, \gamma)$ generated by $q_0$.

2. Factorize the unique $T_\Sigma$-coalgebra homomorphism $\mathcal{L}_\delta : (R, \delta) \to (\rho T_\Sigma, \gamma_\rho)$ as:

$$ (R, \delta) \xrightarrow{s} (R', \delta') \xrightarrow{m} (\rho T_\Sigma, \gamma_\rho) $$

Then $(R', \delta', s(q_0))$ is minimal.

**Theorem 2.20.** Let $L \subseteq \Sigma^*$ be a regular language. Then $A_\mathcal{V}^L$ is (up to isomorphism) the unique minimal pointed $\mathcal{V}$-automaton accepting $L$. It arises from any pointed finite $\mathcal{V}$-automaton $(Q, \gamma, q_0)$ accepting $L$ by Construction 2.19.

*Proof.* Viewed as a da, $A_\mathcal{V}^L$ is a subautomaton of the da $\rho T_\Sigma$ of regular languages. Then the state $L$ accepts $L$. It is reachable because every state is a $\mathcal{V}$-algebraic combination of those states reachable from $L$ by transitions i.e. $L$'s derivatives. It is simple because different states accept different languages, so it is minimal.

Now let $(Q, \gamma, q_0)$ be any pointed $T_\Sigma$-coalgebra accepting $L$ and $(R, \delta, q_0)$ its reachable subautomaton, so every $q' \in R$ arises as a $\mathcal{V}$-algebraic combination of those states reachable from $q_0$ by transitions. Now $\mathcal{L}_\delta : R \to \rho T_\Sigma$ is an automata morphism, so the languages of states reachable from $q_0$ are precisely the derivatives of $L$. Since $\mathcal{L}_\delta$ is an algebra morphism its image is $Q_L$. $\square$

# 3 From Deterministic to Nondeterministic Automata

We now know that each regular language $L$ has many canonical deterministic acceptors: one for each locally finite variety $\mathcal{V}$ containing a two-element algebra $\mathcal{D}$. However this canonical acceptor $A_\mathcal{V}^L$ is generally larger than the minimal dfa in Set because one has to close under the $\mathcal{V}$-algebraic operations on the regular languages. In this section we will show how these larger deterministic machines induce smaller nondeterministic ones. Let us outline our approach:

1. We restrict attention to finite da's in $\mathcal{V}$, i.e., $T_\Sigma$-coalgebras with finite carrier.

2. For each of our varieties $\mathcal{V}$ of interest, we describe an equivalence $\mathcal{G}$ of categories between the finite algebras $\mathcal{V}_f$ and another category $\bar{\mathcal{V}}$ where (i) $\bar{\mathcal{V}}$'s objects are “small” representations of their counterparts in $\mathcal{V}_f$, and (ii) $\bar{\mathcal{V}}$'s morphisms are relations, not functions (see Lemmas 3.4, 3.8 and 3.10).

3. From $\mathcal{G}$ we derive equivalences $\mathcal{G}$ and $\mathcal{G}_*$ between (pointed) deterministic finite $\mathcal{V}$-automata and (pointed) coalgebras in $\bar{\mathcal{V}}$ which are *nondeterministic* finite automata, see Lemma 3.17.

4. Applying this equivalence to the minimal deterministic $\mathcal{V}$-automaton $A_\mathcal{V}^L$ gives a canonical nondeterministic acceptor for $L$. This is illustrated in Section 3.3.
## 3.1 The Equivalence between $\mathcal{V}_f$ and $\bar{\mathcal{V}}$

For each of our varieties $\mathcal{V}$ of interest there is a well-known description of the dual category of $\mathcal{V}_f$: we have Stone duality (BA$_f \cong \text{Set}_f^{\text{op}}$), Priestley duality (DL$_f \cong \text{Poset}_f^{\text{op}}$), where Poset$_f$ is the category of finite posets and monotone functions, and the self-dualities JSL$_f \cong JSL_f^{\text{op}}$ and Vect$_f(Z_2) \cong \text{Vect}_f(Z_2)^{\text{op}}$. We now describe each of these dually equivalent categories as a category $\bar{\mathcal{V}}$ of finite structured sets and relations. The idea is to represent the finite algebras in $\mathcal{V}$ in terms of a minimal set of generators.

**Example 3.1.** (a) For any $Q \in \text{Set}_*$ the subset $Q \setminus \{0\}$ generates $Q$; that means that we can always drop one element.

(b) Any finite boolean algebra $Q \in \text{BA}_f$ is generated by its atoms $\text{At}(Q)$, these being the join-irreducible elements.

(c) Any finite join-semilattice $Q \in \text{JSL}_f$ is generated by its join-irreducibles $J(Q)$.

(d) A finite dimensional vector space $Q \in \text{Vect}_f(Z_2)$ is generated by any basis $B \subseteq Q$, although there is no canonical choice of a basis.

(e) Any finite distributive lattice $Q \in \text{DL}_f$ is generated by its join-irreducibles $J(Q)$.

In the case of $\text{Set}_*$, BA$_f$ and $\text{Vect}_f(Z_2)$ we can replace each algebra by a set of generators and each algebra morphism by a relation between these generators.

**Definition 3.2.** Let $\text{Set}_*$ be the category $\text{Par}_f$ of finite sets and partial functions. $\overline{\text{BA}}$ is obtained from the category $\text{Rel}_f$ of finite sets and relations by restricting to relations whose converse is a function. Finally $\overline{\text{Vect}}(Z_2)$ has the same objects and morphisms as $\text{Rel}_f$ although now the composition of $R_1 \subseteq X \times Y$ and $R_2 \subseteq Y \times Z$ is defined by

$$R_2 \bullet R_1 := \{(x, z) : |\{y : (x, y) \in R_1, (y, z) \in R_2\}| \text{ is odd.}\}$$

**Notation 3.3.** Given a basis $GQ$ of a vector space $Q$, for each basis vector $z \in GQ$ denote by $\pi_z : Q \to \{0, 1\}$ the projection onto the $z$-coordinate.

**Lemma 3.4.** The following functors $G$ are equivalences of categories where $f : Q \to Q'$ is any $\mathcal{V}_f$-morphism:

1. $G : \text{Set}_* \to \text{Par}_f$ defined by

$$GQ = Q \setminus \{0\} \qquad Gf(z) = \begin{cases} f(z) & \text{if } f(z) \neq 0, \\ \text{undefined} & \text{otherwise.} \end{cases}$$

2. $G : \text{BA}_f \to \overline{\text{BA}}$ where $GQ = \text{At}(Q)$ is the set of atoms and $Gf = \{(z, z') \in \text{At}(Q) \times \text{At}(Q') : z' \leq_{Q'} f(z)\}$.

3. $G : \text{Vect}_f(Z_2) \to \overline{\text{Vect}}(Z_2)$ where $GQ$ chooses a basis and $Gf = \{(z, z') \in GQ \times GQ' : \pi_{z'} \circ f(z) = 1\}$.

Finite join-semilattices are represented using closure spaces:
**Definition 3.5.** For any set $X$ a closure operator (shortly, a closure) on $X$ is a function $\mathrm{cl}_X : \mathcal{P}X \to \mathcal{P}X$ such that for all $S, S' \subseteq X$:

$$ \frac{S \subseteq S'}{\mathrm{cl}_X(S) \subseteq \mathrm{cl}_X(S')} , \quad \mathrm{cl}_X(S) \supseteq S, \quad \mathrm{cl}_X \circ \mathrm{cl}_X = \mathrm{cl}_X. $$

A closure space $X = (X, \mathrm{cl}_X)$ is a set with a closure defined on it. It is finite if $X$ is finite, strict if $\mathrm{cl}_X(\emptyset) = \emptyset$, separable if $x \neq x'$ implies $\mathrm{cl}_X(x) \neq \mathrm{cl}_X(x')$, and topological if $\mathrm{cl}_X(A \cup B) = \mathrm{cl}_X(A) \cup \mathrm{cl}_X(B)$ for all $A, B \subseteq X$. A subset $S \subseteq X$ is closed if $\mathrm{cl}_X(S) = S$ and open if its complement is closed.

Finite posets are well-known to be equivalent to finite $T_0$ topological spaces, which amount to finite separable topological closures. For finite join-semilattices we instead use finite strict closures i.e. we do not require separability or preservation of unions.

**Example 3.6.** Each finite join-semilattice $Q$ has an associated finite strict closure space $GQ = (J(Q), \mathrm{cl}_{J(Q)})$ where $J(Q) \subseteq Q$ is the set of join-irreducibles and

$$ \mathrm{cl}_{J(Q)}(S) = \{j \in J(Q) : j \leq \sum_{s \in S} s\} \quad \text{for any } S \subseteq J(Q). $$

For example the closure space associated to the free join-semilattice $\mathcal{P}n$ is $(n, \mathrm{id}_{\mathcal{P}n})$, identifying $J(\mathcal{P}n)$ with $n$.

**Definition 3.7.** The category $\overline{\mathcal{JSL}}$ has as objects all finite strict closure spaces as morphisms all continuous relations. Here a relation $R \subseteq X \times Y$ between two finite strict closure spaces $X$ and $Y$ is called continuous if, for all $x \in X$ and $S \subseteq X$,

1. $R[x] \subseteq Y$ is closed, and

2. if $x \in \mathrm{cl}_X(S)$ then $R[x] \subseteq \mathrm{cl}_Y(R[S])$.

The composition of $R_1 \subseteq X \times Y$ and $R_2 \subseteq Y \times Z$ is defined by

$$ R_2 \bullet R_1 := \{(x, z) \in X \times Z : z \in \mathrm{cl}_Z(R_2 \circ R_1[x])\}, $$

and the identity morphism on $X$ is $\mathrm{id}_X = \{(x, x') \in X \times X : x' \in \mathrm{cl}_X(\{x\})\}$.

The following equivalence was derived from a similar one due to Moshier [13].

**Lemma 3.8.** The functor $G : \overline{\mathcal{JSL}}_f \to \overline{\mathcal{JSL}}$, defined on objects $Q$ as in Example 3.6 and for morphisms $f : Q \to Q'$ by

$$ Gf = \{(j, j') \in J(Q) \times J(Q') : j' \leq_Q f(j)\}, $$

is an equivalence of categories.

*Proof.* (Sketch) We describe the opposite equivalence $H : \overline{\mathcal{JSL}} \to \mathcal{JSL}_f$ and also the unit and counit. Given $X = (X, \mathrm{cl}_X)$ then $HX = \{S \subseteq X : \mathrm{cl}_X(S) = S\} \subseteq \mathcal{P}X$ is the join-semilattice of closed subsets where $0_{HX} = \emptyset$ and $S +_{HX} S' = \mathrm{cl}_X(S \cup S')$.
Given a continuous relation $R \subseteq X \times Y$ then $HR = \lambda S \cdot cl_Y(R[S]) : HX \to HY$ is the corresponding algebra morphism. The unit $\eta : \text{Id} \Rightarrow \text{HG}$ is defined

$$ \eta_Q = \lambda q \in Q.\{j \in J(Q) : j \le_Q q\}, $$

and for $X = (X, cl_X)$ the counit $\varepsilon : GH \Rightarrow \text{Id}$ is defined:

$$ \varepsilon_X = \{(K, x) \in J(HX) \times X : K \in J(HX), x \in K\}. $$

It is well-typed because $J(HX) \subseteq HX \subseteq \mathcal{P}X$.

□

**Definition 3.9.** $\overline{DL}$ has finite posets as objects and as morphisms those relations $R \subseteq P \times Q$ such that:

1. Each $R[p] \subseteq Q$ is downclosed,

2. If $p \le_P p'$ then $R[p] \subseteq R[p']$,

3. $R$ preserves all intersections of downclosed subsets.

$\text{id}_P$ is the relation $\{(p, p') \in P \times P : p' \le_P p\}$ and composition is relational composition.

**Lemma 3.10.** The functor $G : DL_f \to \overline{DL}$ where $GQ = J(Q)$ (considered as a subposet of $Q$) and for morphisms $f : Q \to Q'$

$$ Gf = \{(z, z') \in J(Q) \times J(Q') : z' \le_{Q'} f(z)\} $$

is an equivalence of categories.

*Proof.* $G$ is restriction of the equivalence $JSL_f \cong \overline{JSL}$ described above. The closure spaces associated to distributive lattices are precisely the separable topological ones, so we can replace them by finite posets. This gives the first two conditions on morphisms, where closed means downwards closed. However semilattice morphisms between distributive lattices need not preserve meets. This is captured by the third condition. □

## 3.2 From Determinism to Nondeterminism

We first restrict the endofunctor $T_\Sigma$ of Definition 2.6 to finite algebras:

$$ T_\Sigma = 2 \times \text{Id}^\Sigma : \mathcal{V}_f \to \mathcal{V}_f $$

Then for each of our five equivalences $G : \mathcal{V}_f \to \overline{\mathcal{V}}$ described in the previous section we have a corresponding functor

$$ \overline{T}_\Sigma = 1 \times \text{Id}^\Sigma : \overline{\mathcal{V}} \to \overline{\mathcal{V}} $$

where $1 = G2 \in \overline{\mathcal{V}}$. In each case $1$ has carrier $\{1\}$.

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>$\mathcal{V}$</td><td>$1$</td></tr><tr><td>$\text{Set}_*$</td><td>$2 \setminus \{0\} = \{1\}$</td></tr><tr><td>$\text{BA}$</td><td>$\text{At}(2) = \{1\}$ the unique atom</td></tr><tr><td>$\text{Vect}(\mathbb{Z}_2)$</td><td>$\{1\}$ unique basis of $2 = \mathbb{Z}_2$</td></tr><tr><td>$\text{JSL}$</td><td>$(J(2), \text{cl})$ where $J(2) = \{1\}$, $\text{cl} = \text{id}_{\mathcal{P}\{1\}}$</td></tr><tr><td>$\text{DL}$</td><td>$J(2) = \{1\}$ a discrete poset</td></tr></tbody></table>
**Lemma 3.11.** There is an equivalence $\mathcal{G} : \text{Coalg}(T_\Sigma) \to \text{Coalg}(\bar{T}_\Sigma)$ defined by

$\mathcal{G}(Q, \gamma) = (GQ, \gamma')$ on objects and $\mathcal{G}f = Gf$ on morphisms,

where $\gamma' : GQ \to 1 \times (GQ)^\Sigma$ is the $\bar{V}$-morphism uniquely determined by the morphisms $G\gamma_\epsilon : GQ \to 1$ and $G\gamma_a : GQ \to GQ$ for each $a \in \Sigma$.

Given a $\bar{T}_\Sigma$-coalgebra $\delta : Z \to \bar{T}_\Sigma Z = 1 \times Z^\Sigma$ we write its component maps as $\delta_\epsilon : Z \to 1$ and $\delta_a : Z \to Z$ for $a \in \Sigma$. Notice that these are *relations* rather than functions, so $\bar{T}_\Sigma$-coalgebras are *nondeterministic automata*.

**Example 3.12.** (a) When $\mathcal{V} = \text{Set}_\star$ a $\bar{T}_\Sigma$-coalgebra $\delta : X \to \bar{T}_\Sigma X$ consists of:

1. A finite set $X$.

2. A partial function $\delta_\epsilon : X \to \{1\}$ whose domain defines the final states.

3. A partial function $\delta_a : X \to X$ for each $a \in \Sigma$, defining the transitions.

Hence $\bar{T}_\Sigma$-coalgebras are *partial dfas*. The equivalence $\mathcal{G}$ assigns to each deterministic Set$_\star$-automaton $(Q, \gamma)$ the partial dfa $(Q \setminus \{0_Q\}, \delta)$ whose final states are the given ones and $q \xrightarrow{a} q'$ iff $\gamma_a(q) = q' \neq 0_Q$.

(b) When $\mathcal{V} = \text{BA}$ a $\bar{T}_\Sigma$-coalgebra $\delta : X \to \bar{T}_\Sigma X$ consists of:

1. A finite set $X$.

2. A converse-functional relation $\delta_\epsilon \subseteq X \times \{1\}$ whose domain defines a single final state.

3. Converse-functional relations $\delta_a \subseteq X \times X$ for $a \in \Sigma$.

Hence $\bar{T}_\Sigma$-coalgebras are *reverse-deterministic nfas*, i.e., reversing all transitions yields a dfa. The equivalence $\mathcal{G}$ assigns to each deterministic BA-automaton $(Q, \gamma)$ an nfa $(\text{At}(Q), \delta)$ whose states are $Q'$'s atoms. Moreover, its single final state is the unique atom generating the ultrafilter $\gamma_\epsilon^{-1}(\{1\})$ and $z \xrightarrow{a} z'$ iff $z' \le Q \gamma_a(z)$.

(c) If $\mathcal{V} = \text{Vect}(\mathbb{Z}_2)$ then a $\bar{T}_\Sigma$-coalgebra $\delta : X \to \bar{T}_\Sigma X$ consists of:

1. A finite set $X$.

2. An arbitrary relation $\delta_\epsilon \subseteq X \times \{1\}$, amounting to an arbitrary set of final states by taking the domain.

3. Arbitrary relations $\delta_a \subseteq X \times X$ for each $a \in \Sigma$.

Hence $\bar{T}_\Sigma$-coalgebras are classical nfas. The equivalence $\mathcal{G}$ assigns to a deterministic $\text{Vect}(\mathbb{Z}_2)$-automaton $(Q, \gamma)$ the nfa $(Z, \delta)$ for some chosen basis $Z \subseteq Q$. The final states are $Z \cap \gamma_\epsilon^{-1}(\{1\})$ and $z \xrightarrow{a} z'$ iff $\pi_{z'} \circ \gamma_a(z) = 1$, cf. Notation 3.3.

(d) If $\mathcal{V} = \text{JSL}$ then a $\bar{T}_\Sigma$-coalgebra $\delta : Z \to \bar{T}_\Sigma Z$ consists of:

1. A finite strict closure space $Z = (Z, \text{cl}_Z)$.

2. A continuous relation $\delta_\epsilon \subseteq Z \times \{1\}$, equivalently $\delta_\epsilon$'s domain $F \subseteq Z$ is an open set of final states.

3. Continuous relations $\delta_a \subseteq Z \times Z$.

We call $\bar{T}_\Sigma$-coalgebras *nondeterministic closure automata*. The equivalence $\mathcal{G}$ assigns to each deterministic JSL-automaton $(Q, \gamma)$ the nondeterministic closure automaton $((J(Q), \text{cl}_Q), \delta)$ whose states are $Q$'s join-irreducibles. The open set of final states is $J(Q) \cap \gamma_\epsilon^{-1}(\{1\})$ and $z \xrightarrow{a} z'$ iff $z' \le Q \gamma_a(z)$.

Note that every nfa can be turned into a nondeterministic closure automaton by endowing the states with the identity closure, so classical nfas form a proper subclass.

(e) If $\mathcal{V} = \text{DL}$ then a $\bar{T}_\Sigma$-coalgebra $\delta : P \to \bar{T}_\Sigma P$ consists of:
1. A finite poset $P$.

2. A non-empty relation $\delta_{\varepsilon} \subseteq P \times \{1\}$ whose domain is a filter (i.e., a down-directed upset), these being the final states.

3. Transition relations $\delta_a \subseteq P \times P$ such that:

(i) $\delta_a[p]$ is downclosed for each $p \in P$.

(ii) $p \leq_P q$ implies $\delta_a[p] \subseteq \delta_a[q]$.

(iii) $\delta_a[\bigcap_I A_i] = \bigcap_I \delta_a[A_i]$ for downclosed $A_i$.

Note that reverse-deterministic nfas are the special case where $P$ is discrete. An important non-discrete example is the universal automaton [14], we recall it after Corollary 3.21.

The equivalence $\mathcal{G}$ assigns to each deterministic DL-automaton $(Q, \gamma)$ the $\overline{T}_{\Sigma}$-coalgebra $(J(Q), \delta)$ where $J(Q)$ is a subposet of $Q$. The final states form the upwards closed set $J(Q) \cap \gamma_{\varepsilon}^{-1}(1)$ and $z \xrightarrow{a} z'$ iff $z' \leq_Q \gamma_a(z)$.

**Remark 3.13.** A morphism $f : (Z, \delta) \to (Z', \delta')$ of $\overline{T}_{\Sigma}$-coalgebras is, by definition, a $\overline{\mathcal{V}}$-morphism $f : Z \to Z'$ satisfying $\overline{T}_{\Sigma}f \circ \delta = \delta' \circ f$, or equivalently:

$$ \delta_{\varepsilon} = \delta'_{\varepsilon} \circ f, \quad \delta'_{a} \circ f = f \circ \delta_{a} \quad (a \in \Sigma). $$

For $\mathcal{V} = \text{Set}_*$, BA and DL, these morphisms are those relations (from $\overline{\mathcal{V}}$) which (i) reflect and preserve transitions and (ii) have $z \in Z$ final iff some $z' \in f[z]$ is final. The cases $\mathcal{V} = \text{JSL}$, $\text{Vect}(\mathbb{Z}_2)$ are different because composition in $\overline{\mathcal{V}}$ is not relational.

## 3.3 Canonical Nondeterministic Automata

So far we have seen equivalences between deterministic and nondeterministic automata without initial states. Next, for each of our five running examples $\mathcal{V} = \text{Set}_*$, BA, $\text{Vect}(\mathbb{Z}_2)$, JSL, DL we will extend $\mathcal{G} : \text{Coalg}(T_{\Sigma}) \to \text{Coalg}(\overline{T}_{\Sigma})$ to an equivalence of pointed coalgebras.

**Definition 3.14.** Coalg$_*(T_{\Sigma})$ is the category whose objects are the pointed $T_{\Sigma}$-coalgebras and whose morphisms $f : (Q, \gamma, q_0) \to (Q', \gamma', q'_0)$ are those $T_{\Sigma}$-coalgebra homomorphisms $f : (Q, \gamma) \to (Q', \gamma')$ preserving initial states, i.e., $f \circ q_0 = q'_0$.

Using the equivalence $G : \mathcal{V}_f \to \overline{\mathcal{V}}$, a pointed $\overline{T}_{\Sigma}$-coalgebra is a $\overline{T}_{\Sigma}$-coalgebra $(Z, \delta)$ equipped with a $\overline{\mathcal{V}}$-morphism $i : GV \to Z$. And pointed $\overline{T}_{\Sigma}$-coalgebra homomorphisms are those $\overline{T}_{\Sigma}$-coalgebra homomorphisms $f$ from $(Z, \delta)$ to $(Z', \delta')$ such that $f \circ i = i'$. Just as a morphism $q_0 : V \to Q$ corresponds to an initial state $q_0(g)$, it turns out that a morphism $i : GV \to Z$ corresponds to a set of initial states $I = i[g] \subseteq Z$, as one would expect for nfas.

**Example 3.15.** For each $\mathcal{V}$ we describe the possible sets of initial states $I \subseteq Z$ for a $\overline{T}_{\Sigma}$-coalgebra $(Z, \delta)$.

(a) If $\mathcal{V} = \text{Set}_*$ then $V = \{0, g\}$ and $GV = \{g\}$. Partial functions $i : \{g\} \to Z$ are determined by their codomain $I = i[g]$. Then $I$ is either empty or any singleton subset.
(b) If $V = BA$ then $V = \{\perp, g, \neg g, \top\}$ and $GV = \{g, \neg g\}$. Given $i \subseteq \{g, \neg g\} \times Z$ then $i[g], i[\neg g]$ partition $Z$ so $i$ is determined by $I = i[g]$. Then $I$ is any subset of $Z$.

(c) If $V = \text{Vect}(\mathbb{Z}_2)$ then $V = \{0, g\}$ and $GV = \{g\}$, so the arbitrary relation $i \subseteq \{g\} \times Z$ is determined by its codomain $I = i[g]$. Then $I$ is any subset of $Z$.

(d) If $V = \text{JSL}$ then $V = \{0, g\}$ and $GV = \{g\}$ with closure $id_{\mathcal{P}\{g\}}$. The relation $i \subseteq \{g\} \times Z$ is determined by $I = i[g]$. By continuity $I \subseteq Z$ is any closed subset.

(e) If $V = \text{DL}$ then $V = \{\perp, g, \top\}$ is a 3-chain and $GV = \{g, \top\}$ a 2-chain. Given $i \subseteq \{g, \top\} \times Z$ then $i[g] \subseteq i[\top]$ and $i[\{g, \top\}] = Z$ implies $i[\top] = Z$, so $i$ is determined by $I = i[g]$. Then $I$ is any downclosed subset of $Z$.

By reinterpreting point preservation relative to $I$ we can finally define the category of pointed $\overline{T}_{\Sigma}$-coalgebras.

**Definition 3.16.** For each of our five running examples, $\text{Coalg}_*(\overline{T}_{\Sigma})$'s objects are triples $(Z, \delta, I)$ where $(Z, \delta)$ is a $\overline{T}_{\Sigma}$-coalgebra and $I \subseteq Z$ is restricted as in Example 3.15. The pointed $\overline{T}_{\Sigma}$-coalgebra homomorphisms $f : (Z, \delta, I) \to (Z', \delta', I')$ are $\overline{T}_{\Sigma}$-coalgebra homomorphisms $f : (Z, \delta) \to (Z', \delta')$ such that:

1. If $V = \text{Set}_*$, BA or DL then $I' = f[I]$.

2. If $V = \text{JSL}$ then $I'$ is the closure of $f[I]$.

3. If $V = \text{Vect}(\mathbb{Z}_2)$ then $I' = \{z' \in Z' : |I \cap \tilde{f}[z']| \text{ is odd}\}$.

where $\tilde{f} \subseteq Z' \times Z$ is the converse relation.

**Lemma 3.17.** There is an equivalence of pointed coalgebras $\mathcal{G}_* : \text{Coalg}_*(T_{\Sigma}) \to \text{Coalg}_*(\overline{T}_{\Sigma})$ defined by

$$ \mathcal{G}_*(Q, \gamma, q_0) = (\mathcal{G}(Q, \gamma), I) \qquad \mathcal{G}_*f = Gf $$

where $I = Gq_0[g] \subseteq GQ$.

Let us spell out the equivalence $\mathcal{G}_*$ for each of our varieties $V$. For the rest of this section fix a $T_{\Sigma}$-coalgebra $A = (Q, \gamma, q_0)$ and a regular language $L \subseteq \Sigma^*$. We give an explicit description of the nfa $G_*A$ and, in particular, of the canonical nfa for $L$ obtained by applying $\mathcal{G}_*$ to $A^L$ from Construction 2.15.

(a) **The Minimal Partial Dfa.** If $V = \text{Set}_*$ then $\mathcal{G}_*A$ is the partial dfa $(Q \setminus \{0_Q\}, \delta, I)$ that arises from $A$ by deleting the state $0_Q$ along with all in- and outgoing transitions. Hence the initial states are $I = \{q_0\}$ if $q_0 \neq 0_Q$ and $I = \emptyset$ if $q_0 = 0_Q$. Clearly $\mathcal{G}_*A$ (viewed as an nfa) accepts $A$'s language.

In particular, $\mathcal{G}_*(A^L_{\text{Set}_*})$ is the minimal partial dfa of $L$. It has states

$$ Q_L = \{w^{-1}L : w \in \Sigma^*\} \setminus \{\emptyset\}, $$

transitions $K \xrightarrow{a} a^{-1}K$ whenever $a^{-1}K \neq \emptyset$, and a state is final iff it contains $\varepsilon$. The initial states are $\{L\}$ if $L \neq \emptyset$ and $\emptyset$ otherwise. Hence the minimal partial dfa is the trim part of $L$'s minimal dfa (obtained by deleting its sink state, if it exists).
(b) **The Átomaton.** If $\mathcal{V} = \text{BA}$ then $\mathcal{G}_*A$ is the nfa $(\text{At}(Q), \delta, I)$ with initial states $I = \{q \in \text{At}(Q) : q \leq_q q_0\}$. It accepts $A$'s language. In particular, $\mathcal{G}_*(A_{\text{BA}}^L)$ is called the átomaton of $L$, see [8]. Its states

$$Q_L = \text{At}(\langle\{w^{-1}L : w \in \Sigma^*\}\rangle_{\nu_{T\Sigma}})$$

are the atoms of the finite boolean subalgebra of $\mathcal{P}\Sigma^*$ generated by $L$'s derivatives. An atom $K$ is an initial state if $K \subseteq L$, the final states are the atoms containing $\epsilon$, and one has transitions $K \xrightarrow{a} K'$ whenever $K' \subseteq a^{-1}K$. Explicitly constructing $Q_L$ can be difficult. Fortunately, a simpler method is known [8]:

1. Construct the minimal dfa for $L$'s reversed language.

2. Construct its reversed nfa i.e. flip initial/final states and reverse all transitions.

The átomaton is isomorphic to the resulting nfa as we now explain coalgebraically. Let $T'_{\Sigma} = 2 \times \text{Id}_{\Sigma} : \text{Set}_f \to \text{Set}_f$. Then the usual reversal of finite pointed deterministic automata defines a dual equivalence:

$$H : (\text{Coalg}_*(T'_{\Sigma}))^{op} \to \text{Coalg}_*(\bar{T}_{\Sigma}) \\ H f^{op} = \{(z', z) : z \in f^{-1}(\{z'\})\} \subseteq Z' \times Z,$$

Since reachability (no proper subobjects) and simplicity (no proper quotients) are dual concepts (see Definition 2.13), a $T'_{\Sigma}$-coalgebra is minimal iff its image under $H$ is minimal, implying the above description.

*Example 3.18.* 1. The átomaton for $L = (a+b)^*b(a+b)^n$ in Example 1.1 arises by constructing the minimal dfa for the reversed language $\text{rev}(L)$ and taking the reverse nfa. Its atoms are $\{(a+b)^*a(a+b)^n, L\} \cup \{(a+b)^j : 0 \leq j \leq n\}$.

2. The átomaton can have exponentially many more states than the minimal dfa, e.g. for $L = (a+b)^n b(a+b)^*$ it has $\geq 2^n$ states.

(c) **The Minimal Xor Automaton.** If $\mathcal{V} = \text{Vect}(\mathbb{Z}_2)$ then $\mathcal{G}_*A$ is the nfa $(Z, \delta, I)$ where $Z \subseteq Q$ is a basis and $I = \{z \in Z : \pi_z(q_0) = 1\}$, see Notation 3.3. It accepts $A$'s language by $\mathbb{Z}_2$-weighted nondeterministic acceptance: a word $w \in \Sigma^*$ is accepted iff its number of accepting paths is odd (this is different than the usual acceptance condition of standard nondeterministic automata).

The nfa $\mathcal{G}_*(A_{\text{Vect}(\mathbb{Z}_2)}^L)$ is called the minimal xor automaton of $L$, see [17]. Note that its construction depends on the choice of a basis, so the minimal xor automaton is only determined up to isomorphism in the category of pointed $\bar{T}_{\Sigma}$-coalgebras. We provide a new way to construct it:

1. Construct $L$'s átomaton $(Z, R_a, F, I)$ and determine the collection $C \subseteq \mathcal{P}Z$ of all subsets of $Z$ which are reachable from $I$.

2. Find any minimal $Q \subseteq \mathcal{P}Z$ whose closure under set-theoretic symmetric difference equals $C$'s closure.

3. Build the nfa $(Q, R'_a, Q \cap F, I)$ where $R'_a(y, y')$ iff $\pi_{y'}(R_a[y]) = 1$ and $I = \{y \in Q : \pi_y(I) = 1\}$.
Briefly, closure under boolean operations implies closure under symmetric difference. Then $A_{\text{Vect}(\mathbb{Z}_2)}^L \subseteq A_{\text{BA}}^L$ as da's, leading to the above algorithm. Since the basis $Q$ has $|Q| \le |C| = |\{w^{-1}L : w \in \Sigma^*\}|$ it follows that the minimal xor automaton is never larger than the minimal dfa of $L$, see [17].

**Example 3.19.** Take the átomaton of Example 1.1, with states $Z = \{x\} \cup \{z_i : 0 \le i \le n + 1\}$ and reachable subsets $C = \{S \subseteq Z : x \notin S, z_0 \in S\}$. One can verify that (i) the closure of $Q = \{\{z_i\} : 0 \le i \le n + 1\}$ under symmetric difference is the closure of $C$ and (ii) $Q$ is minimal. The induced nfa is the minimal xor automaton of Example 1.1. Alternatively $Q = \{\{z_0, z_i\} : 0 \le i \le n + 1\} \subseteq C$ yields a different nfa.

(d) **The Jiromaton.** If $V = \text{JSL}$ then $\mathcal{G}_*A$ is the nondeterministic closure automaton $(J(Q), \delta, I)$ with initial states $I = \{z \in J(Q) : z \le_q q_0\}$ where $J(Q)$ is the closure space of Example 3.6. The underlying nfa (forgetting the closure) accepts $A$'s language. In particular, $\mathcal{G}_*(A_{\text{JSL}}^L)$'s underlying nfa is called the *jiromaton* of $L$, see [10]. Its states

$$Q_L = J(\langle\{w^{-1}L : w \in \Sigma^*\}\rangle_{\nu_{T_\Sigma}})$$

are the join-irreducibles of the finite join-subsemilattice of $\mathcal{P}\Sigma^*$ generated by $L$'s derivatives. Since the latter form the minimal generating set, $Q_L$ consists of those $L$-derivatives not arising as unions of other derivatives – the *prime* derivatives. Therefore, the *jiromaton* has no more states than the minimal dfa. Its structure is analogous to the átomaton: $K \in Q_L$ is initial iff $K \subseteq L$, final iff $\varepsilon \in K$ and $K \xrightarrow{a} K'$ iff $K' \subseteq a^{-1}K$. An algorithm to construct the *jiromaton* from any nfa accepting $L$ is given in [10].

**Example 3.20.** In the *jiromaton* of Example 1.1, the state $z_0$ accepts $L$ and state $z_i$ accepts $L + (a+b)^{i-1}$ for each $i > 0$. These are the prime derivatives of $L$. The closure is defined $\text{cl}_Z(\emptyset) = \emptyset$, $\text{cl}_Z(S) = \{z_0\} \cup \{S\}$ for $S \neq \emptyset$. It is topological: the closed sets are the downsets of the poset where $z_0 \leq z_i$ for all $0 \leq i \leq n + 1$.

(e) **The Distromaton.** If $V = \text{DL}$ then $\mathcal{G}_*A = (J(Q), \delta, I)$ with initial states $I = \{z \in J(Q) : z \le_q q_0\}$. Forgetting $J(Q)$'s poset structure, the underlying nfa accepts $A$'s language. We call $\mathcal{G}_*(A_{\text{DL}}^L)$ the *distromaton* of $L$. Its states

$$Q_L = J(\langle\{w^{-1}L : w \in \Sigma^*\}\rangle_{\nu_{T_\Sigma}})$$

are the join-irreducibles of the sublattice of $\mathcal{P}\Sigma^*$ generated by $L$'s derivatives. One can close under intersections and then unions (which cannot add or remove join-irreducibles) so $Q_L$ consists of finite intersections $\bigcap_i w_i^{-1}L$ not arising as finite unions of other such intersections. The structure is again analogous to the átomaton and the *jiromaton*: $K \in Q_L$ is initial iff $K \subseteq L$, final iff $\varepsilon \in K$ and $K \xrightarrow{a} K$ iff $K' \subseteq a^{-1}K$. There is another way to construct the *distromaton*, analogous to the construction of the átomaton:

1. Take the minimal pointed dfa $(Z, \xrightarrow{a}, z_0, F)$ for the reversed language $\text{rev}(L)$ where $Z$ is ordered by language-inclusion.

2. Build the pointed $\bar{T}_{\Sigma}$-coalgebra $(Z^{op}, \delta, F)$ with final states $\downarrow_Z z_0$ and $z' \in \delta_a[z]$ iff $z' \xrightarrow{a} y \geq_Z z$.
The initial states $F$ are downclosed in $Z^{op}$ and the final states are upclosed in $Z^{op}$, as required. The proof that this is isomorphic to the distromaton is analogous to our earlier argument regarding the átomaton. Briefly, let $T'_{\Sigma} = 2 \times \text{Id}_{\Sigma} : \text{Poset}_f \to \text{Poset}_f$ where 2 is the two-chain. Then there is a dual equivalence

$$H : (\text{Coalg}_*(T'_{\Sigma}))^{op} \to \text{Coalg}_*(\bar{T}_{\Sigma}),$$

which 'reverses' finite pointed deterministic automata equipped with a compatible ordering. The minimal $T'_{\Sigma}$-coalgebra for $L$ is the usual minimal dfa, now equipped with the language-inclusion ordering. Its image under $H$ is again minimal, yielding the above description of the distromaton.

**Corollary 3.21.** *L's átomaton and distromaton have the same number of states, namely, the number of states of the minimal dfa for the reversed language rev($L$).*

*Example 3.22.* The distromaton in Example 1.1 has order $z_0 \leq z_i$ and $z_i \leq z$ for all $0 \leq i \leq n+1$. We have the state $\top$ because $\Sigma^*$ is not the union of non-empty intersections of $L$'s derivatives, see Example 3.20. It arises from the jiomaton by adding a final sink state, see Corollary 4.6.

We finally mention the well-studied *universal automaton* for $L$ [14]. It is the nfa with states

$$Q = \{ \bigcap_{w \in I} w^{-1} L : I \subseteq \omega, \Sigma^* \}$$

ordered by inclusion, where $K$ is final iff $\varepsilon \in K$ and $K \xrightarrow{a} K'$ iff $K' \subseteq a^{-1}K$. The distromaton is never larger and often much smaller because one restricts to the join-irreducible intersections. However the universal automaton has its own advantages: in a sense every state-minimal nfa lies inside it.

# 4 State Minimality and Universal Properties

This final section is split into three parts.

1. We prove $L$'s jiomaton is minimal amongst all nondeterministic acceptors of $L$ relative to a suitable measure (Section 4.1).

2. We give a sufficient condition on $L$ such that the jiomaton is state-minimal and the distromaton and átomaton have at most one more state (Section 4.2).

3. We characterize each of our canonical nfas amongst subclasses of nondeterministic acceptors (Section 4.3).

## 4.1 The Jiomaton is Minimal

There is a measure on finite nondeterministic automata such that $L$'s jiomaton is smaller than any other nfa accepting $L$. For any nfa $N = (Q, R_a, F)$ and $I \subseteq Q$ let $\mathcal{L}_N(I) \subseteq \Sigma^*$ be the accepted language. Define the following measures:

$$|N| = |Q|, \quad \text{acc}(N) = |\{\mathcal{L}_N(I) : I \subseteq Q\}|, \quad \text{tr}(N) = \sum_{a \in \Sigma} |R_a|.$$
These are the number of states, the number of distinct languages accepted and the number of transitions. Let $J_L$ be L's jiromaton without initial states. Recall that isomorphisms of nfas are bijective bisimulations (see Definition 2.1).

**Theorem 4.1.** The jiromaton $J_L$ is (up to isomorphism) the unique nfa accepting L such that for every nfa N accepting L:

(1) $acc(J_L) \leq acc(N)$,

(2) If additionally $acc(J_L) = acc(N)$ then either:

(a) $|J_L| < |N|$ or

(b) $|J_L| = |N|$ and $\text{tr}(N) \leq \text{tr}(J_L)$.

*Proof.* Since $J_L$'s individual states accept derivatives of L, it follows that $J_L$ accepts precisely the unions of derivatives of L. Any nfa N accepting L accepts these languages, so $acc(J_L) \leq acc(N)$. Suppose $acc(J_L) = acc(N)$, so N accepts precisely the unions of L's derivatives. Then each prime derivative has a distinct state in N accepting it, as it cannot arise as the union of other derivatives, so $|J_L| \leq |N|$. Lastly if $acc(J_L) = acc(N)$ and $|J_L| = |N|$ then there is language preserving bijection between N's states and the set of prime derivatives $P_L$, so assume N's carrier is $P_L$. Given $K \xrightarrow{a} K'$ in N we must have $K' \subseteq a^{-1}K$, so there is a corresponding transition in $J_L$. Hence $\text{tr}(N) \leq \text{tr}(J_L)$ and (2) holds. Moreover, in case $\text{tr}(N) = \text{tr}(J_L)$ the previous argument shows that N and $J_L$ are isomorphic. Thus the conditions (1) and (2) determine $J_L$ up to isomorphism. $\square$

## 4.2 Conditions for Canonical State-minimality

In the following let $d_L$ and $n_L$ be the minimal number of states of a dfa (respectively nfa) accepting the regular language L. For any state-minimal nfa $N = (n_L, R_a, F)$ accepting L via $I \subseteq n_L$, one can construct a simple pointed $T_\Sigma$-coalgebra $(Q, \gamma', L)$ whose equivalent nondeterministic closure automaton is another state-minimal acceptor of L. First view N as the $T_\Sigma$-coalgebra $(Pn_L, \gamma)$ via the subset construction. Factorizing the unique homomorphism $L_\gamma$ we obtain $(Q, \gamma')$ where Q is the semilattice of languages accepted by N. Then $(Q, \gamma')$ is equivalent to a nondeterministic closure automaton accepting L. Since $Pn_L \to Q$ implies $n_L = |J(Pn_L)| \geq |J(Q)|$, by forgetting the closure we obtain a state-minimal nfa accepting L.

Hence instead of working with state-minimal nfas we may work with simple $T_\Sigma$-coalgebras which are supercoalgebras of $A_{JSL}^L$. This follows because $A_{JSL}^L$'s carrier is the semilattice $S_L$ of unions of L's derivatives, which Q necessarily contains. We now provide a condition ensuring that $|J(S_L)|$ is the minimal size of an nfa accepting L and hence L's jiromaton is state-minimal.

**Definition 4.2.** A regular language L is intersection-closed if every binary intersection of L's derivatives is a union of L's derivatives.

*Example 4.3.* 1. $L = (a+b)^*b(a+b)^n$ where $n \in \omega$ is intersection-closed.

2. $\emptyset, \Sigma^*$ and $\{w\}$ for $w \in \Sigma^*$ are intersection-closed.
3. Fix $n \in \omega$, $t \in \mathbb{R}$ and $k_i \in \mathbb{R}$ ($1 \le i \le n$). Then the language $L = \{w \in 2^n : \sum_i k_i w_i \ge t\}$ (modeling the behaviour of an artificial neuron) is intersection-closed.

4. Every linear subspace $L \subseteq \mathbb{Z}_2^n$ (viewed as a language over the alphabet $\{0, 1\}$) is intersection-closed.

**Theorem 4.4.** If $L$ is intersection-closed then its jiomaton is state-minimal.

*Proof.* By assumption the carrier $S_L$ of $A_{\text{JSL}}^L$ is closed under both unions and non-empty intersections, so $D = S_L \cup \{\Sigma^*\}$ is a distributive lattice of languages. Let $N$ be any state-minimal nfa accepting $L$ via initial states $I$, and $S \subseteq \mathcal{P}\Sigma^*$ be the semilattice of languages accepted by $N$ (by varying $I$). The nfa $N$ must at least accept $L$'s derivatives. Since $S$ is closed under unions we have $S_L \subseteq S$. By the surjective morphism $\mathcal{P}n_L \twoheadrightarrow S$ it follows that $|N| \ge |J(S)|$, so it suffices to prove that $|J(S)| \ge |J(S_L)|$. Let $S_* = S \cup \{\Sigma^*\}$ be the semilattice obtained by adding a top element if necessary. We have a $\text{JSL}_f$-morphism $\iota : D \hookrightarrow S_*$. The meets in $D$ are also meets in $S_*$ so the same function defines a $\text{JSL}_f$-morphism $\iota : D^{\text{op}} \hookrightarrow S_*^{\text{op}}$. By the self-duality of $\text{JSL}_f$ we obtain a surjective morphism $\iota' : S_* \twoheadrightarrow D$, hence $|J(S_*)| \ge |J(D)|$. If $D = S_L$ then $S_* = S$, so $|J(S)| \ge |J(S_L)|$ and we are done. Otherwise $\Sigma^* \notin S_L$ and we now prove $\Sigma^* \notin S$. By state minimality $N$ is reachable, so each state $q$ accepts a subset of some $L$-derivative. Then if $\Sigma^* \in S$ we deduce $\Sigma^*$ is the union of $L$'s derivatives, so $\Sigma^* \in S_L$ – a contradiction. Consequently $|J(D)| = 1 + |J(S_L)|$ and $|J(S_*)| = 1 + |J(S)|$ hence $|J(S)| \ge |J(S_L)|$ again. $\square$

*Remark 4.5.* The converse of this theorem is generally false: the language $L = \overline{\{aa\}}$ is not intersection-closed, but its jiomaton is state-minimal.

**Corollary 4.6.** If $L$ is intersection-closed then its átomaton and distromaton have at most one more state than the jiomaton.

*Proof.* By the above proof the distromaton may only have an additional final sink state – otherwise it has the same transition structure. By Corollary 3.21 the átomaton has the same number of states. $\square$

By Corollary 3.21 we further deduce:

**Corollary 4.7.** If $L \subseteq \Sigma^*$ is intersection-closed then any state-minimal nfa accepting $L$ has (i) $d_{\text{rev}(L)}$ states if $\Sigma^*$ is a union of $L$'s derivatives and (ii) $d_{\text{rev}(L)} - 1$ otherwise.

**Theorem 4.8.** If $d_L = 2^{n_L}$ then the jiomaton of $L$ is state-minimal.

*Proof.* Let $N = (n_L, R_a, F)$ be a state-minimal nfa accepting $L$ via $I \subseteq n_L$. View it as a pointed $T_\Sigma$-coalgebra $A = (\mathcal{P}n_L, \gamma, I)$ via the subset-construction. By assumption $d_L = |\mathcal{P}n_L|$, so this is a state-minimal dfa accepting $L$; in particular, it is a reachable pointed $T_\Sigma$-coalgebra. Then the surjective morphism $A \to A_{\text{JSL}}^L$ implies that $A_{\text{JSL}}^L$ has no more than $n_L$ join-irreducibles, so the jiomaton is state-minimal. $\square$

## 4.3 Characterizing the Canonical Nfas

Although the canonical nfas are generally not state-minimal, they are state-minimal amongst certain subclasses of nfas.
**Theorem 4.9.** The átomaton of a regular language *L* is state-minimal amongst all nfas accepting *L* whose accepted languages are closed under complement.

*Proof.* Assume the weaker condition that an nfa *N* accepts every language in the boolean algebra *B* ⊆<sub>ω</sub> *P*Σ*\* generated by *L*'s derivatives. By an earlier argument, *N* induces a simple *T*Σ-coalgebra (*Q*, γ) whose states are the languages *N* accepts and |*N*| ≥ |*J*(*Q*)|. By assumption *Q* ⊇ *B* (a distributive lattice), so |*J*(*Q*)| ≥ |*J*(*B*)| by the proof of Theorem 4.4. The join-irreducibles of a finite boolean algebra are its atoms, so *N* has no less states than the átomaton. □

The next result is from [17]. It follows because quotients and subspaces of finite-
dimensional vector spaces cannot have larger dimension.

**Theorem 4.10 ([17]).** Any canonical xor nfa for *L* is state-minimal amongst nfas accepting *L* via Z₂-weighted acceptance.

We give a mild generalization of a result in [10]. Recall that nfas accepting *L* also accept all unions of its derivatives. Then we can conclude from Theorem 4.1:

**Corollary 4.11.** *The jiromaton of a regular language *L* is state-minimal amongst nfas accepting precisely the unions of *L*'s derivatives.*

*Example 4.12.* Let *N* be an nfa accepting *L* via initial states *I*. If every singleton set of states is reachable from *I* then *N* accepts precisely the unions of *L*'s derivatives. Thus, it is no smaller than *L*'s jiromaton.

**Theorem 4.13.** *The distromaton of a regular language *L* is state-minimal amongst all nfas accepting *L* whose accepted languages are closed under intersection.*

*Proof.* Reuse the proof of Theorem 4.9. Again we actually have a stronger result: the distromaton is state-minimal amongst all nfas which can accept every intersection of *L*'s derivatives. □

**5 Conclusions and Future Work**

It is often claimed in the literature that canonical nondeterministic automata do not exist, usually as a counterpoint to the minimal dfa. On the contrary we have shown that they *do* exist and moreover arise from the minimal dfa interpreted in a locally finite variety. In so doing we have unified previous work from three sources [8, 10, 17] and introduced a new canonical nondeterministic acceptor, the distromaton. We also identified a class of languages where canonical *state-minimal* nfas exist. These results depend heavily on a coalgebraic approach to automata theory, providing not only new structural insights and construction methods but also a new perspective on what a state-minimal acceptor actually is.

In this paper we introduced nondeterministic closure automata, viz. $\overline{T}_{\Sigma}$-coalgebras
in the category of closure spaces, mainly as a tool for constructing the jiromaton.
However, nondeterministic closure automata bear interesting structural properties them-
selves, which we did not discuss here in depth. We expect that a proper investigation of
these machines will lead to further insights about nondeterminism, in particular addi-
tional and more general criteria for the (state-)minimality of nfas.

Another point we aim to investigate in more detail are the algorithmic aspects of the state-minimization problem for nfas. Although this problem is known to be PSPACE-complete in general, the canonicity of our nfas suggests that – at least for certain natural subclasses of nfas – efficient state-minimization procedures may be in reach. We leave the study of such complexity-related issues for future work.

References

[1] Adámek, J., Bonchi, F., Hülsbusch, M., König, B., Milius, S., Silva, A.: A coalgebraic perspective on minimization and determinization. In: FoSSaCS. pp. 58–73 (2012)

[2] Adámek, J., Milius, S., Moss, L.S., Sousa, L.: Well-pointed coalgebras (extended abstract). In: FoSSaCS. pp. 89–103 (2012)

[3] Barr, M.: Terminal coalgebras in well-founded set theory. Theor. Comput. Sci. 114(2), 299–315 (1993)

[4] Bezhanishvili, N., Kupke, C., Panangaden, P.: Minimization via duality. In: WoLLIC. pp. 191–205 (2012)

[5] Bonchi, F., Bonsangue, M.M., Boreale, M., Rutten, J.J.M.M., Silva, A.: A coalgebraic perspective on linear weighted automata. Inform. and Comput. 211, 77–105 (2012)

[6] Bonchi, F., Bonsangue, M.M., Rutten, J.J.M.M., Silva, A.: Brzozowski's algorithm (co)algebraically. In: Logic and Program Semantics. pp. 12–23 (2012)

[7] Bonsangue, M.M., Milius, S., Silva, A.: Sound and complete axiomatizations of coalgebraic language equivalence. ACM Trans. Comput. Log. 14(1:7) (2013)

[8] Brzozowski, J., Tamm, H.: Theory of Átomata. In: Proc. 15th International Conference on Developments in Language Theory (DLT’11). Lecture Notes Comput. Sci., vol. 6795, pp. 105–116. Springer (2011)

[9] Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Mathematical theory of Automata, pp. 529–561. Volume 12 of MRI Symposia Series, Polytechnic Press, Polytechnic Institute of Brooklyn, N.Y. (1962)

[10] Denis, F., Lemay, A., Terlutte, A.: Residual finite state automata. Fund. Inform. XX, 1–30 (2002)

[11] Hasuo, I., Jacobs, B., Sokolova, A.: Generic trace semantics via coinduction. Log. Methods Comput. Sci. 3(4:11) (2007)

[12] Jacobs, B., Silva, A., Sokolova, A.: Trace semantics via determinization. In: Pattinson, D., Schröder, L. (eds.) Proc. CMCS 2012. Lecture Notes Comput. Sci., vol. 7399, pp. 109–129. Springer (2012)

[13] Jipsen, P.: Categories of algebraic contexts equivalent to idempotent semirings and domain semirings. In: Kahl, W., Griffin, T.G. (eds.) RAMICS. Lecture Notes in Computer Science, vol. 7560, pp. 195–206. Springer (2012)

[14] Lombardy, S., Sakarovitch, J.: The universal automaton. In: Flum, J., Grädel, E., Wilke, T. (eds.) Logic and Automata. Texts in Logic and Games, vol. 2, pp. 457–504. Amsterdam University Press (2008)

[15] Milius, S.: A sound and complete calculus for finite stream circuits. In: Proc. 25th Annual Symposium on Logic in Computer Science (LICS’10). pp. 449–458. IEEE Computer Society (2010)

[16] Silva, A., Bonchi, F., Bonsangue, M.M., Rutten, J.J.M.M.: Generalizing determinization from automata to coalgebras. Log. Methods Comput. Sci 9(1:9) (2013)

[17] Vuillemin, J., Gama, N.: Efficient Equivalence and Minimization for Non Deterministic XOR Automata. Research report, LIENS (May 2010), http://hal.inria.fr/inria-00487031