Graph-based patterns in inconsistent declarative process models

Declarative process models are widely used in process mining to describe flexible process behavior through sets of constraints. However, models discovered automatically from event logs may contain inconsistent constraints, which can make them difficult to interpret and unusable for execution, conformance checking, or further analysis. Existing methods for consistency analysis either rely on automata-based constructions with high worst-case time complexity or use heuristics based on MIS (minimal inconsistent subsets) that do not provide a full formal characterization of the inconsistency patterns they detect. In this paper, we propose a graph-based approach to the inconsistency analysis for a restricted fragment of Declare process modeling language. We represent dependencies between constraints through the task entailment graph and characterize inconsistency by means of three structural witness types. Based on this characterization, we first detect candidate inconsistent subsets and then verify whether a candidate is a minimal inconsistent subset by dedicated verification procedures. In contrast to automata-based approaches, the proposed method avoids explicit automata products and relies instead on graph-based analysis and constructive trace arguments. We implement the proposed approach and evaluate it on real-life event logs, showing that it is practically feasible and achieves competitive runtime.

1. W. M. P. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer, 2011.

2. W. M. P. van der Aalst, M. L. Rosa, and F. M. Santoro, “Business Process Management,” Business & Information Systems Engineering, vol. 58, no. 1, pp. 1–6, 2016.

3. M. Pesic, H. Schonenberg, and W. M. P. van der Aalst, “Declare: Full Support for Loosely-Structured Processes,” in Proceedings of the 11th IEEE International Enterprise Distributed Object Computing Conference (EDOC), 2007, pp. 287–300.

4. W. M. P. van der Aalst, M. Pesic, and H. Schonenberg, “Declarative Workflows: Balancing between Flexibility and Support,” Computer Science - Research and Development, vol. 23, no. 2, pp. 99–113, 2009.

5. F. M. Maggi, R. P. J. C. Bose, and W. M. P. van der Aalst, “Efficient Discovery of Understandable Declarative Process Models from Event Logs,” in Proceedings of the International Conference on Advanced Information Systems Engineering, 2012, pp. 270–285.

6. C. D. Ciccio and M. Mecella, “On the Discovery of Declarative Control Flows for Artful Processes,” ACM Transactions on Management Information Systems, vol. 5, no. 4, pp. 24:1–24:37, 2015.

7. C. D. Ciccio, F. M. Maggi, M. Montali, and J. Mendling, “Resolving Inconsistencies and Redundancies in Declarative Process Models,” Information Systems, vol. 64, pp. 425–443, 2017.

8. C. Corea, M. Deisen, and P. Delfmann, “Resolving Inconsistencies in Declarative Process Models Based on Culpability Measurement,” in Proceedings of the 14th International Conference on Wirtschaftsinformatik (WI), 2019, pp. 1–16.

9. A. P. Sistla and E. M. Clarke, “The Complexity of Propositional Linear Temporal Logics,” Journal of the ACM, vol. 32, no. 3, pp. 733–749, 1985.

10. C. Corea, J. Grant, and M. Thimm, “Measuring inconsistency in declarative process specifications,” in Proceedings of the International Conference on Business Process Management, 2022, pp. 289–306.

11. A. Hunter and S. Konieczny, “Measuring Inconsistency through Minimal Inconsistent Sets,” in Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), 2008, pp. 358–366.

12. C. D. Ciccio and M. Montali, “Declarative Process Specifications,” in Process Mining Handbook, Springer, 2022, pp. 119–147.

13. F. M. Maggi, M. Westergaard, M. Montali, and W. M. P. van der Aalst, “Runtime Verification of LTL-Based Declarative Process Models,” in Runtime Verification, in Lecture Notes in Computer Science, vol. 7186. 2012, pp. 131–146.

14. M. de Leoni, F. M. Maggi, and W. M. P. van der Aalst, “Aligning Event Logs and Declarative Process Models for Conformance Checking,” in Business Process Management, in Lecture Notes in Computer Science, vol. 7481. Springer, 2012, pp. 82–97.

15. M. Montali, F. Chesani, P. Mello, and F. M. Maggi, “Towards Data-Aware Constraints in Declare,” in Proceedings of the 28th Annual ACM Symposium on Applied Computing, 2013, pp. 1391–1396.

16. D. Borrego and I. Barba, “Conformance Checking and Diagnosis for Declarative Business Process Models in Data-Aware Scenarios,” Expert Systems with Applications, vol. 41, no. 11, pp. 5340–5352, 2014.

17. A. Burattin, F. M. Maggi, and A. Sperduti, “Conformance Checking Based on Multi-Perspective Declarative Process Models,” Expert Systems with Applications, vol. 65, pp. 194–211, 2016.

18. G. D. Giacomo, R. D. Masellis, M. Grasso, F. M. Maggi, and M. Montali, “Monitoring Business Metaconstraints Based on LTL and LDL for Finite Traces,” in Business Process Management, in Lecture Notes in Computer Science, vol. 8659. 2014, pp. 1–17.

19. A. Alman, C. D. Ciccio, D. Haas, F. M. Maggi, and J. Mendling, “Rule Mining in Action: The RuM Toolkit,” in Proceedings of the ICPM Doctoral Consortium and Tool Demonstration Track 2020, in CEUR Workshop Proceedings, vol. 2703. 2020, pp. 51–54.

20. I. Donadello, F. Riva, F. M. Maggi, and A. Shikhizada, “Declare4Py: A Python Library for Declarative Process Mining,” in BPM 2022 Demos & Resources Forum, in CEUR Workshop Proceedings, vol. 3216. 2022, pp. 117–121.

21. I. Kuhlmann, C. Corea, and J. Grant, “An ASP-Based Framework for Solving Problems Related to Declarative Process Specifications,” in Proceedings of the 21st International Workshop on Nonmonotonic Reasoning, 2023, pp. 129–132.

22. N. Sch"utzenmeier, M. K"appel, L. Ackermann, S. Jablonski, and S. Petter, “Automaton-Based Comparison of Declare Process Models,” Software and Systems Modeling, vol. 22, pp. 667–685, 2023.