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 metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01408760
Contributor : Hal Ifip <>
Submitted on : Monday, December 5, 2016 - 1:25:37 PM
Last modification on : Friday, February 9, 2018 - 9:22:02 AM
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)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Robert 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⟩

Share

Metrics

Record views

79

Files downloads

185