License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2023.14
URN: urn:nbn:de:0030-drops-190089
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19008/
Go to the corresponding LIPIcs Volume Portal

Finkel, Alain ; Haddad, Serge ; Ye, Lina

About Decisiveness of Dynamic Probabilistic Models

pdf-format:
LIPIcs-CONCUR-2023-14.pdf (0.8 MB)

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 upward-closed 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:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19008},
  URN =		{urn:nbn:de:0030-drops-190089},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI