Coalgebraic constructions of canonical nondeterministic automata (Q890382)

The paper uses a coalgebraic approach and gives a construction to obtain canonical nondeterministic acceptors (NFAs). The procedure is described by the authors as follows: given a regular language \(L\), build the minimal deterministic finite automaton (DFA) for \(L\) in a locally finite variety \(V\), apply an equivalence between the category of finite \(V\)-algebras and a suitable category of finite structured sets and relations; the canonical nondeterministic acceptor is the image of the minimal finite automaton for \(L\) under the equivalence. The case when \(V =\) Boolean algebras (via Stone duality) yields the átomaton of Brzozowski and Tamm. The case when \(V =\) semilattices (via self dualities \(\mathrm{JSL}_f=\mathrm{JSL}_f^{\mathrm{op}}\)) yields the jiromaton of Denis, Lemay and Terlutte. The case when \(V = \mathbb Z_2\)-vector spaces yields the minimal xor automaton of Vuillemin and Gama (and even though this example differs substantially from the others it is still captured by the same procedure). The case when \(V =\) distributive lattices is considered (via Priestely duality \(\mathrm{DL}_f\cong \mathrm{PoSet}_f^{\mathrm{op}}\)) and a new automaton is obtained which the authors call the distromaton. In Section 4, the authors characterize the canonical NFAs by universal properties and discuss their state minimality.