2019/10/22 by Daniel Reißner, Abel Armas-Cervantes, Reißner, Daniel +9
Business, Management and Accounting · Computer Science · #Business Process Modeling and Analysis #FOS: Computer and information sciences #Service-Oriented Architecture and Web Services #Software Engineering (cs.SE) #Software System Performance and Reliability
paper · pdf · doi:10.48550/arxiv.1910.09767
openalex publication_date 2019/10/22 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Given a model of the expected behavior of a business process and an event log\nrecording its observed behavior, the problem of business process conformance\nchecking is that of identifying and describing the differences between the\nmodel and the log. A desirable feature of a conformance checking technique is\nto identify a minimal yet complete set of differences. Existing conformance\nchecking techniques that fulfil this property exhibit limited scalability when\nconfronted to large and complex models and logs. This paper presents two\ncomplementary techniques to address these shortcomings. The first technique\ntransforms the model and log into two automata. These automata are compared\nusing an error-correcting synchronized product, computed via an A* that\nguarantees the resulting automaton captures all differences with a minimal\namount of error corrections. The synchronized product is used to extract\nminimal-length alignments between each trace of the log and the closest\ncorresponding trace of the model. A limitation of the first technique is that\nas the level of concurrency in the model increases, the size of the automaton\nof the model grows exponentially, thus hampering scalability. To address this\nlimitation, the paper proposes a second technique wherein the process model is\nfirst decomposed into a set of automata, known as S-components, such that the\nproduct of these automata is equal to the automaton of the whole process model.\nAn error-correcting product is computed for each S-component separately and the\nresulting automata are recomposed into a single product automaton capturing all\ndifferences without minimality guarantees. An empirical evaluation shows that\nthe proposed techniques outperform state-of-the-art baselines in terms of\ncomputational efficiency. Moreover, the decomposition-based technique is\noptimal for the vast majority of datasets and quasi-optimal for the remaining\nones.\n