Quantitative Kleene coalgebras (Q532394): Difference between revisions

Coalgebras serve as a generic framework for state-based systems, generalizating system types such as deterministic finite automata or labelled transition systems. Finite coalgebras are of particular interest as they relate to generalized notions of a regular language. In earlier work, some of the authors of the current article have provided a language of generalized regular expressions for finite coalgebras of so-called Kripke polynomial functors, generated from the powerset functor, constant functors, and the identity functor by closing under finite sums and products (with some modifications required to propagate semi-lattice structure) [\textit{A. Silva}, \textit{M. Bonsangue} and \textit{J. Rutten}, ``Non-deterministic Kleene coalgebras'', Log. Methods Comput. Sci. 6, No. 3, Paper No. 23, 39 p. (2010; Zbl 1208.68141)]. The main results are a generalization of Kleene's theorem, stating that generalized regular expressions describe exactly the finite coalgebras, as well as a sound and complete equational axiomatization. In the current work, these results are extended to so-called quantitative functors, which additionally allow the use of monoidal exponentiation, i.e., the formation of functors \(M^H\) where \(M\) is a commutative monoid and \(H\) is a quantitative functor. This generalization covers, e.g., various forms of weighted automata. Moreover, expression languages are often easy to restrict to subfunctors; in particular, the method can easily be made to apply to probabilistic systems. Instantiating the generic framework often yields subsets (typically distinguished by the omission of parallel operators) of existing expression languages from the literature. In some cases, the axiomatization thus obtained is new; this holds in particular for the expression language for weighted automata [\textit{P. Buchholz} and \textit{P. Kemper}, ``Quantifying the dynamic behavior of process algebras'', Lect. Notes Comput. Sci. 2165, 184--199 (2001; Zbl 1007.68130)] and the expression language for stratified probabilistic systems [\textit{R. J. van Glabbeek}, \textit{S. A. Smolka} and \textit{B. Steffen}, ``Reactive, generative and stratified models of probabilistic processes'', Inf. Comput. 121, No. 1, 59--80 (1995; Zbl 0832.68042)].