Lifting Adjunctions to Coalgebras to (Re)Discover Automata Constructions

Abstract : It is a well-known fact that a nondeterministic automaton can be transformed into an equivalent deterministic automaton via the powerset construction. From a categorical perspective this construction is the right adjoint to the inclusion functor from the category of deterministic automata to the category of nondeterministic automata. This is in fact an adjunction between two categories of coalgebras: deterministic automata are coalgebras over S e t and nondeterministic automata are coalgebras over R e l . We will argue that this adjunction between coalgebras originates from a canonical adjunction between S e t and R e l . In this paper we describe how, in a quite generic setting, an adjunction can be lifted to coalgebras, and we compare some sufficient conditions. Then we illustrate this technique in length: we recover several constructions on automata as liftings of basic adjunctions including determinization of nondeterministic and join automata, codeterminization, and the dualization of linear weighted automata. Finally, we show how to use the lifted adjunction to check behavioral equivalence.
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.168-188, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_10〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01408759
Contributeur : Hal Ifip <>
Soumis le : lundi 5 décembre 2016 - 13:25:24
Dernière modification le : lundi 5 décembre 2016 - 14:27:31
Document(s) archivé(s) le : mardi 21 mars 2017 - 08:06:08

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Henning Kerstan, Barbara König, Bram Westerbaan. Lifting Adjunctions to Coalgebras to (Re)Discover Automata Constructions. 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.168-188, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_10〉. 〈hal-01408759〉

Partager

Métriques

Consultations de la notice

36

Téléchargements de fichiers

13