{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T05:18:03Z","timestamp":1778563083153,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T00:00:00Z","timestamp":1624233600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T00:00:00Z","timestamp":1624233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 Ca\u2019 Foscari Venezia"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we deal with the lumpability approach to cope with the state space explosion problem inherent to the computation of the stationary performance indices of large stochastic models. The lumpability method is based on a state aggregation technique and applies to Markov chains exhibiting some structural regularity. Moreover, it allows one to efficiently compute the exact values of the stationary performance indices when the model is actually lumpable. The notion of quasi-lumpability is based on the idea that a Markov chain can be altered by relatively small perturbations of the transition rates in such a way that the new resulting Markov chain is lumpable. In this case, only upper and lower bounds on the performance indices can be derived. Here, we introduce a novel notion of quasi-lumpability, named <jats:italic>proportional lumpability<\/jats:italic>, which extends the original definition of lumpability but, differently from the general definition of quasi-lumpability, it allows one to derive exact stationary performance indices for the original process. We then introduce the notion of <jats:italic>proportional bisimilarity<\/jats:italic> for the terms of the performance process algebra PEPA. Proportional bisimilarity induces a proportional lumpability on the underlying continuous-time Markov chains. Finally, we prove some compositionality results and show the applicability of our theory through examples.<\/jats:p>","DOI":"10.1007\/s00236-021-00404-y","type":"journal-article","created":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T18:03:01Z","timestamp":1624298581000},"page":"211-244","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Proportional lumpability and proportional bisimilarity"],"prefix":"10.1007","volume":"59","author":[{"given":"Andrea","family":"Marin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carla","family":"Piazza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1189-4439","authenticated-orcid":false,"given":"Sabina","family":"Rossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,21]]},"reference":[{"key":"404_CR1","doi-asserted-by":"crossref","unstructured":"Abate, A., Brim, L., \u010ce\u0161ka, M., Kwiatkowska, M.: Adaptive aggregation of Markov chains: Quantitative analysis of chemical reaction networks. In Proceedings of computer aided verification (CAV\u201915), pp. 195\u2013213. Springer International Publishing, (2015)","DOI":"10.1007\/978-3-319-21690-4_12"},{"key":"404_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.ic.2018.04.002","volume":"260","author":"G Alzetta","year":"2018","unstructured":"Alzetta, G., Marin, A., Piazza, C., Rossi, S.: Lumping-based equivalences in Markovian automata: Algorithms and applications to product-form analyses. Inf. Comput. 260, 99\u2013125 (2018)","journal-title":"Inf. Comput."},{"key":"404_CR3","doi-asserted-by":"crossref","unstructured":"Baarir, S., Beccuti, M., Dutheillet, C., Franceschinis, G.: From partially to fully lumped Markov chains in stochastic well formed Petri nets. In Proceedings of Valuetools 2009 conference, pp.\u00a044. ACM, (2009)","DOI":"10.4108\/ICST.VALUETOOLS2009.7733"},{"issue":"1","key":"404_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.peva.2010.09.002","volume":"68","author":"S Baarir","year":"2011","unstructured":"Baarir, S., Beccuti, M., Dutheillet, C., Franceschinis, G., Haddad, S.: Lumping partially symmetrical stochastic models. Perform. Eval. 68(1), 21\u201344 (2011)","journal-title":"Perform. Eval."},{"key":"404_CR5","doi-asserted-by":"crossref","unstructured":"Baarir, S., Dutheillet, C., Haddad, S., Ili\u00e8, J.-M.: On the use of exact lumping in partially symmetrical Well-formed Petri Nets. In Proceedings of International Conference on the Quantitative Evaluation of Systems (QEST\u201905), pp. 23\u201332, Torino, Italy. IEEE Comp. Soc (2005)","DOI":"10.1109\/QEST.2005.26"},{"issue":"2","key":"404_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.ic.2005.03.001","volume":"200","author":"C Baier","year":"2005","unstructured":"Baier, C., Katoen, J.-P., Hermanns, H., Wolf, V.: Comparative branching-time semantics for Markov chains. Inf. Comput. 200(2), 149\u2013214 (2005)","journal-title":"Inf. Comput."},{"key":"404_CR7","doi-asserted-by":"crossref","unstructured":"Balsamo, S., Marin, A.: Queueing Networks in Formal methods for performance evaluation, chapter\u00a02, pp. 34\u201382. M. Bernardo and J. Hillston (Eds), LNCS, Springer, (2007)","DOI":"10.1007\/978-3-540-72522-0_2"},{"key":"404_CR8","doi-asserted-by":"crossref","unstructured":"Balsamo, Simonetta, Marin, Andrea: Product-form solutions for models with joint-state dependent transition rates. In Analytical and Stochastic Modeling Techniques and Applications, 17th International Conference, ASMTA 2010, volume 6148 of Lecture Notes in Computer Science, pp. 87\u2013101, (2010)","DOI":"10.1007\/978-3-642-13568-2_7"},{"key":"404_CR9","doi-asserted-by":"crossref","unstructured":"Bernardo, M.: Weak Markovian bisimulation congruences and exact CTMC-level aggregations for concurrent processes. In Proceedings of the 10th Workshop on Quantitative Aspects of Programming Languages and Systems (QALP\u201912), pp. 122\u2013136. EPTCS, (2012)","DOI":"10.4204\/EPTCS.85.9"},{"key":"404_CR10","doi-asserted-by":"crossref","unstructured":"Bernardo, M.: Weak Markovian bisimulation congruences and exact CTMC-level aggregations for sequential processes. In Proceedings of the 6th international conference on trustworthy global computing (TGC\u201911), volume 7173 of LNCS, pp. 89\u2013103. Springer, (2012)","DOI":"10.1007\/978-3-642-30065-3_6"},{"key":"404_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.tcs.2014.10.025","volume":"563","author":"M Bernardo","year":"2015","unstructured":"Bernardo, M.: On the tradeoff between compositionality and exactness in weak bisimilarity for integrated-time markovian process calculi. Theor. Comput. Sci. 563, 99\u2013143 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"404_CR12","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S1571-0661(04)80520-6","volume":"68","author":"M Bravetti","year":"2003","unstructured":"Bravetti, M.: Revisiting interactive Markov chains. Electr. Notes Theor. Comput. Sci. 68(5), 65\u201384 (2003)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"404_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.2307\/3215235","volume":"31","author":"P Buchholz","year":"1994","unstructured":"Buchholz, P.: Exact and ordinary lumpability in finite Markov chains. J. Appl. Probab. 31, 59\u201375 (1994)","journal-title":"J. Appl. Probab."},{"key":"404_CR14","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2019.03.018","volume":"777","author":"L Cardelli","year":"2019","unstructured":"Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Symbolic computation of differential equivalences. Theoret. Comput. Sci. 777, 132\u2013154 (2019)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"404_CR15","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0166-5316(95)00023-2","volume":"26","author":"JL Coleman","year":"1996","unstructured":"Coleman, J.L., Henderson, W., Taylor, P.G.: Product form equilibrium distributions and a convolution algorithm for Stochastic Petri nets. Perf. Eval. 26(3), 159\u2013180 (1996)","journal-title":"Perf. Eval."},{"key":"404_CR16","unstructured":"Daly, D., Buchholz, P., Sanders, W.H.: Bound-preserving composition for markov reward models. In Third International Conference on the Quantitative Evaluation of Systems (QEST 2006), pp. 243\u2013252, (2006)"},{"issue":"6","key":"404_CR17","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0020-0190(03)00343-0","volume":"87","author":"S Derisavi","year":"2003","unstructured":"Derisavi, S., Hermanns, H., Sanders, W.H.: Optimal state-space lumping in Markov chains. Elsevier Inform. Process. Lett. 87(6), 309\u2013315 (2003)","journal-title":"Elsevier Inform. Process. Lett."},{"issue":"1\u20133","key":"404_CR18","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-5316(94)90015-9","volume":"20","author":"G Franceschinis","year":"1994","unstructured":"Franceschinis, G., Muntz, R.: Bounds for quasi-lumpable Markov chains. Perform. Eval. 20(1\u20133), 223\u2013243 (1994)","journal-title":"Perform. Eval."},{"issue":"7","key":"404_CR19","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1109\/32.297940","volume":"20","author":"G Franceschinis","year":"1994","unstructured":"Franceschinis, G., Muntz, R.: Computing bounds for the performance indices of quasi-lumpable stochastic well-formed nets. IEEE Trans. Softw. Eng. 20(7), 516\u2013525 (1994)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"404_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45804-2","volume-title":"Interactive Markov Chains","author":"H Hermanns","year":"2002","unstructured":"Hermanns, H.: Interactive Markov Chains. Springer, New York (2002)"},{"key":"404_CR21","doi-asserted-by":"crossref","unstructured":"Hillston, J.: A Compositional Approach to Performance Modelling. Cambridge Press, (1996)","DOI":"10.1017\/CBO9780511569951"},{"key":"404_CR22","volume-title":"Finite Markov Chains","author":"JG Kemeny","year":"1976","unstructured":"Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Springer, New York (1976)"},{"issue":"1","key":"404_CR23","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1021\/i160029a020","volume":"8","author":"JCW Kuo","year":"1969","unstructured":"Kuo, J.C.W., Wei, J.: Lumping analysis in monomolecular reaction systems. analysis of approximately lumpable system. Ind. Eng. Chem. Fund. 8(1), 124\u2013133 (1969)","journal-title":"Ind. Eng. Chem. Fund."},{"issue":"3","key":"404_CR24","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0167-6377(93)90006-3","volume":"13","author":"J Ledoux","year":"1993","unstructured":"Ledoux, J.: A necessary condition for weak lumpability in finite Markov processes. Oper. Res. Lett. 13(3), 165\u2013168 (1993)","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"404_CR25","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.1016\/0009-2509(89)85014-6","volume":"44","author":"G Li","year":"1989","unstructured":"Li, G., Rabitz, H.: A general analysis of exact lumping in chemical kinetics. Chem. Eng. Sci. 44(6), 1413\u20131430 (1989)","journal-title":"Chem. Eng. Sci."},{"key":"404_CR26","doi-asserted-by":"crossref","unstructured":"Marin, A., Piazza, C., Rossi, S.: Proportional lumpability. In Formal modeling and analysis of timed systems\u201417th international conference, formats 2019, proceedings, volume 11750 of lecture notes in computer science, pp. 265\u2013281. Springer, (2019)","DOI":"10.1007\/978-3-030-29662-9_16"},{"key":"404_CR27","doi-asserted-by":"crossref","unstructured":"Marin, A., Rossi, S.: Autoreversibility: exploiting symmetries in Markov chains. In Proceedings of IEEE MASCOTS, pages 151\u2013160, san Francisco, CA, USA (2013)","DOI":"10.1109\/MASCOTS.2013.23"},{"issue":"5","key":"404_CR28","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s00236-016-0266-1","volume":"54","author":"A Marin","year":"2017","unstructured":"Marin, A., Rossi, S.: On the relations between Markov chain lumpability and reversibility. Acta Inform. 54(5), 447\u2013485 (2017)","journal-title":"Acta Inform."},{"key":"404_CR29","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.peva.2015.09.004","volume":"94","author":"D Milios","year":"2015","unstructured":"Milios, D., Gilmore, S.: Component aggregation for PEPA models: An approach based on approximate strong equivalence. Perform. Eval. 94, 43\u201371 (2015)","journal-title":"Perform. Eval."},{"issue":"9","key":"404_CR30","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1109\/TC.1982.1676110","volume":"31","author":"MK Molloy","year":"1982","unstructured":"Molloy, M.K.: Performance analysis using stochastic petri nets. IEEE Trans. Comput. 31(9), 913\u2013917 (1982)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"404_CR31","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/317786.317819","volume":"13","author":"B Plateau","year":"1985","unstructured":"Plateau, B.: On the stochastic structure of parallelism and synchronization models for distributed algorithms. SIGMETRICS Perf. Eval. Rev. 13(2), 147\u2013154 (1985)","journal-title":"SIGMETRICS Perf. Eval. Rev."},{"key":"404_CR32","doi-asserted-by":"crossref","unstructured":"Smith, M.J.A.: Compositional abstractions for long-run properties of stochastic systems. In: Eighth international conference on quantitative evaluation of systems, QEST 2011, 223\u2013232 (2011)","DOI":"10.1109\/QEST.2011.37"},{"key":"404_CR33","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1080\/15326348908807099","volume":"5","author":"U Sumita","year":"1989","unstructured":"Sumita, U., Rieders, M.: Lumpability and time-reversibility in the aggregation-disaggregation method for large Markov chains. Commun. Stat. Stoch. Models 5, 63\u201381 (1989)","journal-title":"Commun. Stat. Stoch. Models"},{"key":"404_CR34","doi-asserted-by":"crossref","unstructured":"Thomas, Nigel, Harrison, Peter\u00a0G.: Semi-product-form solution for PEPA models with functional rates. In Analytical and Stochastic Modelling Techniques and Applications - 20th International Conference, ASMTA 2013, volume 7984 of Lecture Notes in Computer Science, pages 416\u2013430, (2013)","DOI":"10.1007\/978-3-642-39408-9_29"},{"issue":"6","key":"404_CR35","doi-asserted-by":"publisher","first-page":"1531","DOI":"10.1137\/S0036139995293294","volume":"57","author":"AS Tomlin","year":"1997","unstructured":"Tomlin, A.S., Li, G., Rabitz, H., T\u00f3th, J.: The effect of lumping and expanding on kinetic differential equations. SIAM J. Appl. Math. 57(6), 1531\u20131556 (1997)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"404_CR36","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/322186.322196","volume":"27","author":"DF Towsley","year":"1980","unstructured":"Towsley, D.F.: Queuing network models with state-dependent routing. J. ACM 27(2), 323\u2013337 (1980)","journal-title":"J. ACM"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00404-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-021-00404-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00404-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T09:09:23Z","timestamp":1652519363000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-021-00404-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,21]]},"references-count":36,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["404"],"URL":"https:\/\/doi.org\/10.1007\/s00236-021-00404-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,21]]},"assertion":[{"value":"5 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}