Stochastic process discovery requires efficient procedures to compute the stochastic language emitted by a model. A natural approach consists in unfolding the underlying state-transition graph; however, for Stochastic Workflow Nets (SWN), this is severely hampered by silent transitions, which hinder scalability and may prevent termination in the presence of silent loops. Stochastic Process Trees (SPTs) were introduced as a more compact alternative, yet so far they have lacked semantics enabling exact, rather than simulation-based, language computation. We address this gap by defining a Markovian semantics for SPTs in terms of Labeled Absorbing Discrete-Time Markov Chains (LADTMCs), enabling exact language computation via DTMC unfolding while entirely bypassing the silent-loop issue. The resulting framework drastically reduces computational complexity and allows optimization engines to scale to large real-world event logs.

Exact Language Computation for Stochastic Process Trees via Discrete-Time Markov Chain Construction

Horváth, András
;
Ballarini, Paolo;
2026-01-01

Abstract

Stochastic process discovery requires efficient procedures to compute the stochastic language emitted by a model. A natural approach consists in unfolding the underlying state-transition graph; however, for Stochastic Workflow Nets (SWN), this is severely hampered by silent transitions, which hinder scalability and may prevent termination in the presence of silent loops. Stochastic Process Trees (SPTs) were introduced as a more compact alternative, yet so far they have lacked semantics enabling exact, rather than simulation-based, language computation. We address this gap by defining a Markovian semantics for SPTs in terms of Labeled Absorbing Discrete-Time Markov Chains (LADTMCs), enabling exact language computation via DTMC unfolding while entirely bypassing the silent-loop issue. The resulting framework drastically reduces computational complexity and allows optimization engines to scale to large real-world event logs.
2026
24th International Conference on Business Process Management, BPM 2026
can
2026
Lecture Notes in Computer Science
Springer Science and Business Media Deutschland GmbH
16936
166
183
9783032377760
9783032377777
Discrete-Time Markov Chains; Stochastic Languages; Stochastic Process Trees
Horváth, András; Ballarini, Paolo; Cry, Pierre
File in questo prodotto:
File Dimensione Formato  
CTMC_from_TSPT__DTMC_from_SPT__unfolding-17.pdf

Accesso aperto

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 666.08 kB
Formato Adobe PDF
666.08 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/2170034
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact