Графовые паттерны в несогласованных декларативных моделях процессов

Моделирование и анализ информационных систем. 2026. Т. 33. № 2. С. 176–205.

Анненков А. Н., Нестеров Р. А.

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

Ключевые слова: интеллектуальный анализ процессов, process mining, declarative process models, inconsistency analysis, task entailment graph, minimal inconsistent subsets, structural witnesses, декларативные модели процессов, анализ несогласованности, граф следования задач, минимальные несогласованные подмножества, структурные свидетели

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Новые методы в исследовании формальных моделей вычислений, компьютерных систем и смежных задач теоретической информатики (2025)