Quantitative Kleene coalgebras

A. Silva, F. Bonchi, M.M. Bonsangue, J.J.M.M. Rutten

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We present a systematic way to generate (1) languages of (generalised) regular expressions, and (2) sound and complete axiomatizations thereof, for a wide variety of quantitative systems. Our quantitative systems include weighted versions of automata and transition systems, in which transitions are assigned a value in a monoid that represents cost, duration, probability, etc. Such systems are represented as coalgebras and (1) and (2) above are derived in a modular fashion from the underlying (functor) type of these coalgebras. In previous work, we applied a similar approach to a class of systems (without weights) that generalizes both the results of Kleene (on rational languages and DFA's) and Milner (on regular behaviours and finite LTS's), and includes many other systems such as Mealy and Moore machines. In the present paper, we extend this framework to deal with quantitative systems. As a consequence, our results now include languages and axiomatizations, both existing and new ones, for many different kinds of probabilistic systems. © 2010 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)822-849
JournalInformation and Computation
Volume209
Issue number5
DOIs
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'Quantitative Kleene coalgebras'. Together they form a unique fingerprint.

Cite this