- LSF ID
- 62659
- ORCID
- 0000-0001-8307-503X
- Sonstiges
- der Hochschule zugeordnete*r Autor*in
korrespondierende*r Autor*in
- LSF ID
- 60566
- ORCID
- 0000-0002-3240-0952
- Sonstiges
- der Hochschule zugeordnete*r Autor*in
- ORCID
- 0000-0003-4719-0772
- ORCID
- 0000-0003-3371-8564
- GND
- 1050396502
- LSF ID
- 15982
- ORCID
- 0000-0002-4193-2889
- Sonstiges
- der Hochschule zugeordnete*r Autor*in
Abstract in Englisch:
We introduce stochastic decision Petri nets (SDPNs), which are a form of stochastic Petri nets equipped with rewards and a control mechanism via the deactivation of controllable transitions. Such nets can be translated into Markov decision processes (MDPs), potentially leading to a combinatorial explosion in the number of states due to concurrency. Hence we restrict ourselves to instances where nets are either safe, free-choice and acyclic nets (SAFC nets) or even occurrence nets and policies are defined by a constant deactivation pattern. We obtain complexity-theoretic results for such cases via a close connection to Bayesian networks, in particular we show that for SAFC nets the question whether there is a policy guaranteeing a reward above a certain threshold is -complete. We also introduce a partial-order procedure which uses an SMT solver to address this problem.