Discovering block-structured process models from event logs : a constructive approach

S.J.J. Leemans; D. Fahland; W.M.P. Aalst, van der

doi:10.1007/978-3-642-38697-8_17

Discovering block-structured process models from event logs : a constructive approach

S.J.J. Leemans, D. Fahland, W.M.P. Aalst, van der

Process Analytics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

450 Citations (Scopus)

1 Downloads (Pure)

Abstract

Process discovery is the problem of, given a log of observed behaviour, finding a process model that ‘best’ describes this behaviour. A large variety of process discovery algorithms has been proposed. However, no existing algorithm guarantees to return a fitting model (i.e., able to reproduce all observed behaviour) that is sound (free of deadlocks and other anomalies) in finite time. We present an extensible framework to discover from any given log a set of block-structured process models that are sound and fit the observed behaviour. In addition we characterise the minimal information required in the log to rediscover a particular process model. We then provide a polynomial-time algorithm for discovering a sound, fitting, block-structured model from any given log; we give sufficient conditions on the log for which our algorithm returns a model that is language-equivalent to the process model underlying the log, including unseen behaviour. The technique is implemented in a prototypical tool.

Original language	English
Title of host publication	Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings)
Editors	J.M. Colom, J. Desel
Place of Publication	Berlin
Publisher	Springer
Pages	311-329
ISBN (Print)	978-3-642-38696-1
DOIs	https://doi.org/10.1007/978-3-642-38697-8_17
Publication status	Published - 2013
Event	34th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2013), June 24-28, 2013, Milan, Italy - Milan, Italy Duration: 24 Jun 2013 → 28 Jun 2013 http://www.mc3.disco.unimib.it/petrinets2013/

Publication series

Name	Lecture Notes in Computer Science
Volume	7927
ISSN (Print)	0302-9743

Conference

Conference	34th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2013), June 24-28, 2013, Milan, Italy
Abbreviated title	Petri Nets 2013
Country/Territory	Italy
City	Milan
Period	24/06/13 → 28/06/13
Internet address	http://www.mc3.disco.unimib.it/petrinets2013/

Access to Document

10.1007/978-3-642-38697-8_17

Cite this

Leemans, S. J. J., Fahland, D., & Aalst, van der, W. M. P. (2013). Discovering block-structured process models from event logs : a constructive approach. In J. M. Colom, & J. Desel (Eds.), Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings) (pp. 311-329). (Lecture Notes in Computer Science; Vol. 7927). Springer. https://doi.org/10.1007/978-3-642-38697-8_17

Leemans, S.J.J. ; Fahland, D. ; Aalst, van der, W.M.P. / Discovering block-structured process models from event logs : a constructive approach. Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings). editor / J.M. Colom ; J. Desel. Berlin : Springer, 2013. pp. 311-329 (Lecture Notes in Computer Science).

@inproceedings{444985afdb154b1dafb2c7b5fd63adb6,

title = "Discovering block-structured process models from event logs : a constructive approach",

abstract = "Process discovery is the problem of, given a log of observed behaviour, finding a process model that {\textquoteleft}best{\textquoteright} describes this behaviour. A large variety of process discovery algorithms has been proposed. However, no existing algorithm guarantees to return a fitting model (i.e., able to reproduce all observed behaviour) that is sound (free of deadlocks and other anomalies) in finite time. We present an extensible framework to discover from any given log a set of block-structured process models that are sound and fit the observed behaviour. In addition we characterise the minimal information required in the log to rediscover a particular process model. We then provide a polynomial-time algorithm for discovering a sound, fitting, block-structured model from any given log; we give sufficient conditions on the log for which our algorithm returns a model that is language-equivalent to the process model underlying the log, including unseen behaviour. The technique is implemented in a prototypical tool.",

author = "S.J.J. Leemans and D. Fahland and {Aalst, van der}, W.M.P.",

year = "2013",

doi = "10.1007/978-3-642-38697-8_17",

language = "English",

isbn = "978-3-642-38696-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "311--329",

editor = "J.M. Colom and J. Desel",

booktitle = "Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings)",

address = "Germany",

note = "34th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2013), June 24-28, 2013, Milan, Italy, Petri Nets 2013 ; Conference date: 24-06-2013 Through 28-06-2013",

url = "http://www.mc3.disco.unimib.it/petrinets2013/",

}

Leemans, SJJ, Fahland, D & Aalst, van der, WMP 2013, Discovering block-structured process models from event logs : a constructive approach. in JM Colom & J Desel (eds), Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings). Lecture Notes in Computer Science, vol. 7927, Springer, Berlin, pp. 311-329, 34th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2013), June 24-28, 2013, Milan, Italy, Milan, Italy, 24/06/13. https://doi.org/10.1007/978-3-642-38697-8_17

Discovering block-structured process models from event logs : a constructive approach. / Leemans, S.J.J.; Fahland, D.; Aalst, van der, W.M.P.
Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings). ed. / J.M. Colom; J. Desel. Berlin: Springer, 2013. p. 311-329 (Lecture Notes in Computer Science; Vol. 7927).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Discovering block-structured process models from event logs : a constructive approach

AU - Leemans, S.J.J.

AU - Fahland, D.

AU - Aalst, van der, W.M.P.

PY - 2013

Y1 - 2013

N2 - Process discovery is the problem of, given a log of observed behaviour, finding a process model that ‘best’ describes this behaviour. A large variety of process discovery algorithms has been proposed. However, no existing algorithm guarantees to return a fitting model (i.e., able to reproduce all observed behaviour) that is sound (free of deadlocks and other anomalies) in finite time. We present an extensible framework to discover from any given log a set of block-structured process models that are sound and fit the observed behaviour. In addition we characterise the minimal information required in the log to rediscover a particular process model. We then provide a polynomial-time algorithm for discovering a sound, fitting, block-structured model from any given log; we give sufficient conditions on the log for which our algorithm returns a model that is language-equivalent to the process model underlying the log, including unseen behaviour. The technique is implemented in a prototypical tool.

AB - Process discovery is the problem of, given a log of observed behaviour, finding a process model that ‘best’ describes this behaviour. A large variety of process discovery algorithms has been proposed. However, no existing algorithm guarantees to return a fitting model (i.e., able to reproduce all observed behaviour) that is sound (free of deadlocks and other anomalies) in finite time. We present an extensible framework to discover from any given log a set of block-structured process models that are sound and fit the observed behaviour. In addition we characterise the minimal information required in the log to rediscover a particular process model. We then provide a polynomial-time algorithm for discovering a sound, fitting, block-structured model from any given log; we give sufficient conditions on the log for which our algorithm returns a model that is language-equivalent to the process model underlying the log, including unseen behaviour. The technique is implemented in a prototypical tool.

U2 - 10.1007/978-3-642-38697-8_17

DO - 10.1007/978-3-642-38697-8_17

M3 - Conference contribution

SN - 978-3-642-38696-1

T3 - Lecture Notes in Computer Science

SP - 311

EP - 329

BT - Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings)

A2 - Colom, J.M.

A2 - Desel, J.

PB - Springer

CY - Berlin

T2 - 34th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2013), June 24-28, 2013, Milan, Italy

Y2 - 24 June 2013 through 28 June 2013

ER -

Leemans SJJ, Fahland D, Aalst, van der WMP. Discovering block-structured process models from event logs : a constructive approach. In Colom JM, Desel J, editors, Application and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings). Berlin: Springer. 2013. p. 311-329. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-38697-8_17

Discovering block-structured process models from event logs : a constructive approach

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this