Canonical Nondeterministic Automata
Author(s): Myers R, Adámek J, Milius S, Urbat H
Title edited volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publishing place: Heidelberg
Publication year: 2014
Title of series: Lecture Notes in Computer Science
Conference Proceedings Title: Coalgebraic Methods in Computer Science
Pages range: 189-210
Event: 12th International Workshop on Coalgebraic Methods in Computer Science
Event location: Grenoble, France
Start date of the event: 05/04/2014
End date of the event: 06/04/2014
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. © 2014 IFIP International Federation for Information Processing.
FAU Authors / FAU Editors How to cite
APA: Myers, R., Adámek, J., Milius, S., & Urbat, H. (2014). Canonical Nondeterministic Automata. In Coalgebraic Methods in Computer Science (pp. 189-210). Heidelberg: Springer.
MLA: Myers, Robert, et al. "Canonical Nondeterministic Automata." Proceedings of the 12th International Workshop on Coalgebraic Methods in Computer Science, Grenoble, France Heidelberg: Springer, 2014. 189-210.