Myers R, Adámek J, Milius S, Urbat H, Urbat H (2014)
Publication Type: Conference contribution
Publication year: 2014
Publisher: Springer
Edited Volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series: Lecture Notes in Computer Science
City/Town: Heidelberg
Book Volume: 8446
Pages Range: 189-210
Conference Proceedings Title: Coalgebraic Methods in Computer Science
Event location: Grenoble, France
ISBN: 978-3-662-44123-7
URI: http://www8.cs.fau.de/publications
DOI: 10.1007/978-3-662-44124-4
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.
APA:
Myers, R., Adámek, J., Milius, S., Urbat, H., & Urbat, H. (2014). Canonical Nondeterministic Automata. In Coalgebraic Methods in Computer Science (pp. 189-210). Grenoble, France, FR: 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.
BibTeX: Download