# Canonical Nondeterministic Automata

Abstract : For each regular language $L$ we describe a family of canonical nondeterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for $L$ in a locally finite variety $\mathcal{V}$, and apply an equivalence between the finite $\mathcal{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.
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [17 references]

https://hal.inria.fr/hal-01408760
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, December 5, 2016 - 1:25:37 PM
Last modification on : Friday, November 19, 2021 - 12:42:03 PM
Long-term archiving on: : Monday, March 20, 2017 - 5:35:32 PM

### File

328263_1_En_11_Chapter.pdf
Files produced by the author(s)

### Citation

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⟩

Record views