Abstract
This paper considers the problem of comparing process models in terms of their behavior. Given two process models, the problem addressed is that of explaining their differences in terms of simple and intuitive statements. This model differencing operation is needed for example in the context of process consolidation, where analysts need to reconcile differences between process variants in order to produce consolidated process models. The paper presents an approach to acyclic process model differencing based on event structures. First the paper considers the use of prime event structures. It is found that the high level of node duplication inherent to prime event structures hinders on the usefulness of the difference diagnostics that can be extracted thereon. Accordingly, the paper defines a method for producing (asymmetric) event structures with reduced duplication.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Weidlich, M., Mendling, J., Weske, M.: Efficient Consistency Measurement Based on Behavioral Profiles of Process Models. IEEE Transactions on Software Engineering and Methodology 37(3), 410–429 (2011)
Weidlich, M., Mendling, J., Weske, M.: A Foundational Approach for Managing Process Variability. In: Mouratidis, H., Rolland, C. (eds.) CAiSE 2011. LNCS, vol. 6741, pp. 267–282. Springer, Heidelberg (2011)
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)
Baldan, P., Corradini, A., Montanari, U.: Contextual Petri Nets, Asymmetric Event Structures, and Processes. Information and Computation 171(1), 1–49 (2001)
Dijkman, R., Dumas, M., van Dongen, B., Käärik, R., Mendling, J.: Similarity of business process models: Metrics and evaluation. Information Systems 36(2), 498–516 (2011)
Dumas, M., García-Bañuelos, L., Dijkman, R.: Similarity Search of Business Process Models. IEEE Data Engineering Bulletin 32(3), 23–28 (2009)
van Glabbeek, R., Goltz, U.: Refinement of actions and equivalence notions for concurrent systems. Acta Informatica 37, 229–327 (2001)
Cleaveland, R.: On automatically explaining bisimulation inequivalence. In: Clarke, E., Kurshan, R.P. (eds.) CAV 1990. LNCS, vol. 531, pp. 364–372. Springer, Heidelberg (1991)
Sokolsky, O., Kannan, S., Lee, I.: Simulation-Based Graph Similarity. In: Hermanns, H., Palsberg, J. (eds.) TACAS 2006. LNCS, vol. 3920, pp. 426–440. Springer, Heidelberg (2006)
Dijkman, R.: Diagnosing Differences between Business Process Models. In: Dumas, M., Reichert, M., Shan, M.-C. (eds.) BPM 2008. LNCS, vol. 5240, pp. 261–277. Springer, Heidelberg (2008)
Weidlich, M., Polyvyanyy, A., Mendling, J., Weske, M.: Causal Behavioural Profiles - Efficient Computation, Applications, and Evaluation. Fundamenta Informaticae 113(3-4), 399–435 (2011)
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)
van der Aalst, W.M.P., Weijters, T., Maruster, L.: Workflow mining: discovering process models from event logs. IEEE Transactions on Knowledge and Data Engineering 16(9), 1128–1142 (2004)
Badouel, E.: On the α-Reconstructibility of Workflow Nets. In: Haddad, S., Pomello, L. (eds.) PETRI NETS 2012. LNCS, vol. 7347, pp. 128–147. Springer, Heidelberg (2012)
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)
Polyvyany, A., García-Bañuelos, L., Dumas, M.: Structuring acyclic process models. Information Systems 37(6), 518–538 (2012)
Polyvyanyy, A., García-Bañuelos, L., Fahland, D., Weske, M.: Maximal Structuring of Acyclic Process Models. The Computer Journal (to appear)
Polyvyanyy, A.: Structuring Process Models. PhD thesis, University of Potsdam, Germany (2012)
Engelfriet, J.: Branching processes of Petri nets. Acta Informatica 28, 575–591 (1991)
Nielsen, M., Plotkin, G.D., Winskel, G.: Petri Nets, Event Structures and Domains, Part I. Theoretical Computer Science 13, 85–108 (1981)
Best, E., Devillers, R., Kiehn, A., Pomello, L.: Concurrent bisimulations in Petri nets. Acta Informatica 28, 231–264 (1991)
Fahland, D.: From Scenarios to Components. PhD thesis, Humboldt-Universität zu Berlin (2010)
Fahland, D., van der Aalst, W.: Simplifying Mined Process Models: An Approach Based on Unfoldings. In: Rinderle-Ma, S., Toumani, F., Wolf, K. (eds.) BPM 2011. LNCS, vol. 6896, pp. 362–378. Springer, Heidelberg (2011)
Boudol, G., Castellani, I.: Flow Models of Distributed Computations: Event Structures and Nets. Technical Report 1482, INRIA Sophia-Antipolis (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Armas-Cervantes, A., García-Bañuelos, L., Dumas, M. (2013). Event Structures as a Foundation for Process Model Differencing, Part 1: Acyclic processes. In: ter Beek, M.H., Lohmann, N. (eds) Web Services and Formal Methods. WS-FM 2012. Lecture Notes in Computer Science, vol 7843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38230-7_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-38230-7_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38229-1
Online ISBN: 978-3-642-38230-7
eBook Packages: Computer ScienceComputer Science (R0)