--- res: bibo_abstract: - Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) are two standard formalisms in system analysis. Their main associated quantitative objectives are hitting probabilities, discounted sum, and mean payoff. Although there are many techniques for computing these objectives in general MCs/MDPs, they have not been thoroughly studied in terms of parameterized algorithms, particularly when treewidth is used as the parameter. This is in sharp contrast to qualitative objectives for MCs, MDPs and graph games, for which treewidth-based algorithms yield significant complexity improvements. In this work, we show that treewidth can also be used to obtain faster algorithms for the quantitative problems. For an MC with n states and m transitions, we show that each of the classical quantitative objectives can be computed in O((n+m)⋅t2) time, given a tree decomposition of the MC with width t. Our results also imply a bound of O(κ⋅(n+m)⋅t2) for each objective on MDPs, where κ is the number of strategy-iteration refinements required for the given input and objective. Finally, we make an experimental evaluation of our new algorithms on low-treewidth MCs and MDPs obtained from the DaCapo benchmark suite. Our experiments show that on low-treewidth MCs and MDPs, our algorithms outperform existing well-established methods by one or more orders of magnitude.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Ali foaf_name: Asadi, Ali foaf_surname: Asadi - foaf_Person: foaf_givenName: Krishnendu foaf_name: Chatterjee, Krishnendu foaf_surname: Chatterjee foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-4561-241X - foaf_Person: foaf_givenName: Amir Kafshdar foaf_name: Goharshady, Amir Kafshdar foaf_surname: Goharshady foaf_workInfoHomepage: http://www.librecat.org/personId=391365CE-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-1702-6584 - foaf_Person: foaf_givenName: Kiarash foaf_name: Mohammadi, Kiarash foaf_surname: Mohammadi - foaf_Person: foaf_givenName: Andreas foaf_name: Pavlogiannis, Andreas foaf_surname: Pavlogiannis foaf_workInfoHomepage: http://www.librecat.org/personId=49704004-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-8943-0722 bibo_doi: 10.1007/978-3-030-59152-6_14 bibo_volume: 12302 dct_date: 2020^xs_gYear dct_identifier: - UT:000723555700014 dct_isPartOf: - http://id.crossref.org/issn/0302-9743 - http://id.crossref.org/issn/1611-3349 - http://id.crossref.org/issn/9783030591519 dct_language: eng dct_publisher: Springer Nature@ dct_title: Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth@ ...