• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Synthesis and analysis of process models

Priority areas of development: engineering science
2017
The project has been carried out as part of the HSE Program of Fundamental Studies.

Goal of research:

The goal of the research is development of new methods for modeling and analysis of sequential programs and distributed information systems, including development of new approaches for the analysis of information system behavior based on event logs.

Methodology:

The basics of discrete mathematics, theory of finite state machines (including transducers), temporal logic, and abstract algebra were used for modeling and analysis of sequential programs. Temporal logic, the theory of Petri nets and finite state machines, process mining techniques were used for modeling and analysis of distributed system behavior.

Empirical base of research:

The empirical base of research is represented by sequential programs, distributed systems, and event logs of information systems.

Results of research:

In the field of sequential program analysis we obtained the following results:

The algorithmic undecidability of the satisfiability of FL-LTL logic formulas on finite state machines-transducers, operating over free commutative semigroup and Abelian groups, was proven.

It was proven that the minimization of the first-order program schemata, provided that the logic-thermal equivalence is preserved, is algorithmically solvable. An exhaustive search algorithm, based on the verification procedure of the logical-thermal equivalence of the first-order program schemata, was proposed.

It was shown that the first-order program schemata supplied with logical-thermal equivalence and finite state deterministic transducers operating over substitutions are mutually translated into each other.

In the field of modeling and analysis of distributed systems the following results were obtained:

An overview and classification of resource equivalence relations on Petri net markings is presented. Resources are defined as a part of a Petri net marking. Two resources are equivalent if and only if replacing one of them by another in any Petri net marking does not change the observable net behavior. Several types of resource equivalence are studied. It is shown that all of them can be finitely represented. Classification of resource equivalences with respect to their decidability and approximability is done.

The study on controlling Petri net behavior using priority and time constraints was continued. Controlling here means forcing a process to behave in a stable way by associating priorities, or time intervals to transitions. Earlier we have developed a partial algorithm for computing transition priorities by constructing a spin-based coverability tree. These priorities ensure liveness and safety of the net. In 2017 the algorithm was enhanced, and its applicability was extended. We have also proved decidability of a problem of finding priorities for transforming a live, but unbounded Petri net into a live and bounded net with the same structure.

Well-structured transition systems (WSTS) became a well-known tool in the study of concurrency systems for proving decidability of properties based on coverability and boundedness. The tool for behavioral analysis of such systems was developed. Two most studied algorithms for analysis of well-structured transition systems behavior (backward reachability and the Finite Reachability Tree analyses) have been implemented. The WSTSL language is developed to store and define well-structured transition systems.

In the process mining field the following results were obtained:

A real-time temporal logic was developed, suitable for formalization and formal verification of correctness requirements for event logs generated by a distributed system. Events contain a timestamp (a time when an event took place), an identifier of a sender, and a relation to other system components.

To synthesize models for multi-agent systems from event logs, a compositional approach has been suggested.

A system event log is filtered by agents. After that, agent models (in the form of Petri nets) are synthesized from filtered agent event logs. Agent interaction is also described using a Petri net called an interface. Agent models are composed via special constructs on Petri nets – morphisms. They also provide composition correctness – compositional system model inherits agent deadlock-freeness and proper termination. Interface patterns, which can be used for typical interactions, have been suggested. The preliminary experiment results on using the simple causality pattern for compositional synthesis of models for multi-agent systems have shown a significant increase in model quality, i.e. in structuredness and precision estimations.

An algorithm for discovering high-level acyclic process models from event logs and some specified partition of low-level events into subsets associated with abstract events in a high-level model is developed. Events in a high-level model are abstract events, which can be refined to low-level subprocesses, whose behavior is recorded in event logs. It is proved, that the algorithm ensures perfect fitness between the constructed high-level model and a given low-level event log.

A novel method for discovering BPMN (Business Process Model and Notation) was developed. This method allows mining hierarchical business process models with data and resource perspectives at each level of granularity.

A method for synthesizing „hybrid“ UML diagrams (a newly proposed extension of the UML standard) from event logs of service-oriented information systems was developed and implemented. Unlike the previously proposed hierarchical sequence diagrams, hybrid diagrams include different types of diagrams (sequence, activity and collaboration) for the most convenient representation of a SOA system's behavior in different perspectives.

Algorithms for the local repair of process models using information from event logs were developed. These algorithms use maximum decomposition to reduce the size of a given process model.

A novel method for the generation of event logs from BPMN models was developed. This method was implemented and verified on a variety of BPMN models from different domains.

An algorithm for finding a minimal graph edit distance between two graphs was adapted for the comparison of BPMN models. This algorithm was implemented and verified on BPMN models discovered from event logs of an e-government information system.

A novel effective technique for finding subtraces in traces of an event log was developed on the basis of the classical Aho-Corasick approach. This technique allows for searching in several traces simultaneously. It was implemented and tested on real-life event logs.

Level of implementation, recommendations on implementation or outcomes of the implementation of the results:

The proposed methods are focused on the possibility of their practical application. Methods for the behavior analysis of distributed systems have been verified on real data.  For instance, using the proposed methods, various event logs of information systems automating processes in e-government, online sales, banking, and other domains were analyzed.

Publications:


Sergey A. Shershakov, Anna A. Kalenkova, Irina A. Lomazova. Transition Systems Reduction: Balancing Between Precision and Simplicity, in: Lecture Notes in Computer Science Vol. 10470: Transactions on Petri Nets and Other Models of Concurrency XII. Berlin, Heidelberg : Springer, 2017. doi P. 119-139. doi
Lomazova I. A., Popova-Zeugmann L., Bartels A. Controlling boundedness for live Petri nets, in: International Conference on Control, Decision and Information Technologies, CoDIT 2017, Barcelona, Spain, April 5-7, 2017. IEEE, 2017. P. 0236-0241. doi
Мицюк А. А., Ломазова И. А., ван дер Аалст В. Использование журналов событий для локальной корректировки моделей процессов // Моделирование и анализ информационных систем. 2017. Т. 24. № 4. С. 459-480. doi
Kalenkova A. A., van der Aalst W., Lomazova I. A., Rubin V. Process Mining Using BPMN: Relating Event Logs and Process Models // Software and Systems Modeling. 2017. Vol. 16. No. 4. P. 1019-1048. doi
Begicheva A.K., Lomazova I.A. Discovering High-Level Process Models from Event Logs // Моделирование и анализ информационных систем. 2017. Vol. 24. No. 2. P. 125-140. doi
Захаров В. А., Жайлауова Ш. Р. О задаче минимизации последовательных программ // Моделирование и анализ информационных систем. 2017. Т. 24. № 4. С. 415-433. doi
R.A. Nesterov, I.A. Lomazova. Using Interface Patterns for Compositional Discovery of Distributed System Models // Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 21-38. doi
Mitsyuk A. A., Shugurov I., Kalenkova A. A., van der Aalst W. Generating Event Logs for High-Level Process Models // Simulation Modelling Practice and Theory. 2017. Vol. 74. P. 1-16. doi
Lomazova I. A. Resource Equivalences in Petri Nets, in: Application and Theory of Petri Nets and Concurrency. 38th International Conference, PETRI NETS 2017, Zaragoza, Spain, June 25–30, 2017, Proceedings / Ed. by W. van der Aalst, E. Best. Vol. 10258: Lecture Notes in Computer Science. Switzerland : Springer, 2017. doi P. 19-34. doi
Dworzanski L. W., Михайлов В. Е. Tool for Behavioral Analysis of Well-Structured Transition Systems // Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 175-190. doi
Konchagin A., Kalenkova A. A. On the efficient application of Aho-Corasick algorithm in process mining, in: Analysis of Images, Social Networks and Texts. 6th International Conference, 2017, Lecture Notes in Computer Science, Revised Selected Papers / Ed. by W. M. van der Aalst, D. I. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. A. Lomazova, A. Napoli, A. Panchenko, P. M. Pardalos, A. V. Savchenko, S. Wasserman. Vol. 10716. Cham : Springer, 2018. doi P. 371-377. doi
K. Davydova, S. Shershakov. Mining Hybrid UML Models from Event Logs of SOA Systems // Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 155-174. doi
Mitsyuk A. A., Lomazova I. A., van der Aalst W. Using Event Logs for Local Correction of Process Models / Пер. с рус. // Automatic Control and Computer Sciences. 2017. Vol. 51. No. 7. P. 709-723. doi
Mitsyuk A. A., Lomazova I. A., Ivan S. Shugurov, Wil M.P. van der Aalst. Process Model Repair by Detecting Unfitting Fragments, in: Supplementary Proceedings of the 6th International Conference on Analysis of Images, Social Networks and Texts (AIST-SUP 2017), Moscow, Russia, July 27-29, 2017 / Ed. by W. van der Aalst, M. Y. Khachay, S. Kuznetsov, V. Lempitsky, I. A. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. M. Pardalos, A. V. Savchencko, S. Wasserman, D. I. Ignatov. Vol. 1975. Aachen : CEUR-WS.org, 2017. Ch. 32. P. 301-313.