Canonical Nondeterministic Automata

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 FR

ISBN: 978-3-662-44123-7

URI: http://www8.cs.fau.de/publications

DOI: 10.1007/978-3-662-44124-4

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. © 2014 IFIP International Federation for Information Processing.

Authors with CRIS profile

Involved external institutions

How to cite

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