%0 Conference Proceedings
%T Canonical Nondeterministic Automata
%+ Technische Universität Braunschweig = Technical University of Braunschweig [Braunschweig]
%+ Friedrich-Alexander Universität Erlangen-Nürnberg = University of Erlangen-Nuremberg (FAU)
%A Myers, Robert, R.
%A Adámek, Jiří
%A Milius, Stefan
%A Urbat, Henning
%Z Part 2: Regular Contributions
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS)
%C Grenoble, France
%Y Marcello M. Bonsangue
%3 Coalgebraic Methods in Computer Science
%V LNCS-8446
%P 189-210
%8 2014-04-05
%D 2014
%R 10.1007/978-3-662-44124-4_11
%Z Computer Science [cs]Conference papers
%X For each regular language <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>L</mi></math> we describe a family of canonical nondeterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>L</mi></math> in a locally finite variety <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">V</mi> </mrow></math>, and apply an equivalence between the finite <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">V</mi> </mrow></math>-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.
%G English
%Z TC 1
%Z WG 1.3
%2 https://inria.hal.science/hal-01408760/document
%2 https://inria.hal.science/hal-01408760/file/328263_1_En_11_Chapter.pdf
%L hal-01408760
%U https://inria.hal.science/hal-01408760
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-8446
%~ IFIP-WG1-3
%~ IFIP-CMCS