Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata

Abstract : Coalgebra offers a general framework for modelling different types of state-based systems. Our aim is to present generic algorithms to decide behavioural equivalence for coalgebras which generalize partition refinement. The underlying idea of the algorithms is to work on the final chain and to factor out redundant information. If the algorithm terminates, the result of the construction is a representative of the given coalgebra that is not necessarily unique and that allows to precisely answer questions about behavioural equivalence. We apply the algorithm to weighted automata over semirings in order to obtain a procedure for checking language equivalence for a large number of semirings.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.311-325, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_24〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01402080
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 11:09:13
Dernière modification le : jeudi 24 novembre 2016 - 11:14:10
Document(s) archivé(s) le : lundi 27 mars 2017 - 09:15:25

Fichier

978-3-662-44602-7_24_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Barbara König, Sebastian Küpper. Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.311-325, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_24〉. 〈hal-01402080〉

Partager

Métriques

Consultations de la notice

40

Téléchargements de fichiers

4