Stream Automata Are Coalgebras

Abstract : Stream automata (also called ω-automata) and ω-regular languages are of paramount importance in Computer Science and Logic. A coalgebraic treatment of these structures has not been given yet. We study a simple two-sorted setting where deterministic Muller automata can be cast as coalgebras, so that coalgebraic bisimilarity coincides with language equivalence. From this characterisation, we derive concise and natural decision procedures for complementation, union, intersection, and equivalence check.
Type de document :
Communication dans un congrès
Dirk Pattinson; Lutz Schröder. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. Springer, Lecture Notes in Computer Science, LNCS-7399, pp.90-108, 2012, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-642-32784-1_6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01539881
Contributeur : Hal Ifip <>
Soumis le : jeudi 15 juin 2017 - 15:02:44
Dernière modification le : jeudi 15 juin 2017 - 15:25:48
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 11:44:58

Fichier

978-3-642-32784-1_6_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Vincenzo Ciancia, Yde Venema. Stream Automata Are Coalgebras. Dirk Pattinson; Lutz Schröder. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. Springer, Lecture Notes in Computer Science, LNCS-7399, pp.90-108, 2012, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-642-32784-1_6〉. 〈hal-01539881〉

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

20