# Canonical Nondeterministic Automata

Abstract : For each regular language $L$ we describe a family of canonical nondeterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for $L$ in a locally finite variety $\mathcal{V}$, and apply an equivalence between the finite $\mathcal{V}$-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.
Type de document :
Communication dans un congrès
Marcello M. Bonsangue. 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2014, Grenoble, France. Lecture Notes in Computer Science, LNCS-8446, pp.189-210, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_11〉
Domaine :

Littérature citée [17 références]

https://hal.inria.fr/hal-01408760
Contributeur : Hal Ifip <>
Soumis le : lundi 5 décembre 2016 - 13:25:37
Dernière modification le : vendredi 9 février 2018 - 09:22:02
Document(s) archivé(s) le : lundi 20 mars 2017 - 17:35:32

### Fichier

328263_1_En_11_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Robert Myers, Jiří Adámek, Stefan Milius, Henning Urbat. Canonical Nondeterministic Automata. Marcello M. Bonsangue. 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2014, Grenoble, France. Lecture Notes in Computer Science, LNCS-8446, pp.189-210, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_11〉. 〈hal-01408760〉

### Métriques

Consultations de la notice

## 45

Téléchargements de fichiers