| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Canonical Nondeterministic Automata
Abstract : For each regular language we describe a family of canonical nondeterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for in a locally finite variety , and apply an equivalence between the finite -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.
Cited literature [17 references]
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
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