maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2026-2-176-205mais-2092Research ArticleTheory of ComputingГрафовые паттерны в несогласованных декларативных моделях процессовGraph-based patterns in inconsistent declarative process modelshttps://orcid.org/0009-0007-4682-5226АнненковАлексей НиколаевичAnnenkovAleksei N.alniannenkov@edu.hse.ruhttps://orcid.org/0000-0002-4162-9070НестеровРоман АлександровичNesterovRoman A.rnesterov@hse.ruНациональный исследовательский университет «Высшая школа экономики»РоссияNational Research University Higher School of EconomicsRussian Federation202618062026332176205Copyright © Анненков А.Н., Нестеров Р.А., 20262026Анненков А.Н., Нестеров Р.А.Annenkov A.N., Nesterov R.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/2092

Декларативные модели процессов широко используются в process mining для гибкого описания поведения процессов с помощью наборов ограничений. Однако модели, автоматически извлекаемые из журналов событий, могут содержать несогласованные ограничения, что затрудняет их интерпретацию и делает их непригодными для исполнения, проверки соответствия или дальнейшего анализа. Существующие методы анализа согласованности либо опираются на автоматные конструкции с высокой асимптотической сложностью в худшем случае, либо используют эвристики, ориентированные на минимальные несогласованные подмножества (MIS), которые не дают полного формального описания обнаруживаемых ими паттернов несогласованности. В данной работе предлагается графовый подход к анализу несогласованности для ограниченного фрагмента языка Declare. Мы представляем зависимости между ограничениями с помощью графа следования задач и характеризуем несогласованность посредством трёх типов структурных свидетелей. На основе этого описания мы сначала выявляем кандидаты в несогласованные подмножества, а затем проверяем, является ли кандидат минимальным несогласованным подмножеством, с помощью специализированных процедур верификации. В отличие от подходов, основанных на автоматах, предлагаемый метод избегает явного построения произведений автоматов и вместо этого опирается на графовый анализ и конструктивное построение трасс. Мы реализовали предложенный подход и провели его экспериментальную оценку на реальных журналах событий, показав, что он практически применим и обеспечивает конкурентоспособное время работы.

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.

интеллектуальный анализ процессовдекларативные модели процессованализ несогласованностиграф следования задачминимальные несогласованные подмножестваструктурные свидетелиprocess miningdeclarative process modelsinconsistency analysistask entailment graphminimal inconsistent subsetsstructural witnessesНИУ ВШЭ (HSE-BR-2025-024)HSE University (HSE-BR-2025-024)ReferencesW. M. P. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer, 2011.W. M. P. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer, 2011.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.C. D. Ciccio and M. Montali, “Declarative Process Specifications,” in Process Mining Handbook, Springer, 2022, pp. 119–147.C. D. Ciccio and M. Montali, “Declarative Process Specifications,” in Process Mining Handbook, Springer, 2022, pp. 119–147.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.

The authors declare that there are no conflicts of interest present.