The 4C spectrum of fundamental behavioral relations for concurrent systems. (English) Zbl 1393.68123

Ciardo, Gianfranco (ed.) et al., Application and theory of Petri nets and concurrency. 35th international conference, PETRI NETS 2014, Tunis, Tunisia, June 23–27, 2014. Proceedings. Berlin: Springer (ISBN 978-3-319-07733-8/pbk). Lecture Notes in Computer Science 8489, 210-232 (2014).
Summary: The design of concurrent software systems, in particular process-aware information systems, involves behavioral modeling at various stages. Recently, approaches to behavioral analysis of such systems have been based on declarative abstractions defined as sets of behavioral relations. However, these relations are typically defined in an ad-hoc manner. In this paper, we address the lack of a systematic exploration of the fundamental relations that can be used to capture the behavior of concurrent systems, i.e., co-occurrence, conflict, causality, and concurrency. Besides the definition of the spectrum of behavioral relations, which we refer to as the 4C spectrum, we also show that our relations give rise to implication lattices. We further provide operationalizations of the proposed relations, starting by proposing techniques for computing relations in unlabeled systems, which are then lifted to become applicable in the context of labeled systems, i.e., systems in which state transitions have semantic annotations. Finally, we report on experimental results on efficiency of the proposed computations.
For the entire collection see [Zbl 1291.68014].


68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)


Full Text: DOI Link


[1] Winkler, S.: Information flow between requirement artifacts. Results of an empirical study. In: Sawyer, P., Heymans, P. (eds.) REFSQ 2007. LNCS, vol. 4542, pp. 232–246. Springer, Heidelberg (2007)
[2] Dumas, M., van der Aalst, W.M.P., ter Hofstede, A.H.M.: Process-Aware Information Systems: Bridging People and Software Through Process Technology. Wiley (2005)
[3] ter Hofstede, A.H.M., van der Aalst, W.M.P., Adams, M., Russell, N. (eds.): Modern Business Process Automation – YAWL and its Support Environment. Springer (2010)
[4] Sassone, V., Nielsen, M., Winskel, G.: Models for concurrency: Towards a classification. TCS 170(1-2), 297–348 (1996) · Zbl 0874.68120
[5] Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press (2008) · Zbl 1179.68076
[6] Reisig, W.: Elements of Distributed Algorithms: Modeling and Analysis with Petri Nets. Springer (1998) · Zbl 0907.68130
[7] Object Management Group (OMG): Unified Modeling Language: Superstructure. Version 2.1.2. Technical report (November 2007)
[8] Hack, M.: Decidability Questions for Petri Nets. Outstanding Dissertations in the Computer Sciences. Garland Publishing, New York (1975)
[9] Nielsen, M., Plotkin, G.D., Winskel, G.: Petri nets, event structures and domains, Part I. TCS 13, 85–108 (1981) · Zbl 0452.68067
[10] Weidlich, M., van der Werf, J.M.: On profiles and footprints – relational semantics for Petri nets. In: Haddad, S., Pomello, L. (eds.) PETRI NETS 2012. LNCS, vol. 7347, pp. 148–167. Springer, Heidelberg (2012) · Zbl 1358.90067
[11] Dunham, M.H.: Data Mining: Introductory and Advanced Topics. Prentice-Hall (2002)
[12] Dijkman, R.M., La Rosa, M., Reijers, H.A.: Managing large collections of business process models – current techniques and challenges. Computers in Industry 63(2), 91–97 (2012)
[13] Petri, C.A.: Non-Sequential Processes. ISF, GMD (1977)
[14] ter Hofstede, A.H.M., Ouyang, C., La Rosa, M., Song, L., Wang, J., Polyvyanyy, A.: APQL: A process-model query language. In: Song, M., Wynn, M.T., Liu, J. (eds.) AP-BPM 2013. LNBIP, vol. 159, pp. 23–38. Springer, Heidelberg (2013)
[15] Polyvyanyy, A., La Rosa, M., ter Hofstede, A.H.M.: Indexing and efficient instance-based retrieval of process models using untanglings. In: Jarke, M., Mylopoulos, J., Quix, C., Rolland, C., Manolopoulos, Y., Mouratidis, H., Horkoff, J. (eds.) CAiSE 2014. LNCS, vol. 8484, pp. 439–456. Springer, Heidelberg (2014) · Zbl 06414212
[16] Kunze, M., Weidlich, M., Weske, M.: Behavioral similarity – A proper metric. In: Rinderle-Ma, S., Toumani, F., Wolf, K. (eds.) BPM 2011. LNCS, vol. 6896, pp. 166–181. Springer, Heidelberg (2011) · Zbl 05974869
[17] van Dongen, B.F., Dijkman, R., Mendling, J.: Measuring similarity between business process models. In: Bellahsène, Z., Léonard, M. (eds.) CAiSE 2008. LNCS, vol. 5074, pp. 450–464. Springer, Heidelberg (2008) · Zbl 05291109
[18] Zha, H., Wang, J., Wen, L., Wang, C., Sun, J.: A workflow net similarity measure based on transition adjacency relations. Computers in Industry 61(5), 463–471 (2010)
[19] Goltz, U., Reisig, W.: The non-sequential behavior of Petri nets. IANDC 57(2/3) (1983) · Zbl 0551.68050
[20] Desel, J.: Validation of process models by construction of process nets. In: van der Aalst, W.M.P., Desel, J., Oberweis, A. (eds.) Business Process Management. LNCS, vol. 1806, pp. 110–128. Springer, Heidelberg (2000)
[21] Mayr, E.W.: Persistence of vector replacement systems is decidable. Acta Inf. 15, 309–318 (1981) · Zbl 0454.68048
[22] Kosaraju, S.R.: Decidability of reachability in vector addition systems (preliminary version). In: STOC, pp. 267–281. ACM (1982)
[23] Rackoff, C.: The covering and boundedness problems for vector addition systems. TCS 6, 223–231 (1978) · Zbl 0368.68054
[24] Escrig, D.F.: Decidability of home states in place transition systems, Internal Report. Dpto. Informatica y Automatica. Univ. Complutense de Madrid (1986)
[25] Best, E., Devillers, R.R., Kiehn, A., Pomello, L.: Concurrent bisimulations in Petri nets. Acta Inf. 28(3), 231–264 (1991) · Zbl 0718.68034
[26] Polyvyanyy, A., Weidlich, M.: Towards a compendium of process technologies: The jBPT library for process model analysis. In: CAiSE Forum. CEUR, vol. 998 (2013)
[27] Fahland, D., Favre, C., Koehler, J., Lohmann, N., Völzer, H., Wolf, K.: Analysis on demand: Instantaneous soundness checking of industrial business process models. DKE (5), 448–466 (2011)
[28] van der Aalst, W.M.P.: Verification of workflow nets. In: Azéma, P., Balbo, G. (eds.) ICATPN 1997. LNCS, vol. 1248, pp. 407–426. Springer, Heidelberg (1997)
[29] van der Aalst, W.M.P., Pesic, M.: DecSerFlow: Towards a truly declarative service flow language. In: Bravetti, M., Núñez, M., Zavattaro, G. (eds.) WS-FM 2006. LNCS, vol. 4184, pp. 1–23. Springer, Heidelberg (2006)
[30] Meseguer, J., Talcott, C.: A partial order event model for concurrent objects. In: Baeten, J.C.M., Mauw, S. (eds.) CONCUR 1999. LNCS, vol. 1664, pp. 415–430. Springer, Heidelberg (1999) · Zbl 0939.68084
[31] van der Aalst, W.M.P.: Process Mining – Discovery, Conformance and Enhancement of Business Processes. Springer (2011) · Zbl 1216.68016
[32] van der Aalst, W.M.P., Weijters, T., Maruster, L.: Workflow mining: Discovering process models from event logs. TKDE 16(9), 1128–1142 (2004)
[33] Weidlich, M., Polyvyanyy, A., Desai, N., Mendling, J., Weske, M.: Process compliance analysis based on behavioural profiles. IS 36(7), 1009–1025 (2011) · Zbl 1234.68312
[34] Weidlich, M., Mendling, J., Weske, M.: Propagating changes between aligned process models. JSS 85(8), 1885–1898 (2012)
[35] Kindler, E., van der Aalst, W.M.P.: Liveness, fairness, and recurrence in Petri nets. IPL 70(6), 269–274 (1999) · Zbl 0953.68575
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.