Abstract
Decisiveness of infinite Markov chains with respect to some (finite or infinite) target set of states is a key property that allows to compute the reachability probability of this set up to an arbitrary precision. Most of the existing works assume constant weights for defining the probability of a transition in the considered models. However numerous probabilistic modelings require the (dynamic) weight to also depend on the current state. So we introduce a dynamic probabilistic version of counter machine (pCM). After establishing that decisiveness is undecidable for pCMs even with constant weights, we study the decidability of decisiveness for subclasses of pCM. We show that, without restrictions on dynamic weights, decisiveness is undecidable with a single state and single counter pCM. On the contrary with polynomial weights, decisiveness becomes decidable for single counter pCMs under mild conditions. Then we show that decisiveness of probabilistic Petri nets (pPNs) with polynomial weights is undecidable even when the target set is upwardclosed unlike the case of constant weights. Finally we prove that the standard subclass of pPNs with a regular language is decisive with respect to a finite set whatever the kind of weights.
BibTeX  Entry
@InProceedings{finkel_et_al:LIPIcs.CONCUR.2023.14,
author = {Finkel, Alain and Haddad, Serge and Ye, Lina},
title = {{About Decisiveness of Dynamic Probabilistic Models}},
booktitle = {34th International Conference on Concurrency Theory (CONCUR 2023)},
pages = {14:114:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772990},
ISSN = {18688969},
year = {2023},
volume = {279},
editor = {P\'{e}rez, Guillermo A. and Raskin, JeanFran\c{c}ois},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19008},
URN = {urn:nbn:de:0030drops190089},
doi = {10.4230/LIPIcs.CONCUR.2023.14},
annote = {Keywords: infinite Markov chain, reachability probability, decisiveness}
}
Keywords: 

infinite Markov chain, reachability probability, decisiveness 
Collection: 

34th International Conference on Concurrency Theory (CONCUR 2023) 
Issue Date: 

2023 
Date of publication: 

07.09.2023 