Conference contribution

Canonical Nondeterministic Automata

Publication Details
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)
Publisher: Springer
Publishing place: Heidelberg
Publication year: 2014
Title of series: Lecture Notes in Computer Science
Volume: 8446
Conference Proceedings Title: Coalgebraic Methods in Computer Science
Pages range: 189-210
ISBN: 978-3-662-44123-7
ISSN: 1611-3349

Event details
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.

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.

BibTeX: Download
Share link
Last updated on 2017-06-26 at 03:45
PDF downloaded successfully