Skip to Main content Skip to Navigation
Conference papers

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 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
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


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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


Files downloads