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.
Type de document :
Communication dans un congrès
Marcello M. Bonsangue. 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2014, Grenoble, France. Lecture Notes in Computer Science, LNCS-8446, pp.189-210, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_11〉
https://hal.inria.fr/hal-01408760
Contributeur : Hal Ifip
<>
Soumis le : lundi 5 décembre 2016 - 13:25:37
Dernière modification le : vendredi 9 février 2018 - 09:22:02
Document(s) archivé(s) le : lundi 20 mars 2017 - 17:35:32
Robert Myers, Jiří Adámek, Stefan Milius, Henning Urbat. Canonical Nondeterministic Automata. Marcello M. Bonsangue. 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2014, Grenoble, France. Lecture Notes in Computer Science, LNCS-8446, pp.189-210, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_11〉. 〈hal-01408760〉
