Computing behavioral distances, compositionally

Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

19 Citations (Scopus)


We propose a general definition of composition operator on Markov Decision Processes with rewards (MDPs) and identify a well behaved class of operators, called safe, that are guaranteed to be non-extensive w.r.t. the bisimilarity pseudometrics of Ferns et al. [10], which measure behavioral similarities between MDPs. For MDPs built using safe/non-extensive operators, we present the first method that exploits the structure of the system for (exactly) computing the bisimilarity distance on MDPs. Experimental results show significant improvements upon the non-compositional technique.

Original languageEnglish
Title of host publication Mathematical Foundations of Computer Science 2013
EditorsK. Chatterjee, J. Sgall
Place of PublicationBerlin
Number of pages12
ISBN (Print)9783642403125
Publication statusPublished - 15 Oct 2013
Event38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria
Duration: 26 Aug 201330 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8087 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013


  • discount factor
  • multi-agent system
  • composition operator
  • Markov decision processes
  • parallel composition


Dive into the research topics of 'Computing behavioral distances, compositionally'. Together they form a unique fingerprint.

Cite this