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

­­­Information system processes modeling, analysis and enhancement

Priority areas of development: mathematics
2015
The project has been carried out as part of the HSE Program of Fundamental Studies.

The goal of the research is to extend existing and develop new approaches for modeling, analysis and monitoring of information systems, including sequential program and process-aware information system analysis. 

Methodology: Discrete mathematics, mathematical logic, theory of algorithms, automata theory, and abstract algebra were used for the development of novel methods for system analysis. Process mining techniques (methods for discovering process models from event logs, checking process models against event logs, and enhancing process models with additional information) were extended and used within the project.    

Empirical base of research:Event logs of real-life information systems from healthcare, tourism, municipalities and other domains form an empirical base of research.

Results of research:

In the field of formal information system analysis the following results were obtained.

An algorithm for checking the equivalence of two programs in automata models was presented. The semantics, which determines the state of the data transformed by a program as a semigroup constructed above the characters of program instructions was used. Polynomial solvability of the program equivalence problem was proven.

The properties of finite state transducers (formalism for extending the finite state automata to model functions on strings or lists) were analyzed. In particular it was shown that the problem of testing the equivalence of deterministic finite transducers over semigroups is solvable in polynomial time.

The possibility for obtaining a live and bounded Petri net from a live and unbounded one by adding time constrains in terms of time intervals associated to each transition was studied. Necessary conditions for existence of such priorities were presented. Although these conditions are not sufficient, they help to exclude unsolvable cases. Furthermore, an algorithm for computing (minimal) time intervals for transforming a live and unbounded Petri net into live and bounded net was presented.

In the field of Process mining the following results were obtained.

First, some results concerning the discovery of BPMN models and models with subprocesses from localized event logs were obtained.

The BPMN 2.0 (Business Process Model and Notation) standard is widely used and allows building conventional and understandable process models. In addition to the flat control flow perspective, subprocesses, data flows, resources can be integrated within one BPMN diagram. Robust control flow conversion algorithms, which provide the basis for more advanced BPMN -based discovery and conformance checking algorithms, were described and justified. Moreover, behavioral relations between Petri nets and BPMN models were established and used to adopt existing conformance checking and performance analysis techniques in order to visualize conformance and performance information within a BPMN diagram. Also metrics for the processes discovered before and after the conversion to BPMN structures were provided. Cases for which conversion algorithms produce more compact or more complicated BPMN were identified.

An approach where events are localized by assigning a nonempty set of regions to each event was proposed. It was assumed that regions can only interact through shared events.  A generic process discovery approach based on localized event logs was developed. The approach has been implemented in ProM (Process mining framework) and it was shown experimentally that location information crucially helps to improve the quality of the discovered models.

Automatic comparison of business processes plays an important role in their analysis and optimization. Therefor novel techniques for processes comparison were proposed.

A generic comparison approach, which is applicable to XML representations of business process models, was proposed. Using this approach a tool, which currently supports BPMN 2.0, but can be extended to support other business process modeling standards, was developed.

 Also a web-based tool BPMNDiffViz that finds business processes discrepancies and visualizes them was developed. BPMN (Business Process Model and Notation) 2.0 - one of the most commonly used notations for process modeling was chosen as a representation. This tool implements a structural graph-based comparison analysis using an A* algorithm.

A novel technique for checking log and model conformance was proposed. Conformance checking is intensively studied in the frame of process mining research, but only models and event logs of the same granularity were considered before. A novel method of checking conformance between an abstract model (e.g. built by an expert) and a low-level log (generated by a system) was presented and justified.

Several novel tools for process modeling, analysis and mining were developed.

A new approach for mining fuzzy process models, based on logs representation in the form of relation databases, was proposed. Fast and effective SQL queries to such logs were earlier implemented as a part of a DPMine workflow model proposed. Resulting datasets are processed and visualized by a special DPMine module.

 A model editor, which allows for dealing with classical graphs, Petri nets, finite-state machines and similar systems, was developed. Additionally, the tool has a list of features such as simulation of Petri nets, import and export of models in different storage formats. Carassius is a modular tool, which can be extended for new formalisms. 

A tool Iskra (ProM Framework plug-in) whose aim is to facilitate process mining experiments and evaluate the repair algorithms was developed as well.

Level of implementation,  recommendations on implementation or outcomes of the implementation of the results. The theoretical results presented in this work were implemented and tested within various tools such as ProM framework, DPMine Carassius. Most of the theoretical results gave a background for further research. The applied research in its turn provided interesting insights of the real-life processes, the results of this research can be used for further fundamental studies.

Publications:


Begicheva A., Lomazova I. A. Does your event log fit the high-level process model? // Моделирование и анализ информационных систем. 2015. Vol. 22. No. 3. P. 392-403. doi
I. S. Shugurov, A. A. Mitsyuk. Iskra: A Tool for Process Model Repair, in: Preliminary Proceedings of the 9th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE 2015) / Ed. by A. Kamkin, A. Petrenko, A. Terekhov. M. : , 2015. P. 137-143.
N. M. Nikitina, A. A. Mitsyuk. Carassius: A Simple Process Model Editor, in: Preliminary Proceedings of the 9th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE 2015) / Ed. by A. Kamkin, A. Petrenko, A. Terekhov. M. : , 2015. P. 129-136.
Ivanov S. Y., Kalenkova A. A. Comparing process models in the BPMN 2.0 XML format, in: Preliminary Proceedings of the 9th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE 2015) / Ed. by A. Kamkin, A. Petrenko, A. Terekhov. M. : , 2015. P. 144-148.
Sergey Andreevich Shershakov. VTMine Framework as Applied to Process Mining Modeling // International Journal of Computer and Communication Engineering. 2015. Vol. 4. No. 3. P. 166-179.
Zakharov V.A. Equivalence Checking Problem for Finite State Transducers // Lecture Notes in Computer Science. 2015. Vol. 9270. P. 208-221.
Ivanov S. Y., Kalenkova A. A., van der Aalst W. BPMNDiffViz: A Tool for BPMN Models Comparison, in: Proceedings of the BPM Demo Session 2015. Co-located with the 13th International Conference on Business Process Management (BPM 2015) Vol. 1418. Innsbruck : CEUR-WS.org, 2015. Ch. 8. P. 35-39.
Захаров В. А. Моделирование и анализ поведения последовательных реагирующих программ // Труды Института системного программирования РАН. 2015. Т. 27. № 2. С. 221-250.
Vladislav Podymov. An efficient equivalence-checking algorithm for a model of programs with commutative and absorptive statements, in: Concurrency, Specification & Programming. 24th International Workshop, CS&P 2015. Rzeszow, Poland, September 28-30, 2015. Proceedings Vol. 2. University of Rzeszow, 2015. P. 85-96.
Ivanov S. Y., Kalenkova A. A. Comparing process models in the BPMN 2.0 XML format // Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 3. P. 255-266.
Zakharov V., Подымов В. В., Алтухов В. С., Чемерицкий Е. В. VERMONT - a toolset for checking SDN packet forwarding policies on-line, in: Proceedings of 2014 International Science and Technology Conference "Modern Networking Technologies (MoNeTec): SDN&NFV Next Generation of Computational Infrastructure", Moscow, Russia, October 27-29, 2014. M. : Max press, 2014. P. 7-12.
Lomazova I. A., Popova-Zeugmann L. Controlling Petri Net Behavior Using Time Constraints, in: Concurrency, Specification & Programming. 24th International Workshop, CS&P 2015. Rzeszow, Poland, September 28-30, 2015. Proceedings Vol. 2. University of Rzeszow, 2015. P. 19-35.
N. Nikitina, A. Mitsyuk. Carassius: A Simple Process Model Editor // Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 3. P. 219-236. doi
Shershakov S. A., Rubin V. A. System Runs Analysis with Process Mining // Моделирование и анализ информационных систем. 2015. Vol. 22. No. 6. P. 818-833. doi
Захаров В. А., Подымов В. В. Применение алгоритмов проверки эквивалентности для оптимизации программ // Труды Института системного программирования РАН. 2015. Т. 27. № 4
van der Aalst W., Kalenkova A. A., Verbeek H., Rubin V. Process Discovery Using Localized Events, in: Application and Theory of Petri Nets and Concurrency. 36th International Conference, PETRI NETS 2015, Brussels, Belgium, June 21-26, 2015, Proceedings Issue 9115. Switzerland : Springer, 2015. P. 287-308.
I. Shugurov, A. Mitsyuk. Iskra: A Tool for Process Model Repair // Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 3. P. 237-254. doi