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.